Teoretyczne podstawy informatyki 2025

Czwartek 11¹⁵ - 13⁰⁰ C-3/22 wykład

Środa 11¹⁵ - 13⁰⁰ C-4/35 ćwiczenia (dr inż. Karol Gotfryd)

Czwartek 13¹⁵ - 15⁰⁰ C-4/34 ćwiczenia (dr inż. Karol Gotfryd)

Literatura

1. T.A. Sudkamp, Languages and Machines, Pearson 2017 (ISBN 978-81-317-1475-1)
2. Ch.H. Papadimitriou, Złożoność obliczeniowa, WNT, Warszawa 2002 (ISBN 83-204-2659-6)
3. M. Sipser, Wprowadzenie do teorii obliczeń, WNT, Warszawa 2009 (ISBN 978-83-204-3436-1)
4. J.E. Hopcroft, J.D. Ullman, Wprowadzenie do teorii automatów, języków i obliczeń, WNT, Warszawa 1994 (ISBN 83-01-11298-0)
5. T.H. Cormen, Ch.E. Leiserson, R.L. Rivest, Wprowadzenie do algorytmów, WNT, Warszawa 1997 (ISBN 83-204-2144-6)
6. Ch. Bernhardt, Obliczenia kwantowe dla każdego, WN PWN, Warszawa 2020 (ISBN 978-83-012-1215-5)
7. H. Barendregt, E. Barendsen, Introduction to Lambda Calculus, 1994

Ćwiczenia

• Lista nr 0
• Lista nr 1

Notatki do wykładów

• Maszyna Turinga (4h)
• Nieobliczalność (2h)

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

1. Maszyna Turinga. (6-03-2025)
   [Definicja TM, konfiguracja TM, redukcja taśm, symulowanie niedeterminizmu. ]
2. Maszyna Turinga (cd). (13-03-2025)
   [Uniwersalna maszyna Turinga. Definicja języków rekurencyjnych i rekurencyjnie przeliczalnych. Generatory. Własności języków rozstrzygalnych i rozpoznawalnych.]
3. Języki nierozstrzygalne. (20-03-2025)
   [Nierozstrzygalność problemu stopu. Inne przykłady języków nierozstrzygalnych. Twierdzenie Rice'a.]

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. Punktacja 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. Ś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ązań przydzielonych zadań z listy. Rozwiązania powinny 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.
3. Z kolokwium można uzyskać od 0 do 5.5 punktu.

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).