Maszyna Turinga (cd). (7-03-2019) [Uniwersalna maszyna Turinga. Definicja języków rekurencyjnych i rekurencyjnie przeliczalnych. Generatory. Własności języków rozstrzygalnych i rozpoznawalnych.]
Języki nierozstrzygalne. (14-03-2019) [Nierozstrzygalność problemu stopu. Inne przykłady języków nierozstrzygalnych. Twierdzenie Rice'a.]
Maszyna licznikowa. (21-03-2019) [Redukcja automatu z dwoma stosami do maszyny licznikowej. Teza Churcha. Maszyna RAM.]
Problem Posta. Nierozstrzygalność pustości przekroju języków bezkontekstowych. (28-03-2019) []
Funkcje rekurencyjne na liczbach naturalnych. (4-04-2019) [Pojęcie funkcji rekurencyjnej. Lemat Gödla o kodowaniu. Równoważność z obliczeniami na TM.]
Wprowadzenie do λ-rachunku. (11-04-2019) [Składnia λ-rachunku, α-kongruencje, β-redukcje i η-redukcje. Rachunek zdań w λ-rachunku.]
Liczebniki Church-a. Równoważność z obliczeniami na TM. (15-04-2019) []
Maszyny Turinga - klasy złożoności obliczeniowej i pamięciowej. (25-04-2019) [Podstawowe klasy złożoności i relacje między nimi. Twierdzenie o hierarchii czasowej. Twierdzenie o hierarchii pamięciowej.]
Definicja redukcji i problemów trudnych i zupełnych w danej klasie. Przykład problemu P-zupełnego i NP-zupełnego. (9-05-2019) [Redukcje z klasy L - własności. Problem Circuit Value. Problem Circuit Satisfability. Redukcja do problemu 3SAT.]
Przykłady redukcji dla problemów NP-zupełnych. Problemy pseudowielomianowe i silnie NP-zupełne. (16-05-2019) [Ścieżka i cykl Hamiltona. Problem komiwojażera. Zbiór niezależny. Problem plecakowy.]
Zaliczenie kursu składa się z dwóch części: zaliczenia ćwiczeń i kolokwium 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 zaliczenia ćwiczeń 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.
Zaliczenie ćwiczeń jest średnią ze sprawdzianów.
Średnia może być podwyższona przez prowadzącego w zależności od aktywności studenta na ćwiczeniach (jednak nie wyżej niż do 7.0).
Dodatkowym warunkiem zaliczenia jest oddanie przez studenta w formie pisemnej (PDF) rozwiązania przydzielonego zadania z listy.
Rozwiązanie powinno być napisane dokładnie, w sposób formalny i przejrzysty.
Średnia z ćwiczeń nie podlega poprawianiu po zakończeniu zajęć.
Kolokwium końcowe
Kolokwium końcowe odbędzie się na ostatnim wykładzie.
Na kolokwium 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.
Z kolokwium można uzyskać od 0 do 5.5 punktu. Nieobecność na kolokwium daje 2 punkty.
Ocena końcowa
Ocena końcowa jest wyliczana według wzoru 0.4 średniej z ćwiczeń + 0.6 punktów z kolokwium zaokrąglonej w górę do najbliższej oceny
(2.5 zaokrągla się jednak do 2.0).
