Teoria obliczeń i złożoność obliczeniowa 2011

Wtorek 7³⁰ - 9⁰⁰ C-11/P.01 wykład

Czwartek 11¹⁵ - 13⁰⁰ C-7/202 ćwiczenia

Czwartek 13¹⁵ - 15⁰⁰ C-7/202 ćwiczenia

Literatura

1. Ch.H. Papadimitriou, Złożoność obliczeniowa, WNT, Warszawa 2002 (ISBN 83-204-2659-6)
2. J.E. Hopcroft, J.D. Ullman, Wprowadzenie do teorii automatów, języków i obliczeń, WNT, Warszawa 1994 (ISBN 83-01-11298-0)
3. T.H. Cormen, Ch.E. Leiserson, R.L. Rivest, Wprowadzenie do algorytmów, WNT, Warszawa 1997 (ISBN 83-204-2144-6)
4. A. Kościelski, Teoria obliczeń. Wykłady z matematycznych podstaw informatyki, Wydawnictwo Uniwersytetu Wrocławskiego, 1997 (ISBN 83-229-1696-5)
5. H. Barendregt, E. Barendsen, Introduction to Lambda Calculus, 1994

Listy zadań

• Lista nr 1 na 24 lutego
• Lista nr 2 na 3 marca
• Lista nr 3 na 10 marca
• Lista nr 4 na 17 marca
• Lista nr 5 na 24 marca
• Lista nr 6 na 31 marca
• Lista nr 7 na 7 kwietnia
• Lista nr 8 na 14 kwietnia
• Lista nr 9 na 5 maja
• Lista nr 10 na 12 maja
• Lista nr 11 na 19 maja
• Lista nr 12 na 26 maja
• Lista nr 13 na 2 czerwca
• Lista nr 14 na 9 czerwca

Zasady zaliczenia kursu

1. Zaliczenie kursu następuje przez zaliczenie egzaminu końcowego.
2. Zasadniczym celem ćwiczeń jest ułatwienie studentom samodzielnej pracy nad opanowaniem materiału w czasie całego semestru.
3. Wykładowca ogłasza z odpowiednim wyprzedzeniem listy zadań do samodzielnego rozwiązania przed zajęciami. Na ćwiczeniach studenci prezentują rozwiązania zadań. W trakcie rozwiązywania wyjaśniane są wątpliwości dotyczące rozwiązania oraz przedstawiane alternatywne rozwiązania.
4. Na każde ćwiczenia jest przygotowywana osobna lista zadań, ogłaszana co najmniej na trzy dni przed zajęciami. Na ćwiczeniach rozwiązywane są wybrane zadania z tej listy. Decyzję odnośnie wyboru zadań do rozwiązania podejmuje prowadzący.
5. Dodatkowym warunkiem zaliczenia jest oddanie przez studenta w formie pisemnej (PDF) wyznaczonych zadań zrobionych na ćwiczeniach. Oddawane zadanie powinno być rozwiązane dokładnie, w sposób formalny i przejrzysty. Zadanie wyznacza prowadzący ćwiczenia.
6. Na egzaminie jedyną dopuszczalną pomocą naukową jest kartka formatu a4 podpisana w ten sposób aby z odległości 2 metrów dało się ustalić jej właściciela. Oprócz tego student nie ma prawa mieć żadnych innych kartek, książek i innych pomocy. Kartki z treścią zadań i miejscem na rozwiązania oraz brudnopisy dostarcza wykładowca.
7. W przypadku nie zdania egzaminu końcowego można go jeden raz poprawiać ale tylko na ocenę co najwyżej 3.0.
8. Oceną końcową jest ocena z egzaminu która może być podwyższona za aktywność na ćwiczeniach.

Tematy wykładów (w przybliżeniu)

1. Maszyna Turinga. Własności różnych modeli maszyny Turinga (22-02-2011)
2. Języki rekurencyjne i rekurencyjnie przeliczalne (1-03-2011)
3. Uniwersalna maszyna Turinga. Nierozstrzygalność problemu stopu (8-03-2011)
4. Twierdzenie Rice'a. Teza Churcha. Maszyna licznikowa (15-03-2011)
5. Maszyna RAM. Równoważność maszyny RAM i maszyny Turinga jako modeli obliczeń (22-03-2011)
6. Funkcje rekurencyjne na liczbach naturalnych. Lemat Godla o kodowaniu. Równoważność modelu funkcji rekurencyjnych i modelu maszyn Turinga (29-03-2011)
7. Podstawy lambda rachunku. Liczebniki Churcha. Równoważność z innymi modelami obliczeń (5-04-2011)
8. Problem odpowiedniości Posta. Podstawy złożoności obliczeniowej Relacje między klasami złożoności. Twierdzenia o hierarchii. Metoda osiągalności (12-04-2011)
9. Redukcje między problemami. P-zupełność. NP-zupełność. (19-04-2011)
10. Przykłady redukcji między problemami NP-zupełnymi. Klasa co-NP. Problemy funkcyjne. (10.05.2011)
11. Obliczenia losowe. (17.05.2011)
12. Aproksymowalność. (24.05.2011)
13. Sieci logiczne. Obliczenia równoległe. Klasa NC. (31.05.2011)
14. Klasa PSPACE. Alternujące maszyny Turinga. (7.06.2011)
15. Podsumowanie wykładu. (14.06.2011)