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

Alfabety nieskończone

Informacje ogólne

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

monograficzne

Pełny opis:

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

Literatura:

Slightly infinite sets. Mikołaj Bojańczyk

https://www.mimuw.edu.pl/~bojan/upload/main-2.pdf

Efekty uczenia się:

Znajomość teorii systemów nieskończnie stanowych oraz ich związków z teorią modeli.

Metody i kryteria oceniania:

egzamin ustny + zadania gwiazdkowe do domu

Przedmiot nie jest oferowany w żadnym z aktualnych cykli dydaktycznych.
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Warszawski.