Module also offered within study programmes:
General information:
Name:
On some models of discrete mathematics
Course of study:
2019/2020
Code:
ZSDA-3-0134-s
Faculty of:
Szkoła Doktorska AGH
Study level:
Third-cycle studies
Specialty:
-
Field of study:
Szkoła Doktorska AGH
Semester:
0
Profile of education:
Academic (A)
Lecture language:
Polski i Angielski
Form and type of study:
Full-time studies
Course homepage:
 
Responsible teacher:
dr hab. Foryś Wit (foryswit@wms.mat.agh.edu.pl)
Dyscypliny:
matematyka, nauki fizyczne
Module summary

Zajęcia prezentują wybrane modele matematyki dyskretnej, a mianowicie:
1. automaty skończenie stanowe i aktualne problemy tej teorii
2. sieci Petriego i możliwości ich zastosowań
3. automaty komórkowe
4. przesunięcia (shifty) – modele dynamiki symbolicznej

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: is able to
M_K001 Potrafi samodzielnie wykorzystać wyszukaną przez siebie literaturę SDA3A_K01, SDA3A_K02 Examination,
Activity during classes
Skills: he can
M_U001 Potrafi samodzielnie zilustrować różne typy dynamiki poprzez konstrukcję odpowiednich modeli SDA3A_U01 Examination,
Activity during classes
M_U002 Potrafi wskazać związki pomiędzy rodzajami zachowań dynamicznych a poznanymi modelami SDA3A_U02, SDA3A_U01 Examination,
Activity during classes
Knowledge: he knows and understands
M_W001 Zna modele matematyczne prezentowane na wykładzie SDA3A_W02 Examination
M_W002 Zna problematykę, charakteryzacje i własności automatów skończonych, automatów ze stosem i możliwości ich zastosowań SDA3A_W01 Examination,
Activity during classes
M_W003 Zna problematykę, charakteryzacje i własności sieci Petriego oraz możliwości ich zastosowań SDA3A_W01 Examination,
Activity during classes
M_W004 Zna problematykę, charakteryzacje i własności automatów komórkowych i możliwości zastosowań SDA3A_W01 Examination,
Activity during classes
M_W005 Zna problematykę, własności przesunięć podstawieniowych i typu sofic oraz możliwości zastosowań SDA3A_W01 Examination,
Activity during classes
Number of hours for each form of classes:
Sum (hours)
Lecture
Audit. classes
Lab. classes
Project classes
Conv. seminar
Seminar classes
Pract. classes
Zaj. terenowe
Zaj. warsztatowe
Prace kontr. przejść.
Lektorat
60 30 30 0 0 0 0 0 0 0 0 0
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
Prace kontr. przejść.
Lektorat
Social competence
M_K001 Potrafi samodzielnie wykorzystać wyszukaną przez siebie literaturę + + - - - - - - - - -
Skills
M_U001 Potrafi samodzielnie zilustrować różne typy dynamiki poprzez konstrukcję odpowiednich modeli + + - - - - - - - - -
M_U002 Potrafi wskazać związki pomiędzy rodzajami zachowań dynamicznych a poznanymi modelami + + - - - - - - - - -
Knowledge
M_W001 Zna modele matematyczne prezentowane na wykładzie + + - - - - - - - - -
M_W002 Zna problematykę, charakteryzacje i własności automatów skończonych, automatów ze stosem i możliwości ich zastosowań + + - - - - - - - - -
M_W003 Zna problematykę, charakteryzacje i własności sieci Petriego oraz możliwości ich zastosowań + + - - - - - - - - -
M_W004 Zna problematykę, charakteryzacje i własności automatów komórkowych i możliwości zastosowań + + - - - - - - - - -
M_W005 Zna problematykę, własności przesunięć podstawieniowych i typu sofic oraz możliwości zastosowań + + - - - - - - - - -
Student workload (ECTS credits balance)
Student activity form Student workload
Summary student workload 122 h
Module ECTS credits 4 ECTS
Udział w zajęciach dydaktycznych/praktyka 60 h
Preparation for classes 25 h
przygotowanie projektu, prezentacji, pracy pisemnej, sprawozdania 15 h
Realization of independently performed tasks 2 h
Examination or Final test 20 h
Module content
Lectures (30h):
  1. modele dyskretne I – automaty skończone

    1. Automaty skończenie stanowe, automaty ze stosem – procesy modelowane tymi automatami, własności, problem synchronizacji, przykłady zastosowań
    2. Hipoteza Cernego,
    3. Road coloring problem

  2. modele dyskretne II – sieci Petriego

    4. Sieci Petriego – modelowanie procesów równoległych.
    5. Analiza sieci Petriego; równania stanu; warunki typu wkw gwarantujące określone własności dynamiczne
    6. Klasyfikacja sieci Petriego;
    7. Sieci Petriego – modelowanie, analiza i zarządzanie systemami produkcyjnymi -case study

  3. modele dyskretne III – automaty komórkowe

    8. Automaty komórkowe – procesy modelowane tymi automatami
    9. Automaty komórkowe 0 wymiarowe; entropia Shannona; funkcja Ulama
    10. Automaty komórkowe 1 wymiarowe; prawa jako jądro konwolucji; przykłady
    11. Automaty komórkowe 2 wymiarowe; ”The game of live”

  4. modele dyskretne IV – dynamika symboliczna

    12. dynamika symboliczna, własności kombinatoryczne, topologiczne, entropia
    13. Przesunięcia (shift) – definicje równoważne; aspekty kombinatoryczne; topologia metryczna. Języki przesunięć. Przykłady i zastosowania.
    14. Przesunięcia typu sofic. Reprezentacja grafowa. Nieredukowalność. . Przesunięcia podstawieniowe. Własności.

Auditorium classes (30h):
modele dyskretne I, II, III, IV

ćwiczenia są powiazane z wykładem i obejmują te same tematy.

Additional information
Teaching methods and techniques:
  • Lectures: wyklad z wykorzystaniem technik i metod multimedialnych.
  • Auditorium classes: praca nad wskazaną literaturą - wspólna z wykładowcą.
Warunki i sposób zaliczenia poszczególnych form zajęć, w tym zasady zaliczeń poprawkowych, a także warunki dopuszczenia do egzaminu:

egzamin – egzamin ustny lub przygotowanie projektu pisemnego (do wyboru)
ćwiczenia – aktywność; ocena opracowanego problemu

Participation rules in classes:
  • Lectures:
    – Attendance is mandatory: Yes
    – Participation rules in classes: Ocena końcowa (OK) jest oceną z egzaminu / średnią ocen z ćwiczeń i egzaminu (gdy uruchomione są ćwiczenia)
  • Auditorium classes:
    – Attendance is mandatory: Yes
    – Participation rules in classes: opracowywanie zadanych problemów - projektów indywidualnie lub w grupach
Method of calculating the final grade:

Ocena końcowa (OK) jest oceną z egzaminu / średnią ocen z ćwiczeń i egzaminu (gdy uruchomione są ćwiczenia)

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

konsultacje w ustalonym terminie; kontakt mailowy.

Prerequisites and additional requirements:

Ukończenie studiów I i II stopnia

Recommended literature and teaching resources:

1. D. Lind and B. Marcus, An introduction to symbolic dynamics
and coding, Cambridge University Press, Cambridge, 1995.
2. H. Xie, Gramatical Complexity and One-dimensional Dynamical
Systems, Directions in Chaos. World Scientific, Singapore, 1996.
3. P. Kurka, Topological and symbolic dynamics, Cours
Specialises [Specialized Courses], 11. Societe Mathematique de France, Paris, 2003
4. T.Murata, Petri Nets: Properties, Analysis and Applications, Proceedings of the IEEE, 2000
5. M. Delorme, J. Mazoyer, Cellular Automata: A Parallel Model, Kluwer Academic Publishers,
1999
6. M.Foryś, W.Foryś, Teoria automatów i języków formalnych – AOW EXIT, Warszawa 2005

Scientific publications of module course instructors related to the topic of the module:

1. W.Foryś, P.Oprocha, Infinite traces and symbolic dynamics, Theory of Comp. Systems, 45 (2009) 133-149
2. W.Foryś, J.Matyja, On One-sided, D-chaotic Cellular Automata without Fixed Points, having Continuum of Periodic Points with Period 2 and Topological Entropy log(p) for any Prime p, Entropy, vol. 16, 2014 pp. 5601-5617
3. W. Forys, J. Matyja , On One-sided, Topologically Mixing and Strongly Transitive CA with a Continuum of Period-two Points, Journal of Cellular Automata 11, 399-424, 2016
4. W.Foryś, Asymptotic behaviour of bi-infinite words, RAIRO – Theoretical Informatics and Applications, 38, 2004,pp. 27-48
5. W.Foryś, T.Krawczyk, An algorithmic approach to the problem of a semiretract base, Theoretical Computer Science, vol.369, 2006, pp.314-322
6. W.Foryś, Retractions and retracts of free topological monoids, Intern.J. Comp. Mathematics vol.83, 2006 pp. 21-26

Additional information:

None