navigation
hledat
Rozdíly
Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
|
courses:a4m39vge [2015/01/14 11:34] smrceant [Zkouška] |
courses:a4m39vge [2025/01/03 18:23] (aktuální) |
||
|---|---|---|---|
| Řádek 69: | Řádek 69: | ||
| = Písemná = | = Písemná = | ||
| - | ** 2.termín (8.1.2015), evidentně stejné jako 2.termín 2014!** ** | + | ** 2.termín (8.1.2015), evidentně stejné jako 2.termín 2014! ** |
| - Paměťová složitost arrangementu přímek. Odpověď rozdělit na pam. slož. pro frontu událostí, stav podél sweep line. Výsledek vysvětlit. (3b) | - Paměťová složitost arrangementu přímek. Odpověď rozdělit na pam. slož. pro frontu událostí, stav podél sweep line. Výsledek vysvětlit. (3b) | ||
| - Navrhnout algoritmus: Pro DCEL a půlhranu vypíše koncové body všech půlhran, které vychází ze stejného počátečního vrcholu. Deklarujte datové struktury pro DCEL, dat. struk. pro běh algoritmu. Napsat pseudokód, napsat jeho složitost. (7b) | - Navrhnout algoritmus: Pro DCEL a půlhranu vypíše koncové body všech půlhran, které vychází ze stejného počátečního vrcholu. Deklarujte datové struktury pro DCEL, dat. struk. pro běh algoritmu. Napsat pseudokód, napsat jeho složitost. (7b) | ||
| Řádek 80: | Řádek 80: | ||
| ** 3.termín (14.1.2015), ústní cca za 3h od skončení písemné ** | ** 3.termín (14.1.2015), ústní cca za 3h od skončení písemné ** | ||
| - | - DCEL: máme zadanou stěnu, napsat algoritmus který vypíše všechny hrany, které s ní incidují. Datové struktury DCEL, složitost algoritmu. | + | - DCEL: máme zadanou stěnu, napsat algoritmus který vypíše všechny hrany, které incidují z vrcholů této stěny. Datové struktury DCEL, složitost algoritmu. (10b) |
| - | - Datová struktura u Overmars algoritmu - popsat | + | * POZOR, algoritmus který obejde stěnu a vypíše hrany které jí tvoří nestačí - to bylo hodnoceno 5b. |
| - | - 3 případy které můžou nastat při vkládání do Trapezoidal Map. Nakreslit, popsat jak se změní point location struktura. | + | - Datová struktura u Overmars algoritmu - popsat (4b) |
| - | - Navrhnout algoritmus, který v arrangementu každé úsečce přiřadí číslo od 0 do n-1, které vyjadřuje, kolik přímek je nad ní. Vyjdetě z (nějakého podobného) existujícího algoritmu. | + | - 3 případy které můžou nastat při vkládání do Trapezoidal Map. Nakreslit, popsat jak se změní point location struktura. (6b) |
| - | - Interval tree pro 6 segmentů | + | - Navrhnout algoritmus, který v arrangementu každé úsečce přiřadí číslo od 0 do n-1, které vyjadřuje, kolik přímek je nad ní. Vyjdetě z (nějakého podobného) existujícího algoritmu. (9b) |
| - | - Definice D-simplexu | + | - Interval tree pro 6 segmentů (3b) |
| - | - Co je to graf konfliktů, co je v něm na začátku, co je v něm na konci, co umožňuje | + | - Definice D-simplexu (1b) |
| - | - Vzorec pro maximální počet oblouků u Fortune Sweep Algoritmu a nakreslit takový případ | + | - Co je to graf konfliktů, co je v něm na začátku, co je v něm na konci, co umožňuje (4b) |
| + | - Vzorec pro maximální počet oblouků u Fortune Sweep Algoritmu a nakreslit takový případ (3b) | ||
| = Ústní = | = Ústní = | ||
| Řádek 95: | Řádek 96: | ||
| - Dual graf pro Voronoi diagram, Delaunay graf, legalizace hrany | - Dual graf pro Voronoi diagram, Delaunay graf, legalizace hrany | ||
| + | == 2015 == | ||
| + | = Písemná = | ||
| + | |||
| + | ** 1.termín (20.1.2016) ** | ||
| + | * Fractional Cascading - popsat, co setri (3 b.) | ||
| + | * Quick Hull - popsat, slozitosti a pripady, kdy k nim dochazi (4 b.) | ||
| + | * Sweep Line algoritmus pro ziskani pruseciku usecek - nakreslit pripad, kdy v jednom bode nekolik usecek konci, zacina a bodem prochazi, jak se tento pripad osetri (6 b.) | ||
| + | * Arrangement - oznacit hrany cislem, ktere znamena pocet primek nad hranou (neco s hladinou - level, doplnte, tohle jsem netusil) (9 b.) | ||
| + | * Interval Tree - dany nakreslene intervaly, udelat k nim interval tree (jako obr. 10.3, str. 223 v de Bergovi 3rd ed.) (3 b.) | ||
| + | * Definice planarniho deleni (2 b.) | ||
| + | * Test pruniku intervalu - dany dva intervaly (x1, y1), (x2, y2), napsat kod podminky, ktera zjisti, zda se protinaji (2 b.) | ||
| + | * Konstrukce Trapezoidove mapy, cim je zajisteno, aby pruchod byl O(log n) (2 b.) | ||
| + | * DCEL - nadefinovat struktury a pak napsat kod, ktery pro danou plosku vypise vsechny plosky, ktere s ni sousedi (pres hranu nebo bod vstupni plosky), nevadi, pokud se nejaka ploska vypise vickrat (9 b.) | ||
| + | |||
| + | ** 2.termín (27.1.2016) ** | ||
| + | * Maximální počet hran v arrangementu přímek - odvodit složitost. (2b) | ||
| + | * Monotenizace polygonu - popsat algoritmus. (4b) | ||
| + | * Vytvořit segment tree pro 6 úseček. (5b) | ||
| + | * DCEL - vypsat součet délek hran které incidují se stěnou. (7b) | ||
| + | * Algoritmus DeWall - k čemu slouží, jak nalezne první trojúhelník. (3b) | ||
| + | * Popsat algoritmus sweep line úseček. (8b) | ||
| + | * Vysvětlit princip Priority Search Tree a jak se v něm hledá. (6b) | ||
| + | * Metoda rozděl a panuj - vysvětlit, odůvodnit složitosti, včetně složitosti hledání sešívacích čar. (5b) | ||
| + | |||
| + | = Ústní = | ||
| + | * Konvexni obalky - jake znam algoritmy, jejich slozitosti, pouzitelnost ve 3D, paralelizovatelnost | ||
| + | * Dualita - v cem spociva, jak se da vyuzit; mluvil jsem o vypoctu kolinearity bodu, ze jde vypocist prevedenim do dualniho prostoru a vypoctem pruseciku, kdyz se to pocita normalne, tak je to O(n^3), takhle O(n^2) | ||
| + | * Duální struktura k Voronoi Diagramu - co to je apod., nakreslit příklad, legalizace hrany, ... | ||
| + | * Trapezoid maps - co to je, porovnat s metodou pásů - chtěl hlavně kombinatorickou složitost porovnat, PŘESNĚ zdůvodnit paměťové nároky | ||
| ===== Literatura ===== | ===== Literatura ===== | ||
| [[http://www.scribd.com/doc/7619913/Computational-Geometry-Algorithms-and-Applications-2d-Ed-De-Berg|Computational geometry: algorithms and applications ]] | [[http://www.scribd.com/doc/7619913/Computational-Geometry-Algorithms-and-Applications-2d-Ed-De-Berg|Computational geometry: algorithms and applications ]] | ||
| ~~DISCUSSION~~ | ~~DISCUSSION~~ | ||
