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 I stopnia
Program:
Informatyka
Grupa przedmiotów:
Wspólne
Kod przedmiotu:
1120-IN000-ISP-0355
Semestr nominalny:
5 / rok ak. 2015/2016
Liczba punktów ECTS:
4
Liczba godzin pracy studenta związanych z osiągnięciem efektów uczenia się:
Liczba punktów ECTS na zajęciach wymagających bezpośredniego udziału nauczycieli akademickich:
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
  • Ć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. J. E. Hopcroft, J. D. Ullman, 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

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 i laboratoriach, 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 i laboratoriach, 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 i laboratoriach, 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