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.
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).
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++.
Python
Przepływ sterowania
Kontenery (tablice, listy, słowniki itp.)
Klasy, obiekty i dziedziczenie
Moduły
Mechanizm refleksji
Metaprogramowanie