Moduł oferowany także w ramach programów studiów:
Informacje ogólne:
Nazwa:
Kombinatoryka na słowach / Combinatorics on words
Tok studiów:
2019/2020
Kod:
AMAT-2-011-MI-s
Wydział:
Matematyki Stosowanej
Poziom studiów:
Studia II stopnia
Specjalność:
Matematyka w informatyce
Kierunek:
Matematyka
Semestr:
0
Profil:
Ogólnoakademicki (A)
Język wykładowy:
Polski i Angielski
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ęć

Kombinatoryka na słowach.

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 podstawowe pojęcia i problemy kombinatoryki na słowach MAT2A_W09, MAT2A_W07, MAT2A_U16, MAT2A_W10, MAT2A_W08 Egzamin,
Aktywność na zajęciach
M_W002 Zna problematykę słów bez powtórzeń, w szczególności kombinatoryczne własności słowa Thue-Morse’a i możliwości zastosowań MAT2A_W09, MAT2A_W07, MAT2A_W10, MAT2A_W08 Egzamin,
Aktywność na zajęciach
M_W003 Zna problematykę słów okresowych, homomorfizmów generujących takie słowa i ich zastosowania MAT2A_W09, MAT2A_W07, MAT2A_U13, MAT2A_U11, MAT2A_W10, MAT2A_W08 Egzamin,
Aktywność na zajęciach
M_W004 Zna podstawowe problemy wymiaru i ich zastosowania w kodowaniu MAT2A_W09, MAT2A_U06, MAT2A_W07, MAT2A_U18, MAT2A_U16, MAT2A_W10, MAT2A_W08 Egzamin,
Aktywność na zajęciach
Umiejętności: potrafi
M_U001 Potrafi samodzielnie wykorzystać metody generowania słów okresowych i słów bez powtórzeń MAT2A_W07, MAT2A_U16, MAT2A_W08 Egzamin,
Aktywność na zajęciach
M_U002 Potrafi rozwiązać proste równanie na słowach MAT2A_U20, MAT2A_W09, MAT2A_U06, MAT2A_W07, MAT2A_W10, MAT2A_W08 Kolokwium,
Esej,
Egzamin,
Aktywność na zajęciach
Kompetencje społeczne: jest gotów do
M_K001 Potrafi samodzielnie i zespołowo pracować nad projektem MAT2A_K03 Egzamin,
Aktywność na zajęciach
M_K002 Potrafi samodzielnie wykorzystać znalezioną przez siebie literaturę MAT2A_K06 Egzamin,
Aktywność na zajęciach
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 podstawowe pojęcia i problemy kombinatoryki na słowach + + - - - - - - - - -
M_W002 Zna problematykę słów bez powtórzeń, w szczególności kombinatoryczne własności słowa Thue-Morse’a i możliwości zastosowań + + - - - - - - - - -
M_W003 Zna problematykę słów okresowych, homomorfizmów generujących takie słowa i ich zastosowania + + - - - - - - - - -
M_W004 Zna podstawowe problemy wymiaru i ich zastosowania w kodowaniu + + - - - - - - - - -
Umiejętności
M_U001 Potrafi samodzielnie wykorzystać metody generowania słów okresowych i słów bez powtórzeń + + - - - - - - - - -
M_U002 Potrafi rozwiązać proste równanie na słowach + + - - - - - - - - -
Kompetencje społeczne
M_K001 Potrafi samodzielnie i zespołowo pracować nad projektem + + - - - - - - - - -
M_K002 Potrafi samodzielnie wykorzystać znalezioną przez siebie literaturę + + - - - - - - - - -
Nakład pracy studenta (bilans punktów ECTS)
Forma aktywności studenta Obciążenie studenta
Sumaryczne obciążenie pracą studenta 150 godz
Punkty ECTS za moduł 6 ECTS
Udział w zajęciach dydaktycznych/praktyka 60 godz
Przygotowanie do zajęć 33 godz
Samodzielne studiowanie tematyki zajęć 50 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. PL

    1. Wolne półgrupy i monoidy, słowa, podpółgrupy i podmonoidy,

    2. Wkw na wolny podmonoid, kodowanie – zastosowania

    3. Sprzężenie, szeregi formalne słów

    4. słowa bez kwadratu, słowa nieskończone bez powtórzeń – zastosowania

    5. Słowo Thue-Morse’a; własności kombinatoryczne i inne – zastosowania

    6. Homomorfizmy wolnych monoidów, iteracje, powtarzalność

    7. Słowa okresowe, własności związane z okresowością – zastosowania

    8. Problemy wymiaru – twierdzenie o defekcie – zastosowanie w problemach kodowania

    9. Równania na słowach

    10. Twierdzenie o faktoryzacji (M.P.Schutzenberger)

  2. EN

    Combinatorics on words is a field that has grown separately within several branches of mathematics – for example finite group and/or semigroup theory, probability theory. It appears very frequently in theoretical computer science, especially dealing with formal languages, grammars and automata theory. The lecture is an attempt to present a unified treatment of the theory of combinatorics on words.

    1. Free semigroups and free monoids, words; subsemigroups and submonoids

    2. Free submonoids (subsemigroups); coding – applications

    3. Conjugacy; formal series of words

    4. square-free words, Infinite words with no repetition – applications

    5. Infinite Thue-Morse word; combinatorial properties – applications

    6. Morphisms of free monoids; iteration of a morphism; repetitive morphisms

    7. Periodic words, properties connected with periodicity – applications

    8. Dimension problem – Defect Theorem – application in coding problems

    9. Equations on words

    10. Critical Factorization Theorem (M.P.Schutzenberger)

Ćwiczenia audytoryjne (30h):
-//-
Pozostałe informacje
Metody i techniki kształcenia:
  • Wykład: Wykład jest klasycznym wykładem tablicowym. Mile widziana aktywność studentów podczas wykładu - np. zadawanie pytań wykładowcy.
  • Ć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:

-

Zasady udziału w zajęciach:
  • Wykład:
    – Obecność obowiązkowa: Nie
    – 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:

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.

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

licencjat

Zalecana literatura i pomoce naukowe:

1. M. Lothaire, Combinatorics on words,Cambridge Univ.Press, 1997
2. J.Karhumaki, Combinatorics on words, Univ.Turku, preprint, 2015

Publikacje naukowe osób prowadzących zajęcia związane z tematyką modułu:

• W.Foryś, Asymptotic behaviour of bi-infinite words, RAIRO – Theoretical Informatics and Applications, 38, 2004,pp. 27-48

• W.Foryś, T.Krawczyk, An algorithmic approach to the problem of a semiretract base, Theoretical Computer Science, vol.369, 2006, pp.314-322

• W.Foryś, Retractions and retracts of free topological monoids, Intern.J. Comp. Mathematics vol.83, 2006 pp. 21-26

• M. Foryś,On the Growth Rate of Words in Generalized Thue-Morse Sequence, Int. J. Comp. Math., 91(8) (2014), 1627-1634

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

Informacje dodatkowe:

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