Drukuj Eksport do pliku (MS Word)
Nazwa przedmiotu:
Teoria automatów i języków
Koordynator przedmiotu:
Dr hab. Władysław Homenda
Status przedmiotu:
Obowiązkowy
Poziom kształcenia:
Studia I stopnia
Program:
Informatyka
Grupa przedmiotów:
Wspólne
Kod przedmiotu:
Semestr nominalny:
5 / rok ak. 2012/2013
Liczba punktów ECTS:
4
Liczba godzin pracy studenta związanych z osiągnięciem efektów uczenia się:
1. godziny kontaktowe - 65 h; w tym a. obecność na wykładach – 30 h b. obecność na ćwiczeniach – 30 h c. konsultacje – 5 h 2. przygotowanie do zajęć – 60 h, w tym a. przygotowanie do wykładów – 15 h b. przygotowanie do ćwiczeń – 30 h c. dodatkowo przygotowanie do sprawdzianów pisemnych i egzaminu – 10 h d. egzamin 5 h Razem nakład pracy studenta 125 h = 4 pkt. 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. obecność na egzaminach – 5 h 4. konsultacje z prowadzącymi zajęcia – 5 h Razem 30+30+5+5 = 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:
1. obecność na ćwiczeniach – 30 h 2. przygotowanie do ćwiczeń – 30 h 3. przygotowanie do sprawdzianów pisemnych i egzaminu – 10 h Razem 30+30+10= 70 h, co odpowiada 3 pkt. ECTS
Formy zajęć i ich wymiar w semestrze:
  • Wykład30h
  • Ćwiczenia30h
  • Laboratorium0h
  • Projekt0h
  • Lekcje komputerowe0h
Wymagania wstępne:
Algebra, Wstęp do logiki i teorii mnogości
Limit liczby studentów:
Bez limitu
Cel przedmiotu:
Celem przedmiotu jest przekazanie wiedzy z podstaw teorii automatów i języków formalnych. Po ukończeniu kursu studenci powinni wiedzę i umiejętności sformułowane w tabeli efektów kształcenia.
Treści kształcenia:
Wykład: Wiadomości wstępne - przypomnienie: relacje, indukcja zupełna. Wyrażenia i języki regularne, lemat o pompowaniu, lemat Myhill-Nerode. Gramatyki i języki, gramatyki i języki bezkontekstowe, lemat o pompowaniu, lemat Ogdena. Gramatyki i języki kontekstowe. Gramatyki nieograniczone i języki rekurencyjnie przeliczalne. Maszyny Turinga i ich odmiany, języki rekurencyjnie przeliczalne i rekurencyjne. Automaty liniowo ograniczone i języki kontekstowe. Automaty ze stosem i języki bezkontekstowe. Automaty skończone i języki regularne, twierdzenie Myhill-Nerode. Hierarchia Chomsky’ego języków . Uwagi o rozstrzygalności.   Ćwiczenia: Rozwiązywanie problemów lingwistyki matematycznej i teorii automatów.
Metody oceny:
- 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.      Łączną ocenę punktową przelicza się na stopnie według poniższych zasad: b)  3.5 jeżeli uzyskali od 61 do 70  pkt. c)  4.0 jeżeli uzyskali od 71 do 80  pkt. d)  4.5 jeżeli uzyskali  od 81 do 90  pkt. e)  5.0 jeżeli uzyskali powyżej 90  pkt.
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 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: aktywny udział w ćwiczeniach, sprawdzian pisemny, egzamin ustny
Powiązane efekty kierunkowe: K_W04, K_W07, K_W10, K_W12
Powiązane efekty obszarowe: T1A_W03, T1A_W03, T1A_W07, T1A_W07
Efekt 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: aktywny udział w ćwiczeniach, sprawdzian pisemny, egzamin ustny
Powiązane efekty kierunkowe: K_W04, K_W07, K_W10, K_W12
Powiązane efekty obszarowe: T1A_W03, T1A_W03, T1A_W07, T1A_W07

Profil ogólnoakademicki - umiejętności

Efekt 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: aktywny udział w ćwiczeniach, sprawdzian pisemny, egzamin pisemny
Powiązane efekty kierunkowe: K_U01, K_U04, K_U09, K_U14, K_U23
Powiązane efekty obszarowe: T1A_U09, T1A_U09, T1A_U09, T1A_U09, T1A_U15, T1A_U09, T1A_U16
Efekt U02
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: K_U01, K_U04, K_U09, K_U14, K_U23
Powiązane efekty obszarowe: T1A_U09, T1A_U09, T1A_U09, T1A_U09, T1A_U15, T1A_U09, T1A_U16
Efekt U03
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: K_U01, K_U04, K_U09, K_U14, K_U23
Powiązane efekty obszarowe: T1A_U09, T1A_U09, T1A_U09, T1A_U09, T1A_U15, T1A_U09, T1A_U16

Profil ogólnoakademicki - kompetencje społeczne

Efekt 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: udział w dyskusji,
Powiązane efekty kierunkowe: K_K01, K_K02, K_K04, K_K07
Powiązane efekty obszarowe: T1A_K01, T1A_K01, T1A_K02, T1A_K05, T1A_K07