Ogłoszenia:

  • (9 marca 2015) Jest pierwsza seria zadań z gwiazdką. Termin 7 kwietnia 2015. Powodzenia!
  • (12 marca 2015) Wykład został przeniesiony do sali 5440.
  • (8 kwietnia 2015) Kolokwium będzie 6 maja, w godz. 12:15-13:45.
  • (14 kwietnia 2015) Oto osoby, które poprawnie rozwiązały zadanie 3 z gwiazdką:
    • Wojciech Nadara, Krzysztof Pszeniczny, Rafał Stefański, Bartłomiej Zawalski.
    Gratuluję! Zadań 1, 2 nie rozwiązał poprawnie nikt. W związku z tym przedłużam termin rozwiązywania tych zadań do końca semestru. Wkrótce następna seria zadań.
  • (15 kwietnia 2015) Zmiana terminu kolokwium: 13 maja, godz. 12:15-13:45.
  • (17 kwietnia 2015) Jest druga seria zadań z gwiazdką. Termin 7 maja 2015. Powodzenia!
  • (22 kwietnia 2015) Mała poprawka w drugiej serii zadań z gwiazdką.
  • (13 maja 2015) Zadania z kolokwium i przykładowe rozwiązania.
  • (16 maja 2015) Oto osoby, które poprawnie rozwiązały zadania z gwiazdką z drugiej serii:
    • zadanie 1: Michał Błaziak, Krzysztof Pszeniczny, Rafał Stefański, Arkadiusz Wróbel;
    • zadanie 2: Wojciech Nadara, Krzysztof Pszeniczny, Rafał Stefański, Arkadiusz Wróbel;
    • zadanie 3: Krzysztof Pszeniczny, Rafał Stefański, Arkadiusz Wróbel.
    Gratuluję! Wkrótce następna seria zadań.
  • (21 maja 2015) Jest trzecia seria zadań z gwiazdką. Termin 10 czerwca 2015. Powodzenia! (Na marginesie: model maszyny licznikowej w zadaniu 2 jest wskazówką do zadania 2 z pierwszej serii.)
  • (14 czerwca 2015) Oto osoby, które poprawnie rozwiązały zadania z gwiazdką z trzeciej serii:
    • zadanie 1: Krzysztof Pszeniczny;
    • zadanie 2: Wojciech Nadara, Krzysztof Pszeniczny.
    Ponadto, Pan
    • Rafał Stefański
    poprawnie rozwiązał zadanie 1 z pierwszej serii! Wszystkim serdecznie gratuluję!
  • (21 czerwca 2015) Pan
    • Marek Sommer
    poprawnie rozwiązał zadanie 1 z pierwszej serii! Serdecznie gratuluję!

Wykłady:

  • Wykład 1 (25 lutego): Słowa, języki, homomorfizmy i podstawienia, wyrażenia regularne, przykład automatu. [SLAJDY]
  • Wykład 2 (4 marca): Automaty skończone niedeterministyczne i deterministyczne. Determinizacja. Operacje na automatach: przecięcie, dopełnienie, przeplot. [SLAJDY]
  • Wykład 3 (11 marca): Równoważność wyrażeń regularnych i automatów skończonych. Lemat o pompowaniu. Problemy decyzyjne dla języków regularnych. [SLAJDY]
  • Wykład 4 (18 marca): Język jest regularny wtw gdy ma skończenie wiele ilorazów lewostronnych. Minimalizacja automatów deterministycznych. Automaty a monoidy. [SLAJDY]
  • Wykład 5 (25 marca): Automaty dwukierunkowe. Automaty alternujące. [SLAJDY]
  • Wykład 6 (1 kwietnia): Prima aprilis: automaty na... drzewach. [SLAJDY]
  • Wykład 7 (8 kwietnia): Języki bezkontekstowe. Związek pomiędzy językami bezkontekstowymi a regularnymi językami drzew. Gramatyki jednoznaczne. [SLAJDY]
  • Wykład 8 (15 kwietnia): Automaty ze stosem. Równoważnośc automatów ze stosem i gramatyk bezkontekstowych. Deterministyczne automaty ze stosem a gramatyki jednoznaczne. [SLAJDY]
  • Wykład 9 (22 kwietnia): Pompowanie języków bezkontekstowych, własności domknięcia, twierdzenie Parikha. [SLAJDY]
  • Wykład 10 (29 kwietnia): Maszyny Turinga, problemy częściowo rozstrzygalne, maszyna uniwersalna. [SLAJDY]
  • Wykład 11 (6 maja): Problemy (częściowo) rozstrzygalne, funkcje (częściowo) obliczalne. Redukcje. Przykłady problemów nierozstrzygalnych, m.in. PCP. [SLAJDY]
  • Wykład 12 (20 maja): Gramatyki i inne modele równoważne maszynom Turinga. Wstęp do złożoności obliczeniowej. [SLAJDY]
  • Wykład 13 (27 maja): Wielomianowy czas i pamięć. [SLAJDY]

Materiały dodatkowe:

Książka: