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: 13%
Algebra liniowa: 13%
Matematyka Dyskretna: 13%
Python: 10%
Analiza matematyczna: 7%
Podstawy matematyki: 7%
Algorytmy i struktury danych: 7%
Bazy danych: 3%
Programowanie współbieżne: 7%
Sieci komputerowe: 3%
Systemy operacyjne: 3%
Wstęp do uczenia maszynowego: 13%

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

Wstęp do uczenia maszynowego

Estymacja parametrów
Testowanie hipotez
p-wartości i testowanie wielu hipotez
Uczenie statystyczne
Regresja liniowa
Klasyfikacja
Metody repróbkowania, wybór modelu
Regularyzacja
Metody drzewiaste
Podstawy sieci neuronowych
Redukcja wymiaru
Klastrowanie

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++