Teoretyczne podstawy informatyki 2023
Piątek 915 - 1100 C-16/D2.2 wykład
Wtorek 1705 - 1845 C-4/32 ćwiczenia (dr inż. Karol Gotfryd)
Literatura
- T.A. Sudkamp, Languages and Machines, Pearson 2017 (ISBN 978-81-317-1475-1)
- Ch.H. Papadimitriou, Złożoność obliczeniowa, WNT, Warszawa 2002 (ISBN 83-204-2659-6)
- M. Sipser, Wprowadzenie do teorii obliczeń, WNT, Warszawa 2009 (ISBN 978-83-204-3436-1)
- J.E. Hopcroft, J.D. Ullman, Wprowadzenie do teorii automatów, języków i obliczeń, WNT, Warszawa 1994 (ISBN 83-01-11298-0)
- T.H. Cormen, Ch.E. Leiserson, R.L. Rivest, Wprowadzenie do algorytmów, WNT, Warszawa 1997 (ISBN 83-204-2144-6)
- Ch. Bernhardt, Obliczenia kwantowe dla każdego, WN PWN, Warszawa 2020 (ISBN 978-83-012-1215-5)
- H. Barendregt, E. Barendsen, Introduction to Lambda Calculus, 1994
Ćwiczenia
Notatki do wykładów
Tematy wykładów (w przybliżeniu)
- Maszyna Turinga. (03-03-2023)
[Definicja TM, konfiguracja TM, redukcja taśm, symulowanie niedeterminizmu. ]
- Maszyna Turinga (cd). (10-03-2023)
[Uniwersalna maszyna Turinga. Definicja języków rekurencyjnych i rekurencyjnie przeliczalnych. Generatory. Własności języków rozstrzygalnych i rozpoznawalnych.]
- Języki nierozstrzygalne. (17-03-2023)
[Nierozstrzygalność problemu stopu. Inne przykłady języków nierozstrzygalnych. Twierdzenie Rice'a.]
- Maszyna licznikowa. (24-03-2023)
[Redukcja automatu z dwoma stosami do maszyny licznikowej. Teza Churcha. Maszyna RAM.]
- Problem Posta. Nierozstrzygalność pustości przekroju języków bezkontekstowych. (31-03-2023)
[]
- Funkcje rekurencyjne na liczbach naturalnych. (14-04-2023)
[Pojęcie funkcji rekurencyjnej. Przykłady konstrukcji. Lemat Gödla o kodowaniu. Równoważność z obliczeniami na TM.]
- Wprowadzenie do λ-rachunku. (21-04-2023)
[Składnia λ-rachunku, α-kongruencje, β-redukcje i η-redukcje. Rachunek zdań w λ-rachunku.]
- Liczebniki Church-a. Równoważność z obliczeniami na TM. (28-04-2023)
[]
- Maszyny Turinga - klasy złożoności obliczeniowej i pamięciowej. (12-05-2023)
[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. (19-05-2023)
[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. (26-05-2023)
[Ścieżka i cykl Hamiltona. Problem komiwojażera. Zbiór niezależny. Problem plecakowy.]
- Obliczenia kwantowe. (2-06-2023)
[Kubity. Splątanie.]
- Obliczenia kwantowe. (16-06-2023)
[Kwantowe układy logiczne.]
- Obliczenia kwantowe. (23-06-2023)
[Przykłady algorytmów kwantowych.]
- Kolokwium. (27-06-2023)
[]
Zasady zaliczenia kursu
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).