Przekształcenia automatowe 1000-2M23PA
1. Maszyny Mealy’ego oraz twierdzenie Krohna-Rhodesa o ich rozkładzie
2. Funkcje wymierne na słowach
3. Automaty ważone, szczególnie nad ciałami.
4. Automaty wielomianowe oraz metoda Hilberta.
5. Funkcje regularne liniowe, w tym: automaty dwukierunkowe, logika monadyczna, automaty rejestrowe, rachunek kombinatorów, rozkład Krohna-Rhodesa
6. Funkcje regularne wielomianowe, w tym: automaty kamykowe, logika monadyczna, programy for, rachunek lambda
7. Rozstrzyganie f=g, czyli problem równoważności
8. Przekształcenia drzew
9. Przekształcenia grafów
Kierunek podstawowy MISMaP
matematyka
Rodzaj przedmiotu
Tryb prowadzenia
Założenia (lista przedmiotów)
Koordynatorzy przedmiotu
Kryteria oceniania
Wiedza:
* Student ma opanowaną wiedzę na temat teorii funkcji opisywanych przez automatów, a szczególnie funkcji ze słów do słów, oraz poznaje ich związki z logicznymi podstawami informatyki (K_W01).
Umiejętności
* Student potrafi stosować modele matematyczne przekształceń i rozpoznawać, które programy komputerowa takimi modelami się opisują (K_U01, K_U05).
Literatura
Podstawowym materiałem będą interaktywne slajdy przygotowane podczas trwania przedmiotu.
Literatura uzupełniająca:
1. Bojańczyk, Czerwiński “Automata Toolbox”
2. Sakharovitch “Elements of Automata Theory”
Uwagi
|
W cyklu 2023L:
Egzamin ustny. Przedmiot przeznaczony również dla doktorantów. |
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: