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. 2009/2010
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
  • Ćwiczenia30h
  • Laboratorium0h
  • Projekt0h
  • Lekcje komputerowe0h
Wymagania wstępne:
Algebra, Wstęp do logiki i teorii mnogości
Limit liczby studentów:
Cel przedmiotu:
Podstawowe pojęcia teorii automatów, języków formalnych: gramatyk, języków, automatów skończonych, ze stosem, maszyn Turinga, niedeterminizmu, równoważności gramatyk i automatów, hierarchii Chomsky'ego języków.
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:
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:
Uwagi:

Efekty uczenia się