MIMINF:Języki, automaty i obliczenia

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

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 matematy
  • 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 pozytywnym zastosowanie problemów trudnych obliczeniowo, np. w kryptografii.

Literatura

  1. L. Banachowski, K. Diks, W. Rytter, Algorytmy i struktury danych, Wydawnictwa Naukowo - Techniczne, 2006.
  2. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Wprowadzenie do algorytmów, Wydawnictwa Naukowo - Techniczne, 2004.
Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=MIMINF:Języki,_automaty_i_obliczenia&oldid=64183”