Języki, automaty i obliczenia: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
| (Nie pokazano 4 wersji utworzonych przez 2 użytkowników) | |||
| Linia 8: | Linia 8: | ||
=== Autorzy === | === Autorzy === | ||
* Maria Foryś | * Maria Foryś — Uniwersytet Jagielloński | ||
* Wit Foryś | * Wit Foryś — Uniwersytet Jagielloński | ||
* Adam Roman | * Adam Roman — Uniwersytet Jagielloński | ||
=== Wymagania wstępne === | === Wymagania wstępne === | ||
| Linia 20: | Linia 20: | ||
=== Zawartość === | === Zawartość === | ||
* Alfabet, słowo, język - elementy teorii półgrup; półgrupy i monoidy wolne | * Alfabet, słowo, język - elementy teorii półgrup; półgrupy i monoidy wolne | ||
* Gramatyki – model obliczeń; hierarchia Chomsky' ego | * Gramatyki – model obliczeń; hierarchia Chomsky'ego | ||
* Języki regularne; automat skończenie stanowy; automat minimalny i algorytmy; automaty deterministyczne i niedeterministyczne; algorytm determinizacji; własności języków regularnych; lemat o pompowaniu i języki nieregularne; wyrażenia regularne i algorytmy; | * Języki regularne; automat skończenie stanowy; automat minimalny i algorytmy; automaty deterministyczne i niedeterministyczne; algorytm determinizacji; własności języków regularnych; lemat o pompowaniu i języki nieregularne; wyrażenia regularne i algorytmy; twierdzenie Kleenego; problemy rozstrzygalności | ||
* Języki bezkontekstowe; własności języków bezkontekstowych, gramatyka - postać Chomsky'ego i Greibach | * Języki bezkontekstowe; własności języków bezkontekstowych, gramatyka - postać Chomsky'ego i Greibach oraz algorytmy upraszczania; automat ze stosem; równoważność gramatyki bezkontekstowej i automatu ze stosem - algorytmy; lemat o pompowaniu i języki, które nie są bezkontekstowe; jednoznaczność, problem przynależności i algorytm CYK; problemy rozstrzygalności | ||
* Języki kontekstowe i typu (0); własności; automat liniowo ograniczony; maszyna Turinga i jej wersje | * Języki kontekstowe i typu (0); własności; automat liniowo ograniczony; maszyna Turinga i jej wersje | ||
* Podstawowe klasy złożoności w języku maszyn Turinga | * Podstawowe klasy złożoności w języku maszyn Turinga | ||
| Linia 28: | Linia 28: | ||
=== Literatura === | === Literatura === | ||
# M.Foryś, W.Foryś, Teoria automatów i języków formalnych, AOW EXIT, Warszawa 2005 | # M. Foryś, W. Foryś, ''Teoria automatów i języków formalnych'', AOW EXIT, Warszawa 2005. | ||
# J.Gruska, Foundations of computing, Thompson, 1997 | # J. Gruska, ''Foundations of computing'', Thompson, 1997. | ||
# J.E.Hopcroft, J.D.Ulman, Introduction to automata theory, languages and computing, Addison-Wesley, 1979 | # J.E. Hopcroft, J.D. Ulman, ''Introduction to automata theory, languages and computing'', Addison-Wesley, 1979. | ||
# A.Salomaa, Computation and automata, Cambridge Univ.Press, 1985 | # A. Salomaa, ''Computation and automata'', Cambridge Univ.Press, 1985. | ||
# M.Sipser, Introduction to the theory of computation, PWS Publishing Company, Boston 1997 | # M. Sipser, ''Introduction to the theory of computation'', PWS Publishing Company, Boston 1997. | ||
== Moduły == | == Moduły == | ||
| Linia 42: | Linia 42: | ||
# [[Języki, automaty i obliczenia/Wykład 6: Automat niedeterministyczny. Lemat o pompowaniu|Automat niedeterministyczny. Lemat o pompowaniu]] ([[Języki, automaty i obliczenia/Ćwiczenia 6: Automat niedeterministyczny. Lemat o pompowaniu|ćwiczenia]]) | # [[Języki, automaty i obliczenia/Wykład 6: Automat niedeterministyczny. Lemat o pompowaniu|Automat niedeterministyczny. Lemat o pompowaniu]] ([[Języki, automaty i obliczenia/Ćwiczenia 6: Automat niedeterministyczny. Lemat o pompowaniu|ćwiczenia]]) | ||
# [[Języki, automaty i obliczenia/Wykład 7: Twierdzenie Kleene'ego. Własności języków i gramatyk regularnych|Twierdzenie Kleene'ego. Własności języków i gramatyk regularnych]] ([[Języki, automaty i obliczenia/Ćwiczenia 7: Twierdzenie Kleene'ego. Własności języków i gramatyk regularnych|ćwiczenia]]) | # [[Języki, automaty i obliczenia/Wykład 7: Twierdzenie Kleene'ego. Własności języków i gramatyk regularnych|Twierdzenie Kleene'ego. Własności języków i gramatyk regularnych]] ([[Języki, automaty i obliczenia/Ćwiczenia 7: Twierdzenie Kleene'ego. Własności języków i gramatyk regularnych|ćwiczenia]]) | ||
# [[Języki, automaty i obliczenia/Wykład 8: Dalsze algorytmy dla języków regularnych. Problemy rozstrzygalne|Dalsze algorytmy dla języków regularnych. Problemy rozstrzygalne]] ([[Języki, automaty i obliczenia/Ćwiczenia 8: Dalsze algorytmy dla języków regularnych. Problemy rozstrzygalne|ćwiczenia]]) | # [[Języki, automaty i obliczenia/Wykład 8: Dalsze algorytmy dla języków regularnych. Problemy rozstrzygalne|Dalsze algorytmy dla języków regularnych. Problemy rozstrzygalne]] ([[Języki, automaty i obliczenia/Ćwiczenia 8: Dalsze algorytmy dla języków regularnych. Problemy rozstrzygalne|ćwiczenia]]) ([[Języki, automaty i obliczenia/Test 8: Dalsze algorytmy dla języków regularnych. Problemy rozstrzygalne|test]]) | ||
# [[Języki, automaty i obliczenia/Wykład 9: Języki bezkontekstowe i ich gramatyki|Języki bezkontekstowe i ich gramatyki]] ([[Języki, automaty i obliczenia/Ćwiczenia 9: Języki bezkontekstowe i ich gramatyki|ćwiczenia]]) | # [[Języki, automaty i obliczenia/Wykład 9: Języki bezkontekstowe i ich gramatyki|Języki bezkontekstowe i ich gramatyki]] ([[Języki, automaty i obliczenia/Ćwiczenia 9: Języki bezkontekstowe i ich gramatyki|ćwiczenia]]) | ||
# [[Języki, automaty i obliczenia/Wykład 10: Lemat o pompowaniu dla języków bezkontekstowych. Własności języków bezkontekstowych. Problemy rozstrzygalne|Lemat o pompowaniu dla języków bezkontekstowych. Własności języków bezkontekstowych. Problemy rozstrzygalne]] ([[Języki, automaty i obliczenia/Ćwiczenia 10: Lemat o pompowaniu dla języków bezkontekstowych. Własności języków bezkontekstowych. Problemy rozstrzygalne |ćwiczenia]]) | # [[Języki, automaty i obliczenia/Wykład 10: Lemat o pompowaniu dla języków bezkontekstowych. Własności języków bezkontekstowych. Problemy rozstrzygalne|Lemat o pompowaniu dla języków bezkontekstowych. Własności języków bezkontekstowych. Problemy rozstrzygalne]] ([[Języki, automaty i obliczenia/Ćwiczenia 10: Lemat o pompowaniu dla języków bezkontekstowych. Własności języków bezkontekstowych. Problemy rozstrzygalne |ćwiczenia]]) | ||
# [[Języki, automaty i obliczenia/Wykład 11: Automat ze stosem|Automat ze stosem]] ([[Języki, automaty i obliczenia/Ćwiczenia 11: Automat ze stosem|ćwiczenia]]) | # [[Języki, automaty i obliczenia/Wykład 11: Automat ze stosem|Automat ze stosem]] ([[Języki, automaty i obliczenia/Ćwiczenia 11: Automat ze stosem|ćwiczenia]]) ([[Języki, automaty i obliczenia/Test 11: Automat ze stosem|test]]) | ||
# [[Języki, automaty i obliczenia/Wykład 12: Języki kontekstowe i automat liniowo ograniczony. Maszyna Turinga |Języki kontekstowe i automat liniowo ograniczony. Maszyna Turinga]] ([[Języki, automaty i obliczenia/Ćwiczenia 12: Języki kontekstowe i automat liniowo ograniczony. Maszyna Turinga|ćwiczenia]]) | # [[Języki, automaty i obliczenia/Wykład 12: Języki kontekstowe i automat liniowo ograniczony. Maszyna Turinga |Języki kontekstowe i automat liniowo ograniczony. Maszyna Turinga]] ([[Języki, automaty i obliczenia/Ćwiczenia 12: Języki kontekstowe i automat liniowo ograniczony. Maszyna Turinga|ćwiczenia]]) | ||
# [[Języki, automaty i obliczenia/Wykład 13: Złożoność obliczeniowa. |Złożoność obliczeniowa.]] ([[Języki, automaty i obliczenia/Ćwiczenia 13: Złożoność obliczeniowa.|ćwiczenia]]) | # [[Języki, automaty i obliczenia/Wykład 13: Złożoność obliczeniowa. |Złożoność obliczeniowa.]] ([[Języki, automaty i obliczenia/Ćwiczenia 13: Złożoność obliczeniowa.|ćwiczenia]]) | ||
# [[Języki, automaty i obliczenia/Wykład 14: Języki maszyn Turinga i typu (0). Rozstrzygalność|Języki maszyn Turinga i typu (0). Rozstrzygalność]] ([[Języki, automaty i obliczenia/Ćwiczenia 14: Języki maszyn Turinga i typu (0). Rozstrzygalność|ćwiczenia]]) | # [[Języki, automaty i obliczenia/Wykład 14: Języki maszyn Turinga i typu (0). Rozstrzygalność|Języki maszyn Turinga i typu (0). Rozstrzygalność]] ([[Języki, automaty i obliczenia/Ćwiczenia 14: Języki maszyn Turinga i typu (0). Rozstrzygalność|ćwiczenia]]) ([[Języki, automaty i obliczenia/Test 14: Języki maszyn Turinga i typu (0). Rozstrzygalność|test]]) | ||
Aktualna wersja na dzień 12:20, 20 mar 2007
Forma zajęć
Wykład (30 godzin) + ćwiczenia (30 godzin)
Opis
Teoria jezyków formalnych, automatów i gramatyk w zakresie hierarchii Chomsky'ego.
Sylabus
Autorzy
- Maria Foryś — Uniwersytet Jagielloński
- Wit Foryś — Uniwersytet Jagielloński
- Adam Roman — Uniwersytet Jagielloński
Wymagania wstępne
- Logika i teoria mnogości
- Algebra liniowa z geometrią analityczną
- Matematyka dyskretna
- Algorytmy i struktury danych
Zawartość
- Alfabet, słowo, język - elementy teorii półgrup; półgrupy i monoidy wolne
- Gramatyki – model obliczeń; hierarchia Chomsky'ego
- Języki regularne; automat skończenie stanowy; automat minimalny i algorytmy; automaty deterministyczne i niedeterministyczne; algorytm determinizacji; własności języków regularnych; lemat o pompowaniu i języki nieregularne; wyrażenia regularne i algorytmy; twierdzenie Kleenego; problemy rozstrzygalności
- Języki bezkontekstowe; własności języków bezkontekstowych, gramatyka - postać Chomsky'ego i Greibach oraz algorytmy upraszczania; automat ze stosem; równoważność gramatyki bezkontekstowej i automatu ze stosem - algorytmy; lemat o pompowaniu i języki, które nie są bezkontekstowe; jednoznaczność, problem przynależności i algorytm CYK; problemy rozstrzygalności
- Języki kontekstowe i typu (0); własności; automat liniowo ograniczony; maszyna Turinga i jej wersje
- Podstawowe klasy złożoności w języku maszyn Turinga
- Języki maszyn Turinga i języki typu (0); teza Churcha; problemy rozstrzygalności
Literatura
- M. Foryś, W. Foryś, Teoria automatów i języków formalnych, AOW EXIT, Warszawa 2005.
- J. Gruska, Foundations of computing, Thompson, 1997.
- J.E. Hopcroft, J.D. Ulman, Introduction to automata theory, languages and computing, Addison-Wesley, 1979.
- A. Salomaa, Computation and automata, Cambridge Univ.Press, 1985.
- M. Sipser, Introduction to the theory of computation, PWS Publishing Company, Boston 1997.
Moduły
- Słowa, katenacja - elementy teorii półgrup, półgrupy i monoidy wolne (ćwiczenia)
- Gramatyka jako model obliczen. Hierarchia Chomsky'ego (ćwiczenia)
- Automat skończenie stanowy (ćwiczenia)
- Wyrażenia regularne. Automat minimalny (ćwiczenia)
- Algorytmy konstrukcji automatu minimalnego (ćwiczenia)
- Automat niedeterministyczny. Lemat o pompowaniu (ćwiczenia)
- Twierdzenie Kleene'ego. Własności języków i gramatyk regularnych (ćwiczenia)
- Dalsze algorytmy dla języków regularnych. Problemy rozstrzygalne (ćwiczenia) (test)
- Języki bezkontekstowe i ich gramatyki (ćwiczenia)
- Lemat o pompowaniu dla języków bezkontekstowych. Własności języków bezkontekstowych. Problemy rozstrzygalne (ćwiczenia)
- Automat ze stosem (ćwiczenia) (test)
- Języki kontekstowe i automat liniowo ograniczony. Maszyna Turinga (ćwiczenia)
- Złożoność obliczeniowa. (ćwiczenia)
- Języki maszyn Turinga i typu (0). Rozstrzygalność (ćwiczenia) (test)
