Języki, automaty i obliczenia

obowiązkowe

Algorytmy i struktury danych 1000-213bASD
Matematyka dyskretna 1000-212bMD
Podstawy matematyki 1000-211bPM
Wstęp do programowania 1000-211bWPI

Podstawowe modele obliczeń (automaty, gramatyki, maszyna Turinga), związki między trudnością problemów obliczeniowych a strukturalną złożonością modeli obliczeń. Hierarchia Chomsky'ego. Matematyczny sens pojęcia obliczalności oraz jego ograniczenia, a także - w zarysie - podstawowe zagadnienia złożoności obliczeniowej.

- 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.

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.

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)

* 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.).