Module also offered within study programmes:
General information:
Annual:
2017/2018
Code:
AMA-2-208-MZ-s
Name:
Automata and Petri Nets
Faculty of:
Applied Mathematics
Study level:
Second-cycle studies
Specialty:
Matematyka w zarządzaniu
Field of study:
Mathematics
Semester:
2
Profile of education:
Academic (A)
Lecture language:
Polish
Form and type of study:
Full-time studies
Course homepage:
 
Responsible teacher:
dr hab. Foryś Wit (foryswit@wms.mat.agh.edu.pl)
Academic teachers:
dr Foryś Magdalena (maforys@agh.edu.pl)
dr Michalik Marek (michalik@agh.edu.pl)
dr hab. Foryś Wit (foryswit@wms.mat.agh.edu.pl)
Module summary
Pojęcia i struktury matematyczne stosowane w teorii języków formalnych i automatów.
Description of learning outcomes for module
MLO code Student after module completion has the knowledge/ knows how to/is able to Connections with FLO Method of learning outcomes verification (form of completion)
Social competence
M_K001 umie ocenić stopień zrozumienia przez siebie problemu i brakujące elementy rozumowania MA2A_K02, MA2A_K07, MA2A_K01 Activity during classes,
Oral answer
Skills
M_U001 Potrafi rozwiązać algorytmicznie problemy z zakresu automatów, gramatyk i językow odpowiadajacych hierarchi Chomsky’ego MA2A_U07, MA2A_U03, MA2A_U01 Activity during classes,
Test,
Oral answer
M_U002 Potrafi rozpoznać problemy rozstrzygalne i nierozstrzygalne z zakresu automatów, gramatyk i językow odpowiadajacych hierarchi Chomsky’ego MA2A_U03, MA2A_U01, MA2A_U13 Activity during classes,
Test,
Oral answer
M_U003 potrafi zaproponować rozwiązanie problemu, także algorytmicznego, z zakresu automatów, gramatyk i językow odpowiadajacych hierarchi Chomsky’ego MA2A_U07, MA2A_U03, MA2A_U01 Activity during classes,
Test,
Oral answer
Knowledge
M_W001 zna podstawowe pojęcia i struktury matematyczne stosowane w teorii języków formalnych i automatów MA2A_W01, MA2A_W02, MA2A_U02 Activity during classes,
Oral answer,
Test
M_W002 zna klasy języków wystepujace w hierarchii Chomsky’ego i ich wlasnosci MA2A_W10, MA2A_K05, MA2A_W07 Activity during classes,
Test,
Oral answer
M_W003 zna klasy automatów i gramatyk odpowiadające klasom języków hierarchii Chomsky’ego oraz ich wlasności MA2A_W10, MA2A_K05, MA2A_W06 Activity during classes,
Test,
Oral answer
FLO matrix in relation to forms of classes
MLO code Student after module completion has the knowledge/ knows how to/is able to Form of classes
Lecture
Audit. classes
Lab. classes
Project classes
Conv. seminar
Seminar classes
Pract. classes
Zaj. terenowe
Zaj. warsztatowe
Others
E-learning
Social competence
M_K001 umie ocenić stopień zrozumienia przez siebie problemu i brakujące elementy rozumowania + + - - - - - - - - -
Skills
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 + + - - - - - - - - -
Knowledge
M_W001 zna podstawowe pojęcia i struktury matematyczne stosowane w teorii języków formalnych i automatów + + - - - - - - - - -
M_W002 zna klasy języków wystepujace w hierarchii Chomsky’ego i ich wlasnosci + + - - - - - - - - -
M_W003 zna klasy automatów i gramatyk odpowiadające klasom języków hierarchii Chomsky’ego oraz ich wlasności + + - - - - - - - - -
Module content
Lectures:
  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.
Auditorium classes:
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.

Student workload (ECTS credits balance)
Student activity form Student workload
Summary student workload 103 h
Module ECTS credits 4 ECTS
Participation in lectures 30 h
Realization of independently performed tasks 20 h
Participation in auditorium classes 30 h
Preparation for classes 14 h
Contact hours 5 h
Examination or Final test 4 h
Additional information
Method of calculating the final grade:

zaliczenie

Prerequisites and additional requirements:

Prerequisites and additional requirements not specified

Recommended literature and teaching resources:
  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
Scientific publications of module course instructors related to the topic of the module:

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

Additional information:

None