MIMINF:Języki, automaty i obliczenia

Forma zajęć

Wykład (30 godzin) + ćwiczenia (30 godzin)

Opis

Podstawowe modele obliczeń (automaty, gramatyki, maszyna Turinga), związki między trudnością problemów obliczeniowych a strukturalną złożonością modeli obliczeń. Hierarchia Chomsky'ego. Matematyczny sens pojęcia obliczalności oraz jego ograniczenia, a także - w zarysie - podstawowe zagadnienia złożoności obliczeniowej.

Sylabus

Autorzy

• Damian Niwiński — Uniwersytet Warszawski, Wydział Matematyki, Informatyki i Mechaniki, Instytut Informatyki

Wymagania wstępne

• Podstawy matematyki
• Matematyka dyskretna
• Wstęp do programowania

Zawartość

• Elementy teorii języków formalnych: słowa, języki, wyrażenia regularne.
• Automaty skończone i twierdzenie Kleene'go o efektywnej odpowiedniości automatów i wyrażeń.
• Konstrukcje optymalizujące automaty - determinizacja, minimalizacja.
• Języki bezkontekstowe: gramatyki i ich postaci normalne.
• Odpowiedniość gramatyk bezkontekstowych i niedeterministycznych automatów ze stosem.
• Kryteria rozróżniania języków regularnych i bezkontekstowych - lematy o pompowaniu.
• Zagadnienia algorytmiczne: problem niepustości dla automatów i gramatyk, rozpoznawanie jezyków bezkontekstowych.
• Przykłady zastosowań automatów i gramatyk.
• Uniwersalne modele obliczeń: maszyna Turinga i jej warianty.
• Granice obliczalności: nierozstrzygalność problemu stopu, przykłady praktycznych problemów nierozstrzygalnych.
• Podsumowanie - klasyfikacja gramatyk, modeli obliczeń i języków według hierarchii Chomsky'ego.
• Wprowadzenie do zagadnień złożoności obliczeniowej: klasy P i NP.
• Twierdzenie Cooka-Levina o NP-zupełności SAT.
• Hipoteza P=/=NP i jej praktyczne implikacje, informacja o pozytywnych zastosowaniach problemów trudnych obliczeniowo, np. w kryptografii.

Literatura

1. J. E. Hopcroft, R. Motwani, J. D. Ullman, Wprowadzenie do teorii automatów, języków i obliczeń, PWN, Warszawa 2005.
2. Ch. Papadimitriou, Złożoność obliczeniowa, WNT, Warszawa 2002.