Przekształcenia automatowe
Informacje ogólne
Kod przedmiotu: | 1000-2M23PA |
Kod Erasmus / ISCED: |
11.3
|
Nazwa przedmiotu: | Przekształcenia automatowe |
Jednostka: | Wydział Matematyki, Informatyki i Mechaniki |
Grupy: |
Przedmioty obieralne dla informatyki |
Punkty ECTS i inne: |
6.00
|
Język prowadzenia: | angielski |
Kierunek podstawowy MISMaP: | informatyka |
Rodzaj przedmiotu: | monograficzne |
Założenia (lista przedmiotów): | Języki, automaty i obliczenia II 1000-2M15ZTA |
Tryb prowadzenia: | w sali |
Skrócony opis: |
Klasyczny model automatu skończonego czyta słowo i udziela odpowiedzi “tak” czy “nie”. Wykład dotyczy automatów o bardziej złożonych odpowiedziach, przede wszystkim takich, których odpowiedzią jest inne słowo. Oprócz kombinatoryki, teoria takich automatów czerpie również z algebry (ciała, pierścienie, półgrupy), z logiki (interpretacje), czy też programowania funkcyjnego (rachunek λ). |
Pełny opis: |
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 |
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” |
Metody i 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). |
Zajęcia w cyklu "Semestr letni 2023/24" (w trakcie)
Okres: | 2024-02-19 - 2024-06-16 |
Przejdź do planu
PN WYK
CW
WT ŚR CZ PT |
Typ zajęć: |
Ćwiczenia, 30 godzin
Wykład, 30 godzin
|
|
Koordynatorzy: | Mikołaj Bojańczyk | |
Prowadzący grup: | Mikołaj Bojańczyk, Aliaume Lopez | |
Lista studentów: | (nie masz dostępu) | |
Zaliczenie: | Egzamin | |
Uwagi: |
Egzamin ustny. Przedmiot przeznaczony również dla doktorantów. |
Właścicielem praw autorskich jest Uniwersytet Warszawski.