- Nazwa przedmiotu:
- Teoria automatów i języków formalnych
- Koordynator przedmiotu:
- prof. dr hab. inż. Władysław Homenda
- Status przedmiotu:
- Obowiązkowy
- Poziom kształcenia:
- Studia II stopnia
- Program:
- Matematyka
- Grupa przedmiotów:
- Wspólne
- Kod przedmiotu:
- 1120-MAMNI-NSP-0232
- Semestr nominalny:
- 1 / rok ak. 2020/2021
- 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_W10, M2MNI_W08, M2MNI_W09
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_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: