Alfabety nieskończone
Informacje ogólne
Kod przedmiotu: | 1000-2M16AN |
Kod Erasmus / ISCED: |
11.3
|
Nazwa przedmiotu: | Alfabety nieskończone |
Jednostka: | Wydział Matematyki, Informatyki i Mechaniki |
Grupy: |
Przedmioty obieralne dla informatyki Przedmioty obieralne na studiach drugiego stopnia na kierunku bioinformatyka |
Punkty ECTS i inne: |
6.00
|
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 |
Zajęcia w cyklu "Semestr letni 2024/25" (jeszcze nie rozpoczęty)
Okres: | 2025-02-17 - 2025-06-08 |
Przejdź do planu
PN WT ŚR CZ PT |
Typ zajęć: |
Ćwiczenia, 30 godzin
Wykład, 30 godzin
|
|
Koordynatorzy: | Mikołaj Bojańczyk | |
Prowadzący grup: | Mikołaj Bojańczyk, Michał Skrzypczak | |
Lista studentów: | (nie masz dostępu) | |
Zaliczenie: | Egzamin |
Właścicielem praw autorskich jest Uniwersytet Warszawski.