MIMINF:Języki, automaty i obliczenia: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
| (Nie pokazano 5 pośrednich wersji utworzonych przez tego samego użytkownika) | |||
| Linia 3: | Linia 3: | ||
== Opis == | == Opis == | ||
Podstawowe modele obliczeń (automaty, gramatyki, maszyna Turinga), związki między | 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 == | == Sylabus == | ||
| Linia 10: | Linia 10: | ||
=== Wymagania wstępne === | === Wymagania wstępne === | ||
* Podstawy | * Podstawy matematyki | ||
* Matematyka dyskretna | * Matematyka dyskretna | ||
* Wstęp do programowania | * Wstęp do programowania | ||
| Linia 16: | Linia 16: | ||
=== Zawartość === | === Zawartość === | ||
*Elementy teorii języków formalnych: słowa, języki, wyrażenia regularne. | *Elementy teorii języków formalnych: słowa, języki, wyrażenia regularne. | ||
*Automaty skończone i twierdzenie Kleene'go o efektywnej | *Automaty skończone i twierdzenie Kleene'go o efektywnej odpowiedniości automatów i wyrażeń. | ||
*Konstrukcje optymalizujące automaty - determinizacja, minimalizacja. | *Konstrukcje optymalizujące automaty - determinizacja, minimalizacja. | ||
*Języki bezkontekstowe: gramatyki i ich postaci normalne. | *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. | *Kryteria rozróżniania języków regularnych i bezkontekstowych - lematy o pompowaniu. | ||
*Zagadnienia algorytmiczne: problem | *Zagadnienia algorytmiczne: problem niepustości dla automatów i gramatyk, rozpoznawanie jezyków bezkontekstowych. | ||
*Przykłady zastosowań automatów i gramatyk. | *Przykłady zastosowań automatów i gramatyk. | ||
*Uniwersalne modele obliczeń: maszyna Turinga i jej warianty. | *Uniwersalne modele obliczeń: maszyna Turinga i jej warianty. | ||
*Granice | *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. | *Podsumowanie - klasyfikacja gramatyk, modeli obliczeń i języków według hierarchii Chomsky'ego. | ||
*Wprowadzenie do zagadnień | *Wprowadzenie do zagadnień złożoności obliczeniowej: klasy P i NP. | ||
*Twierdzenie Cooka-Levina o NP- | *Twierdzenie Cooka-Levina o NP-zupełności SAT. | ||
*Hipoteza P=/=NP i jej praktyczne implikacje, informacja o | *Hipoteza P=/=NP i jej praktyczne implikacje, informacja o pozytywnych zastosowaniach problemów trudnych obliczeniowo, np. w kryptografii. | ||
=== Literatura === | === Literatura === | ||
# J. E. Hopcroft, R. Motwani, J. D. Ullman, ''Wprowadzenie do teorii automatów, języków i obliczeń'', PWN, Warszawa 2005. | # J. E. Hopcroft, R. Motwani, J. D. Ullman, ''Wprowadzenie do teorii automatów, języków i obliczeń'', PWN, Warszawa 2005. | ||
# Ch. Papadimitriou, '' | # Ch. Papadimitriou, ''Złożoność obliczeniowa'', WNT, Warszawa 2002. | ||
Aktualna wersja na dzień 12:50, 11 sty 2007
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
- J. E. Hopcroft, R. Motwani, J. D. Ullman, Wprowadzenie do teorii automatów, języków i obliczeń, PWN, Warszawa 2005.
- Ch. Papadimitriou, Złożoność obliczeniowa, WNT, Warszawa 2002.
