Politechnika Warszawska - Centralny System Uwierzytelniania
Strona główna

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 Podstawowe informacje o zasadach przyporządkowania punktów ECTS:
  • roczny wymiar godzinowy nakładu pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się dla danego etapu studiów wynosi 1500-1800 h, co odpowiada 60 ECTS;
  • tygodniowy wymiar godzinowy nakładu pracy studenta wynosi 45 h;
  • 1 punkt ECTS odpowiada 25-30 godzinom pracy studenta potrzebnej do osiągnięcia zakładanych efektów uczenia się;
  • tygodniowy nakład pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się pozwala uzyskać 1,5 ECTS;
  • nakład pracy potrzebny do zaliczenia przedmiotu, któremu przypisano 3 ECTS, stanowi 10% semestralnego obciążenia studenta.
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
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Ćwiczenia, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
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
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Ćwiczenia, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Władysław Homenda
Prowadzący grup: Władysław Homenda, Marcin Luckner
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Politechnika Warszawska.
pl. Politechniki 1, 00-661 Warszawa tel: (22) 234 7211 https://pw.edu.pl kontakt deklaracja dostępności USOSweb 7.0.0.0-7 (2024-03-18)