Języki formalne i teoria obliczeń 2006

Poniedziałek 730 - 900 C-11/P01 wykład

Środa 1315 - 1500 C-4/35 ćwiczenia - mgr Wojciech Rutkowski

Czwartek 730 - 900 C-11/P01 wykład

Czwartek 915 - 1100 C-4/35 ćwiczenia

Egzamin końcowy: poniedziałek 5 lutego 2007, godz. 1515-1900, D-1/301

Egzamin poprawkowy: wtorek, 13 lutego 2007, godz. 1315-1600, D-1/301

Osoby które nie zaliczyły ćwiczeń (ocena ndst) mogą wybrać na który egzamin chcą przyjść.

W ramach totalnej amnestii na poprawkę może przyjść każdy kto nie zaliczył pierwszego terminu.

Literatura

  1. J.E. Hopcroft, R. Motwani, J.D. Ullman, Wprowadzenie do teorii automatów, języków i obliczeń, WNT, Warszawa 2005 (ISBN 83-01-14502-1)
  2. J.E. Hopcroft, J.D. Ullman, Wprowadzenie do teorii automatów, języków i obliczeń, WNT, Warszawa 1994 (ISBN 83-01-11298-0)
  3. Ch.H. Papadimitriou, Złożoność obliczeniowa, WNT, Warszawa 2002 (ISBN 83-204-2659-6)
  4. A. Kościelski, Teoria obliczeń. Wykłady z matematycznych podstaw informatyki, Wydawnictwo Uniwersytetu Wrocławskiego, 1997 (ISBN 83-229-1696-5)
  5. T.H. Cormen, Ch.E. Leiserson, R.L. Rivest, Wprowadzenie do algorytmów, WNT, Warszawa 1997 (ISBN 83-204-2144-6)
  6. H. Barendregt, E. Barendsen, Introduction to Lambda Calculus, 1994

Listy zadań

Zasady zaliczenia kursu

Zaliczenie kursu składa się z dwóch części: zaliczenia ćwiczeń i egzaminu końcowego.

Zaliczenie ć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 nie podlega poprawianiu po zakończeniu semestru.

Egzamin końcowy

  1. Egzamin końcowy jest pisany w sesji egzaminacyjnej. Składa się z dwóch części po 90 minut każda. Zdanie egzaminu jest warunkiem koniecznym zaliczenia kursu.
  2. W przypadku nie zdania egzaminu końcowego można go jeden raz poprawiać ale tylko na ocenę co najwyżej 3.0.
  3. Na egzaminie 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.

Ocena końcowa

Ocena końcowa jest średnią z oceny na zaliczenie i oceny z egzaminu zaokrąglonej w górę do najbliższej oceny (2.5 zaokrągla się jednak do 2.0).

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

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

Counter Valid XHTML 1.1! Valid CSS!

Maciej.Gebala@pwr.edu.pl