Drukuj Eksport do pliku (MS Word)
Nazwa przedmiotu:
Teoria automatów i lingwistyka matematyczna
Koordynator przedmiotu:
dr hab. Władysław Homenda
Status przedmiotu:
Obowiązkowy
Poziom kształcenia:
Studia II stopnia
Program:
Matematyka
Grupa przedmiotów:
Wspólne
Kod przedmiotu:
M2TAL
Semestr nominalny:
1 / rok ak. 2013/2014
Liczba punktów ECTS:
6
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. konsultacje – 5 h d. egzamin 5 h 2. przygotowanie do zajęć – 85 h, w tym a. przygotowanie do wykładów – 30 h b. przygotowanie do ćwiczeń – 30 h c. dodatkowo przygotowanie do spraw-dzianów pisemnych i egzaminu – 25 h Razem: 155 h, 5 ECTS
Liczba punktów ECTS na zajęciach wymagających bezpośredniego udziału nauczycieli akademickich:
1. obecność na wykładach – 30 h 2. obecność na ćwiczeniach – 30 h 3. konsultacje z prowadzącymi zajęcia – 5 h 4. obecność na egzaminach – 5 h Razem: 70 h, 3 ECTS
Język prowadzenia zajęć:
polski
Liczba punktów ECTS, którą student uzyskuje w ramach zajęć o charakterze praktycznym:
1. obecność na ćwiczeniach – 30 h 2. przygotowanie do ćwiczeń – 30 h 3. przygotowanie do sprawdzianów pisemnych i egzaminu – 15 h Razem: 75 h, 3 ECTS
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:
Zasady zaliczania: - dopuszczenie do egzaminu wymaga zaliczenia dwóch prac pisemnych (w listopadzie i styczniu) lub – w przypadku niezaliczenia którejkolwiek – zaliczenia części pisemnej egzaminu. Dopuszczenie do egzaminu powinno być uzyskane w bieżącym roku akademickim, - egzamin składa się z dwóch części: pisemnej i ustnej. Niezaliczenie lub nieprzystąpienie do którejkolwiek wymaga ponownego przystąpienia do obu części. Student ma prawo do jednego egzaminu poprawkowego.  
Egzamin:
tak
Literatura:
Hopcroft J.E. Ullman J.D., Wprowadzenie do teorii automatów, języków i obliczeń, WNT W. Homenda, Elementy lingwistyki matematycznej i teorii automatów, WPW
Witryna www przedmiotu:
brak
Uwagi:

Efekty uczenia się

Profil ogólnoakademicki - wiedza

Efekt TAL_W_01
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: aktywny udział w ćwiczeniach, sprawdzian pisemny, egzamin ustny
Powiązane efekty kierunkowe: MNI_W12, MNI_W13, MNI_W14
Powiązane efekty obszarowe: X2A_W01, X2A_W01, X2A_W01, X2A_W04
Efekt TAL_W_02
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: aktywny udział w ćwiczeniach, sprawdzian pisemny, egzamin ustny
Powiązane efekty kierunkowe: MNI_W12, MNI_W13, MNI_W14
Powiązane efekty obszarowe: X2A_W01, X2A_W01, X2A_W01, X2A_W04

Profil ogólnoakademicki - umiejętności

Efekt TAL_U_01
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: aktywny udział w ćwiczeniach, sprawdzian pisemny, egzamin pisemny
Powiązane efekty kierunkowe: MNI_U01
Powiązane efekty obszarowe: X2A_U08, X2A_U09, X2A_U06
Efekt TAL_U_02
Potrafi wskazać i uzasadnić zależności między klasami automatów, gramatyk i języków.
Weryfikacja: aktywny udział w ćwiczeniach, sprawdzian pisemny, egzamin pisemny
Powiązane efekty kierunkowe: MNI_U20
Powiązane efekty obszarowe: X2A_U08, X2A_U09, X2A_U06, X2A_U07
Efekt TAL_U_03
Potrafi stosować metody teorii automatów i lingwistyki matematycznej do opisu syntaktycznego prostych problemów i struktur wiedzy.
Weryfikacja: aktywny udział w ćwiczeniach, sprawdzian pisemny, egzamin pisemny
Powiązane efekty kierunkowe: MNI_U01, MNI_U20
Powiązane efekty obszarowe: X2A_U08, X2A_U09, X2A_U06, X2A_U08, X2A_U09, X2A_U06, X2A_U07

Profil ogólnoakademicki - kompetencje społeczne

Efekt TAL_K_01
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: udział w dyskusji, egzamin ustny
Powiązane efekty kierunkowe: MNI_K03
Powiązane efekty obszarowe: X2A_K01, X2A_K05