Języki formalne i teoria obliczeń 2003

Poniedziałek 17:05-18:45 C-11/P.01 wykład

Poniedziałek 18:55-20:40 C-11/P.01 ćwiczenia

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

Terminy egzaminów: 3 luty 2004 godz. 15:15 (D1/301), 9 luty 2004 godz. 15:15 (B5/25).

Egzamin poprawkowy tylko na ocenę dst.

Konsultacje i wpisywanie ocen: sobota 10-11, poniedziałek 12-13.

Konsultacje i wpisywanie ocen: piatek 15-16.

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. T.H. Cormen, Ch.E. Leiserson, R.L. Rivest, Wprowadzenie do algorytmów, WNT, Warszawa 1997 (ISBN 83-204-2144-6)

Listy zadań

1. Lista nr 1 na 6 października
2. Lista nr 2 na 13 października
3. Lista nr 3 na 20 października
4. Lista nr 4 na 27 października
5. Lista nr 5 na 3 listopada
6. Lista nr 6 na 10 listopada
7. Lista nr 7 na 17 listopada
8. Lista nr 8 na 24 listopada
9. Lista nr 9 na 1 grudnia
10. Lista nr 10 na 8 grudnia
11. Lista nr 11 na 15 grudnia
12. Lista nr 12 na 5 stycznia
13. Lista nr 12,(9) na 12 stycznia
14. Lista nr 14 na 19 stycznia
15. Lista nr 15 na 26 stycznia

Formularz zgłaszania zadań

Wyniki ćwiczeń

Zasady zaliczenia ćwiczeń

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.

Wykładowca ogłasza z odpowiednim wyprzedzeniem listy zadań do samodzielnego rozwiązania przed zajęciami. Jeśli student ma wątpliwości i chciałby je skonsultować z prowadzącym, powinien to uczynić w czasie godzin konsultacji.

Podstawą do wystawienia oceny jest liczba zadań, które student rozwiązał w trakcie całego semestru.

Szczegółowe zasady zajęć

1. 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.
2. Przed rozpoczęciem zajęć student przekazuje prowadzącemu ćwiczenia kartkę z numerami zadań z listy, które potrafi rozwiązać. Kartka powinna być wypełniona czytelnie, zawierać datę i jednoznacznie wpisane numery zadań. Po rozpoczęciu zajęć dokonywanie jakichkolwiek zmian w treści przekazanych kartek jest niedopuszczalne. Rozwiązanie danego zadania na tablicy przedstawia jedna z osób, wybrana przez prowadzącego, która zgłosiła gotowość rozwiązania tego zadania. Osoba referująca rozwiązanie nie używa notatek.
3. Na każdych zajęciach student zdobywa tyle punktów ile zadań zgłosi do rozwiązania.
4. Jeżeli podczas przedstawiania rozwiązania na tablicy okaże się, że student popełnił błąd (np. przeoczył trudność lub źle zrozumiał treść zadania) i nie jest w stanie rozwiązać poprawnie tego zadania, traci wszystkie punkty za zgłoszone tego dnia zadania. Jeżeli okaże się, że student oświadczył nieprawdę i nie umie w ogóle przedstawić rozwiązania zadania lub nawet nie rozumie jego treści, traci dodatkowo 10 punktów.
5. W semestrze można zdobyć x punktów (suma z zadań ze wszystkich ogłoszonych list). Ocena końcowa z zajęć jest wystawiana na podstawie liczby uzyskanych przez studenta punktów: dst za co najmniej 34%x, dst+ za co najmniej 42%x, db za co najmniej 50%x, db+ za co najmniej 58%x, bdb za co najmniej 66%x, oraz bdb+ za co najmniej 80%x.
6. 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.
2. Równoważność deterministycznych i niedeterministycznych automatów skończonych i wyrażeń regularnych.
3. Lemat o pompowaniu. Własności języków regularnych.
4. Twierdzenie Myhill'a-Nerode'a i minimalizacja automatów skończonych.
5. Gramatyki i języki bezkontekstowe.
6. Postacie normalne gramatyk bezkontekstowych.
7. Automaty ze stosem. Równoważność gramatyk bezkontekstowych i automatów ze stosem.
8. Lemat o pompowaniu dla języków bezkontekstowych. Lemat Ogdena.
9. Własności języków bezkontekstowych.
10. Maszyna Turinga. Zbiory rekurencyjne i rekurencyjnie przeliczalne.
11. Modyfikacje maszyn Turinga. Niedeterminizm.
12. Uniwersalna maszyna Turinga. Kodowanie maszyn Turinga. Nierozstrzygalność problemu stopu. Twierdzenie Rice'a.
13. Teza Church-a. Inne modele obliczeń. Maszyna RAM.
14. Równoważność modeli obliczeń: RAM i maszyn Turinga.
15. Arytmetyczne funkcje rekurencyjne na liczbach naturalnych.
16. Lemat Godla o kodowaniu. Równoważność klasy arytmetycznych funkcji rekurencyjnych z klasą funkcji obliczalnych na maszynach Turinga.
17. Hierarchia Chomsky'ego.
18. Relacje między klasami złożoności. Twierdzenie o hierarchii.
19. Metoda osiągalności. Redukcje problemów.
20. Zupełność. Circuit value jako problem P-zupełny. Twierdzenie Cook'a - NP-zupełność problemu SAT.
21. Przykłady redukcji dla problemów NP-zupełnych. NP-zupełność 3SAT, HAMILTON-PATH. Wielomianowość 2SAT.
22. Przykłady problemów NP-zupełnych: MAX2SAT(K), INDEPENDENT-SET(K), traveller salesman problem TSP(K).
23. Problemy co-NP-zupełne. Problemy pseudowielomianowe. Silna NP-zupełność.
24. Problemy PSPACE-zupełne.
25. Podstawy lambda rachunku.
26. Obliczalność w lambda rachunku.
27. Uzupełnienie własności automatów: automaty dwustronne, maszyny licznikowe.
28. Problem odpowiedniości Posta.