Moduł oferowany także w ramach programów studiów:
Informacje ogólne:
Nazwa:
Teoria automatów i języków formalnych
Tok studiów:
2014/2015
Kod:
IIN-1-406-s
Wydział:
Informatyki, Elektroniki i Telekomunikacji
Poziom studiów:
Studia I stopnia
Specjalność:
-
Kierunek:
Informatyka
Semestr:
4
Profil kształcenia:
Ogólnoakademicki (A)
Język wykładowy:
Polski
Forma i tryb studiów:
Stacjonarne
Osoba odpowiedzialna:
Majewski Janusz (majew@agh.edu.pl)
Osoby prowadzące:
Kuta Marcin (mkuta@agh.edu.pl)
Majewski Janusz (majew@agh.edu.pl)
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 Zna i rozumie podstawy teoretyczne konstrukcji i opisu języków formalnych, w szczególności języków programowania IN1A_W05, IN1A_W04 Egzamin
M_W002 Zna i rozumie podstawy teoretyczne budowy translatorów języków programowania IN1A_W04 Egzamin
M_W003 Zna i rozumie podstawowe problemy lingwistyki matematycznej w zakresie objętym i nieobjętym hierarchią Chomsky’ego IN1A_W04 Egzamin
Umiejętności
M_U001 Potrafi integrować i wykorzystywać uzyskaną wiedzę teoretyczną dotyczącą sposobu opisu języków formalnych i operowania automatami abstrakcyjnymi do rozwiązywania zadań. IN1A_U01 Kolokwium
Kompetencje społeczne
M_K001 Rozumie potrzebę uczenia się IN1A_K01 Egzamin
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 Zna i rozumie podstawy teoretyczne konstrukcji i opisu języków formalnych, w szczególności języków programowania + - - - - - - - - - -
M_W002 Zna i rozumie podstawy teoretyczne budowy translatorów języków programowania + - - - - - - - - - -
M_W003 Zna i rozumie podstawowe problemy lingwistyki matematycznej w zakresie objętym i nieobjętym hierarchią Chomsky’ego + - - - - - - - - - -
Umiejętności
M_U001 Potrafi integrować i wykorzystywać uzyskaną wiedzę teoretyczną dotyczącą sposobu opisu języków formalnych i operowania automatami abstrakcyjnymi do rozwiązywania zadań. - + - - - - - - - - -
Kompetencje społeczne
M_K001 Rozumie potrzebę uczenia się + - - - - - - - - - -
Treść modułu zajęć (program wykładów i pozostałych zajęć)
Wykład:
  1. Podstawowe pojęcia (4 godz.)

    Język naturalny a język formalny. Symbol, alfabet, łańcuch, zbiór łańcuchów. Operacje na łańcuchach i zbiorach łańcuchów. Definiowanie języka formalnego. Gramatyka i automat. Operacje na językach. Wyprowadzenie łańcucha w gramatyce. Klasyfikacja Chomsky’ego.

  2. Języki i gramatyki bezkontekstowe (3 godz.)

    Gramatyka bezkontekstowa, jednoznaczność gramatyki. Języki ściśle wieloznaczne. Przekształcenia gramatyk bezkontekstowych, algorytmy decyzyjne. Rozbiór gramatyczny. Metoda generacyjna (top-down) i redukcyjna (bottom-up).

  3. Automat ze stosem (4 godz.)

    Niedeterministyczny i deterministyczny automat ze stosem. Automat ze stosem a gramatyka bezkontekstowa. Od gramatyki bezkontekstowej do automatu ze stosem.

  4. Własności języków bezkontekstowych, problem parsingu (4 godz.)

    Postaci normalne gramatyk bezkontekstowych. Lematy o rozrastaniu. Własności zamkniętości języków bezkontekstowych. Technologie parsingu. Algorytm Cocke’a-Youngera-Kasamiego. Deterministyczne języki bezkontekstowe.

  5. Języki i gramatyki regularne, automaty skończone (6 godz.)

    Wyrażenia regularne, języki regularne. Deterministyczny (DFA) i niederministyczny (NFA) automat skończony. Gramatyka regularna. Od wyrażenia regularnego do DFA. Twierdzenie Myhilla-Nerode’a. Minimalizacja automatu skończonego. Automaty Moore’a i Mealy’ego.

  6. Własności języków regularnych (4 godz.)

    Od DFA do wyrażenia regularnego i gramatyki regularnej. Lemat o rozrastaniu. Własności zamkniętości języków regularnych.

  7. Języki kontekstowe i rekurencyjnie przeliczalne, maszyna Turinga, języki spoza hierarchii Chomsky’ego (5 godz.)

    Języki kontekstowe i automaty liniowo-ograniczone. Deterministyczne i niedeterministyczne maszyny Turinga. Języki rekurencyjne i rekurencyjnie przeliczalne. Problemy nierozstrzygalne. Języki nie będące rekurencyjnie przeliczalnymi.

Ćwiczenia audytoryjne:

Treści tych zajęć ugruntowują i rozszerzają wiedzę przekazywaną podczas wykładów. Rozwiązywane są zadania, dowodzone są niektóre rezultaty teoretyczne. Szczególną uwagę zwraca się na zagadnienia teoretyczne rozwiązywane z wykorzystaniem podejścia algorytmicznego, jak np. algorytmy decyzyjne dla języków bezkontekstowych i regularnych, dowodzenie w oparciu o lematy o pompowaniu, przekształcenia gramatyk, automatów i wyrażeń regularnych, klasyfikowanie gramatyk i języków z wykorzystaniem hierarchii Chomsky’ego, projektowanie gramatyk i automatów dla zadanych języków formalnych.

  1. Gramatyki wyrażeń, jednoznaczność gramatyk (2 godz.)
  2. Domknięcia relacji, wyprowadzenia w gramatyce, przekształcenia języków (2 godz.)
  3. Gramatyki bezkontekstowe, frazy, przekształcenia gramatyk bezkontekstowych (2 godz.)
  4. Automat ze stosem, postaci normalne gramatyk bezkontekstowych, lematy o rozrastaniu, własności języków bezkontekstowych (2 godz.)
  5. Wyrażenia regularne, automaty skończone (2 godz.)
  6. Przekształcenia automatów skończonych (2 godz.)
  7. Własności języków regularnych, lemat o rozrastaniu (2 godz.)
  8. Powtórzenie i sprawdzenie wiadomości (1 godz.)

Nakład pracy studenta (bilans punktów ECTS)
Forma aktywności studenta Obciążenie studenta
Sumaryczne obciążenie pracą studenta 75 godz
Punkty ECTS za moduł 3 ECTS
Udział w wykładach 28 godz
Udział w ćwiczeniach audytoryjnych 14 godz
Samodzielne studiowanie tematyki zajęć 23 godz
Przygotowanie do zajęć 10 godz
Pozostałe informacje
Sposób obliczania oceny końcowej:
  1. Aby uzyskać pozytywną ocenę końcową niezbędne jest uzyskanie pozytywnej oceny z ćwiczeń oraz egzaminu.
  2. Obliczamy średnią arytmetyczną z ocen zaliczenia i egzaminów uzyskanych we wszystkich terminach.
  3. Wyznaczmy ocenę końcową na podstawie zależności:
    if sr>4.75 then OK:=5.0 else
    if sr>4.25 then OK:=4.5 else
    if sr>3.75 then OK:=4.0 else
    if sr>3.25 then OK:=3.5 else OK:=3
  4. Jeżeli pozytywną ocenę z ćwiczeń i egzaminu uzyskano w pierwszym terminie oraz ocena końcowa jest mniejsza niż 5.0 to ocena końcowa jest podnoszona o 0.5
Wymagania wstępne i dodatkowe:

Matematyka dyskretna w zakresie nauczanym na pierwszym roku studiów (teoria mnogości, relacje, grafy)

Zalecana literatura i pomoce naukowe:
  1. Aho A. V., Sethi R., Ullman J. D.: Kompilatory. Reguły, metody i narzędzia, WNT, 2002
  2. Homenda W.: Elementy lingwistyki matematycznej i teorii automatów, Oficyna Wydawnicza Politechniki Warszawskiej, 2005
  3. Hopcroft J. E., Motwani R., Ullman J. D.: Wprowadzenie do teorii automatów, języków i obliczeń, PWN, 2005
  4. Ross K. A., Wright C. R. B.: Matematyka dyskretna, PWN, 1996
  5. Sipser M.: Wprowadzenie do teorii obliczeń, WNT, 2009
  6. http://kompilatory.agh.edu.pl
Publikacje naukowe osób prowadzących zajęcia związane z tematyką modułu:

Nie podano dodatkowych publikacji

Informacje dodatkowe:

Brak