témata diplomových a doktorských prací:
Efektivita algoritmů komprese dat na procesech s nulovou entropií
Univerzální kódy komprese dat jako je Ziv-Lempelův kód mají vlastnost,
že délka kódu slova je asymptoticky úměrná délce tohoto slova.
Konstantou úměrnosti je přitom entropie daného (ergodického)procesu.
Tento vztah platí i pro procesy s nulovou entropií, zde však
vzniká otázka po jemnější klasifikaci této (sublineární) závislosti.
Cílem práce je najít odhady závislosti délky kódu na délce slova pro některé
procesy (posuny) s nulovou entropií, jako jsou Sturmovské nebo substituční
systémy.
Literatura
Petr Kůrka: Entropie, informace, kódování, studijní text,
http://www.cts.cuni.cz/~kurka/studij.html
Svazy atraktorů dynamických systémů
Systém všech atraktorů daného dynamického systému uspořádaný inkluzí tvoří
svaz s maximálním prvkem, ve kterém je spojení sjednocení a průsek
je podmnožinou průniku. Cílem práce je najít nutné nebo postačující
podmínky pro to aby svaz byl svazem atraktorů. Speciální pozornost bude
věnována svazům atraktorů celulárních automatů.
Literatura:
Petr Kůrka: Cellular automata with infinite number of subshift attractors,
submitted
Univerzální regulární dynamické systémy
Dynamický systém je regulární, pokud každý konečný rozklad
stavového prostoru (na obojetné množiny) určuje regulární
množinu slov přechodů mezi těmito třídami rozkladu. Regulární
systém je univerzální, lze-li z něj každý regulární systém
sestrojit faktorizací. Cílem práce je popsat strukturu a
dynamické vlastnosti univerzálních systémů.
Literatura:
Petr Kůrka: Zero-dimensional dynamical systems, formal languages,
and universality, Theory of Computing Systems 32, 423-433 (1999)
Charakteristiky substitutivních dynamických systémů
Substituce je morfismus monoidu slov, která má pevné nekonečné
skoroperiodické slovo. Například Morseova substituce m(0)=01,
m(1)=10 má pevné slovo 0110 1001 1001 0110... Cílem práce
je analyzovat časovou složitost algoritmů které počítají
určité charakteristiky takových substitucí.
Literatura:
Petr Kůrka: Local return rates in substitutive subshifts. Acta Universitatis
Carolinae - Mathematica et Physica Vol. 44, No. 2, 29-42 (2003)
probíhající diplomové práce:
Dynamika v prostoru borelovských měr.
Ergodický atraktor dynamického systému (tj. spojitého zobrazení
na kompaktním metrickém prostoru) je podmnožina prostoru borelovských
měr daného stavového prostoru, která atrahuje všechny ergodické míry ze
svého okolí. Cílem práce je charakterizace ergodických atraktorů
celulárních automatů a nalezení podmínek, za kterých je ergodický atraktor
sjednocení konečně mnoha signálních posunů.
Literatura:
Petr Kůrka: On the measure attractor of a cellular automaton.,
Discrete and Continuous Dynamical systems, Supplement volume 2005,
pp 524-535.
Ljapunovské funkce celulárních automatů
Ljapunovské funkce přiřazují váhy určitým slovům dané abecedy
tak, že při časovém vývoji celulárního automatu celková váha
konfigurace neroste. Cílem práce je konstrukce heuristických
algoritmů na hledání Ljapunovských funkcí.
Literatura:
Petr Kůrka: Cellular automata with vanishing particles,
Fundamenta Informaticae 58, 203-221 (2003)