Ogłoszenia:

  • (8 marca) Jest pierwsza seria zadań z gwiazdką. Termin 6 kwietnia. Powodzenia!
  • (15 marca) Kolokwium będzie 18 maja.
  • (6 kwietnia) Termin oddawania zadań z gwiazdką z pierwszej serii przedłużony do 17 kwietnia.
  • (22 kwietnia) Jest druga seria zadań z gwiazdką. Termin 20 maja. Powodzenia!
  • (25 kwietnia) Oto osoby, które poprawnie rozwiązały zadania z gwiazdką z pierwszej serii:
    • zadanie 1: Albert Gutowski, Jakub Marciniszyn, Grzegorz Pierczyński, Jakub Skorupski, Marek Sokołowski, Magdalena Szarkowska, Adam Trzaskowski;
    • zadanie 2: Marek Sokołowski, Jakub Staroń;
    • zadanie 3: Albert Gutowski, Grzegorz Pierczyński, Magdalena Szarkowska, Adam Trzaskowski.
    Gratuluję!
  • (29 maja) Jest trzecia seria zadań z gwiazdką. Termin 22 czerwca. Powodzenia!
  • (29 maja) Zadania 1 z drugiej serii zadań z gwiazdką nie rozwiązał nikt. W związku z tym rozwiązania tego zadania będę przyjmował do końca semestru. Życzę dobrej zabawy!
  • (6 czerwca) Oto osoby, które poprawnie rozwiązały zadania z gwiazdką z drugiej serii:
    • zadanie 2: Jakub Marciniszyn, Jakub Skorupski, Adam Trzaskowski;
    • zadanie 3: Jakub Skorupski, Adam Trzaskowski.
    Gratuluję!
  • (27 czerwca) Oto osoby, które poprawnie rozwiązały zadania z gwiazdką z trzeciej serii:
    • zadanie 1: Krystyna Gajczyk, Jakub Marciniszyn, Mateusz Sokołowski, Mateusz Śmiech;
    • zadanie 3: Krystyna Gajczyk.
    Gratuluję!

Wykłady:

  • Wykład 1 (2 marca): Słowa, języki i operacje na nich. Wyrażenia regularne. [SLAJDY]
  • Wykład 2 (9 marca): Automaty skończone niedeterministyczne i deterministyczne i operacje na nich. Determinizacja. [SLAJDY]
  • Wykład 3 (16 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 (23 marca): Języki regularne mają skończenie wiele ilorazów lewostronnych. Minimalizacja automatów deterministycznych. [SLAJDY]
  • Wykład 5 (30 marca): Automaty dwukierunkowe. Automaty alternujące. [SLAJDY]
  • Wykład 6 (6 kwietnia): Automaty na drzewach. [SLAJDY]
  • Wykład 7 (13 kwietnia): Języki bezkontekstowe. Związek pomiędzy językami bezkontekstowymi a regularnymi językami drzew. Gramatyki jednoznaczne. [SLAJDY]
  • Wykład 8 (20 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 (27 kwietnia): Pompowanie języków bezkontekstowych, własności domknięcia, twierdzenie Parikha. [SLAJDY]
  • Wykład 10 (4 maja): Maszyny Turinga, problemy częściowo rozstrzygalne, maszyna uniwersalna. [SLAJDY]
  • Wykład 11 (25 maja): Problemy (częściowo) rozstrzygalne, funkcje (częściowo) obliczalne. Redukcje. Przykłady problemów nierozstrzygalnych, m.in. PCP. [SLAJDY]
  • Wykład 12 (1 czerwca): Modele równoważne maszynom Turinga. Wstęp do złożoności obliczeniowej. [SLAJDY]
  • Wykład 13 (8 czerwca): Wielomianowy czas i pamięć. [SLAJDY]

Materiały dodatkowe:

Książka: