Uniwersytet Warszawski - Centralny System UwierzytelnianiaNie jesteś zalogowany | zaloguj się
katalog przedmiotów - pomoc

Języki, automaty i obliczenia II

Informacje ogólne

Kod przedmiotu: 1000-2M15ZTA Kod Erasmus / ISCED: 11.3 / (0612) Database and network design and administration
Nazwa przedmiotu: Języki, automaty i obliczenia II
Jednostka: Wydział Matematyki, Informatyki i Mechaniki
Grupy: Przedmioty monograficzne dla III - V roku informatyki
Przedmioty obieralne dla informatyki
Punkty ECTS i inne: 6.00
zobacz reguły punktacji
Język prowadzenia: angielski
Rodzaj przedmiotu:

monograficzne

Skrócony opis:

Automaty nad obiektami wejściowymi innymi niż słowa skończone, jak drzewa lub nieskończone słowa.

Niestandardowe mechanizmy kontroli: automaty probabilistyczne, stratne, współbieżne.

Zagadnienie algorytmicznej nierozstrzygalności.

Pełny opis:

• Koszt tłumaczenia pomiędzy różnymi reprezentacjami języków regularnych.

• Automaty Büchiego na słowach nieskończonych. Twierdzenie McNaughtona i algorytm determinizacji z wykorzystaniem automatów parzystości.

• Automaty na drzewach skończonych.

• Automaty probabilistyczne. Rozstrzygalność problemu równoważności i nierozstrzygalność problemu akceptacji słowa z zadanym prawdopodobieństwem błędu.

• Automaty realizujące obliczenia współbieżne, sieci Petriego.

• Transduktory.

• Nierozstrzygalność algorytmiczna. Przykłady zaskakująco prostych problemów nierozstrzygalnych.

• Stopnie nierozstrzygalności i Twierdzenie Friedberga-Mucznika.

Literatura:

• J. E. Hopcroft, R. Motwani, J. D. Ullman, Wprowadzenie do teorii automatów, języków i obliczeń, PWN, Warszawa 2005.

• Ch. Papadimitriou, Złożoność obliczeniowa, WNT, Warszawa 2002.

• Dominique Perrin i Jean-Eric Pin, Infinite words, Elsevier 2004.

Efekty kształcenia:

Wiedza

Student pogłębia wiedzę o klasycznych zagadnieniach obliczalności i poznaje kilka gałęzi współczesnej zaawansowanej teorii automatów.

Umiejętności

Student potrafi przechodzić pomiędzy różnymi reprezentacjami języków regularnych ze świadomością ograniczeń złożonościowych.

Student potrafi modelować proste własności systemów informatycznych za pomocą automatów, dobierając odpowiedni typ i mechanizm kontroli.

Student nabywa wprawy w rozpoznawaniu problemów nierozstrzygalnych i potrafi konstruować odpowiednie redukcje.

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

Zajęcia w cyklu "Semestr zimowy 2018/19" (zakończony)

Okres: 2018-10-01 - 2019-01-25
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Wojciech Czerwiński
Prowadzący grup: Wojciech Czerwiński, Janusz Schmude
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin

Zajęcia w cyklu "Semestr zimowy 2019/20" (w trakcie)

Okres: 2019-10-01 - 2020-01-27
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Wojciech Czerwiński
Prowadzący grup: Wojciech Czerwiński, Janusz Schmude, Rafał Stefański
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Warszawski.