MIMINF:Języki, automaty i obliczenia

From Studia Informatyczne

Spis treści

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.