Uniwersytet Warszawski - Centralny System Uwierzytelniania

Alfabety nieskończone

Informacje ogólne

Kod przedmiotu:	1000-2M16AN
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:	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 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
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	Wybrany podział planu: tygodniowy cykl przedmiotu Przejdź do planu PN WT ŚR CZ PT
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, Michał Skrzypczak
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.