navigation
hledat
Rozdíly
Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
|
courses:a4m39vge [2010/12/19 23:52] petul.ka |
courses:a4m39vge [2025/01/03 18:23] (aktuální) |
||
|---|---|---|---|
| Řádek 1: | Řádek 1: | ||
| - | ====== Název předmětu ====== | + | ====== Výpočetní geometrie ====== |
| - | * Stránky předmětu: http://service.felk.cvut.cz/courses/A4M39VG/ | + | * Stránky předmětu: https://cw.felk.cvut.cz/wiki/misc/projects/oppa_oi_english/courses/ae4m39vg/start |
| * Přednášející: [[http://dcgi.felk.cvut.cz/en/members/felkepet|Petr Felkel]] | * Přednášející: [[http://dcgi.felk.cvut.cz/en/members/felkepet|Petr Felkel]] | ||
| - | * Cvičící: Lukas M. Novosad | + | * Cvičící: Petr Felkel |
| ===== Cvičení ===== | ===== Cvičení ===== | ||
| * [[courses/a4m39vge/uloha1|1. úloha]] | * [[courses/a4m39vge/uloha1|1. úloha]] | ||
| * [[courses/a4m39vge/uloha3|3. úloha]] | * [[courses/a4m39vge/uloha3|3. úloha]] | ||
| + | |||
| Řádek 12: | Řádek 13: | ||
| Na zkoušce se prověřují teoretické znalosti v plném rozsahu odpřednášené a odcvičené látky. | Na zkoušce se prověřují teoretické znalosti v plném rozsahu odpřednášené a odcvičené látky. | ||
| + | == 2013 == | ||
| + | V otázkách nebylo nic z odcvičené látky. Jen z přednášek | ||
| + | = Písemná = | ||
| + | |||
| + | **1.termín** | ||
| + | - Vysvětlit rozdíl mezi složitostí algoritmu a složitostí problému, který z nich může být větší, od obou příklad | ||
| + | - Popsat DCEL strukturu(detailně) | ||
| + | - Popsat vysledek counting query a report query, který z nich lze implementovat rychleji(více efektivněji)+příklad od každého | ||
| + | - Popsat metodu slabs k hledání úseček v rovině, popsat operační a paměťovou složitost. Porovnat s metodou "trapezoid subdivison" | ||
| + | - Popsat princip 2D range tree(co je v listech a vnitrnich uzlech, co je v kanonických množinách v druhém stromě), nakreslete příklad 2D range tree s pár elementy | ||
| + | - Popsat Grahamův algoritmus pro konstrukci konvexní obálky, jaká je operační složitost předprocesní fáze a jaká samotné konstrukce? | ||
| + | - Popsat pár slovy princip inkrementální konstrukce straight line | ||
| + | - Vysvětlit princip konstrukce Voronoi diagramu pomocí rozděl a panuj | ||
| + | - Vysvětlit algoritmus inkrementálního Delaunay triangulace a vysvětlete operace flip edge a legalize edge | ||
| + | |||
| + | **2.termín** | ||
| + | - Vytvořit nad danými čísly 1D range tree a přiřadit kanonické množiny uzlům | ||
| + | - Jak se spočítá orientovaná plocha trojúhelníku, jak se využije k určení leftturn | ||
| + | - Jaká je souvislost VD a DT? | ||
| + | - Jaká je struktura u lichoběžníkových map pro vyhledávání, jakou má složitost | ||
| + | - Fortune sweep line algoritmus - pojmy beach line, druhy událostí, jak se zpracují tyto události | ||
| + | - Z jakých objektů se skládá Voronoi diagram úseček | ||
| + | - Pseudoalgoritmus na dolní konvexní obálku přímek | ||
| + | = Ústní = | ||
| + | - Kde se objevuje pojem Zona? | ||
| + | - Vysvětlit kanonické množiny | ||
| + | - Popsat DCEL | ||
| + | Letos byly dva termíny, další se nevypsal, pokud vim. Nakonec to dal skoro všem, i když písemná tomu vůbec nenapovídala: | ||
| + | [[courses/a4m39vge/strana 1]], [[courses/a4m39vge/strana 2]] | ||
| + | |||
| + | == 2014 == | ||
| + | = Písemná = | ||
| + | |||
| + | **2.termín** | ||
| + | * Napište algoritmus pro výpis koncových bodů hran v DCEL, které mají společný bod (složitosti napsat). | ||
| + | * Fortune sweep line algoritmus - pojmy beach line, druhy událostí, jak se zpracují tyto události. | ||
| + | * Popsat triangulaci monotoního polygonu. | ||
| + | * Vytvořit Voronoi diagram pro 5 úseček, jaké geometrické útvary využíváme. | ||
| + | * Popište metodu legalizace hrany. | ||
| + | * Vytvořte segment tree pro zadané intervaly. | ||
| + | * Pseudoalgoritmus na dolní konvexní obálku přímek. | ||
| + | * Něco ohledně sweep line v Arrangements of lines (paměťové složitosti). * Nečíslovaný seznam | ||
| + | |||
| + | **3.termín** | ||
| + | - Vyčíslit kolik vznikne maximálně hran při uspořádání úseček. | ||
| + | - Napsat algoritmus který převede nemonotoní polygon na monotoní. | ||
| + | - Vytvořit segmentový strom zadaných úseček. | ||
| + | - Vymyslet algoritmus, který spočítá délku všech hran zadané plochy, s využitím DCELu. | ||
| + | - Algoritmus De Wall, k čemu slouží, jak vytvoří první trojúhelník. | ||
| + | - Popsat sweep line algoritmus pro detekci průsečíků úseček, události složitost atd.. | ||
| + | - Popsat D&C algoritmus pro vytvoření konvexní obálky, složitosti jak se hledají tangenty. | ||
| + | - Princip priority search tree, k čemu slouží, jak se v něm hledá. | ||
| + | |||
| + | == 2015 == | ||
| + | = Písemná = | ||
| + | |||
| + | ** 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) | ||
| + | - 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) | ||
| + | - Triangulace monotoního polygonu. (3b) | ||
| + | - Co je to legalizace hrany u Delaunay triangulace. (3b) | ||
| + | - Udělat segmentový strom (bylo tam 6 segmentů, tři v jedné úrovni nahoře, tři v druhé úrovni dole) (5b) | ||
| + | - Vysvělete Fortune Sweep Line algoritmus. Beach line, typy událostí, postup jejich zpracování. (10b) | ||
| + | - Z jakých geometrických útvarů se skládá Voronoi diagram izolovaných úseček? Nakreslit příklad Voronoi diagramu pro 5 úseček. (5b) | ||
| + | - Pseudokód algoritmu konstrukce dolní obálky množiny přímek (3b) | ||
| + | |||
| + | ** 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é incidují z vrcholů této stěny. Datové struktury DCEL, složitost algoritmu. (10b) | ||
| + | * POZOR, algoritmus který obejde stěnu a vypíše hrany které jí tvoří nestačí - to bylo hodnoceno 5b. | ||
| + | - Datová struktura u Overmars algoritmu - popsat (4b) | ||
| + | - 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) | ||
| + | - 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) | ||
| + | - Interval tree pro 6 segmentů (3b) | ||
| + | - Definice D-simplexu (1b) | ||
| + | - 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í = | ||
| + | - Range search, na co se používá, nakreslit range tree, co jsou kanonické množiny | ||
| + | - Kd stromy | ||
| + | - Order-k Voronoi Diagram, Farthest-point | ||
| + | - 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~~ | ||
