Języki formalne i teoria obliczeń 2005

Poniedziałek 7³⁰ - 9⁰⁰ C-11/P.01 wykład

Poniedziałek 11¹⁵ - 13⁰⁰ C4/35 ćwiczenia - mgr Wojciech Rutkowski

Czwartek 7³⁰ - 9⁰⁰ C-11/P.01 wykład

Czwartek 9¹⁵ - 11⁰⁰ C4/35 ćwiczenia

Egzamin końcowy: wtorek, 7 lutego 2006, godz. 15¹⁵, D-1/301

Egzamin poprawkowy: wtorek, 14 lutego 2006, godz. 16¹⁵, D-1/301

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ń

• Lista nr 1 na 3/6 października
• Lista nr 2 na 10/13 października
• Lista nr 3 na 17/20 października
• Lista nr 4 na 24/27 października
• Lista nr 5 na 3/7 listopada
• Lista nr 6 na 10/14 listopada
• Lista nr 7 na 17/21 listopada
• Lista nr 8 na 24/28 listopada
• Lista nr 9 na 1/5 grudnia
• Lista nr 10 na 8/12 grudnia
• Lista nr 11 na 15/19 grudnia
• Lista nr 12 na 5/9 stycznia
• Lista nr 13 na 12/16 stycznia
• Lista nr 14 na 23/26 stycznia

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