- Nazwa przedmiotu:
- Teoria automatów i języków formalnych
- Koordynator przedmiotu:
- Prof. nzw. dr hab. inż. Władysław Homenda
- Status przedmiotu:
- Obowiązkowy
- Poziom kształcenia:
- Studia I stopnia
- Program:
- Informatyka i Systemy Informacyjne
- Grupa przedmiotów:
- Wspólne
- Kod przedmiotu:
- 1120-IN000-ISP-0355
- Semestr nominalny:
- 5 / rok ak. 2019/2020
- Liczba punktów ECTS:
- 4
- 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 – 15 h
c) obecność na laboratoriach – 15 h
d) konsultacje – 5 h
e) egzamin – 5 h
2. praca własna studenta – 55 h, w tym
a) przygotowanie do wykładów – 15 h
b) przygotowanie do ćwiczeń i zajęć laboratoryjnych – 30 h
c) dodatkowo przygotowanie do sprawdzianów pisemnych i egzaminu – 10 h
Razem 125 h, co odpowiada 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 – 15 h
3. obecność na laboratoriach – 15 h
4. obecność na egzaminach – 5 h
5. konsultacje z prowadzącymi zajęcia – 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:
- 1. obecność na ćwiczeniach – 15 h
2. obecność na laboratoriach – 15 h
3. przygotowanie do ćwiczeń i zajęć laboratoryjnych – 30 h
4. przygotowanie do sprawdzianów pisemnych i egzaminu – 10 h
Razem 70 h, co odpowiada 3 pkt. ECTS
- Formy zajęć i ich wymiar w semestrze:
-
- Wykład30h
- Ćwiczenia15h
- Laboratorium15h
- Projekt0h
- Lekcje komputerowe0h
- Wymagania wstępne:
- Algebra liniowa z geometrią
Elementy logiki i teorii mnogości
- Limit liczby studentów:
- Ćwiczenia – 30 os/grupa, Laboratoria (ćwiczenia komputerowe) – 15-24 os/grupa
- 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, laboratoria:
Rozwiązywanie problemów lingwistyki matematycznej i teorii automatów.
- Metody oceny:
- Zaliczenie przedmiotu wymaga uzyskania zaliczenia części praktycznej i części teoretycznej, zaliczenie obu części musi być uzyskane w bieżącym roku akademickim.
Zaliczenie części praktycznej można uzyskać:
a) na ćwiczeniach przez zaliczenie dwóch prac pisemnych, jednej w połowie semestru, drugiej pod koniec semestru,
b) w terminie poprawkowym, którym jest pierwszy termin egzaminu.
Do zaliczenia części teoretycznej można przystąpić po wcześniejszym zaliczeniu części praktycznej, zaliczenie części teoretycznej uzyskuje się przystępując do egzaminu (dwa terminy w sesji zimowej, jeden termin w sesji jesiennej).
Ocena z części teoretycznej jest oceną z pierwszej próby lub ndst i ocena z drugiej próby (wpisana ocena niedostateczna z pierwszej próby i ocena z drugiej próby) lub ndst, ndst i ocena według formuły max(2,floor(o3)-1), gdzie o3 jest oceną z trzeciej próby.
Końcowa ocena jest średnią ocen z części praktycznej i teoretycznej.
Sprawdziany są organizowane według reguł przygotowanych przez dziekanat (procedura przeprowadzania sprawdzianów). Ponadto: na sprawdzianach części praktycznej można mieć własnoręcznie zapisaną kartkę formatu A5, na sprawdzianach części teoretycznej nie można korzystać z żadnych pomocy.
- 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:
- e.mini.pw.edu.pl
- Uwagi:
Efekty uczenia się
Profil ogólnoakademicki - wiedza
- Charakterystyka 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 charakterystyki kierunkowe:
K_W04, K_W07, K_W10, K_W12
Powiązane charakterystyki obszarowe:
- Charakterystyka 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 charakterystyki kierunkowe:
K_W04, K_W07, K_W10, K_W12
Powiązane charakterystyki obszarowe:
Profil ogólnoakademicki - umiejętności
- Charakterystyka 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 i laboratoriach, sprawdzian pisemny, egzamin pisemny
Powiązane charakterystyki kierunkowe:
K_U01, K_U04, K_U09, K_U14, K_U23
Powiązane charakterystyki obszarowe:
- Charakterystyka U02
- Potrafi wskazać i uzasadnić zależności między klasami automatów, gramatyk i języków.
Weryfikacja: aktywny udział w ćwiczeniach i laboratoriach, sprawdzian pisemny, egzamin pisemny
Powiązane charakterystyki kierunkowe:
K_U01, K_U04, K_U09, K_U14, K_U23
Powiązane charakterystyki obszarowe:
- Charakterystyka U03
- Potrafi stosować metody teorii automatów i lingwistyki matematycznej do opisu syntaktycznego prostych problemów i struktur wiedzy.
Weryfikacja: aktywny udział w ćwiczeniach i laboratoriach, sprawdzian pisemny, egzamin pisemny
Powiązane charakterystyki kierunkowe:
K_U01, K_U04, K_U09, K_U14, K_U23
Powiązane charakterystyki obszarowe:
Profil ogólnoakademicki - kompetencje społeczne
- Charakterystyka K01
- Ma świadomość ograniczeń metod formalizacji syntaktycznej wiedzy, potrafi wyjaśnić różnicę złożoności między problemami i językami formalnymi odpowied-nich klas oraz różnicę między językami formalnymi i naturalnymi.
Weryfikacja: udział w dyskusji
Powiązane charakterystyki kierunkowe:
K_K02, K_K04, K_K07, K_K01
Powiązane charakterystyki obszarowe: