Moduł oferowany także w ramach programów studiów:
Informacje ogólne:
Nazwa:
Automaty i Sieci Petriego ()
Tok studiów:
2019/2020
Kod:
AMAT-2-016-MO-s
Wydział:
Matematyki Stosowanej
Poziom studiów:
Studia II stopnia
Specjalność:
Matematyka obliczeniowa i komputerowa
Kierunek:
Matematyka
Semestr:
0
Profil:
Ogólnoakademicki (A)
Język wykładowy:
Polski
Forma studiów:
Stacjonarne
Strona www:
 
Prowadzący moduł:
dr hab. Foryś Wit (foryswit@wms.mat.agh.edu.pl)
Treści programowe zapewniające uzyskanie efektów uczenia się dla modułu zajęć
Pojęcia i struktury matematyczne stosowane w teorii języków formalnych i automatów.
Opis efektów uczenia się dla modułu zajęć
Kod MEU Student, który zaliczył moduł zajęć zna i rozumie/potrafi/jest gotów do Powiązania z KEU Sposób weryfikacji i oceny efektów uczenia się osiągniętych przez studenta w ramach poszczególnych form zajęć i dla całego modułu zajęć
Wiedza: zna i rozumie
M_W001 zna klasy automatów i gramatyk odpowiadające klasom języków hierarchii Chomsky’ego oraz ich wlasności MAT2A_W11, MAT2A_W06, MAT2A_W10, MAT2A_K05 Aktywność na zajęciach,
Kolokwium,
Odpowiedź ustna
M_W002 zna klasy języków wystepujace w hierarchii Chomsky’ego i ich wlasnosci MAT2A_W10, MAT2A_K05, MAT2A_W07 Aktywność na zajęciach,
Kolokwium,
Odpowiedź ustna
M_W003 zna podstawowe pojęcia i struktury matematyczne stosowane w teorii języków formalnych i automatów MAT2A_W11, MAT2A_W01, MAT2A_W02, MAT2A_U02 Aktywność na zajęciach,
Odpowiedź ustna,
Kolokwium
Umiejętności: potrafi
M_U001 Potrafi rozwiązać algorytmicznie problemy z zakresu automatów, gramatyk i językow odpowiadajacych hierarchi Chomsky’ego MAT2A_U07, MAT2A_U01, MAT2A_U03 Aktywność na zajęciach,
Kolokwium,
Odpowiedź ustna
M_U002 Potrafi rozpoznać problemy rozstrzygalne i nierozstrzygalne z zakresu automatów, gramatyk i językow odpowiadajacych hierarchi Chomsky’ego MAT2A_U19, MAT2A_U21, MAT2A_U01, MAT2A_U13, MAT2A_U03 Aktywność na zajęciach,
Kolokwium,
Odpowiedź ustna
M_U003 potrafi zaproponować rozwiązanie problemu, także algorytmicznego, z zakresu automatów, gramatyk i językow odpowiadajacych hierarchi Chomsky’ego MAT2A_U07, MAT2A_U01, MAT2A_U03 Aktywność na zajęciach,
Kolokwium,
Odpowiedź ustna
Kompetencje społeczne: jest gotów do
M_K001 umie ocenić stopień zrozumienia przez siebie problemu i brakujące elementy rozumowania MAT2A_K01, MAT2A_K07, MAT2A_K02 Aktywność na zajęciach,
Odpowiedź ustna
Liczba godzin zajęć w ramach poszczególnych form zajęć:
SUMA (godz.)
Wykład
Ćwicz. aud
Ćwicz. lab
Ćw. proj.
Konw.
Zaj. sem.
Zaj. prakt
Zaj. terenowe
Zaj. warsztatowe
Prace kontr. przejść.
Lektorat
60 30 30 0 0 0 0 0 0 0 0 0
Matryca kierunkowych efektów uczenia się w odniesieniu do form zajęć i sposobu zaliczenia, które pozwalają na ich uzyskanie
Kod MEU Student, który zaliczył moduł zajęć zna i rozumie/potrafi/jest gotów do Forma zajęć dydaktycznych
Wykład
Ćwicz. aud
Ćwicz. lab
Ćw. proj.
Konw.
Zaj. sem.
Zaj. prakt
Zaj. terenowe
Zaj. warsztatowe
Prace kontr. przejść.
Lektorat
Wiedza
M_W001 zna klasy automatów i gramatyk odpowiadające klasom języków hierarchii Chomsky’ego oraz ich wlasności + + - - - - - - - - -
M_W002 zna klasy języków wystepujace w hierarchii Chomsky’ego i ich wlasnosci + + - - - - - - - - -
M_W003 zna podstawowe pojęcia i struktury matematyczne stosowane w teorii języków formalnych i automatów + + - - - - - - - - -
Umiejętności
M_U001 Potrafi rozwiązać algorytmicznie problemy z zakresu automatów, gramatyk i językow odpowiadajacych hierarchi Chomsky’ego + + - - - - - - - - -
M_U002 Potrafi rozpoznać problemy rozstrzygalne i nierozstrzygalne z zakresu automatów, gramatyk i językow odpowiadajacych hierarchi Chomsky’ego + + - - - - - - - - -
M_U003 potrafi zaproponować rozwiązanie problemu, także algorytmicznego, z zakresu automatów, gramatyk i językow odpowiadajacych hierarchi Chomsky’ego + + - - - - - - - - -
Kompetencje społeczne
M_K001 umie ocenić stopień zrozumienia przez siebie problemu i brakujące elementy rozumowania + + - - - - - - - - -
Nakład pracy studenta (bilans punktów ECTS)
Forma aktywności studenta Obciążenie studenta
Sumaryczne obciążenie pracą studenta 101 godz
Punkty ECTS za moduł 4 ECTS
Udział w zajęciach dydaktycznych/praktyka 60 godz
Przygotowanie do zajęć 14 godz
Samodzielne studiowanie tematyki zajęć 20 godz
Egzamin lub kolokwium zaliczeniowe 2 godz
Dodatkowe godziny kontaktowe 5 godz
Szczegółowe treści kształcenia w ramach poszczególnych form zajęć (szczegółowy program wykładów i pozostałych zajęć)
Wykład (30h):
  1. Wiadomości wstępne

    WYKŁADY

    Alfabet, słowo, język – elementy teorii półgrup; półgrupy i monoidy wolne.

  2. Języki regularne

    Automat skończenie stanowy; automat minimalny i algorytmy; automaty deterministyczne i niedeterministyczne; algorytm determinizacji; własności języków regularnych; lemat o pompowaniu i języki nieregularne; wyrażenia regularne i algorytmy; twierdzenie Kleenego; problemy rozstrzygalności.

  3. Języki bezkontekstowe

    Własności języków bezkontekstowych, gramatyka – postać Chomsky’ego i Greibach oraz algorytmy upraszczania; automat ze stosem; równoważność gramatyki bezkontekstowej i automatu ze stosem – algorytmy; lemat o pompowaniu i języki, które nie są bezkontekstowe; jednoznaczność, problem przynależności i algorytm CYK; problemy rozstrzygalności.

  4. Sieci Petriego

    Wiadomości wstępne. Miejsca i tranzycje – reguły odpalania; przykłady modelowania przy wykorzystaniu sieci (przetwarzanie równoległe, protokoły komunikacji dla przepływu danych, synchronizacja, układy multiprocesorów).

  5. Systemy produkcji

    Modelowanie, analiza i zarządzanie systemami produkcyjnymi – „case study” – systemy cykliczne (linia produkcyjna, system składająco/rozkładający, hala produkcyjna) – systemy acykliczne (short-term planning, scheduling).

  6. Gramatyki – model obliczeń; hierarchia Chomsky'ego.
Ćwiczenia audytoryjne (30h):
Program ćwiczeń laboratoriów pokrywa się z programem wykładów

Rozwiązywanie problemów, implementacja algorytmów,realizacja małych projektów ilustrujących treści przekazywanych na kolejnych wykładach.

Pozostałe informacje
Metody i techniki kształcenia:
  • Wykład: Treści prezentowane na wykładzie są przekazywane w formie prezentacji multimedialnej w połączeniu z klasycznym wykładem tablicowym wzbogaconymi o pokazy odnoszące się do prezentowanych zagadnień.
  • Ćwiczenia audytoryjne: Podczas zajęć audytoryjnych studenci na tablicy rozwiązują zadane wcześniej problemy. Prowadzący na bieżąco dokonuje stosowanych wyjaśnień i moderuje dyskusję z grupą nad danym problemem.
Warunki i sposób zaliczenia poszczególnych form zajęć, w tym zasady zaliczeń poprawkowych, a także warunki dopuszczenia do egzaminu:

dwa zaliczenia poprawkowe

Zasady udziału w zajęciach:
  • Wykład:
    – Obecność obowiązkowa: Tak
    – Zasady udziału w zajęciach: Studenci uczestniczą w zajęciach poznając kolejne treści nauczania zgodnie z syllabusem przedmiotu. Studenci winni na bieżąco zadawać pytania i wyjaśniać wątpliwości. Rejestracja audiowizualna wykładu wymaga zgody prowadzącego.
  • Ćwiczenia audytoryjne:
    – Obecność obowiązkowa: Tak
    – Zasady udziału w zajęciach: Studenci przystępując do ćwiczeń są zobowiązani do przygotowania się w zakresie wskazanym każdorazowo przez prowadzącego (np. w formie zestawów zadań). Ocena pracy studenta może bazować na wypowiedziach ustnych lub pisemnych w formie kolokwium, co zgodnie z regulaminem studiów AGH przekłada się na ocenę końcową z tej formy zajęć.
Sposób obliczania oceny końcowej:

zaliczenie

Sposób i tryb wyrównywania zaległości powstałych wskutek nieobecności studenta na zajęciach:

Wg indywidualnych ustaleń między prowadzącym a studentem.

Wymagania wstępne i dodatkowe, z uwzględnieniem sekwencyjności modułów :

Nie podano wymagań wstępnych lub dodatkowych.

Zalecana literatura i pomoce naukowe:
  1. M.Foryś, W.Foryś, Teoria automatów i języków formalnych – AOW EXIT, Warszawa 2005
  2. J.E.Hopcroft, J.D.Ulman, Introduction to automata theory, languages and computing, Addison-Wesley, 1979 – dostępna w języku polskim
  3. J.M.Proth, X.Xie – Petri Nets, A Tool for Design and Management of Manufacturing Systems , J.Wiley&Sons, 1996
Publikacje naukowe osób prowadzących zajęcia związane z tematyką modułu:

1. Foryś, Wit; Matyja, Janusz; On one-sided, topologically mixing cellular automata, having continuum of fixed points and topological entropy log(n) for any integer n>1; J. Cell. Autom. 9, No. 1, 37-58 (2014).

2. Foryś, Wit; Matyja, Janusz; On one-sided, D-chaotic cellular automaton, having continuum of fixed points and topological entropy log(3); J. Cell. Autom. 8, No. 3-4, 131-146 (2013).

3. Foryś, Wit; Matyja, Janusz; On one-sided, D-chaotic cellular automata, having continuum of fixed points and topological entropy log(p) for any prime p>3; J. Cell. Autom. 7, No. 4, 303-319 (2012).

4. Foryś, Wit; Oprocha, Piotr; Infinite traces and symbolic dynamics – the minimal shift case;
Fundam. Inform. 111, No. 2, 147-161 (2011).

Informacje dodatkowe:

Brak