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

Poniedziałek 9¹⁵ - 11⁰⁰ D-1/312B wykład

Poniedziałek 11¹⁵ - 13⁰⁰ D-1/312B ć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 13 lutego
• Lista nr 2 na 20 lutego
• Lista nr 3 na 5 marca
• Lista nr 4 na 12 marca
• Lista nr 5 na 19 marca
• Lista nr 6 na 26 marca
• Lista nr 7 na 2 kwietnia
• Lista nr 8 na 23 kwietnia
• Lista nr 9 na 30 kwietnia
• Lista nr 10 na 7 maja
• Lista nr 11 na 14 maja
• Lista nr 12 na 21 maja
• Lista nr 13 na 28 maja

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

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

Zasady zaliczenia kursu

Zaliczenie kursu składa się z dwóch części: zaliczenia ćwiczeń i egzaminu końcowego.

Zaliczenie ćwiczeń

1. Zasadniczym celem ćwiczeń jest ułatwienie studentom samodzielnej pracy nad opanowaniem materiału w czasie całego semestru. Ocena z ćwiczeń jest oceną jakości i intensywności pracy studenta w czasie semestru.
2. 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.
3. Podstawą do wystawienia oceny są wyniki krótkich sprawdzianów. Sprawdziany będą polegały na rozwiązaniu jednego zadania i punktowane od 0 do 5. Materiałem obowiązującym na sprawdzianie są 3 poprzednie listy. Sprawdziany przeprowadzane są bez uprzedniej zapowiedzi. Nieobecność na sprawdzianie daje 0. Jeden, najsłabszy sprawdzian studenta w semestrze zostanie anulowany.
4. Podstawą do oceny na zaliczenie jest średnia ze sprawdzianów zaokrąglona w górę do najbliższej oceny. Ocena może być podwyższona przez prowadzącego w zależności od aktywności studenta na ćwiczeniach.
5. 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.
6. 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.
7. Ocena nie podlega poprawianiu po zakończeniu zajęć.

Egzamin końcowy

1. Zdanie egzaminu jest warunkiem koniecznym zaliczenia kursu.
2. W przypadku nie zdania egzaminu końcowego można go jeden raz poprawiać ale tylko na ocenę co najwyżej 3.0.
3. 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.

Ocena końcowa

Ocena końcowa jest średnią z oceny na zaliczenie i oceny z egzaminu zaokrąglonej w górę do najbliższej oceny (2.5 zaokrągla się jednak do 2.0).