Západočeská univerzita v Plzni
Fakulta aplikovaných věd
Katedra informatiky a výpočetní techniky
Centrum počítačové grafiky a vizualizace dat

Předmět: KIV/ZPG

ZPG vstupní test

Zadání úlohy: viz příloha č. 1: papers/priloha-1-zadani.pdf

Prohlášení:
Prohlašuji, že všechny použité zdroje jsou řádně citovány 

e-mail studenta: neumann@students.zcu.cz		
		
Jméno a příjmení studenta:

Antonín Neumann	Hodnocení (počet bodů):
	
Datum odevzdání:
30. 9. 2013	Jméno a příjmení vyučujícího:

Podpis studenta:
	Podpis vyučujícího:

 1.	Úvod
Úkolem bylo nalézt optimalizované řešení, oproti řešení tzv. metodou „Brute force“, pro vykreslení úplné grafu. Minimalizovat se měl pohyb z jednoho bodu do jiného kdy nedochází ke kreslení hrany mezi dvěma vrcholy.
 2.	Známé metody
Brute force – metoda hrubé síly
Při použití této metody vždy z jednoho bodu povedeme hrany do všech ostatních bodů a metodou Move() se opět vrátíme do výchozího bodu. V bodě do kterého vykreslíme hranu jako poslední zůstaneme a následně z něj povedeme hrany opět do všech ostatních vrcholů.
 3.	Navrhovaná modifikace, metoda
 3.1.	Rozdělíme si problém na dva podproblémy. Jeden pro lichá čísla a jeden pro sudá a každý tento podproblém budeme implementovat zvlášť.
 3.2.	Algoritmus pro lichá čísla
Tento algoritmus začne z výchozího bodu kreslit hranu délky 1, následně hranu délky 2, atd. A to až do maximální délky hrany (N - 1) / 2, poté začneme kreslit opět hranu délky 1.
Při tomto algoritmu nedochází k žádnému přesunu (použití funkce Move()) pro žádná   lichá čísla.
 3.3.	Algoritmus pro sudá čísla
Algoritmus pro sudá čísla funguje na principu „od nejdelší po kratší“, tedy nejprve z výchozího bodu kreslíme nejdelší možnou hranu (tj. N / 2) a tuto hranu zkoušíme vykreslovat dokud je to možné. Pokud již není možné z daného bodu vykreslit hranu o délce (N / 2), přejdeme ke kreslení hrany délky (N / 2) - 1. Takto postupujeme až dokud není možné hranu o nějaké délce vykreslit.
 3.3.1.	Pokud vykreslíme hranu o jakékoli délce, v následujícím kroku zkoušíme vykreslit opět největší možnou délku hrany (tj. N / 2).
 3.3.2.	Jestliže snížíme délku hrany až na 0 znamená to, že z daného bodu jsme již vykreslili všechny hrany a musíme se posunout. Posunujeme se do prvního volného bodu v protisměru hodinových ručiček.
 4.	Porovnání 
 4.1.	Pro porovnání si vybereme metodu brutální síly, jelikož jsme o toto porovnání byli požádáni v zadání práce.
 4.2.	Experiment bude probíhat porovnáním přesunů u metody hrubé síly a námi navrhovaného algoritmu.
Algoritmus hrubé síly, má počet potřebných přesunů k realizovaní úplného grafu dán vzorcem .
Počet přesunů u námi navrhovaného algoritmu počítáme tak, že při každém volání metody Move() přičteme 1 k definovanému čítači.
 4.3.	Porovnáním výše zmíněných metod, jsme zjistili, že námi navrhovaný algoritmus pro optimalizaci přesunů je mnohonásobně rychlejší než metoda hrubé síly.

 4.4.	Závislost počtu přesunů P na počtu bodů N
Z této závislosti je patrná lineární závislost mezi počtem přesunů (voláním metody Move()) a počtem bodů grafu.
 4.5.	Závislost námi navrženého optimálního algoritmu s algoritmem hrubé síly.
Závislost mezi algoritmy je dána vztahem.
Z grafu opět vyplývá, že závislost mezi algoritmy je lineární.

 5.	Závěr 
Dle dostupných zdrojů a společné debaty na cvičení předmětu jsme dospěli k závěru, že námi implementovaný algoritmus je optimální pro počet přesunů.
Ovšem zcela jistě by šla optimalizovat časová i paměťová náročnost implementace algoritmu.
 6.	Literatura
Publikace WEB
[Wiki00a] Mnohoúhelník: Vlastnosti pravidelného mnohoúhelníku. Wikipedie [online]. 19. 7. 2013 [cit. 2013-09-30]. Dostupné z: https://cs.wikipedia.org/wiki/Mnohoúhelník 
[Wiki01a] Pohyb po kružnici: Poloha hmotného bodu při pohybu po kružnici v kartézské soustavě souřadnic. Wikipedie [online]. 13. 5. 2013 [cit. 2013-09-30]. Dostupné z: https://cs.wikipedia.org/wiki/Pohyb_po_kru%C5%BEnici