Zakres egzaminu na studia doktoranckie w dyscyplinie Informatyka

Kandydat powinien wykazać się znajomością tematów objętych podanym niżej wykazem na poziomie wymaganym od magistrantów uniwersyteckich studiów informatycznych.

1. Moce zbiorów. Zbiory częśsciowo uporządkowane, punkty stałe. Zbiory dobrze ufundowane i dowodzenie przez indukcję.
2. Homomorfizmy i kongruencje. Równościowe definiowanie klas algebr.
3. Składnia i semantyka klasycznego rachunku zdań i rachunku predykatów. Pojęcie dowodu formalnego. Twierdzenia o pełności.
4. Zbieżność ciągów i szeregów funkcyjnych. Miara i całka Lebesgue'a. Związek z całką Riemanna.
5. Liniowa zależność wektorów. Rząd przekształcenia liniowego. Związek macierzy z przekształceniami liniowymi.
6. Arytmetyka zmiennopozycyjna, zakres liczb reprezentowalnych i oszacowanie błędu reprezentacji. Przykład analizy błędu wytworzonego zaokrągleniami. Kwadratury. Rząd kwadratury, zbieżność procesu kwadratur. Zagadnienie rozwiązalności układu równań liniowych. Numeryczne rozwiązywanie układów równań, obliczanie wyznacznika, odwracanie macierzy. Uwarunkowanie zadania.
7. Gramatyki formalne i automaty oraz ich klasyfikacja. Rozstrzygalne i nierozstrzygalne problemy decyzyjne. Klasy złożoności obliczeniowej, NP-zupełność.
8. Semantyczna poprawność algorytmu, koszt pesymistyczny, oczekiwany i zamortyzowany.
9. Algorytmy sortowania i selekcji.
10. Abstrakcyjne struktury danych (słowniki, kolejki priorytetowe, stosy), metody ich implementacji i zastosowania.
11. Formalna semantyka języków programowania. Metoda Floyda-Hoare'a dowodzenia poprawności programów.
12. Programowanie imperatywne i deklaratywne. Programowanie obiektowe.
13. Analiza leksykalna, składniowa i kontekstowa programu. Generacja kodu. Algorytmy optymalizacji. Zjawiska czasu wykonania programu.
14. Metody synchronizacji i komunikacji procesów w systemach scentralizowanych i rozproszonych, przykładowe formalizmy.
15. Poprawność programu współbieżnego, podstawowe założenia. Przykłady naruszenia własności poprawności. Klasyczne problemy współbieżności.
16. Podstawowe zadania systemu operacyjnego. Typowe problemy powstające przy ich realizacji i główne metody rozwiązywania tych problemów.
17. Systemy rozproszone: aspekty sprzętowe i programowe funkcjonowania systemów rozproszonych, metody komunikacji, rozproszone systemy plików, rozproszona pamięć dzielona, przykłady algorytmów rozproszonych.