Automaty ważone 1000-2M22AW
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.
Kierunek podstawowy MISMaP
Rodzaj przedmiotu
Wymagania (lista przedmiotów)
Założenia (lista przedmiotów)
Efekty kształcenia
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
Kryteria oceniania
Prace domowe i egzamin.
Więcej informacji
Więcej informacji o poziomie przedmiotu, roku studiów (i/lub semestrze) w którym się odbywa, o rodzaju i liczbie godzin zajęć - szukaj w planach studiów odpowiednich programów. Ten przedmiot jest związany z programami:
Dodatkowe informacje (np. o kalendarzu rejestracji, prowadzących zajęcia, lokalizacji i terminach zajęć) mogą być dostępne w serwisie USOSweb: