Zachodniopomorski Uniwersytet Technologiczny w Szczecinie

Wydział Informatyki - Informatyka (S1)

Sylabus przedmiotu Podstawy teorii automatów:

Informacje podstawowe

Kierunek studiów Informatyka
Forma studiów studia stacjonarne Poziom pierwszego stopnia
Tytuł zawodowy absolwenta inżynier
Obszary studiów nauki techniczne, studia inżynierskie
Profil ogólnoakademicki
Moduł
Przedmiot Podstawy teorii automatów
Specjalność przedmiot wspólny
Jednostka prowadząca Katedra Architektury Komputerów i Telekomunikacji
Nauczyciel odpowiedzialny Dorota Majorkowska-Mech <Dorota.Majorkowska-Mech@zut.edu.pl>
Inni nauczyciele Piotr Dziurzański <Piotr.Dziurzanski@zut.edu.pl>
ECTS (planowane) 2,0 ECTS (formy) 2,0
Forma zaliczenia zaliczenie Język polski
Blok obieralny Grupa obieralna

Formy dydaktyczne

Forma dydaktycznaKODSemestrGodzinyECTSWagaZaliczenie
ćwiczenia audytoryjneA3 15 1,10,41zaliczenie
wykładyW3 15 0,90,59zaliczenie

Wymagania wstępne

KODWymaganie wstępne
W-1Znajomość podstaw informatyki.

Cele przedmiotu

KODCel modułu/przedmiotu
C-1Student rozumie zasadność nauki informatyki teoretycznej.
C-2Student rozumie potrzebę wykorzystywania automatów skończonych w codziennych praktykach informatycznych.
C-3Student rozumie zastosowanie lingwistyki matematycznej w informatyce.

Treści programowe z podziałem na formy zajęć

KODTreść programowaGodziny
ćwiczenia audytoryjne
T-A-1Wyznaczanie podstawowych parametrów automatów skończonych.2
T-A-2Konwersja między automatami deterministycznymi i niedeterministycznymi.2
T-A-3Konstruowanie wyrażenia regularnego dla danego automatu skończonego.2
T-A-4Konstrukcja Thompsona.2
T-A-5Optymalizacja automatów skończonych2
T-A-6Użycie wyrażeń regularnych w problemach praktycznych.2
T-A-7Klasyfikowanie gramatyk według hierarchii Chomsky'ego.1
T-A-8Konstruowanie Maszyn Turinga.2
15
wykłady
T-W-1Definicja Automatu skończonego (AS).1
T-W-2Konwersja NAS w DAS.1
T-W-3Automat skończony z ε-ruchami. Pojęcie ε-domknięcia. Konwersja automaty NAS z ε-ruchami na NAS.1
T-W-4Operacje na językach. Definicja rekurencyjna wyrażeń regularnych. Skróty notacyjne w wyrażeniach regularnych.1
T-W-5Konwersja wyrażeń regularnych na automat NAS z ε-ruchami (konstrukcja Thompsona).1
T-W-6Wykorzystanie wyrażeń regularnych w Grep i Perl.1
T-W-7Minimalizacja automatów skończonych.1
T-W-8L-systemy.1
T-W-9Definicja formalnej gramatyki.1
T-W-10Drzewo składniowe. Niejednoznaczność wyprowadzenia.1
T-W-11Notacja BNF i wykresy składniowe.1
T-W-12Definicja automatu ze stosem. Gramatyki akceptowane przez automat ze stosem.1
T-W-13Definicja Maszyny Turinga (MT).1
T-W-14Problem stopu; pojęcie nierozstrzygalności.1
T-W-15Maszyna RAM - budowa i zasady pracy. Akceptowanie języków i obliczanie funkcji na RAM. Złożoność czasowa i pamięciowa programu RAM.1
15

Obciążenie pracą studenta - formy aktywności

KODForma aktywnościGodziny
ćwiczenia audytoryjne
A-A-1Przygotowanie do zajęć.15
A-A-2udział w ćwiczeniach15
A-A-3Udział w zaliczeniu ćwiczeń i konsultacjach2
32
wykłady
A-W-1Przygotowanie do zaliczenia wykładu.10
A-W-2uczestnictwo w zajęciach15
A-W-3Konsultacje do wykładu1
A-W-4Udział w zaliczeniu wykładu1
27

Metody nauczania / narzędzia dydaktyczne

KODMetoda nauczania / narzędzie dydaktyczne
M-1Wykład informacyjny
M-2Wykład problemowy
M-3Metoda przypadków
M-4Ćwiczenia przedmiotowe

Sposoby oceny

KODSposób oceny
S-1Ocena podsumowująca: Ocena wiedzy i umiejętności wykazana na egzaminie pisemnym o charakterze problemowym

Zamierzone efekty kształcenia - wiedza

Zamierzone efekty kształceniaOdniesienie do efektów kształcenia dla kierunku studiówOdniesienie do efektów zdefiniowanych dla obszaru kształceniaOdniesienie do efektów kształcenia prowadzących do uzyskania tytułu zawodowego inżynieraCel przedmiotuTreści programoweMetody nauczaniaSposób oceny
I_1A_B/08_W01
Student zna podstawy lingwistyki matematycznej oraz matematycznych modeli obliczeniowych (automat skończony, automat ze stosem, maszyna Turinga, maszyna RAM), a także posiada podstawową wiedzę z zakresu modelowania systemów dyskretnych z wykorzystaniem automatów skończonych.
I_1A_W18, I_1A_W01C-1, C-3T-A-7, T-W-9, T-W-10, T-W-11, T-W-4M-1, M-2, M-3, M-4S-1

Zamierzone efekty kształcenia - umiejętności

Zamierzone efekty kształceniaOdniesienie do efektów kształcenia dla kierunku studiówOdniesienie do efektów zdefiniowanych dla obszaru kształceniaOdniesienie do efektów kształcenia prowadzących do uzyskania tytułu zawodowego inżynieraCel przedmiotuTreści programoweMetody nauczaniaSposób oceny
I_1A_B/08_U01
Student potrafi modelować proste systemy z wykorzystaniem automatów skończonych.
I_1A_U19

Kryterium oceny - wiedza

Efekt kształceniaOcenaKryterium oceny
I_1A_B/08_W01
Student zna podstawy lingwistyki matematycznej oraz matematycznych modeli obliczeniowych (automat skończony, automat ze stosem, maszyna Turinga, maszyna RAM), a także posiada podstawową wiedzę z zakresu modelowania systemów dyskretnych z wykorzystaniem automatów skończonych.
2,0nie spełnia wymogów na ocenę 3,0.
3,0zna hierarchię Chomsky'ego, zna budowę i sposób działania DAS, NAS, NAS z e-przejściami, AZS, MT i maszyny RAM, zna operacje i skróty notacyjne używane w wyrażeniach regularnych, zna sposób konstrukcji drzew wyprowadzeń, zna pojęcie notacji BNF oraz drzew składniowych.
3,5jak na ocenę 3,0 oraz zna algorytmy konwersji między automatami skończonymi.
4,0jak na ocenę 3,5 oraz zna formalne definicje automatów, algorytmy minimalizacji automatów skończonych, operacje wykonywane na maszynie RAM, rozumie związek między MT a teorią obliczalności i złożoności obliczeniowej.
4,5jak na ocenę 4,0 oraz zna lemat o pompowaniu oraz zna kryteria i sposób obliczania złożoności obliczeniowej maszyny RAM.
5,0jak na ocenę 4,5 oraz zna sposób symulacji maszyny RAM na MT oraz MT na maszynie RAM.

Kryterium oceny - umiejętności

Efekt kształceniaOcenaKryterium oceny
I_1A_B/08_U01
Student potrafi modelować proste systemy z wykorzystaniem automatów skończonych.
2,0nie spełnia wymogów na ocenę 3,0.
3,0potrafi identyfikować gramatykę zgodnie z hierarchią Chomsky'ego, potrafi zaprojektować DAS, NAS, NAS z e-przejściami dla prostego problemu, potrafi zapisać wyrażenie regularne, potrafi przedstawić wyprowadzenie ciągu na drzewie wyprowadzeń, potrafi używać notacji BNF oraz drzew składniowych.
3,5jak na ocenę 3,0 oraz potrafi przedstawić wybrane problemy za pomocą AZS.
4,0jak na ocenę 3,5 oraz potrafi skonstruować MT realizującą przedstawiony algorytm.
4,5jak na ocenę 3,5 oraz potrafi napisać prosty program dla maszyny RAM.
5,0jak na ocenę 4,5 oraz potrafi określić złożoność obliczeniową problemu realizowanego na MT oraz RAM.

Literatura podstawowa

  1. J. E. Hopcroft, J. D. Ullman, Wprowadzenie do teorii automatów, języków i obliczeń, Wydawnictwo Naukowe PWN, Warszawa, 1994
  2. M. Sipser, Introduction to the Theory of Computation, PWS Publishing Company, Boston, 1996
  3. J. E. F. Friedl, Wyrażenia regularne, Wydawnictwo Helion, Gliwice, 2001

Literatura dodatkowa

  1. D. Harel, Rzecz o istocie informatyki. Algorytmika, Wydawnictwo Naukowo Techniczne, Wydawnictwo Naukowo Techniczne, 1992

Treści programowe - ćwiczenia audytoryjne

KODTreść programowaGodziny
T-A-1Wyznaczanie podstawowych parametrów automatów skończonych.2
T-A-2Konwersja między automatami deterministycznymi i niedeterministycznymi.2
T-A-3Konstruowanie wyrażenia regularnego dla danego automatu skończonego.2
T-A-4Konstrukcja Thompsona.2
T-A-5Optymalizacja automatów skończonych2
T-A-6Użycie wyrażeń regularnych w problemach praktycznych.2
T-A-7Klasyfikowanie gramatyk według hierarchii Chomsky'ego.1
T-A-8Konstruowanie Maszyn Turinga.2
15

Treści programowe - wykłady

KODTreść programowaGodziny
T-W-1Definicja Automatu skończonego (AS).1
T-W-2Konwersja NAS w DAS.1
T-W-3Automat skończony z ε-ruchami. Pojęcie ε-domknięcia. Konwersja automaty NAS z ε-ruchami na NAS.1
T-W-4Operacje na językach. Definicja rekurencyjna wyrażeń regularnych. Skróty notacyjne w wyrażeniach regularnych.1
T-W-5Konwersja wyrażeń regularnych na automat NAS z ε-ruchami (konstrukcja Thompsona).1
T-W-6Wykorzystanie wyrażeń regularnych w Grep i Perl.1
T-W-7Minimalizacja automatów skończonych.1
T-W-8L-systemy.1
T-W-9Definicja formalnej gramatyki.1
T-W-10Drzewo składniowe. Niejednoznaczność wyprowadzenia.1
T-W-11Notacja BNF i wykresy składniowe.1
T-W-12Definicja automatu ze stosem. Gramatyki akceptowane przez automat ze stosem.1
T-W-13Definicja Maszyny Turinga (MT).1
T-W-14Problem stopu; pojęcie nierozstrzygalności.1
T-W-15Maszyna RAM - budowa i zasady pracy. Akceptowanie języków i obliczanie funkcji na RAM. Złożoność czasowa i pamięciowa programu RAM.1
15

Formy aktywności - ćwiczenia audytoryjne

KODForma aktywnościGodziny
A-A-1Przygotowanie do zajęć.15
A-A-2udział w ćwiczeniach15
A-A-3Udział w zaliczeniu ćwiczeń i konsultacjach2
32
(*) 1 punkt ECTS, odpowiada około 30 godzinom aktywności studenta

Formy aktywności - wykłady

KODForma aktywnościGodziny
A-W-1Przygotowanie do zaliczenia wykładu.10
A-W-2uczestnictwo w zajęciach15
A-W-3Konsultacje do wykładu1
A-W-4Udział w zaliczeniu wykładu1
27
(*) 1 punkt ECTS, odpowiada około 30 godzinom aktywności studenta
PoleKODZnaczenie kodu
Zamierzone efekty kształceniaI_1A_B/08_W01Student zna podstawy lingwistyki matematycznej oraz matematycznych modeli obliczeniowych (automat skończony, automat ze stosem, maszyna Turinga, maszyna RAM), a także posiada podstawową wiedzę z zakresu modelowania systemów dyskretnych z wykorzystaniem automatów skończonych.
Odniesienie do efektów kształcenia dla kierunku studiówI_1A_W18ma wiedzę w zakresie podstaw modelowania systemów
I_1A_W01ma wiedzę z matematyki teoretycznej ze szczególnym uwzględnieniem jej stosowanych aspektów, matematyki dyskretnej oraz matematyki stosowanej
Cel przedmiotuC-1Student rozumie zasadność nauki informatyki teoretycznej.
C-3Student rozumie zastosowanie lingwistyki matematycznej w informatyce.
Treści programoweT-A-7Klasyfikowanie gramatyk według hierarchii Chomsky'ego.
T-W-9Definicja formalnej gramatyki.
T-W-10Drzewo składniowe. Niejednoznaczność wyprowadzenia.
T-W-11Notacja BNF i wykresy składniowe.
T-W-4Operacje na językach. Definicja rekurencyjna wyrażeń regularnych. Skróty notacyjne w wyrażeniach regularnych.
Metody nauczaniaM-1Wykład informacyjny
M-2Wykład problemowy
M-3Metoda przypadków
M-4Ćwiczenia przedmiotowe
Sposób ocenyS-1Ocena podsumowująca: Ocena wiedzy i umiejętności wykazana na egzaminie pisemnym o charakterze problemowym
Kryteria ocenyOcenaKryterium oceny
2,0nie spełnia wymogów na ocenę 3,0.
3,0zna hierarchię Chomsky'ego, zna budowę i sposób działania DAS, NAS, NAS z e-przejściami, AZS, MT i maszyny RAM, zna operacje i skróty notacyjne używane w wyrażeniach regularnych, zna sposób konstrukcji drzew wyprowadzeń, zna pojęcie notacji BNF oraz drzew składniowych.
3,5jak na ocenę 3,0 oraz zna algorytmy konwersji między automatami skończonymi.
4,0jak na ocenę 3,5 oraz zna formalne definicje automatów, algorytmy minimalizacji automatów skończonych, operacje wykonywane na maszynie RAM, rozumie związek między MT a teorią obliczalności i złożoności obliczeniowej.
4,5jak na ocenę 4,0 oraz zna lemat o pompowaniu oraz zna kryteria i sposób obliczania złożoności obliczeniowej maszyny RAM.
5,0jak na ocenę 4,5 oraz zna sposób symulacji maszyny RAM na MT oraz MT na maszynie RAM.
PoleKODZnaczenie kodu
Zamierzone efekty kształceniaI_1A_B/08_U01Student potrafi modelować proste systemy z wykorzystaniem automatów skończonych.
Odniesienie do efektów kształcenia dla kierunku studiówI_1A_U19ma umiejętność wyboru algorytmu i struktur danych do rozwiązania określonego zadania inżynierskiego
Kryteria ocenyOcenaKryterium oceny
2,0nie spełnia wymogów na ocenę 3,0.
3,0potrafi identyfikować gramatykę zgodnie z hierarchią Chomsky'ego, potrafi zaprojektować DAS, NAS, NAS z e-przejściami dla prostego problemu, potrafi zapisać wyrażenie regularne, potrafi przedstawić wyprowadzenie ciągu na drzewie wyprowadzeń, potrafi używać notacji BNF oraz drzew składniowych.
3,5jak na ocenę 3,0 oraz potrafi przedstawić wybrane problemy za pomocą AZS.
4,0jak na ocenę 3,5 oraz potrafi skonstruować MT realizującą przedstawiony algorytm.
4,5jak na ocenę 3,5 oraz potrafi napisać prosty program dla maszyny RAM.
5,0jak na ocenę 4,5 oraz potrafi określić złożoność obliczeniową problemu realizowanego na MT oraz RAM.