Uniwersytet Warszawski - Centralny System Uwierzytelniania

Przekształcenia automatowe

Informacje ogólne

Kod przedmiotu:	1000-2M23PA
Kod Erasmus / ISCED:	11.3 Kod klasyfikacyjny przedmiotu składa się z trzech do pięciu cyfr, przy czym trzy pierwsze oznaczają klasyfikację dziedziny wg. Listy kodów dziedzin obowiązującej w programie Socrates/Erasmus, czwarta (dotąd na ogół 0) – ewentualne uszczegółowienie informacji o dyscyplinie, piąta – stopień zaawansowania przedmiotu ustalony na podstawie roku studiów, dla którego przedmiot jest przeznaczony. / (0612) Database and network design and administration Kod ISCED - Międzynarodowa Standardowa Klasyfikacja Kształcenia (International Standard Classification of Education) została opracowana przez UNESCO.
Nazwa przedmiotu:	Przekształcenia automatowe
Jednostka:	Wydział Matematyki, Informatyki i Mechaniki
Grupy:	Przedmioty obieralne dla informatyki
Punkty ECTS i inne:	6.00 Podstawowe informacje o zasadach przyporządkowania punktów ECTS: roczny wymiar godzinowy nakładu pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się dla danego etapu studiów wynosi 1500-1800 h, co odpowiada 60 ECTS; tygodniowy wymiar godzinowy nakładu pracy studenta wynosi 45 h; 1 punkt ECTS odpowiada 25-30 godzinom pracy studenta potrzebnej do osiągnięcia zakładanych efektów uczenia się; tygodniowy nakład pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się pozwala uzyskać 1,5 ECTS; nakład pracy potrzebny do zaliczenia przedmiotu, któremu przypisano 3 ECTS, stanowi 10% semestralnego obciążenia studenta. zobacz reguły punktacji
Język prowadzenia:	angielski
Kierunek podstawowy MISMaP:	informatyka matematyka
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	Wybrany podział planu: tygodniowy cykl przedmiotu Przejdź do planu PN WYK CW WT ŚR CZ PT
Typ zajęć:	Ćwiczenia, 30 godzin więcej informacji Wykład, 30 godzin więcej informacji
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.

Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Warszawski.