Notice: Undefined index: HTTP_ACCEPT_ENCODING in /home/felippo/public_html/courses/tpi_2011/index.php on line 3
Teoretyczne podstawy informatyki
Teoretyczne podstawy informatyki (zimowy 2011/12)
WykładyĆwiczeniaFAQLiteratura
Wykłady

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.



Ćwiczenia



Zaliczenie

Wyniki kolokwium

Wyniki końcowe

Poprawka: każde zadanie za 1pkt, 6 pkt.

Używałem tych samych pseudonimów, które podaliście za pierwszym razem.

Wpisy wtorek, 3 I o 9:30.

Jeżeli ktoś zrozumiał i chce spróbować ponownie...







FAQ

Jak można zaliczyć ten przedmiot?
FZ: Należy zdać egzamin.

Wystarczy przyjść na egzamin?
FZ: Do egzaminu należy zostać dopuszczonym.

Jak wygląda dopuszczenie do egzaminu?
FZ: Należy zdobyć odpowiednią liczbę punktów z kartkówek (50%) i zadań z list.

Bibliografia
Rzecz o istocie informatyki - David Harel