Serwisy internetowe Uniwersytetu Warszawskiego | USOSownia - uniwersyteckie forum USOSoweNie 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: 6.00
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 kształcenia:

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

Zajęcia w cyklu "Semestr zimowy 2018/19" (w trakcie)

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: Mikołaj Bojańczyk
Prowadzący grup: Mikołaj Bojańczyk
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.