Teoria automatów i języków formalnych
Informacje ogólne
Kod przedmiotu: | 1120-MAMNI-NSP-0232 |
Kod Erasmus / ISCED: | (brak danych) / (brak danych) |
Nazwa przedmiotu: | Teoria automatów i języków formalnych |
Jednostka: | Wydział Matematyki i Nauk Informacyjnych |
Grupy: |
Przedmioty obowiązkowe, sem. 3 MCB (rozpoczęcie w r. ak. nieparzystym) |
Punkty ECTS i inne: |
5.00
|
Język prowadzenia: | polski |
Skrócony opis: |
Wymagania wstępne: Elementy logiki i teorii mnogości Matematyka dyskretna Algorytmy i podstawy programowania Cel przedmiotu: Zapoznanie studentów z podstawowymi pojęciami teorii automatów, lingwistyki matematycznej i elementami teorii rozstrzygalności |
Pełny opis: |
Treść kształcenia: Wiadomości wstępne - przypomnienie: relacje, indukcja zupełna, języki i gramatyki. 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. |
Literatura: |
Hopcroft J.E. Ullman J.D., Wprowadzenie do teorii automatów, jezyków i obliczen, WNT W. Homenda, Elementy lingwistyki matematycznej i teorii automatów, WPW |
Metody i kryteria oceniania: |
Regulamin zaliczenia: ćwiczenia: prace pisemne w połowie i pod koniec semestru; wykład: egzamin pisemny dwuczęściowy z zadań i z teorii |
Zajęcia w cyklu "rok akademicki 2020/2021 - sem. zimowy" (zakończony)
Okres: | 2020-10-01 - 2021-02-19 |
Przejdź do planu
PN WT ŚR CZ PT WYK
CWI
|
Typ zajęć: |
Ćwiczenia, 30 godzin
Wykład, 30 godzin
|
|
Koordynatorzy: | Władysław Homenda | |
Prowadzący grup: | Władysław Homenda, Marcin Luckner | |
Lista studentów: | (nie masz dostępu) | |
Zaliczenie: | Egzamin |
Zajęcia w cyklu "rok akademicki 2018/2019 - sem. zimowy" (zakończony)
Okres: | 2018-10-01 - 2019-02-17 |
Przejdź do planu
PN WT CWI
ŚR CZ PT WYK
|
Typ zajęć: |
Ćwiczenia, 30 godzin
Wykład, 30 godzin
|
|
Koordynatorzy: | Władysław Homenda | |
Prowadzący grup: | Władysław Homenda, Marcin Luckner | |
Lista studentów: | (nie masz dostępu) | |
Zaliczenie: | Egzamin |
Właścicielem praw autorskich jest Politechnika Warszawska.