Funkcje rekurencyjne na liczbach naturalnych. Lemat Godla o kodowaniu. Równoważność modelu funkcji rekurencyjnych i modelu maszyn Turinga (12-03-2012)
Podstawy lambda rachunku. (19-03-2012)
Liczebniki Churcha. Równoważność z innymi modelami obliczeń. Problem odpowiedniości Posta. (26-03-2012)
Podstawy złożoności obliczeniowej Relacje między klasami złożoności. Twierdzenia o hierarchii. Metoda osiągalności (2-04-2012)
Redukcje między problemami. P-zupełność. NP-zupełność. (16-04-2012)
Przykłady redukcji między problemami NP-zupełnymi. Klasa co-NP. Problemy funkcyjne. (16-04-2012)
Aproksymowalność. (23-04-2012)
Obliczenia losowe. (30-04-2012)
Sieci logiczne. Obliczenia równoległe. Klasa NC. (7-05-2012)
Klasa PSPACE. Alternujące maszyny Turinga. (14-05-2012)
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ń
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.
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.
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.
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.
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.
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.
Ocena nie podlega poprawianiu po zakończeniu zajęć.
Egzamin końcowy
Zdanie egzaminu jest warunkiem koniecznym zaliczenia kursu.
W przypadku nie zdania egzaminu końcowego można go jeden raz poprawiać
ale tylko na ocenę co najwyżej 3.0.
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).