Automaty ważone
Informacje ogólne
Kod przedmiotu: | 1000-2M22AW |
Kod Erasmus / ISCED: |
11.3
|
Nazwa przedmiotu: | Automaty ważone |
Jednostka: | Wydział Matematyki, Informatyki i Mechaniki |
Grupy: |
Przedmioty obieralne dla informatyki Przedmioty obieralne na studiach drugiego stopnia na kierunku bioinformatyka |
Punkty ECTS i inne: |
(brak)
|
Język prowadzenia: | angielski |
Kierunek podstawowy MISMaP: | informatyka |
Rodzaj przedmiotu: | monograficzne |
Wymagania (lista przedmiotów): | Języki, automaty i obliczenia 1000-214bJAO |
Założenia (lista przedmiotów): | Złożoność obliczeniowa 1000-218bZO |
Skrócony opis: |
Najważniejsze twierdzenia dotyczące tematyki automatów ważonych. Przykłady zastosowań w innych dziedzinach. |
Pełny opis: |
1. Wprowadzenie, automaty ważone jako uogólnienie automatów skończonych, lub jako uogólnienie liniowych ciągów rekurencyjnych. Różne półpierścienie na których definiuje się takie automaty. 2. Twierdzenie Schützenbergera o rozstrzygalności równoważności nad ciałami. 3. Uczenie się automatów ważonych. 4. Automaty probabilistyczne. 5. Podklasy definiowane ze względu na ograniczenie biegów w automacie. 6. Charakteryzacja Webera i Seidla. 7. Liniowe ciągi rekurencyjne: Twierdzenie Skolema-Mahlera-Lecha i NP-trudność problemu Skolema. 6. Nierozstrzygalność większości problemów dla automatów ważonych. 7. Twierdzenie Hashiguchiego o rozstrzygalności problemu ograniczoności dla półpierścienia min-plus. 8. Rozstrzygalność problemu skończoności i elementarne ograniczenia. 9. Problem determinizacji, rozstrzygalność dla automatów jednoznacznych. 10. Nieliniowe automaty ważone. |
Efekty uczenia się: |
Wiedza Student pogłębia wiedzę o klasycznych zastosowaniach teorii automatów ważonych. Umiejętności Student umie rozpoznać granice obliczalności różnych wariantów modeli. Student potrafi modelować różne problemy za pomocą odpowiednich automatów. Kompetencje Student rozumie narzędzia matematyczne wypracowane we współczesnej teorii automatów i potrafi z nich korzystać zarówno w samej informatyce, jak i w jej zastosowaniach |
Metody i kryteria oceniania: |
Prace domowe i egzamin. |
Właścicielem praw autorskich jest Uniwersytet Warszawski.