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
Wymagania wstępne
| KOD | Wymaganie wstępne |
|---|---|
| W-1 | Znajomość podstaw informatyki. |
Cele przedmiotu
| KOD | Cel modułu/przedmiotu |
|---|---|
| C-1 | Student rozumie zasadność nauki informatyki teoretycznej. |
| C-2 | Student rozumie potrzebę wykorzystywania automatów skończonych w codziennych praktykach informatycznych. |
| C-3 | Student rozumie zastosowanie lingwistyki matematycznej w informatyce. |
Treści programowe z podziałem na formy zajęć
| KOD | Treść programowa | Godziny |
|---|---|---|
| ćwiczenia audytoryjne | ||
| T-A-1 | Wyznaczanie podstawowych parametrów automatów skończonych. | 2 |
| T-A-2 | Konwersja między automatami deterministycznymi i niedeterministycznymi. | 2 |
| T-A-3 | Konstruowanie wyrażenia regularnego dla danego automatu skończonego. | 2 |
| T-A-4 | Konstrukcja Thompsona. | 2 |
| T-A-5 | Optymalizacja automatów skończonych | 2 |
| T-A-6 | Użycie wyrażeń regularnych w problemach praktycznych. | 2 |
| T-A-7 | Klasyfikowanie gramatyk według hierarchii Chomsky'ego. | 1 |
| T-A-8 | Konstruowanie Maszyn Turinga. | 2 |
| 15 | ||
| wykłady | ||
| T-W-1 | Definicja Automatu skończonego (AS). | 1 |
| T-W-2 | Konwersja NAS w DAS. | 1 |
| T-W-3 | Automat skończony z ε-ruchami. Pojęcie ε-domknięcia. Konwersja automaty NAS z ε-ruchami na NAS. | 1 |
| T-W-4 | Operacje na językach. Definicja rekurencyjna wyrażeń regularnych. Skróty notacyjne w wyrażeniach regularnych. | 1 |
| T-W-5 | Konwersja wyrażeń regularnych na automat NAS z ε-ruchami (konstrukcja Thompsona). | 1 |
| T-W-6 | Wykorzystanie wyrażeń regularnych w Grep i Perl. | 1 |
| T-W-7 | Minimalizacja automatów skończonych. | 1 |
| T-W-8 | L-systemy. | 1 |
| T-W-9 | Definicja formalnej gramatyki. | 1 |
| T-W-10 | Drzewo składniowe. Niejednoznaczność wyprowadzenia. | 1 |
| T-W-11 | Notacja BNF i wykresy składniowe. | 1 |
| T-W-12 | Definicja automatu ze stosem. Gramatyki akceptowane przez automat ze stosem. | 1 |
| T-W-13 | Definicja Maszyny Turinga (MT). | 1 |
| T-W-14 | Problem stopu; pojęcie nierozstrzygalności. | 1 |
| T-W-15 | Maszyna 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
| KOD | Forma aktywności | Godziny |
|---|---|---|
| ćwiczenia audytoryjne | ||
| A-A-1 | Przygotowanie do zajęć. | 15 |
| A-A-2 | udział w ćwiczeniach | 15 |
| A-A-3 | Udział w zaliczeniu ćwiczeń i konsultacjach | 2 |
| 32 | ||
| wykłady | ||
| A-W-1 | Przygotowanie do zaliczenia wykładu. | 10 |
| A-W-2 | uczestnictwo w zajęciach | 15 |
| A-W-3 | Konsultacje do wykładu | 1 |
| A-W-4 | Udział w zaliczeniu wykładu | 1 |
| 27 | ||
Metody nauczania / narzędzia dydaktyczne
| KOD | Metoda nauczania / narzędzie dydaktyczne |
|---|---|
| M-1 | Wykład informacyjny |
| M-2 | Wykład problemowy |
| M-3 | Metoda przypadków |
| M-4 | Ćwiczenia przedmiotowe |
Sposoby oceny
| KOD | Sposób oceny |
|---|---|
| S-1 | Ocena podsumowująca: Ocena wiedzy i umiejętności wykazana na egzaminie pisemnym o charakterze problemowym |
Zamierzone efekty kształcenia - wiedza
| Zamierzone efekty kształcenia | Odniesienie do efektów kształcenia dla kierunku studiów | Odniesienie do efektów zdefiniowanych dla obszaru kształcenia | Odniesienie do efektów kształcenia prowadzących do uzyskania tytułu zawodowego inżyniera | Cel przedmiotu | Treści programowe | Metody nauczania | Sposó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_W01 | — | — | C-1, C-3 | T-A-7, T-W-9, T-W-10, T-W-11, T-W-4 | M-1, M-2, M-3, M-4 | S-1 |
Zamierzone efekty kształcenia - umiejętności
| Zamierzone efekty kształcenia | Odniesienie do efektów kształcenia dla kierunku studiów | Odniesienie do efektów zdefiniowanych dla obszaru kształcenia | Odniesienie do efektów kształcenia prowadzących do uzyskania tytułu zawodowego inżyniera | Cel przedmiotu | Treści programowe | Metody nauczania | Sposó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łcenia | Ocena | Kryterium 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,0 | nie spełnia wymogów na ocenę 3,0. |
| 3,0 | zna 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,5 | jak na ocenę 3,0 oraz zna algorytmy konwersji między automatami skończonymi. | |
| 4,0 | jak 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,5 | jak na ocenę 4,0 oraz zna lemat o pompowaniu oraz zna kryteria i sposób obliczania złożoności obliczeniowej maszyny RAM. | |
| 5,0 | jak 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łcenia | Ocena | Kryterium oceny |
|---|---|---|
| I_1A_B/08_U01 Student potrafi modelować proste systemy z wykorzystaniem automatów skończonych. | 2,0 | nie spełnia wymogów na ocenę 3,0. |
| 3,0 | potrafi 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,5 | jak na ocenę 3,0 oraz potrafi przedstawić wybrane problemy za pomocą AZS. | |
| 4,0 | jak na ocenę 3,5 oraz potrafi skonstruować MT realizującą przedstawiony algorytm. | |
| 4,5 | jak na ocenę 3,5 oraz potrafi napisać prosty program dla maszyny RAM. | |
| 5,0 | jak na ocenę 4,5 oraz potrafi określić złożoność obliczeniową problemu realizowanego na MT oraz RAM. |
Literatura podstawowa
- J. E. Hopcroft, J. D. Ullman, Wprowadzenie do teorii automatów, języków i obliczeń, Wydawnictwo Naukowe PWN, Warszawa, 1994
- M. Sipser, Introduction to the Theory of Computation, PWS Publishing Company, Boston, 1996
- J. E. F. Friedl, Wyrażenia regularne, Wydawnictwo Helion, Gliwice, 2001
Literatura dodatkowa
- D. Harel, Rzecz o istocie informatyki. Algorytmika, Wydawnictwo Naukowo Techniczne, Wydawnictwo Naukowo Techniczne, 1992