Geometrické algoritmy

Tento elektronický učební text byl napsán pro studenty předmětu Geometrické algoritmy, který na Přírodovědecké fakultě a Fakultě informatiky Masarykovy univerzity probíhá od poloviny 90. let 20. století. Tehdy byla počítačová geometrie novým oborem a její první učebnice se teprve začaly objevovat. Jednou z nich byla kniha Computational Geometry, Algorithms and Applications autorů de Berga, van Krevelda, Overmarse a Schwarzkopfa vydaná nakladatelstvím Springer v roce 1997. Kniha se rychle dočkala druhého (v roce 2000) a třetího, přepracovaného vydání (2008). Jako autoři třetího vydání jsou uvedeni de Berg, Cheong, van Kreveld a Overmars. A právě témata a algoritmy z prvé poloviny této knihy jsou obsahem předkládaného učebního textu.

Text je psán s maximální snahou o jednoduchost, srozumitelnost a krátkost. Je doprovázen velkým množstvím obrázků a animací, které mají ilustrovat zaváděné pojmy a popisované algoritmy. Důraz je kladen na myšlenky algoritmů, ty jsou vysvětlovány a ilustrovány dříve, než se začnou popisovat pseudokódy. Pseudokódy algortimů s výjimkou kapitoly 5 jsou převzaty z výše uvedené knihy. Z téhož zdroje je rovněž převzato několik obrázků v kapitolách 2 a 3. Většina obrázků a všechny animace jsou však původní. Předkládaný text nemůže knihu samozřejmě nahradit. V ní totiž čtenář nalezne pro každý algoritmus na začátku kapitoly motivaci a na závěr kapitoly několik aplikací. V textu a v literatuře na jeho konci najde čtenář odkazy na bakalářské a diplomové práce několika mých studentů. V nich jsou uvedeny detailnější popisy některých algoritmů, případně i jejich implementace.

V roce 2017 se předmět Geometrické algortimy začal učit anglicky. V souvislosti s tím vznikla i anglická verze e-learningu. S jejími opravami mi významně pomohl Bc. Tadeáš Kučera. Významnější korekce byly provedeny i v české verzi. Nepochybně však v textu mnohé chyby zůstaly a budu rád, pokud mne čtenář na ně upozorní emailem na adresu cadek@math.muni.cz.

Za realizaci textu jako e-learningu patří mé poděkování pracovníkům Servisního střediska pro e-learning na MU, především panu Jiřímu Bočkovi za pečlivost a trpělivost.

Martin Čadek

K tisku

Skripta ke stažení se připravují

Autoři publikace

	doc. RNDr. Martin Čadek, CSc. Ústav matematiky a statistiky, Přírodovědecká fakulta MU Osobní stránka v IS MU