Uniwersytet Warszawski - Centralny System Uwierzytelniania
Strona główna

Języki, automaty i obliczenia II

Informacje ogólne

Kod przedmiotu: 1000-2M15ZTA
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: Języki, automaty i obliczenia II
Jednostka: Wydział Matematyki, Informatyki i Mechaniki
Grupy: 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 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
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
Wybrany podział planu:
Przejdź do planu
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, Lorenzo Clemente
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.
Krakowskie Przedmieście 26/28
00-927 Warszawa
tel: +48 22 55 20 000 https://uw.edu.pl/
kontakt deklaracja dostępności USOSweb 7.0.2.0-1 (2024-03-12)