Języki formalne i teoria obliczeń 2007
Poniedziałek 730 - 900 C-11/P01 wykład
Czwartek 730 - 900 C-11/P01 wykład
Czwartek 915 - 1100 C-4/35 ćwiczenia
Czwartek 1315 - 1500 C-7/303 ćwiczenia - mgr Anna Lauks
Wykład z 3 stycznia został przeniesiony na 18 stycznia o
730 w C-13/0.31. Termin odrobienia ćwiczeń z 3 stycznia
zostanie podany później.
Egzamin końcowy: poniedziałek 4 lutego 2008, godz.
1715-2100, A-1/329
Egzamin poprawkowy: środa, 13 lutego 2008, godz.
1715-2000, A-1/329
Literatura
- 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)
- J.E. Hopcroft, J.D. Ullman, Wprowadzenie do teorii automatów, języków
i obliczeń, WNT, Warszawa 1994 (ISBN 83-01-11298-0)
- Ch.H. Papadimitriou, Złożoność obliczeniowa, WNT, Warszawa 2002
(ISBN 83-204-2659-6)
- A. Kościelski, Teoria obliczeń. Wykłady z matematycznych podstaw
informatyki, Wydawnictwo Uniwersytetu Wrocławskiego, 1997
(ISBN 83-229-1696-5)
- T.H. Cormen, Ch.E. Leiserson, R.L. Rivest, Wprowadzenie do algorytmów,
WNT, Warszawa 1997 (ISBN 83-204-2144-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ń
- 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. 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.
- 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.
- 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.
- 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.
- 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.
- Ocena nie podlega poprawianiu po zakończeniu semestru.
Egzamin końcowy
- 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.
- W przypadku nie zdania egzaminu końcowego można go jeden raz poprawiać
ale tylko na ocenę co najwyżej 3.0.
- 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)
- Automaty skończone. Wyrażenia i języki regularne. (1-10-2007)
- Równoważność deterministycznych i niedeterministycznych automatów skończonych i wyrażeń regularnych. (4-10-2007)
- Własności klasy języków regularnych. Lemat o pompowaniu. (8-10-2007)
- Twierdzenie Myhill-Nerode. Minimalizacja automatów. (11-10-2007)
- Dwukierunkowy DFA. Podsumowanie języków regularnych. (15-10-2007)
- Gramatyki bezkontekstowe. Usuwanie symboli bezużytecznych, epsilon-produkcji i produkcji jednostkowych. (18-10-2007)
- Godziny rektorskie. (22-10-2007)
- Postać normalna Chomsky'ego. Postać normalna Greibach'a. (29-10-2007)
- Automaty ze stosem (PDA). Równoważność PDA i gramatyk bezkontekstowych. (29-10-2007)
- Lemat o pompowaniu dla języków bezkontekstowych. Lemat Ogdena. (5-11-2007)
- Własności języków bezkontekstowych. Dwukierunkowe PDA. Podsumowanie języków bezkontekstowych. (08-11-2007)
- Maszyna Turinga. Języki rekurencyjne i rekurencyjnie przeliczalne. (12-11-2007)
- Wielotaśmowe TM. Niedeterministyczne TM. Równoważność z jednotaśmową deterministyczną TM. (15-11-2007)
- Uniwersalna TM. Problem stopu. Nierozstrzygalność problemu stopu. Twierdzenie Rice'a. (19-11-2007)
- Maszyna licznikowa. Teza Church'a. (22-11-2007)
- Maszyna RAM. (26-11-2007)
- Równoważność maszyny RAM i maszyn Turinga jako modeli obliczeń. (29-11-2007)
- Funkcje rekurencyjne na liczbach naturalnych. (3-12-2007)
- Lemat Godla o kodowaniu. Równoważność modelu funkcji rekurencyjnych i maszyn Turinga. (6-12-2007)
- Inny sposób definiowania funkcji rekurencyjnych - rekursja prosta. (10-12-2007)
- Problem odpowiedniości Posta. (13-12-2007) - mgr Anna Lauks
- Hierarchia Chomsky'ego. (17-12-2007)
- Podstawy lambda rachunku. (20-12-2007)
- Liczebniki Churcha. Równoważność lambda rachunku z innymi modelami obliczeń. (7-01-2008)
- Złożoność obliczeniowa. Relacje między klasami złożoności. (10-01-2008)
- Twierdzenia o hierarchii. Metoda osiągalności. (14-01-2008)
- NP-zupełność. Twierdzenie Cook'a. (17-01-2008)
- Przykłady problemów NP-zupełnych. (18-01-2008)
- Podsumowanie wykładu (21-01-2008)
- Podsumowanie wykładu (24-01-2008)