Module also offered within study programmes:
General information:
Name:
INTRODUCTION TO SYMBOLIC DYNAMICS
Course of study:
2019/2020
Code:
AMAT-2-018-MZ-s
Faculty of:
Applied Mathematics
Study level:
Second-cycle studies
Specialty:
Mathematics in Management
Field of study:
Mathematics
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)
Module summary

Dynamika symboliczna. Języki dynamiczne. Kombinatoryka.

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ę MAT2A_K06 Examination
Skills: he can
M_U001 Potrafi samodzielnie zilustrować różne typy dynamiki poprzez konstrukcję odpowiednich przesunięć MAT2A_W07, MAT2A_U16, MAT2A_W08 Examination,
Activity during classes
M_U002 Potrafi wskazać związki pomiędzy rodzajami zachowań dynamicznych a typami języków dynamicznych. MAT2A_U20, MAT2A_W09, MAT2A_U06, MAT2A_W07, MAT2A_W10, MAT2A_W08 Examination,
Activity during classes
Knowledge: he knows and understands
M_W001 Zna podstawowe pojęcia dynamiki symbolicznej MAT2A_W09, MAT2A_W07, MAT2A_U16, MAT2A_W10, MAT2A_W08 Examination,
Activity during classes
M_W002 Zna problematykę, charakteryzacje i własności przesunięć typu skończonego i możliwości zastosowań MAT2A_W09, MAT2A_W07, MAT2A_W10, MAT2A_W08 Examination,
Activity during classes
M_W003 Zna problematykę, charakteryzacje i własności języków dynamicznych MAT2A_W09, MAT2A_W07, MAT2A_U13, MAT2A_U11, MAT2A_W10, MAT2A_W08 Examination,
Activity during classes
M_W004 Zna problematykę, charakteryzacje i własności przesunięć typu sofic i możliwości zastosowań MAT2A_W09, MAT2A_U06, MAT2A_W07, MAT2A_U18, MAT2A_U16, MAT2A_W10, MAT2A_W08 Examination,
Activity during classes
M_W005 Zna problematykę, własności przesunięć podstawieniowych i możliwości zastosowań MAT2A_W09, MAT2A_U06, MAT2A_W07, MAT2A_U18, MAT2A_U16, MAT2A_W10, MAT2A_W08 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 przesunięć + + - - - - - - - - -
M_U002 Potrafi wskazać związki pomiędzy rodzajami zachowań dynamicznych a typami języków dynamicznych. + + - - - - - - - - -
Knowledge
M_W001 Zna podstawowe pojęcia dynamiki symbolicznej + + - - - - - - - - -
M_W002 Zna problematykę, charakteryzacje i własności przesunięć typu skończonego i możliwości zastosowań - + - - - - - - - - -
M_W003 Zna problematykę, charakteryzacje i własności języków dynamicznych + + - - - - - - - - -
M_W004 Zna problematykę, charakteryzacje i własności przesunięć typu sofic i możliwości zastosowań + + - - - - - - - - -
M_W005 Zna problematykę, własności przesunięć podstawieniowych i możliwości zastosowań + + - - - - - - - - -
Student workload (ECTS credits balance)
Student activity form Student workload
Summary student workload 150 h
Module ECTS credits 6 ECTS
Udział w zajęciach dydaktycznych/praktyka 60 h
Preparation for classes 33 h
Realization of independently performed tasks 50 h
Examination or Final test 2 h
Contact hours 5 h
Module content
Lectures (30h):
  1. PL

    1. Dynamika symboliczna, przestrzenie przesunięć – układy dynamiczne. Przykłady.

    2. Przesunięcia – definicje równoważne; aspekty kombinatoryczne; topologia metryczna. Języki przsunięć. Przykłady i zastosowania.

    3. Języki dynamiczne; język słów zabronionych. Języki i grafy. Twierdzenie o charakteryzacji przesunięcia poprzez język. Przykłady.

    4. Przesunięcie skończonego typu. Reprezentacja grafowa. Macierz grafu. Języki przesunięć skończonych. Twierdzenie o przesunięciach określonych przez grafy i macierze. Sprzężenie. Przykłady.

    5. Przesunięcia typu sofic. Reprezentacja grafowa. Nieredukowalność. Prezentacje minimalne. Języki przesunięć typu sofic. Charakteryzacja przesunięcia typu sofic przez faktor typu skończonego. Przykłady.

    6. Przesunięcia podstawieniowe. Przegląd wybranych przesunięć i ich własności

  2. EN

    Symbolic dynamics is a rapidly growing part of dynamical systems. Although it originated as a method to study general dynamical systems, the techniques and ideas have found significant applications, for example in data storage and transmission as well as linear algebra. The lecture is an attempt to present basic notions and problems of the theory, focusing on combinatorial aspects of the field.

    1. Symbolic dynamics; shift spaces – dynamical systems. Examples.

    2. Shifts – various equivalent definitions; combinatorial aspects; metric on words. Shift languages. Examples and applications.

    3. Dynamical languages; languages of forbidden words. Languages and graphs – Theorem. Examples.

    4. Shifts of finite type. Graph presentation. Matrices and graphs. Languages of shifts of finite type. Theorems on shifts defined by graphs and matrices. Conjugacy. Examples

    5. Sofic shifts. Graph presentation. Matrices and graphs. Non-reducubility. Minimal presentations. Languages os sofic shifts. Characterization by factors of finite type. Examples

    6. Substitution shifts. Properties. Examples.

Auditorium classes (30h):
-//-
Additional information
Teaching methods and techniques:
  • Lectures: 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ń.
  • Auditorium classes: 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:

Warunkiem dopuszczenia do egzaminu jest uzyskanie oceny pozytywnej z ćwiczeń (w przypadku braku zaliczenia z ćwiczeń w pierwszym terminie, student ma prawo do dwóch zaliczeń poprawkowych, których sposób przeprowadzenia ustala osoba prowadząca ćwiczenia).

Participation rules in classes:
  • Lectures:
    – Attendance is mandatory: Yes
    – Participation rules in classes: 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.
  • Auditorium classes:
    – Attendance is mandatory: Yes
    – Participation rules in classes: 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ęć.
Method of calculating the final grade:

Ocena końcowa (OK) jest oceną biorącą pod uwagę ocenę z ćwiczeń i egzaminu pisemnego

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

Student powinien zgłosić się do prowadzącego w celu ustalenia indywidualnego sposobu nadrobienia zaległości.

Prerequisites and additional requirements:

licencjat

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.

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 CA 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. M. Foryś,On the Growth Rate of Words in Generalized Thue-Morse Sequence, Int. J. Comp. Math., 91(8) (2014), 1627-1634

4. M. Foryś,On sequence entropy of Thue-Morse shift, Schedae Inf., Vol.22, pp.19-25, 2013

Additional information:

Przedmiot może być prowadzony w języku angielskim.