Funkcje rekurencyjne na liczbach naturalnych. Lemat Godla o kodowaniu. Równoważność modelu funkcji rekurencyjnych i modelu maszyn Turinga. (28-10-2015)
Podstawy lambda rachunku. (4-11-2015)
Liczebniki Churcha. Równoważność z innymi modelami obliczeń. Problem odpowiedniości Posta. (12-11-2015)
Podstawy złożoności obliczeniowej Relacje między klasami złożoności. Twierdzenia o hierarchii. Metoda osiągalności. (18-11-2015)
Redukcje między problemami. P-zupełność. NP-zupełność. (25-12-2015)
Przykłady redukcji między problemami NP-zupełnymi. Klasa co-NP. Problemy funkcyjne. (2-12-2015)
Aproksymowalność. (9-12-2015)
Obliczenia losowe. (16-12-2015)
Sieci logiczne. Obliczenia równoległe. Klasa NC. (4-01-2016)
Klasa PSPACE. Alternujące maszyny Turinga. (13-01-2016)
Problemy zliczania. Podsumowanie wykładu. (20-01-2016)
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.
Decyzja odnośnie wyboru zadań do rozwiązania podejmuje prowadzący.
Dodatkowym warunkiem zaliczenia jest oddanie przez studenta w formie pisemnej (PDF) wyznaczonych zadań z list.
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.
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).
