Uniwersytet w Białymstoku - Centralny System Uwierzytelniania
Strona główna

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) 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.

zobacz reguły punktacji
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

Przedmiot nie jest oferowany w żadnym z aktualnych cykli dydaktycznych.
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet w Białymstoku.
ul. Świerkowa 20B, 15-328 Białystok tel: +48 85 745 70 00 (Centrala) https://uwb.edu.pl kontakt deklaracja dostępności USOSweb 7.0.2.0-1 (2024-03-12)