Języki, automaty i obliczenia

3 zadania domowe, każde za max 0.5 punktu. Zadania będą zadawane w trakcie trwania semestru, do rozwiązania pisemnego z czasem na rozwiązanie około 2-3 tygodni. Celem zadań jest danie możliwości studentom sprawdzenia swoich umiejętności przeprowadzania i redagowania kompletnego rozumowania. Dozwolona jest współpraca nad zadaniem, lecz niedopuszczalne jest wspólne zapisywanie rozwiązania. Każde rozwiązanie musi być samodzielnie zredagowane i spisane.
~~kolokwium za max 1 punkt, 8 maja, w trakcie trwania wykładu. Podczas kolokwium nie będzie można korzystać z materiałów pomocniczych.~~
testy domowe łącznie za max 1 punkt. po każdym wykładzie będzie udostępniony test. Testy są do samodzielnego wykonania. Każdy test daje około 50 punktów. Łącznie będzie około 10 testów. Zachęcam do wykonania testu po wysłuchaniu odpowiedniego wykładu, jeszcze przed ćwiczeniami. Można to jednak zrobić w dowolnym terminie w ciągu tygodnia od publikacji testu (dokładniej: do kolejnego wtorku, g. 23:59).
egzamin za max. 3 punkty (test i zadania). Do egzaminu są dopuszczeni wszyscy.
zadania z gwiazdką w trakcie trwania semestru. Zadania są przeznaczone dla osób które chcą się zmierzyć z trudniejszymi wyzwaniami. Przewiduję około 10 zadań. Każde zadanie jest warte max 2 punkty, do podziału po równo pomiędzy wszystkie osoby, które oddadzą poprawne rozwiązanie.
Ostateczna ocena będzie otrzymana z sumy wszystkich zdobytych punktów, w przybliżeniu według następującej zasady: od 3 punktów ocena 3, od 3.5 punktów ocena 3.5, itd. Zatrzegam sobie możliwość zmodyfikowania tej odpowiedniości celem skorygowania niewłaświe dobranej trudności zadań.

W związku z wybuchem pandemii COVID-19, wszystkie wykłady począwszy od trzeciego były prowadzone online. Są one nagrane i dostępne na tym kanale youtube.

26.02 – słowa, języki, wyrażenia regularne.
4.03 – automaty niedterministyczne, równoważność z wyrażniami regularnymi.
11.03 – własności języków regularnych. Link
18.03 – minimalizacja, twierdzenie Myhilla-Nerodego. Link
25.03 – języki bezkontekstowe. Link
1.04 – własności języków bezkontekstowych, automaty ze stosem. Link
15.04 – algorytmy dla gramatyk bezkontekstowych. Maszyny Turinga. Link
22.04 – funkcje obliczalne. Teza Churcha-Turinga. Link
6.05 – twierdzenie Turinga. Nierozstrzygalność problemu stopu.
13.05 – nierozstrzygalność. Kafelkowanie kwadratu i płaszczyzny.
20.05 – nierozstrzygalność – ciąg dalszy.
27.05 – niedeterminizm, klasy P, NP.

Prowadzę skrypt do wykładu. Kolejne jego części będą pojawiały się po odpowiednich wykładach. Skrypt z grubsza, lecz niedokładnie, odpowiada wykładowi. Będę bardzo wdzięczny za zgłoszone uwagi i znalezione błędy w skrypcie.

Skrypt z minionymi wykładami. Data ostatniej modyfikacji: 13.09.2021 17:29

Zadanie 1 – termin 26.04.
Zadanie 2 – termin 25.05.
Zadanie 3 – termin 14.06.

Zadania – termin ~~8.06~~ 10.06

Polecane podręczniki:

John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, "Wprowadzenie do teorii automatów, języków i obliczeń", PWN.
Michael Sipser, "Wprowadzenie do teorii obliczeń", PWN.

Strony poprzednich edycji tego wykładu:

Materiały Damiana Niwińskiego

Materiały Wojciecha Ryttera

Materiały Mikołaja Bojańczyka

Materiały Pawła Urzyczyna

Materiały Sławomira Lasoty

Materiały Wojciecha Czerwińskiego

Strona wykładu z zeszłego roku

Książka 200 Problems in Formal Languages and Automata Theory to zbiór zadań wraz z rozwiązaniami, w języku angielskim. Tu jest strona książki, wraz z próbką. Książka zawiera rozwiązania zadań zebranych przez Damiana Niwińskiego i Wojciecha Ryttera w zbiorku dostępnym po polsku tutaj. Książka jest dostępna w bibliotece wydziałowej. Zachęcam do odnajdywania błędów i wpisywania ich do erraty.