Języki, automaty i obliczenia II
Informacje ogólne
Kod przedmiotu: | 1000-2M15ZTA |
Kod Erasmus / ISCED: |
11.3
|
Nazwa przedmiotu: | Języki, automaty i obliczenia II |
Jednostka: | Wydział Matematyki, Informatyki i Mechaniki |
Grupy: |
Przedmioty informatyczne dla doktorantów Przedmioty obieralne dla informatyki Przedmioty obieralne fakultatywne dla informatyki (IIIr. licencjatu, nowy program) Przedmioty obieralne na studiach drugiego stopnia na kierunku bioinformatyka |
Punkty ECTS i inne: |
6.00
|
Język prowadzenia: | angielski |
Rodzaj przedmiotu: | monograficzne |
Skrócony opis: |
Automaty nad słowami nieskończonymi, drzewami i innymi strukturami wejściowymi. Niestandardowe mechanizmy kontroli: automaty ważone/probabilistyczne, stratne, współbieżne, czasowe. Związki pomiędzy automatami, grami i logikami. Algorytmiczna (nie)rozstrzygalność problemów decyzyjnych. |
Pełny opis: |
• Automaty na słowach nieskończonych, algorytm determinizacji. • Gry nieskończone, determinacja skończenie-pamięciowa. • Automaty a głębokość gwiazdkowa wyrażeń regularnych. • Automaty na drzewach skończonych i nieskończonych. • Rozstrzygalność monadycznej logiki drugiego rzędu na drzewach nieskończonych. • Algorytmy na grafach o ograniczonej szerokości drzewiastej. • Automaty modelujące obliczenia współbieżne: sieci Petriego. • Maszyny stratne: rozstrzygalność przy użyciu dobrych quasi-porządków (ang. wqo). • Automaty uwzględniające upływ czasu: automaty czasowe. • Automaty probabilistyczne/ważone: rozstrzygalność problemu równoważności. • Automaty wielomianowe: rozstrzygalność problemu równoważności przy użyciu twierdzenia Hilberta o bazie. • Algorytm uczenia automatów skończonych. • Funkcje obliczalne przez automaty skończone. • Przykłady zaskakująco prostych problemów nierozstrzygalnych. Stopnie nierozstrzygalności. |
Literatura: |
• M. Bojańczyk, W.Czerwiński, An automata toolbox, https://www.mimuw.edu.pl/~bojan/paper/automata-toolbox-book, 2018. • 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. |
Efekty uczenia się: |
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 |
Metody i kryteria oceniania: |
Egzamin ustny. Dodatkowo, możliwe podwyższenie oceny dzięki rozwiązaniu zadań gwiazdkowych. Każde zadanie warte jest 1 podzielone przez liczbę studentów, którzy prawidłowo je rozwiązali. Dla doktorantów: obowiązkowe wzięcie udziału w rozwiązywaniu zadań gwiazdkowych, albo zapoznanie się z najnowszą literaturą. |
Zajęcia w cyklu "Semestr zimowy 2023/24" (zakończony)
Okres: | 2023-10-01 - 2024-01-28 |
Przejdź do planu
PN WT ŚR WYK
CZ CW
PT |
Typ zajęć: |
Ćwiczenia, 30 godzin
Wykład, 30 godzin
|
|
Koordynatorzy: | Mikołaj Bojańczyk | |
Prowadzący grup: | Mikołaj Bojańczyk, Lorenzo Clemente | |
Lista studentów: | (nie masz dostępu) | |
Zaliczenie: | Egzamin |
Zajęcia w cyklu "Semestr zimowy 2024/25" (w trakcie)
Okres: | 2024-10-01 - 2025-01-26 |
Przejdź do planu
PN CW
WT ŚR WYK
CZ CW
PT |
Typ zajęć: |
Ćwiczenia, 30 godzin
Wykład, 30 godzin
|
|
Koordynatorzy: | Mikołaj Bojańczyk | |
Prowadzący grup: | Mikołaj Bojańczyk, Lorenzo Clemente, Łukasz Kamiński | |
Lista studentów: | (nie masz dostępu) | |
Zaliczenie: | Egzamin | |
Uwagi: |
Zajęcia w grupie 2 odbywają się po angielsku. |
Właścicielem praw autorskich jest Uniwersytet Warszawski, Wydział Nauk Ekonomicznych.