Alfabety nieskończone 1000-2M16AN
Pierwsza część wykładu dotyczy automatów, gdzie alfabet jest nieskończony, ale wyposażony w pewną strukturę (np. porządek, albo tylko równość). Przykłady języków to “wszystkie litery są różne”, “litery są rosnące”, “pewne dwie litery są takie same”.
Druga część wykładu dotyczy bardziej abstrakcyjnej teorii, gdzie algorytmy przetwarzają obiekty nieskończone (jak np. zbiór liczb wymiernych), oczywiście pod warunkiem pewnego skończonego opisu.
Program:
1. Automaty rejestrowe
2. Algorytmy sprawdzające niepustość korzystające z well-quasi orders oraz vector addition systems
3. Zbiory skończenie orbitowe
4. Trochę teorii modeli – struktury oligomorficzne i homogeniczne
5. Algorytmy przetwarzające zbiory skończenie orbitowe
Rodzaj przedmiotu
Koordynatorzy przedmiotu
Efekty kształcenia
Znajomość teorii systemów nieskończnie stanowych oraz ich związków z teorią modeli.
Kryteria oceniania
egzamin ustny + zadania gwiazdkowe do domu
Literatura
Slightly infinite sets. Mikołaj Bojańczyk
https://www.mimuw.edu.pl/~bojan/upload/main-2.pdf
Więcej informacji
Więcej informacji o poziomie przedmiotu, roku studiów (i/lub semestrze) w którym się odbywa, o rodzaju i liczbie godzin zajęć - szukaj w planach studiów odpowiednich programów. Ten przedmiot jest związany z programami:
Dodatkowe informacje (np. o kalendarzu rejestracji, prowadzących zajęcia, lokalizacji i terminach zajęć) mogą być dostępne w serwisie USOSweb: