Výpočet topologického stupně spojitého zobrazení (diplomová práce)

Úkolem práce je optimalizovat a implementovat už existující algoritmus na výpočet topologického stupně zobrazení. Student se seznámí se základy geometrie a výpočetní topologie a s některými jejich aplikacemi, především pro algoritmické řešení soustav nelineárních rovnic a výpočet pevných bodů funkce. Student také do hloubky porozumí odpovědi na následující otázky:     Jak souvisí existence řešení dvou rovnic o dvou neznámých s omotáváním provázku kolem jednoho bodu v rovině?     Jaká je vícerozměrná analogie? Jednoduchá a zcela neoptimalizovaná verze programu je zatím na topdeg.sourceforge.net. Aktuální kód je v jazyce Objective Caml s využitím knihovny smath pro práci s intervalovou aritmetikou, a částmi programu RSolver Stefana Ratschana. Zatím jsme se však u složitějších funkcí nedostali dál než do dimenze asi 10. Algoritmus má potenciál k výrazné optimalizaci. Rád bych ho časem předělal do samostatného a jednodušeji použitelného nástroje který bude nezávislý na RSolveru. Úvodní literatura: John Willard Milnor, Topology from the Differentiable Viewpoint Peter Franek, Stefan Ratschan, Effective Topological Degree Computation Based on Interval Arithmetic Proč programovat topologický stupeň zobrazení? Aplikace jsou v analýze soustav rovnic, vektorových polí na varietách, anebo vlastnostech dynamických systémů. Brouwerova teorie slavila nedávno sté narozeniny.

Robustní kořeny nelineárních soustav (vhodné jako diplomová nebo doktorská práce)

Cílem práce je zdokonalit nástroje pro popis kořenů (t.j. f^-1(0)) funkcí f: X → Rⁿ kde X je kompaktní podmnožina R^m. Tato úloha ve svém speciálním případě zahrnuje řešení n reálnych rovnic o m neznámých. Při studiu robustních vlastností navíc předpokládáme, že funkci f neznáme přesně, ale jenom její aproximaci, která může pocházet z měření anebo odhadů. Funkce může být reprezentována například jako seznam přibližných hodnot ve vrcholech vícerozměrné mřížky.

Kromě řady teoretických analýz pracuji v současné době na praktické implementaci některých algoritmů, které rozpoznají existenci robustních kořenů v určitých případech. (V plné obecnosti jde o nerozhodnutelný problém.)

• Franek P., Krčál M.: Robust satisfiability of systems of equations, Proceedings of ACM-SIAM Symposium of Discrete algorithms, Portland 2014, pp 193--203, preprint arXiv:1402.0858
• Franek P., Krčál M., Cohomotopy groups capture robust properties of zero sets, preprint arXiv:1507.04310.