Drukuj Eksport do pliku (MS Word)
Nazwa przedmiotu:
Teoria automatów i języków formalnych
Koordynator przedmiotu:
dr hab. inż. Władysław Homenda, prof. PW
Status przedmiotu:
Obowiązkowy
Poziom kształcenia:
Studia II stopnia
Program:
Matematyka
Grupa przedmiotów:
Wspólne
Kod przedmiotu:
.
Semestr nominalny:
3 / rok ak. 2019/2020
Liczba punktów ECTS:
5
Liczba godzin pracy studenta związanych z osiągnięciem efektów uczenia się:
1. godziny kontaktowe – 70 h; w tym a) obecność na wykładach – 30 h b) obecność na ćwiczeniach – 30 h c) obecność na egzaminie – 5 h d) konsultacje – 5 h 2. praca własna studenta – 60 h; w tym a) przygotowanie do ćwiczeń i do kolokwiów – 30 h b) przygotowanie do wykładu – 10 b) zapoznanie się z literaturą – 5 h c) przygotowanie do egzaminu – 15 h Razem 130 h, co odpowiada 5 pkt. ECTS
Liczba punktów ECTS na zajęciach wymagających bezpośredniego udziału nauczycieli akademickich:
a) obecność na wykładach – 30 h b) obecność na ćwiczeniach – 30 h c) obecność na egzaminie – 5 h d) konsultacje – 5 h Razem 70 h, co odpowiada 3 pkt. ECTS
Język prowadzenia zajęć:
polski
Liczba punktów ECTS, którą student uzyskuje w ramach zajęć o charakterze praktycznym:
.
Formy zajęć i ich wymiar w semestrze:
  • Wykład30h
  • Ćwiczenia30h
  • Laboratorium0h
  • Projekt0h
  • Lekcje komputerowe0h
Wymagania wstępne:
1. Elementy logiki i teorii mnogości 2. Matematyka dyskretna 3. Algorytmy i podstawy programowania
Limit liczby studentów:
Bez limitu
Cel przedmiotu:
Zapoznanie studentów z podstawowymi pojęciami teorii automatów, lingwistyki matematycznej i elementami teorii rozstrzygalności
Treści kształcenia:
1. Wiadomości wstępne - przypomnienie: relacje, indukcja zupełna, języki i gramatyki. 2. Wyrażenia i języki regularne, lemat o pompowaniu, lemat Myhill-Nerode. 3. Gramatyki i języki, gramatyki i języki bezkontekstowe, lemat o pompowaniu, lemat Ogdena. 4. Gramatyki i języki kontekstowe. Gramatyki nieograniczone i języki rekurencyjnie przeliczalne. 5. Maszyny Turinga i ich odmiany, języki rekurencyjnie przeliczalne i rekurencyjne. 6. Automaty liniowo ograniczone i języki kontekstowe. 7. Automaty ze stosem i języki bezkontekstowe. 8. Automaty skończone i języki regularne, twierdzenie Myhill-Nerode. 9. Hierarchia Chomsky’ego języków, uwagi o rozstrzygalności.
Metody oceny:
ćwiczenia: prace pisemne w połowie i pod koniec semestru; wykład: egzamin pisemny dwuczęściowy z zadań i z teorii
Egzamin:
tak
Literatura:
1. Hopcroft J.E. Ullman J.D., Wprowadzenie do teorii automatów, języków i obliczeń, WNT 2. W. Homenda, Elementy lingwistyki matematycznej i teorii automatów, WPW
Witryna www przedmiotu:
brak
Uwagi:
.

Efekty uczenia się

Profil ogólnoakademicki - wiedza

Charakterystyka TAJF_W01
Zna podstawowe pojęcia teorii automatów: klasy automatów (skończone, ze stosem, maszyny Turinga), obliczenie automatu, język akceptowany, niedeterminizm automatów.
Weryfikacja: egzamin z zadań i teorii, prace pisemne w połowie i pod koniec semestru
Powiązane charakterystyki kierunkowe: M2MNI_W08, M2MNI_W09, M2MNI_W10
Powiązane charakterystyki obszarowe:
Charakterystyka TAJF_W02
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).
Weryfikacja: egzamin z zadań i teorii, prace pisemne w połowie i pod koniec semestru
Powiązane charakterystyki kierunkowe: M2MNI_W08, M2MNI_W09, M2MNI_W10
Powiązane charakterystyki obszarowe:

Profil ogólnoakademicki - umiejętności

Charakterystyka TAJF_U01
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.
Weryfikacja: egzamin z zadań i teorii, prace pisemne w połowie i pod koniec semestru
Powiązane charakterystyki kierunkowe: M2MNI_U09
Powiązane charakterystyki obszarowe:
Charakterystyka TAJF_U02
Potrafi wskazać i uzasadnić zależności między klasami automatów, gramatyk i języków.
Weryfikacja: egzamin z zadań i teorii, prace pisemne w połowie i pod koniec semestru
Powiązane charakterystyki kierunkowe: M2MNI_U09
Powiązane charakterystyki obszarowe:
Charakterystyka TAJF_U03
Potrafi stosować metody teorii automatów i lingwistyki matematycznej do opisu syntaktycznego prostych problemów i struktur wiedzy.
Weryfikacja: egzamin z zadań i teorii, prace pisemne w połowie i pod koniec semestru
Powiązane charakterystyki kierunkowe: M2MNI_U01, M2MNI_U09
Powiązane charakterystyki obszarowe:

Profil ogólnoakademicki - kompetencje społeczne

Charakterystyka TAJF_K01
Ma świadomość ograniczeń metod formalizacji syntaktycznej wiedzy, potrafi wyjaśnić różnicę złożoności między problemami i językami formalnymi odpowiednich klas oraz różnicę między językami formalnymi i naturalnymi.
Weryfikacja: egzamin z zadań i teorii, prace pisemne w połowie i pod koniec semestru
Powiązane charakterystyki kierunkowe: M2MNI_K02
Powiązane charakterystyki obszarowe: