Teoretyczne podstawy informatyki 2018

Piątek 9¹⁵ - 11⁰⁰ D-1/309 wykład

Piątek 11¹⁵ - 13⁰⁰ D-1/312B ćwiczenia

Piątek 13¹⁵ - 15⁰⁰ D-1/312B ćwiczenia - mgr inż. Karol Gotfryd

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. M. Hirvensalo, Algorytmy kwantowe, WSiP, 2008
5. H. Barendregt, E. Barendsen, Introduction to Lambda Calculus, 1994

Ćwiczenia

• Lista nr 0 na 23 lutego 2018
• Lista nr 1 na 2 marca 2018
• Lista nr 2 na 9 marca 2018
• Lista nr 3 na 16 marca 2018
• Lista nr 4 na 23 marca 2018
• Lista nr 5 na 26 marca 2018
• Lista nr 6 na 6 kwietnia 2018
• Lista nr 7 na 13 kwietnia 2018
• Lista nr 8 na 20 kwietnia 2018
• Lista nr 9 na 27 kwietnia 2018
• Lista nr 10 na 11 maja 2018
• Lista nr 11 na 18 maja 2018
• Lista nr 12 na 25 maja 2018
• Lista nr 13 na 8 czerwca 2018

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

1. Maszyna Turinga. (23-02-2018)
   [Definicja TM, redukcja taśm, symulowanie niedeterminizmu. Definicja języków rekurencyjnych i rekurencyjnie przeliczalnych.]
   
2. Maszyna Turinga (cd). (2-03-2018)
   [Konfiguracja TM. Generatory. Uniwersalna maszyna Turinga. Własności języków rozstrzygalnych i rozpoznawalnych.]
3. Języki nierozstrzygalne. (9-03-2018)
   [Nierozstrzygalność problemu stopu. Inne przykłady języków nierozstrzygalnych.]
4. Maszyna licznikowa. Maszyna RAM. (16-03-2018)
   [Redukcja automatu z dwoma stosami do maszyny licznikowej. Maszyna RAM jako model komputera.]
5. Funkcje rekurencyjne na liczbach naturalnych. (23-03-2018)
   [Pojęcie funkcji rekurencyjnej. Lemat Gödla o kodowaniu. Równoważność z obliczeniami na TM.]
6. Wprowadzenie do λ-rachunku. (26-03-2018)
   [Składnia λ-rachunku, α-kongruencje, β-redukcje i η-redukcje. Rachunek zdań w λ-rachunku.]
7. Liczebniki Church-a. Równoważność z obliczeniami na TM. (6-04-2018)
   []
8. Maszyny Turinga - klasy złożoności obliczeniowej i pamięciowej. (13-04-2018)
   [Twierdzenie o hierachi czasowej. Twierdzenie o hierarchi pamięciowej. Podstawowe klasy złożoności i relacje między nimi.]
9. Definicja redukcji i problemów trudnych i zupełnych w danej klasie. Przykład problemu P-zupełnego i NP-zupełnego. (20-04-2018)
   [Redukcje z klasy L - własności. Problem Circuit Value. Problem Circuit Satisfability. Redukcja do problemu 3SAT.]
10. Przykłady redukcji dla problemów NP-zupełnych. (27-04-2018)
    [Ścieżka i cykl Hamiltona. Problem komiwojażera. Zbiór niezależny. Klaca co-NP.]
11. Problemy pseudowielomianowe i silnie NP-zupełne. Problemy PSPACE-zupełne. (11-05-2018)
    [Problem plecakowy. QSAT. Hierarchia wielomianowa.]
12. Wielomianowe klasy losowe. (18-05-2018)
    [Klasy RP, ZPP, BPP i PP.]
13. Obliczenia kwantowe. (25-05-2018)
    []
14. Obliczenia kwantowe. (7-06-2018)
    []
15. Kolokwium. (14-06-2018)
    []

Zasady zaliczenia kursu

Zaliczenie kursu składa się z dwóch części: zaliczenia ćwiczeń i kolokwium 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 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.
4. Zaliczenie ćwiczeń jest średnią ze sprawdzianów zaokrąglona w górę do najbliższej połowy. Ś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).
5. 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.
6. Średnia z ćwiczeń nie podlega poprawianiu po zakończeniu zajęć.

Kolokwium końcowe

1. Kolokwium końcowe odbędzie się na ostatnim wykładzie.
2. 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.

Ocena końcowa

Ocena końcowa jest jest wyliczana według wzoru 0.4 średniej z ćwiczeń + 0.6 oceny z kolokwium zaokrąglonej w górę do najbliższej oceny (2.5 zaokrągla się jednak do 2.0).