Drukuj Eksport do pliku (MS Word)
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 I stopnia
Program:
Informatyka i Systemy Informacyjne
Grupa przedmiotów:
Wspólne
Kod przedmiotu:
1120-IN000-ISP-0355
Semestr nominalny:
5 / rok ak. 2020/2021
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
  • Ćwiczenia30h
  • Laboratorium0h
  • 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: 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_U11, 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_U11, 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_U11, 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_K01, K_K02, K_K04
Powiązane charakterystyki obszarowe: