Zastosowania automatów i języków formalnych
Informacje ogólne
Kod przedmiotu: | 400-IS1-3ZAJF |
Kod Erasmus / ISCED: | (brak danych) / (brak danych) |
Nazwa przedmiotu: | Zastosowania automatów i języków formalnych |
Jednostka: | Filia Uniwersytetu w Białymstoku w Wilnie, Wydział Ekonomiczno-Informatyczny |
Grupy: |
3L stac. I st. studia informatyki - przedmioty obowiązkowe - WILNO Wilno - informatyka 3 rok 1 st. stacjonarne sem.zimowy |
Punkty ECTS i inne: |
(brak)
|
Język prowadzenia: | polski |
Rodzaj przedmiotu: | obowiązkowe |
Skrócony opis: |
Wprowadzenie to teorii języków: alfabet, język, operacje na językach, gramatyka, wywód w gramatyce. Klasa języków regularnych: wyrażenia regularne, gramatyki regularne; automaty skończone deterministyczne, niedeterministyczne, z e-przejściami i ich równoważność; równoważność wyrażeń regularnych, gramatyk regularnych i automatów skończonych; lemat o pompowaniu, twierdzenie Myhill-Nerode. Klasa języków bezkontekstowych: gramatyki bezkontekstowe, drzewo wywodu, lemat o pompowaniu, postaci normalne gramatyki bezkontekstowej, przynależność słowa do języka bezkontekstowego, przykłady zastosowań – gramatyki translacyjne, gramatyki LL(1), automaty ze stosem, równoważność automatów ze stosem i gramatyk bezkontekstowych. Gramatyki kontekstowe i nieograniczone, postać normalna gramatyki kontekstowej. Hierarchia Chomskiego (Chomsky’ego). Maszyny Turinga, model podstawowy i modyfikacje, maszyny niedeterministyczne, równoważność modeli maszyn Turinga. |
Pełny opis: |
Profil studiów: ogólnoakademicki Forma studiów: stacjonarne Rodzaj przedmiotu: obowiązkowy Dziedzina i dyscyplina nauki: Dziedzina nauk ścisłych i przyrodniczych, Informatyka Rok studiów / semestr: 3 / 5 Wymagania wstępne (tzw. sekwencyjny system zajęć i egzaminów): Przedmioty wprowadzające: Podstawy logiki i teorii mnogości, Algorytmy i struktury danych, Matematyka dyskretna, Wykład: 15 Laboratorium: 30 Metody dydaktyczne: Wykład z wykorzystaniem prezentacji multimedialnych oraz angażowanie studentów do aktywnego udziału w dyskusji podczas wykładu i zadawania pytań. Samodzielne oraz grupowe rozwiązywania zadań i tworzenie projektów programistycznych podczas laboratoriów. Punkty ECTS: 3 Bilans nakładu pracy studenta: Udział w zajęciach: - wykład 15h - laboratorium 30h Przygotowanie do zajęć: - laboratorium 40h Czas trwania egzaminu: 2h Udział w konsultacjach: 3h Wskaźniki ilościowe: wymagającymi bezpośredniego udziału nauczyciela: 50, 2ECTS o charakterze praktycznym: 70, 2,8 ECTS |
Literatura: |
Literatura podstawowa: Homenda W., Elementy teorii automatów i lingwistyki matematycznej, Oficyna Wydawnicza Politechniki Warszawskiej, 2004 |
Efekty uczenia się: |
Student zna klasyczne pojęcia oraz wyniki z zakresu teorii języków formalnych i automatów (języki regularne, bezkontekstowe, kontekstowe, klasy 0, gramatyki dla języków w hierarchii Chomsky'ego, automaty skończone, automaty ze stosem, maszyny Turinga) KP6_WG1 KP6_WG3, KA6_WG9 Student potrafi wykorzystywać metody teorii języków formalnych w informatyce, a także przeprowadzać formalne i poprawne rozumowania w obszarze języków formalnych KP6_UW1, KP6_UW3, KP6_UW10, KP6_UW12, KP6_KK1 Student potrafi zaimplementować wybrane automaty oraz maszyny Turinga oraz zwizualizować ich działanie KP6_UW3, KP6_UW12, KP6_UK3, KP6_KO1, |
Metody i kryteria oceniania: |
Ogólna forma zaliczenia: laboratoria - kolokwium, wykład - egzamin |
Właścicielem praw autorskich jest Uniwersytet w Białymstoku.