Automaty, macierze, kody 1000-2M25AMK
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. Automaty jednoznaczne i problem mortalności.
4. Nierozstrzygalność problemu mortalności dla macierzy nad liczbami całkowitymi.
5. Podstawowe definicje teorii kodów i relacje regularnych kodów z automatami jednoznacznymi.
6. Kody synchronizujące i hipoteza Černýego.
7. Liniowe ciągi rekurencyjne: Twierdzenie Skolema-Mahlera-Lecha i NP-trudność problemu Skolema.
8. Ograniczenia na rozmiar skończonych i skończenie generowanych półgrup macierzy nad liczbami wymiernymi.
9. Wielomianowy algorytm dla rozstrzygania skończoności skończonych grup macierzy.
Kierunek podstawowy MISMaP
matematyka
Rodzaj przedmiotu
Koordynatorzy przedmiotu
Efekty kształcenia
Student umie rozpoznać granice obliczalności różnych wariantów modeli.
Student potrafi modelować różne problemy za pomocą odpowiednich automatów. Student rozumie narzędzia matematyczne wypracowane we współczesnej teorii automatów i potrafi z nich korzystać.
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: