Uniwersytet Warszawski - Centralny System Uwierzytelniania
Strona główna

Automaty ważone

Informacje ogólne

Kod przedmiotu: 1000-2M22AW
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: Automaty ważone
Jednostka: Wydział Matematyki, Informatyki i Mechaniki
Grupy: Przedmioty obieralne dla informatyki
Przedmioty obieralne na studiach drugiego stopnia na kierunku bioinformatyka
Punkty ECTS i inne: (brak) 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
Kierunek podstawowy MISMaP:

informatyka

Rodzaj przedmiotu:

monograficzne

Wymagania (lista przedmiotów):

Języki, automaty i obliczenia 1000-214bJAO

Założenia (lista przedmiotów):

Złożoność obliczeniowa 1000-218bZO

Skrócony opis:

Najważniejsze twierdzenia dotyczące tematyki automatów ważonych. Przykłady zastosowań w innych dziedzinach.

Pełny opis:

1. Wprowadzenie, automaty ważone jako uogólnienie automatów skończonych, lub jako uogólnienie liniowych ciągów rekurencyjnych. Różne półpierścienie na których definiuje się takie automaty.

2. Twierdzenie Schützenbergera o rozstrzygalności równoważności nad ciałami. 3. Uczenie się automatów ważonych.

4. Automaty probabilistyczne.

5. Podklasy definiowane ze względu na ograniczenie biegów w automacie.

6. Charakteryzacja Webera i Seidla.

7. Liniowe ciągi rekurencyjne: Twierdzenie Skolema-Mahlera-Lecha i NP-trudność problemu Skolema.

6. Nierozstrzygalność większości problemów dla automatów ważonych.

7. Twierdzenie Hashiguchiego o rozstrzygalności problemu ograniczoności dla półpierścienia min-plus.

8. Rozstrzygalność problemu skończoności i elementarne ograniczenia.

9. Problem determinizacji, rozstrzygalność dla automatów jednoznacznych.

10. Nieliniowe automaty ważone.

Efekty uczenia się:

Wiedza

Student pogłębia wiedzę o klasycznych zastosowaniach teorii automatów ważonych.

Umiejętności

Student umie rozpoznać granice obliczalności różnych wariantów modeli.

Student potrafi modelować różne problemy za pomocą odpowiednich automatów.

Kompetencje

Student rozumie narzędzia matematyczne wypracowane we współczesnej teorii automatów i potrafi z nich korzystać zarówno w samej informatyce, jak i w jej zastosowaniach

Metody i kryteria oceniania:

Prace domowe i egzamin.

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.
ul. Banacha 2
02-097 Warszawa
tel: +48 22 55 44 214 https://www.mimuw.edu.pl/
kontakt deklaracja dostępności USOSweb 7.0.3.0-2b06adb1e (2024-03-27)