1. [27 IX] Wprowadzenie. Modele obliczeń (geometria euklidesowa, obwody logiczne, automaty skończone), obliczalność, dowód.
2. [4 X] Maszyny Turinga - wprowadzenie.
3. [11 X] Klasa funkcji rekurencyjnych - model z
+, x, <=, I_n_k, złożeniem i operacją minimum, lemat Godla o kodowaniu.
4. [18 X] Model z
rekursją prostą, równoważność obu modeli, równoważność obliczeniowa z
maszynami Turinga, funkcja uniwersalna.5. [25 X] Funcja uniwersalna. Twierdzenie o nienależeniu funkcji
uniwersalnej danej klasy do tej klasy. Twierdzenie o nieistnieniu funkcji
uniwersalnej dla klasy rekurencyjnych funkcji całkowitych. Uniwersalna
maszyna Turinga, problem stopu, twierdzenie Rice'a. 6. [8 XI] Maszyny Turinga i klasy złożoności czasowej i
pamięciowej: L, NL, P, NP, co-NP, PSPACE, EXP - definicje i zależności.
Klasy probabilistyczne: RP, co-RP, ZPP, PP i BPP - definicje, zależności i związek z niedeterminizmem.7. [15 XI] Złożoność Kołmogorowa.8. [22 XI] Obliczenia losowe.9. [29 XI] Obliczenia kwantowe.
|