Drukuj Eksport do pliku (MS Word)
Nazwa przedmiotu:
Teoria automatów i lingwistyka matematyczna
Koordynator przedmiotu:
dr hab. Władysław Homenda
Status przedmiotu:
Obowiązkowy
Poziom kształcenia:
Studia II stopnia
Program:
Matematyka
Grupa przedmiotów:
Wspólne
Kod przedmiotu:
Semestr nominalny:
1 / rok ak. 2011/2012
Liczba punktów ECTS:
6
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:
Podstawy matematyki – algebra, wstęp do logiki i teorii mnogości.
Limit liczby studentów:
Cel przedmiotu:
Znajomość podstawowych pojęć lingwistyki matematycznej i teorii automatów: wyrażenia regularne; gramatyki bezkontekstowe, kontekstowe i nieograniczone, automaty skończone, automaty ze stosem, maszyny Turinga; hierarchia Chomskyego
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:
Zasady zaliczania: - 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.  
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ę