Języki, automaty i obliczenia 1000-214bJAO
- Elementy teorii języków formalnych: słowa, języki, wyrażenia regularne.
- Automaty skończone i twierdzenie Kleene'go o efektywnej odpowiedniości automatów i wyrażeń.
- Konstrukcje optymalizujące automaty - determinizacja, minimalizacja.
- Języki bezkontekstowe: gramatyki i ich postaci normalne.
- Odpowiedniość gramatyk bezkontekstowych i niedeterministycznych automatów ze stosem.
- Kryteria rozróżniania języków regularnych i bezkontekstowych - lematy o - pompowaniu.
- Zagadnienia algorytmiczne: problem niepustości dla automatów i gramatyk, rozpoznawanie języków bezkontekstowych.
- Przykłady zastosowań automatów i gramatyk.
- Uniwersalne modele obliczeń: maszyna Turinga i jej warianty.
- Granice obliczalności: nierozstrzygalność problemu stopu, przykłady praktycznych problemów nierozstrzygalnych.
- Podsumowanie - klasyfikacja gramatyk, modeli obliczeń i języków według hierarchii Chomsky'ego.
- Wprowadzenie do zagadnień złożoności obliczeniowej: klasy P i NP.
- Twierdzenie Cooka-Levina o NP-zupełności SAT.
- Hipoteza P=/=NP i jej praktyczne implikacje, informacja o pozytywnych zastosowaniach problemów trudnych obliczeniowo, np. w kryptografii.
Rodzaj przedmiotu
Wymagania (lista przedmiotów)
Koordynatorzy przedmiotu
Efekty kształcenia
Wiedza - absolwent zna i rozumie:
- podstawy teorii języków formalnych (języki, wyrażenia regularne, gramatyki) i formalnych modeli obliczeniowych (automaty, automaty ze stosem, maszyny Turinga) (K_W12)
Umiejętności - absolwent potrafi:
- zastosować wiedzę matematyczną do formułowania, analizowania i rozwiązywania związanych z informatyką zadań (K_U01),
- pozyskiwać informacje z literatury, baz wiedzy, Internetu oraz innych wiarygodnych źródeł, integrować je, dokonywać ich interpretacji oraz wyciągać wnioski i formułować opinie (K_U02),
- samodzielnie planować i realizować własne uczenie się przez całe życie (K_U09),
- definiować języki formalne z pomocą gramatyk i automatów oraz operować abstrakcyjnymi modelami obliczeń ze szczególnym uwzględnieniem maszyn Turinga (K_U11),
Kompetencje społeczne - absolwent jest gotów do:
- uznawania znaczenia wiedzy w rozwiązywaniu problemów poznawczych i praktycznych oraz wyszukiwania informacji w literaturze oraz zasięgania opinii ekspertów (K_K03)
Kryteria oceniania
* 4 zadania domowe po 5 pkt każde.
* 8 testów domowych łącznie za 8 pkt.
* egzamin końcowy za ~30 pkt.
* zadania z gwiazdką pozwalające zdobyć dodatkowe punkty.
By być dopuszczonym do egzaminu w pierwszym terminie, wymagane jest przynajmniej 14 pkt (próg ten może zostać opuszczony).
By zaliczyć przedmiot w pierwszym terminie, wymagane jest przynajmniej 12 pkt z egzaminu (próg ten może zostać opuszczony).
Ostateczna ocena w pierwszym terminie to 1/10 sumy uzyskanych punktów (z zaokrągleniem w dół do 0.5).
Egzamin w drugim terminie będzie skutkował oceną ostateczną (bez wpływu uzyskanych wcześniej punktów j.w.).
Literatura
1. J. E. Hopcroft, R. Motwani, J. D. Ullman, Wprowadzenie do teorii automatów, języków i obliczeń, PWN, Warszawa 2005.
2. Ch. Papadimitriou, Złożoność obliczeniowa, WNT, Warszawa 2002.
Więcej informacji
Więcej informacji o poziomie przedmiotu, roku studiów (i/lub semestrze) w którym się odbywa, o rodzaju i liczbie godzin zajęć - szukaj w planach studiów odpowiednich programów. Ten przedmiot jest związany z programami:
Dodatkowe informacje (np. o kalendarzu rejestracji, prowadzących zajęcia, lokalizacji i terminach zajęć) mogą być dostępne w serwisie USOSweb: