Moduł oferowany także w ramach programów studiów:
Informacje ogólne:
Nazwa:
Języki Formalne i Automaty
Tok studiów:
2015/2016
Kod:
BIT-2-106-OB-s
Wydział:
Geologii, Geofizyki i Ochrony Środowiska
Poziom studiów:
Studia II stopnia
Specjalność:
Oprogramowanie i bazy danych w geologii
Kierunek:
Informatyka Stosowana
Semestr:
1
Profil kształcenia:
Ogólnoakademicki (A)
Język wykładowy:
Polski
Forma i tryb studiów:
Stacjonarne
Strona www:
 
Osoba odpowiedzialna:
dr hab. inż. Piórkowski Adam (pioro@agh.edu.pl)
Osoby prowadzące:
Krótka charakterystyka modułu

Opis efektów kształcenia dla modułu zajęć
Kod EKM Student, który zaliczył moduł zajęć wie/umie/potrafi Powiązania z EKK Sposób weryfikacji efektów kształcenia (forma zaliczeń)
Wiedza
M_W001 Student zna klasyfikację Chomsky’ego IT2A_W08 Wykonanie ćwiczeń
M_W002 Student zna definicje i podstawowe własności automatów skończonych IT2A_W08 Wykonanie ćwiczeń
M_W003 Student zna teorię wyrażeń regularnych i języków bezkontekstowych IT2A_W08 Wykonanie ćwiczeń
Umiejętności
M_U001 Student powinien umieć stosować przekształcenia i uproszczenia dla automatów skończonych oraz dla gramatyk IT2A_U07 Wykonanie ćwiczeń
Kompetencje społeczne
M_K001 Student ma kompetencje do konstrukcji gramatyk dla zadanych problemów przetwarzania danych i kompilacji IT2A_K06 Wykonanie ćwiczeń
Matryca efektów kształcenia w odniesieniu do form zajęć
Kod EKM Student, który zaliczył moduł zajęć wie/umie/potrafi Forma zajęć
Wykład
Ćwicz. aud
Ćwicz. lab
Ćw. proj.
Konw.
Zaj. sem.
Zaj. prakt
Zaj. terenowe
Zaj. warsztatowe
Inne
E-learning
Wiedza
M_W001 Student zna klasyfikację Chomsky’ego + - - - - - - - - - -
M_W002 Student zna definicje i podstawowe własności automatów skończonych + - - - - - - - - - -
M_W003 Student zna teorię wyrażeń regularnych i języków bezkontekstowych + - - - - - - - - - -
Umiejętności
M_U001 Student powinien umieć stosować przekształcenia i uproszczenia dla automatów skończonych oraz dla gramatyk - + - - - - - - - - -
Kompetencje społeczne
M_K001 Student ma kompetencje do konstrukcji gramatyk dla zadanych problemów przetwarzania danych i kompilacji - + - - - - - - - - -
Treść modułu zajęć (program wykładów i pozostałych zajęć)
Wykład:

Wprowadzenie. Niezbędne definicje. Rys historyczny. Opis formalny. Drzewa syntaktyczne. Drzewo rozbioru składniowego. Notacja BNF. Notacja Polska. Odwrotna Notacja Polska. Klasyfikacja Chomsky’ego

Automaty. Deterministyczny Automat Skończony. Niedeterministyczny Automat Skończony. Dwukierunkowy Deterministyczny Automat Skończony. Automat Moore’a. Automat Mealy’ego. Maszyna Turinga. Automaty ze stosem

Wyrażenia regularne

Transformacje automatów skończonych. Eliminacja pustych przejść. Konstrukcja automatu deterministycznego odpowiadającego automatowi niedeterministycznemu. Usuwanie stanów nieosiągalnych. Konstrukcja DAS dla NAS z pustymi przejściami. Minimalizacja deterministycznych automatów skończonych.

Gramatyki bezkontekstowe. Upraszczanie gramatyk. Usuwanie pustych produkcji. Usuwanie symboli bezużytecznych. Postać normalna Chomsky’ego. Faktoryzacja lewostronna. Redukcja bezpośredniej rekursji lewostronnej. Postać normalna Greibach. Automaty Ze Stosem dla Gramatyk Bezkontekstowych

Klasy gramatyk LL i LR. Analiza zstępująca (top-down). Analiza wstępująca (bottom-up).

Teoria Automatów a Teoria Złożoności Obliczeniowej. Klasy złożoności obliczeniowej

Ćwiczenia audytoryjne:

1.Automaty skończone i wyrażenia regularne. Deterministyczny automat skończony. Niedeterministyczny automat skończony. Wyrażenia regularne.
2. Automaty skończone i wyrażenia regularne. Wyrażenia regularne. Konstrukcja niedeterministycznych automatów skończonych. Minimalizacja automatów skończonych.
3. Gramatyki bezkontekstowe. Gramatyka bezkontekstowa. Wyprowadzenia (lewostronne, prawostronne). Język bezkontekstowy. Upraszczanie gramatyk bezkontekstowych.
4. Gramatyki bezkontekstowe. Usuwanie pustych produkcji. Usuwanie symboli bezuzytecznych. Faktoryzacja lewostronna. Postać Normalna Chomsky’ego.
5. Gramatyki bezkontekstowe. Redukcja rekursji lewostronnej. Postać Normalna Greibach.
6. Gramatyki LL, LR. Gramatyki kontekstowe.
7. Maszyna Turinga, złozonosc obliczeniowa.

E-learning:
-
Nakład pracy studenta (bilans punktów ECTS)
Forma aktywności studenta Obciążenie studenta
Sumaryczne obciążenie pracą studenta 60 godz
Punkty ECTS za moduł 2 ECTS
Udział w wykładach 15 godz
Samodzielne studiowanie tematyki zajęć 15 godz
Udział w ćwiczeniach audytoryjnych 15 godz
Przygotowanie do zajęć 15 godz
Pozostałe informacje
Sposób obliczania oceny końcowej:

Ocena końcowa = 100% oceny z ćwiczeń

Wymagania wstępne i dodatkowe:

Nie podano wymagań wstępnych lub dodatkowych.

Zalecana literatura i pomoce naukowe:

1 Hopcroft J.E., Ullman, J.D.: Wprowadzenie do teorii automatów, języków i obliczeń. Wydawnictwo Naukowe PWN, Warszawa 2003
[2 ]Forys M., Forys W.: Teoria Automatów i Języków Formalnych. Akademicka Oficyna Wydawnicza EXIT, Warszawa 2005
3 Waite W. M., Goos G.: Konstrukcja Kompilatorów. Wydawnictwa Naukowo-Techniczne, Warszawa 1989
4 Aho A. V., Sethi R., Ullman J. D.: Kompilatory – reguły, metody i narzędzia. WNT Warszawa 2002.

Publikacje naukowe osób prowadzących zajęcia związane z tematyką modułu:

Nie podano dodatkowych publikacji

Informacje dodatkowe:

Brak