Elementy teorii automatów i języków formalnych 0600-IS1-3TAJF
Profil studiów: ogólnoakademicki
Forma studiów: stacjonarne / niestacjonarne
Rodzaj przedmiotu: obowiązkowy
Dziedzina i dyscyplina nauki:Informatyka
Rok studiów / semestr: 3 / 5
Wymagania wstępne (tzw. sekwencyjny system zajęć i egzaminów): Przedmioty wprowadzające: Podstawy logiki i teorii mnogości, Algorytmy i struktury danych, Matematyka dyskretna,
Wykład: 30 Laboratorium: 30
Metody dydaktyczne: wiedza przekazywana na wykładzie, na laboratorium samodzielne rozwiązywanie problemów dotyczących treści nauczania
Punkty ECTS: 4
Bilans nakładu pracy studenta:
Udział w zajęciach:
- wykład 30h
- laboratorium 30h
Przygotowanie do zajęć:
- wykład 15h
- laboratorium 15h
Zapoznanie z literaturą: 8h
Przygotowanie do egzaminu: 15h
Czas trwania egzaminu: 4h
Udział w konsultacjach: 3h
Wskaźniki ilościowe:
wymagającymi bezpośredniego udziału nauczyciela: 65, 2ECTS
o charakterze praktycznym: 45, 2 ECTS
Rodzaj przedmiotu
Tryb prowadzenia przedmiotu
Założenia (opisowo)
Efekty kształcenia
Efekty kształcenia w ramach realizacji przedmiotu:
Zna podstawowe pojęcia teorii automatów: klasy automatów (skończone, ze stosem, maszyny Turinga), obliczenie automatu, język akceptowany. K_W14
Zna podstawowe pojęcia lingwistyki matematycznej: gramatyki i ich klasy (regularne, bezkontekstowe, kontekstowe, nieograniczone), języki formalne, hierarchia Chomsky'ego języków (regularne, bezkontekstowe, kontekstowe, rekurencyjnie przeliczalne). K_W01, K_W14
Zna podstawowe pojęcia teorii złożoności obliczeniowej: problem jako zbiór zadań, rozmiar zadania, złożoność pesymistyczna i średnia, transformacja wielomianowa, charakteryzacja klas problemów - klasy P, NP, coNP, NPC, Pspace, NPspace, zależności między tymi klasami. . K_W01, K_W14
Potrafi określić przynależność prostych języków do klas hierarchii Chomsky'ego, konstruować automaty odpowiednich klas akceptujące oraz konstruować gramatyki odpowiednich klas generujące proste języki z klas tej hierarchii. . K_U05, K_U16, K_U24, K_U26
Potrafi wskazać zależności między klasami automatów, gramatyk i języków. . K_U05, K_U24, K_U26
Ma świadomość ograniczeń teoretycznych i praktycznych metod obliczeniowych. Potrafi w sposób zrozumiały dla osób nieposiadających wykształcenia w tej dziedzinie wyjaśnić jakościową różnicę złożoności obliczeniowej między klasami problemów (klasy problemów rozstrzygalnych, częściowo rozstrzygalnych, komplementarnych, nierozstrzygalnych), a także ilościową różnicę złożoności obliczeniowej między podklasami klasy problemów rozstrzygalnych (klasy P, NP, coNP, NPC). K_K02, K_K03
Kryteria oceniania
Ogólna forma zaliczenia:egzamin
Literatura
Literatura podstawowa:
Hopocroft J.E., Ullman J. D., Wprowadzenie do teorii automatów, języków i obliczeń, Wydawnictwo Naukowe PWN
Homenda W., Elementy teorii automatów i lingwistyki matematycznej, Oficyna Wydawnicza Politechniki Warszawskiej, 2004
Literatura uzupełniająca:
Więcej informacji
Dodatkowe informacje (np. o kalendarzu rejestracji, prowadzących zajęcia, lokalizacji i terminach zajęć) mogą być dostępne w serwisie USOSweb: