Języki formalne i teoria obliczeń 2004

Środa 9:15-11:00 C-11/P.01 wykład

Czwartek 7:30-9:00 C-11/P.01 wykład

Czwartek 9:15-11:00 C4/35 ćwiczenia

Czwartek 11:15-13:00 C4/35 ćwiczenia - Wojtek Rutkowski

Egzamin: poniedziałek 7.02.2005 godz. 15:00 D-1/301

Egzamin poprawkowy: wtorek 15.02.2005 godz. 17:00 B-5/25

Na egzaminie można posiadać wyraźnie podpisaną ściągę formatu A4. Egzamin poprawkowy zdają tylko osoby które nie zaliczyły właściwego egzaminu i można na nim uzyskać co najwyżej ocenę 3.0.

Literatura

  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)
  2. Ch.H. Papadimitriou, Złożoność obliczeniowa, WNT, Warszawa 2002 (ISBN 83-204-2659-6)
  3. A. Kościelski, Teoria obliczeń. Wykłady z matematycznych podstaw informatyki, Wydawnictwo Uniwersytetu Wrocławskiego, 1997 (ISBN 83-229-1696-5)
  4. T.H. Cormen, Ch.E. Leiserson, R.L. Rivest, Wprowadzenie do algorytmów, WNT, Warszawa 1997 (ISBN 83-204-2144-6)
  5. H. Barendregt, E. Barendsen, Introduction to Lambda Calculus, 1994

Listy zadań

  1. Lista nr 1 na 7 października
  2. Lista nr 2 na 14 października
  3. Lista nr 3 na 21 października
  4. Lista nr 4 na 28 października
  5. Lista nr 5 na 4 listopada
  6. Lista nr 6 na 18 listopada
  7. Lista nr 7 na 25 listopada
  8. Lista nr 8 na 2 grudnia
  9. Lista nr 9 na 9 grudnia
  10. Lista nr 10 na 16 grudnia
  11. Lista nr 11 na 6 stycznia
  12. Lista nr 12 na 13 stycznia
  13. Lista nr 13 na 20 stycznia
  14. Lista nr 14 na 25 stycznia

Zasady zaliczenia ćwiczeń

  1. 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.
  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 wystawienia oceny 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. Podstawą do oceny na zaliczenie jest średnia ze sprawdzianów zaokrąglona w górę do najbliższej oceny. Ocena może być podwyższona przez prowadzącego w zależności od aktywności studenta na ćwiczeniach.
  5. Na każde ćwiczenia jest przygotowywana osobna lista zadań, ogłaszana co najmniej na trzy dni przed zajęciami. Na ćwiczeniach rozwiązywane są wybrane zadania z tej listy. Decyzję odnośnie wyboru zadań do rozwiązania podejmuje prowadzący.
  6. Dodatkowym warunkiem zaliczenia jest oddanie przez studenta w formie pisemnej (PDF) wyznaczonych zadań zrobionych na ćwiczeniach. Oddawane zadanie powinno być rozwiązane dokładnie, w sposób formalny i przejrzysty. Zadanie wyznacza prowadzący ćwiczenia.
  7. Ocena końcowa nie podlega poprawianiu po zakończeniu semestru.

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

  1. Automaty skończone. Wyrażenia i języki regularne. (6-10-2004)
  2. Równoważność deterministycznych i niedeterministycznych automatów skończonych i wyrażeń regularnych. (7-10-2004)
  3. Własności klasy języków regularnych. Lemat o pompowaniu. (13-10-2004)
  4. Twierdzenie Myhill-Nerode. Minimalizacja automatów. (14-10-2004)
  5. Algorytm minimalizacji dla DFA. Dwukierunkowy DFA. (20-10-2004)
  6. Gramatyki bezkontekstowe. (21-10-2004)
  7. Usuwanie symboli bezużytecznych, epsilon-produkcji i produkcji jednostkowych (27-10-2004)
  8. Postacie normalne: Chomsky'ego i Greibach'a. (28-10-2004)
  9. Automaty ze stosem (DFA). Równoważność DFA i gramatyk bezkontekstowych. (3-11-2004)
  10. Lemat o pompowaniu dla języków bezkontekstowych. Lemat Ogdena. (4-11-2004)
  11. Własności języków bezkontekstowych. (10-11-2004)
  12. Maszyna Turinga. Języki rekurencyjne i rekurencyjnie przeliczalne. (17-11-2004)
  13. Wielotaśmowe TM. Niedeterministyczne TM.Uniwersalna maszyna Turinga. (18-11-2004)
  14. Problem stopu. Nierozstrzygalność problemu stopu. (24-11-2004)
  15. Twierdzenie Rice'a. Teza Church'a. Maszyna licznikowa. (25-11-2004)
  16. Maszyna RAM. (1-12-2004)
  17. Równoważność maszyny RAM i maszyn Turinga jako modeli obliczeń. (2-12-2004)
  18. Funkcje rekurencyjne na liczbach naturalnych. (8-12-2004)
  19. Lemat Godla o kodowaniu. (9-12-2004)
  20. Równoważność modelu funkcji rekurencyjnych i maszyn Turinga. (15-12-2004)
  21. Inny sposób definiowania funkcji rekurencyjnych - rekursja prosta. (16-12-2004)
  22. Problem odpowiedniości Posta. Hierarcha Chomsky'ego. (22-12-2004)
  23. Podstawy lambda rachunku. (5-01-2005)
  24. Liczebniki Churcha. Równoważność z innymi modelami obliczeń. (6-01-2005)
  25. Złożoność obliczeniowa. Relacje między klasami złożoności. (12-01-2005)
  26. Twierdzenia o hierarchii. Metoda osiągalności. (13-01-2005)
  27. NP-zupełność. Twierdzenie Cook'a. (19-01-2005)
  28. PSPACE-zupełność. (20-01-2005)

Counter Valid XHTML 1.1! Valid CSS!

Maciej.Gebala@pwr.edu.pl