============================================
               Projekty k zápočtu z Geometrických algoritmů
               ============================================ 

Poslední změna: 6.5.1996

Zásady
------

U jednotlivých zadání je uveden maximální počet studentů, kteří se mohou
práce na příslušném projektu účastnit. Prosím zájemce, aby se u mne ohlásili
(nejlépe e-mailem), jejich jména pak uvedu přímo u zadání (bude k nalezeni
na www.math.muni.cz, lepe primo
file://ftp.math.muni.cz/pub/math/poeple/Slovak/lectures/geometricke.algoritmy/projekty.txt). 
Stejný projekt může být zadán i vícekrát (posoudím individuálně).
Pokud někdo přijde s vlastním návrhem projektu týkajícím se dané
problematiky, uvítám to. 

Projekt musí být dokončen před zkouškou kteréhokoliv z účastníků.
Řešení musí být běhu schopné a opatřené stručným popisem tak, abych byl i já
schopen vypracování samostatně prověřit. (Za ideální považuji popis formou
zápisníku MAPLE s příkladem použití.) Součástí zkoušky bude předvedení
řešení (z konzoly mého PC s Linuxem) a udělení zápočtu (za oba semestry).

Vše by mělo být použitelné v rámci systému MAPLE. Buď můžete přímo psát
procedury ve vnitřním jazyku MAPLE, nebo můžete vytvořit samostatně běžící
procedury, ty však opatřte obslužnými procedurami v MAPLE, které umožní
konverzi vstupu a spuštění přímo z MAPLE (jako nezávislého procesu).
Uvítám, když každá úloha bude řešena oběma způsoby (nezávisle).
(V případě, že se někdo chce seznámit s jiným/mi systémy pro CAM, doporučuji
Axiom nebo Mathematica, případně MuPAD. Informace lze získat u mne, přístup
ke stroji s instalací příslušného software lze zajistit.)

Pro unifikaci vstupních a výstupních dat doporučuji použití standardů
použitých v knihovnách geometry a geom3d systému MAPLE (případně pro vyšší
účinnost jinak, ale doplněné vstupní/výstupní konverzí). Vždy uvítám
návaznost na grafické zobrazení výsledku a test dosažené časové složitosti.

Zadání se člení na dva typy.


1. Využití již připravených procedur v MAPLE a příprava 'zápisníků' s
   přehledy využití
---------------------------------------------------------------------

Výsledkem projektu musí být 'pedagogicky použitelný' zápisník pro
samostatné seznámení hypotetického studenta s problematikou

1.1. Provázání balíku geometry (výběr několika vhodných procedur)
     s grafickými procedurami MAPLE a ukázky použití pro polynomiálně zadané
     objekty.
              
     1 řešitel: Petr Kunc
                
1.2. Provázání balíku geom3d (výběr několika vhodných procedur)
     s grafickými procedurami MAPLE a ukázky použití pro polynomiálně zadané
     objekty.

     1 řešitel: Zdeněk Kabeláč

1.3. Statistické testování počtů hran v konvexních obalech v závislosti na
     rozdělení bodů a tvaru oblasti (s použitím balíků stats a geometry).

     1 řešitel: 

1.4. Předvedení balíku grobner a ukázky vhodných aplikací základních
     procedur.

     1 řešitel: Petr Havlík
     1 řešitel: J. Pavlinak

1.5. Vytvoření knihovny 'hezkých' obrázků afinních variet v dimenzi 2 a 3.

     1 řešitel: Mirka Misáková

2. Vlastní tvorba procedur
--------------------------
(uvítám spolupráci všech řešitelů při tvorbě 'základních kostek' jako práce se
stromy apod.)

2.1. Sestrojení hierarchických vyvážených reprezentací konvexních
     mnohoúhelníků a využití k testům incidence a průniků.

     1 řešitel: Honza Pazdziora


2.2. Konvexní obal v rovině, algoritmus Graham's scan.

     1 řešitel: Zdenek Riha
     1 řešitel: Tibor Kalman

2.3. Konvexní obal v rovině, metoda 'rozděl a panuj'.

     1 resitel:  David Smahel

2.4. Konvexní obal a konvexní vrstvy v rovině, algoritmus 'balení balíčku'.

     2 řešitelé: Michael Mraka, Eva Žáčková

2.5. Implementace základního algoritmu pro Voronoiho (Voroného) diagramy.

     1 řešitel: Tomas Telecky 

2.6. Použití hotových procedur z 2.5 pro implementaci diagramů vyšších řádů.
     (po dohodě s řešiteli 2.5 nebo použití loňského projektu)

     2 řešitelé: Mikulas Lengyelfalusy, Miroslav Soja

2.7. Použití hotových procedur z 2.5 ke konstrukci Delaneyovy triangulace a
     využití pro grafy funkcí dvou proměnných zadaných na nepravidelné síti.
     (nebo použití loňského projektu)

     1 řešitel: Jan Struhar

2.8. Použití hotových procedur z 2.5 ke konstrukci diagramů 'v řece'.
     (nebo použití loňského projektu)

     1 řešitel: Richard Nikel

2.9. Implementace postupu pro triangulaci obsahující zadané hrany.

     2 řešitelé: David Kostal, Hana Starostova

2.10.Nalezení jádra jednoduchého mnohoúhelníku.

     1 řešitel: Richard Botik

2.11.Obvod a plocha sjednocení obdélníků.

     1 řešitel: Jan Stambera


2.12.Implementace obecného monomiálního uspořádání a příslušného algoritmu
     pro dělení se zbytkem v okruhu polynomu více proměnných, pbecný
     algoritmus pro Groebnerovu bazi  (s využitím Bulantova projektu z
     loňského roku)

     1 řešitel: Lukas Abram

2.13.Implementace procedur pro nalezení singularit křivek a obálek systémů
     křivek (s využitím knihovny grobner), vítáno doplnění grafickým
     výstupem.

     1 řešitel: Lenka Ulrichova 

2.14.Implementace procedur pro nalezení tečných kuželů křivek (s využitím
     knihovny grobner), grafické znázornění

     1 řešitel: Oto Buchta

2.15.Důkazy geometrických tvrzení pomocí techniky Groebnerových bazí.
     (Výběr tvrzení volný, nebo na požádání dodám)
    
     1 řešitel: Michal Fikera


Další rozšiřování pravděpodobné.