Języki, automaty i obliczenia: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
← poprzednia edycja
WizualnieWikikod
Gracja (dyskusja | edycje)
4759 edycji
Forys (dyskusja | edycje)
60 edycji
 
(Nie pokazano 46 wersji utworzonych przez 6 użytkowników)
Linia 6: Linia 6:


== Sylabus ==
== Sylabus ==
* Słowa, katenacja - 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; tw. Kleene; rozstrzygalność
* Języki bezkontekstowe; własności, gramatyka - postać Chomsky'ego i Greibach i algorytmy do upraszczania; automat ze stosem; równoważność gramatyki bezkontekstowej i automatu ze stosem - algorytmy; lemat o pompowaniu; jednoznaczność, problem przynależności  i algorytm CYK; rozstrzygalność
* Języki kontekstowe i typu (0); własności; automat liniowo ograniczony; maszyna Turinga; inne modele obliczeń; Podstawowe klasy złożoności w języku MT; języki rekurencyjnie przeliczalne i rekurencyjne; teza Churcha
* Problemy złożoności i problemy rozstrzygalności w teorii języków


=== 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 25: Linia 19:


=== Zawartość ===
=== Zawartość ===
* Elementy teorii półgrup, półgrupy i monoidy wolne, podmonoidy monoidów wolnych
* 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–algorytm konstrukcji, automaty deterministyczne i niedeterministyczne, lemat o pompowaniu i języki nieregularne, wyrażenia regularne, tw. Kleene
* 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, gramatyka - postać Chomsky'ego i Greibach, automat ze stosem, równoważność gramatyki bezkontekstowej i automatu ze stosem - algorytmy, lemat o pompowaniu, jednoznaczność
* 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
* Równania dla języków - algorytm rozwiązywania
* Języki kontekstowe i typu (0); własności; automat liniowo ograniczony; maszyna Turinga i jej wersje
* Języki kontekstowe i typu (0), automat liniowo ograniczony, maszyna Turinga, języki rekurencyjnie przeliczalne i rekurencyjne, teza Churcha
* Podstawowe klasy złożoności w języku maszyn Turinga
* Problemy rozstrzygalne i nierozstrzygalne w teorii języków
* Języki maszyn Turinga i języki typu (0); teza Churcha; problemy rozstrzygalności


=== 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 ==
[[Języki, automaty i obliczenia/Wykład 1 Słowa, katenacja - elementy teorii półgrup, półgrupy i monoidy wolne|Słowa, katenacja - elementy teorii półgrup, półgrupy i monoidy wolne ]] ([[Języki, automaty i obliczenia/Ćwiczenia 1 Słowa, katenacja - elementy teorii półgrup, półgrupy i monoidy wolne|ćwiczenia]])
# [[Języki, automaty i obliczenia/Wykład 1: Słowa, katenacja - elementy teorii półgrup, półgrupy i monoidy wolne|Słowa, katenacja - elementy teorii półgrup, półgrupy i monoidy wolne]] ([[Języki, automaty i obliczenia/Ćwiczenia 1: Słowa, katenacja - elementy teorii półgrup, półgrupy i monoidy wolne|ćwiczenia]])
* [[ZASD Moduł 1| Elementy teorii półgrup]] ([[ZASD Ćwiczenia 1|ćwiczenia]])
# [[Języki, automaty i obliczenia/Wykład 2: Gramatyka jako model obliczen. Hierarchia Chomsky'ego|Gramatyka jako model obliczen. Hierarchia Chomsky'ego]] ([[Języki, automaty i obliczenia/Ćwiczenia 2: Gramatyka jako model obliczen. Hierarchia Chomsky'ego|ćwiczenia]])
* [[ZASD Moduł 2|Gramatyki ]]([[ZASD Ćwiczenia 2|ćwiczenia]])
# [[Języki, automaty i obliczenia/Wykład 3: Automat skończenie stanowy|Automat skończenie stanowy]] ([[Języki, automaty i obliczenia/Ćwiczenia 3: Automat skończenie stanowy|ćwiczenia]])
* [[ZASD Moduł 3|Automat skończenie stanowy I]] ([[ZASD Ćwiczenia 3|ćwiczenia]])
# [[Języki, automaty i obliczenia/Wykład 4: Wyrażenia regularne. Automat minimalny|Wyrażenia regularne. Automat minimalny]] ([[Języki, automaty i obliczenia/Ćwiczenia 4: Wyrażenia regularne. Automat minimalny|ćwiczenia]])
* [[ZASD Moduł 4|Automat skończenie stanowy II]] ([[ZASD Ćwiczenia 4|ćwiczenia]])
# [[Języki, automaty i obliczenia/Wykład 5: Algorytmy konstrukcji automatu minimalnego|Algorytmy konstrukcji automatu minimalnego]] ([[Języki, automaty i obliczenia/Ćwiczenia 5: Algorytmy konstrukcji automatu minimalnego|ćwiczenia]])
* [[ZASD Moduł 5|Lemat o pompowaniu ]] ([[ZASD Ćwiczenia 5|ć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]])
* [[ZASD Moduł 6|Wyrażenia regularne ]] ([[ZASD Ćwiczenia 6|ć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]])
* [[ZASD Moduł 7|Gramatyki regularne]] ([[ZASD Ćwiczenia 7|ć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]])
* [[ZASD Moduł 8|Języki bezkontekstowe I ]] ([[ZASD Ćwiczenia 8|ć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]])
* [[ZASD Moduł 9|Języki bezkontekstowe II]] ([[ZASD Ćwiczenia 9|ć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]])
* [[ZASD Moduł 10|Automat ze stosem]] ([[ZASD Ćwiczenia 10|ć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]])
* [[ZASD Moduł 11|Lemat o pompowaniu, jednoznaczność]] ([[ZASD Ćwiczenia 11|ć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]])
* [[ZASD Moduł 12|Równania dla języków ]] ([[ZASD Ćwiczenia 12|ć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]])
* [[ZASD Moduł 13|Języki kontekstowe i typu (0)]] ([[ZASD Ćwiczenia 13|ć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]])
* [[ZASD Moduł 14|Maszyna Turinga]] ([[ZASD Ćwiczenia 14|ćwiczenia]])
* [[ZASD Moduł 15|Problemy rozstrzygalne i nierozstrzygalne]] ([[ZASD Ćwiczenia 15|ćwiczenia]])

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

  1. M. Foryś, W. Foryś, Teoria automatów i języków formalnych, AOW EXIT, Warszawa 2005.
  2. J. Gruska, Foundations of computing, Thompson, 1997.
  3. J.E. Hopcroft, J.D. Ulman, Introduction to automata theory, languages and computing, Addison-Wesley, 1979.
  4. A. Salomaa, Computation and automata, Cambridge Univ.Press, 1985.
  5. M. Sipser, Introduction to the theory of computation, PWS Publishing Company, Boston 1997.

Moduły

  1. Słowa, katenacja - elementy teorii półgrup, półgrupy i monoidy wolne (ćwiczenia)
  2. Gramatyka jako model obliczen. Hierarchia Chomsky'ego (ćwiczenia)
  3. Automat skończenie stanowy (ćwiczenia)
  4. Wyrażenia regularne. Automat minimalny (ćwiczenia)
  5. Algorytmy konstrukcji automatu minimalnego (ćwiczenia)
  6. Automat niedeterministyczny. Lemat o pompowaniu (ćwiczenia)
  7. Twierdzenie Kleene'ego. Własności języków i gramatyk regularnych (ćwiczenia)
  8. Dalsze algorytmy dla języków regularnych. Problemy rozstrzygalne (ćwiczenia) (test)
  9. Języki bezkontekstowe i ich gramatyki (ćwiczenia)
  10. Lemat o pompowaniu dla języków bezkontekstowych. Własności języków bezkontekstowych. Problemy rozstrzygalne (ćwiczenia)
  11. Automat ze stosem (ćwiczenia) (test)
  12. Języki kontekstowe i automat liniowo ograniczony. Maszyna Turinga (ćwiczenia)
  13. Złożoność obliczeniowa. (ćwiczenia)
  14. Języki maszyn Turinga i typu (0). Rozstrzygalność (ćwiczenia) (test)
Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Języki,_automaty_i_obliczenia&oldid=69522”