Języki formalne i teoria obliczeń 2009

Wtorek 15¹⁵ - 16⁵⁵ C-11/2.11 wykład

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

Wtorek 11¹⁵ - 13⁰⁰ C-7/303 ćwiczenia - mgr Filip Zagórski

Egzamin końcowy:
I część: czwartek 10 grudnia 2009, godz. 7³⁰-9⁰⁰, C-11/P.01
II część: czwartek 21 stycznia 2010, godz. 7³⁰-9⁰⁰, C-11/P.01

Egzamin poprawkowy: czwartek 4 lutego 2010, godz. 7³⁰-10⁰⁰, C-11/P.01

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ń

• Lista nr 1 na 6 października
• Lista nr 2 na 13 października
• Lista nr 3 na 20 października
• Lista nr 4 na 27 października
• Lista nr 5 na 3 listopada
• Lista nr 6 na 17 listopada
• Lista nr 7 na 24 listopada
• Lista nr 8 na 1 grudnia
• Lista nr 9 na 8 grudnia
• Lista nr 10 na 15 grudnia
• Lista nr 11 na 22 grudnia
• Lista nr 12 na 5 stycznia
• Lista nr 13 na 12 stycznia
• Lista nr 14 na 19 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 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. (6-10-2009)
2. Równoważność deterministycznych i niedeterministycznych automatów skończonych i wyrażeń regularnych. (8-10-2009)
3. Własności klasy języków regularnych. Lemat o pompowaniu. (13-10-2009)
4. Twierdzenie Myhill-Nerode. Minimalizacja automatów. (15-10-2009)
5. Dwukierunkowy DFA. Podsumowanie języków regularnych. (20-10-2009)
6. Gramatyki bezkontekstowe. Usuwanie symboli bezużytecznych, epsilon-produkcji i produkcji jednostkowych. (22-10-2009)
7. Postać normalna Chomsky'ego. Postać normalna Greibach'a. (27-10-2009)
8. Automaty ze stosem (PDA). Równoważność PDA i gramatyk bezkontekstowych. (29-10-2009)
9. Lemat o pompowaniu dla języków bezkontekstowych. Lemat Ogdena. (3-11-2009)
10. Własności języków bezkontekstowych. Dwukierunkowe PDA. Podsumowanie języków bezkontekstowych. (5-11-2009)
11. Maszyna Turinga. Języki rekurencyjne i rekurencyjnie przeliczalne. (17-11-2009)
12. Wielotaśmowe TM. Niedeterministyczne TM. Równoważność z jednotaśmową deterministyczną TM. (19-11-2009)
13. Uniwersalna TM. Problem stopu. Nierozstrzygalność problemu stopu. Twierdzenie Rice'a. (24-11-2009)
14. Maszyna licznikowa. Teza Church'a. (16-11-2009)
15. Maszyna RAM. (1-12-2009)
16. Równoważność maszyny RAM i maszyn Turinga jako modeli obliczeń. (3-12-2009)
17. Podsumowanie języków regularnych i bezkontekstowych. (8-12-2009)
18. I część egzaminu. (10-12-2009)
19. Funkcje rekurencyjne na liczbach naturalnych. (15-12-2009)
20. Lemat Godla o kodowaniu. Równoważność modelu funkcji rekurencyjnych i maszyn Turinga. (17-12-2009)
21. Inny sposób definiowania funkcji rekurencyjnych - rekursja prosta. (22-12-2009)
22. Podstawy lambda rachunku. (5-01-2010)
23. Liczebniki Churcha. Równoważność lambda rachunku z innymi modelami obliczeń. (7-01-2010)
24. Hierarchia Chomsky'ego. (12-01-2010)
25. Problem odpowiedniości Posta. (14-01-2010)