Uczenie maszynowe — wymagania na egzamin wstępny na studia drugiego stopnia

Nie jesteś zalogowany | Zaloguj się

PL /
EN

Rozkład zagadnień na egzaminie będzie zbliżony do poniższego (mogą się jednak zdarzyć odstępstwa):

Rachunek Prawdopodobieństwa i Statystyka: 17%
Algebra liniowa: 13%
Matematyka Dyskretna: 13%
Python: 10%
Analiza matematyczna: 7%
Podstawy matematyki: 7%
Metody numeryczne: 7%
Algorytmy i struktury danych: 7%
Bazy danych: 7%
Programowanie współbieżne: 7%
Sieci komputerowe: 3%
Systemy operacyjne: 3%

Analiza matematyczna

Szkic teorii aksjomatycznej liczb rzeczywistych, w tym: kresy, indukcja , zapis dziesiętny liczb całkowitych, liczby wymierne, potęga rzeczywista
Ciągi liczbowe: granica (skończona i nie) oraz zbieżność, elementarne własności granicy, ciągi monotoniczne, podciągi i tw. Bolzano - Weierstrassa, warunek Cauchy'ego i zupełność, informacje o dalszych twierdzeniach z teorii granicy (np. tw. Stolza)
Szeregi liczbowe: pojęcie szeregu i jego sumy, zbieżność i zbieżność bezwzględna, kryteria: porównawcze, asymptotyczne, zagęszczeniowe, d'Alemberta, Cauchy'ego, Dirichleta; zmiana kolejności sumowania, iloczyn Cauchy'ego szeregów
Granica i ciągłość funkcji jednej zmiennej: pojęcie punktu skupienia zbioru, pojęcie granicy funkcji i warunki równoważne, własności granicy, ciągłość, własność Darboux, twierdzenie Weierstrassa o osiąganiu kresów, ciągłość jednostajna, szeregi potęgowe - zbiór zbieżności i ciągłość sumy, kilka funkcji elementarnych (wykładnicza, logarytmiczna, potęgowa, trygonometryczne)
Rachunek różniczkowy funkcji jednej zmiennej: pochodna i jej sens geometryczny, własności algebraiczne pochodnej, różniczkowanie elementarnych funkcji, ekstrema lokalne, twierdzenia Rolle'a, Lagrange'a i Cauchy'ego o wartości średniej, monotoniczność a pochodna, reguła de l'Hospitala, wyższe pochodne, wypukłość, wzór Taylora
Zbieżności (punktowa, jednostajna, niemal jednostajna) ciągów i szeregów funkcyjnych: norma „sup” funkcji, warunki konieczne i dostateczne (war. Cauchy’ego, kryt. Weierstrassa) zbieżności jednostajnej szeregów funkcyjnych, twierdzenia o ciągłości i o różniczkowalności granicy, informacja o aproksymacji jednostajnej wielomianami
Rachunek całkowy funkcji jednej zmiennej: całka nieoznaczona i oznaczona, całkowanie przez części i przez podstawianie, całkowanie funkcji wymiernych, informacje o typowych podstawieniach, całka Riemanna, całkowalność i zbieżność sum Riemanna dla funkcji ciągłych, elementarne własności całki Riemanna, podstawowe twierdzenie rachunku całkowego, twierdzenie (tzw. „I-sze”) o wartości średniej, całki niewłaściwe (szkic)
Przestrzenie metryczne i ciągłość funkcji wielu zmiennych: przykłady metryk, normy, zbiory otwarte i domknięte, zbieżność ciągów w przestrzeniach metrycznych, zwartość w Rn i twierdzenie Bolzano Weierstrassa, granica i ciągłość funkcji wielu zmiennych, ciągłość funkcji a otwartość/domkniętość zbiorów, twierdzenie Weierstrassa o osiąganiu kresów dla funkcji wielu zmiennych
Rachunek różniczkowy funkcji wielu zmiennych: pochodna funkcji wektorowej 1-nej zmiennej, pochodne cząstkowe, funkcje klasy C1, tw. o ekstremach lokalnych dla funkcji skalarnych, pochodna kierunkowa, różniczka, macierz Jakobiego, ciągłość funkcji różniczkowalnych i różniczkowalność funkcji klasy C1, różniczka złożenia i reguła „łańcuchowa”, ekstrema warunkowe i tw. o mnożnikach Lagrange'a, pochodne cząstkowe drugiego rzędu i warunki dostateczne na ekstrema lokalne

Algebra liniowa

Grupy. Ciała. Liczby zespolone, postać trygonometryczna, wzór de'Moivre'a, pierwiastki z jedności, pierwiastki z liczby zespolonej
Wielomiany, zasadnicze tw. algebry (bez dowodu)
Macierze o współczynnikach z ciała. Działania na macierzach
Przestrzenie liniowe nad ciałem, podprzestrzeń liniowa, liniowa niezależność, baza, wymiar. Przykłady baz. Część wspólna, suma, suma prosta podprzestrzeni
Obraz, jądro i rząd macierzy. Macierze odwracalne
Układy równań liniowych. Twierdzenie Kroneckera-Capellego. Opis zbioru rozwiązań. Eliminacja Gaussa
Wyznaczniki i ich własności. Wzory Cramera
Przekształcenia liniowe i funkcjonały. Macierz przekształcenia liniowego. Rząd, obraz i jądro przekształcenia liniowego oraz macierzy. Izomorfizm przestrzeni liniowych
Przestrzeń sprzężona, bazy sprzężone, macierz zmiany bazy, związek z przekształceniami liniowymi
Podobieństwo macierzy. Wartość własna, wektor własny, widmo macierzy/przekształcenia liniowego. Wielomian charakterystyczny. Diagonalizacja przekształcenia liniowego/macierzy. Informacja o tw. Jordana
Przestrzenie euklidesowe/unitarne. Iloczyn skalarny, norma euklidesowa, pojęcie kąta. Baza ortogonalna/ortonormalna, tożsamość Parsevala. Ortogonalizacja Grama-Schmidta. Dopełnienie ortogonalne i rozkład ortogonalny przestrzeni, rzut ortogonalny. Izometrie, macierze ortogonalne/unitarne
Formy hermitowskie i symetryczne. Przystawanie macierzy. Diagonalizacja macierzy symetrycznych/hermitowskich. Kryterium Sylvestera

Podstawy matematyki

Rachunek zdań i jego własności. Wprowadzenie do rachunku kwantyfikatorów
Operacje na zbiorach, w tym działania nieskończone
Relacje i funkcje oraz ich podstawowe własności
Relacja równoważności, zasada abstrakcji
Liczby naturalne. Zasada indukcji
Równoliczność. Zbiory skończone i nieskończone, przeliczalne i nieprzeliczalne
Twierdzenie Cantora i twierdzenie Cantora-Bernsteina
Porządki częściowe i liniowe. Kresy. Zastosowania lematu Kuratowskiego - Zorna
Porządki dobre i dobrze ufundowane. Indukcja
Pojęcie dowodu formalnego. Systemy dowodzenia dla rachunku zdań, twierdzenie o pełności
Struktury relacyjne. Język pierwszego rzędu: semantyka, twierdzenie o pełności

Matematyka Dyskretna

Indukcja matematyczna i rekurencja
Sumy skończone
Współczynniki dwumianowe
Permutacje i podziały
Funkcje tworzące i ich zastosowania
Metody zliczania: enumeratory, zasada włączania-wyłączania
Asymptotyka: notacja asymptotyczna (O,Omega, Theta, o, omega), twierdzenie o rekurencji uniwersalnej
Elementarna teoria liczb: podzielność, liczby pierwsze, rozkład na czynniki pierwsze, NWD i algorytm Euklidesa
Arytmetyka modularna: małe twierdzenie Fermata i twierdzenie Eulera, chińskie twierdzenie o resztach, rozwiązywanie równań modularnych
Elementy kryptografii: test Millera-Rabina i system RSA
Grafy: ścieżki, drzewa i cykle, cykle Eulera i Hamiltona, grafy dwudzielne, skojarzenia i twierdzenie Halla, planarność, kolorowanie grafów

Rachunek Prawdopodobieństwa i Statystyka

Przestrzeń probabilistyczna: aksjomaty, własności, schemat klasyczny, prawdopodobieństwo geometryczne, miara
Prawdopodobieństwo warunkowe: prawdopodobieństwo całkowite, wzór Bayesa, niezależność zdarzeń
Dyskretne zmienne losowe: definicja, własności, podstawowe rozkłady – dwupunktowy, dwumianowy, Poissona, geometryczny
Parametry rozkładu: wartość oczekiwana, wariancja, momenty, funkcje tworzące prawdopodobieństwa, ich własności oraz zastosowania do wyznaczania parametrów rozkładu
Szacowanie ogonów: nierówności Markowa, Czebyszewa, Chernoffa, prawa wielkich liczb
Ciągłe zmienne losowe: definicja, własności, rozkład wykładniczy oraz normalny, centralne twierdzenie graniczne
Łańcuchy Markowa: definicja oraz podstawowe własności, prawdopodobieństwa oraz średnie czasy dotarcia, klasyfikacja stanów, twierdzenie ergodyczne, zastosowania
Statystyka opisowa: cechy i ich skale, dane surowe i skumulowane, prezentacja graficzna, miary tendencji centralnej i rozrzutu
Wnioskowanie statystyczne: próbka prosta, statystyka i estimator, estymacja parametryczna i nieparametryczna, metoda największej wiarygodności
Testowanie hipotez i przedziały ufności: przedziały ufności dla średniej, metodologia testu statystycznego, p-value

Metody numeryczne

Rozwiązywanie równań nieliniowych: podstawowe pojęcia w numerycznym rozwiązywaniu równań (kula zbieżności, wykładnik zbieżności), metoda Newtona dla układu równań i jej modyfikacje, kryteria stopu
Arytmetyka zmiennopozycyjna: reprezentacja zmiennopozycyjna liczb, arytmetyka i błędy zaokrągleń
Błędy w obliczeniach: numeryczne uwarunkowanie zadania, numeryczna poprawność i stabilność algorytmu
Rozwiązywanie układów równań liniowych: uwarunkowanie układu równań liniowych, metody bezpośrednie (metoda eliminacji Gaussa, metoda odbić Householdera, metoda Choleskiego, układy i algorytmy blokowe), iteracyjne poprawianie rozwiązania, metody iteracyjne (metody iteracji prostej, metoda sprzężonych gradientów), poprawianie uwarunkowania
Liniowe zadania najmniejszych kwadratów: regularne LZNK, nieregularne LZNK
Algebraiczne zagadnienie własne: metoda potęgowa, odwrotna metoda potęgowa, sprowadzanie macierzy symetrycznej do postaci trójdiagonalnej, algorytm QR
Interpolacja wielomianowa: sformułowanie zadań interpolacji Lagrange’a i Hermite’a, bazy Newtona, różnice dzielone i ich własności, algorytm różnic dzielonych, reszta interpolacyjna
Interpolacja funkcjami sklejanymi: reprezentacja Hermite’a funkcji sklejanych trzeciego stopnia, twierdzenie Holladaya, funkcje B-sklejane, kubiczne funkcje interpolacyjne w reprezentacji B-sklejanej, twierdzenie Schoenberga-Whitney
Interpolacja trygonometryczna: dyskretna transformata Fouriera, algorytm FFT
Aproksymacja funkcji: aproksymacja jednostajna: wielomiany i węzły Czebyszewa, alternans, aproksymacja jednostajna przez funkcje sklejane, aproksymacja średniokwadratowa: wielomiany ortogonalne
Numeryczne obliczanie całek: kwadratury interpolacyjne, kwadratury Gaussa, kwadratury złożone, ekstrapolacja Richardsona i metoda Romberga
Wybrane środowiska i biblioteki dla obliczeń numerycznych

Algorytmy i struktury danych

Podstawowe zasady analizy algorytmów
Metody projektowania wydajnych algorytmów
Sortowanie
Selekcja
Kolejki priorytetowe
Wyszukiwanie i słowniki
Problem "Find-Union" i jego zastosowania
Algorytmy grafowe
Wyszukiwanie wzorca w tekstach
Tekstowe struktury danych

Bazy danych

Relacyjny model danych
Podstawowe konstrukcje języka SQL i sposoby ich realizacji
Rodzaje metadanych i ich rola
Redundancja a postacie normalne
Przejście od modelu pojęciowego do modelu logicznego
Fizyczna reprezentacja danych

Systemy operacyjne

Mechanizmy sprzętowe potrzebne do realizacji wielodostępnych, wieloprocesowych systemów operacyjnych
Podstawy programowania niskopoziomowego, asembler
Algorytmy szeregowania procesów
Pamięć wirtualna. Cechy charakterystyczne różnych technik realizacji pamięci wirtualnej
Funkcje systemowe do obsługi plików z poziomu użytkownika (czynności wykonywane przez system operacyjny, struktury danych)

Sieci komputerowe

Warstwy sieci
Protokoły TCP, UDP, IP, ICMP, Ethernet
Adresy internetowe, tablice tras, zasady trasowania, NAT
System nazw domenowych
Sieciowy interfejs gniazd

Programowanie współbieżne

Metody synchronizacji w modelu współbieżnym: zmienne współdzielone (koalgorytmy wzajemnego wykluczania), semafory, monitory
Analiza poprawności algorytmów współbieżnych (bez użycia LTL - u)
Metody synchronizacji w modelu rozproszonym: komunikacja synchroniczna, komunikacja asynchroniczna (przestrzeń krotek)
Spójność i modele spójności: linearizability (or atomicity), sequential consistency, causal consistency, eventual consistency
Wydajność w modelu współbieżnym: work, span, speed - up, parallelization - ilustrowane i szacowane programami w CILK-u
Metody programowania współbieżnego (wykłady wprowadzające do laboratoriów; synchronizowane z laboratoriami): wątki POSIX, współbieżność w Javie (klasyczna, java.util.concurrency), współbieżność w C++