Rozdíly

Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.

--- courses:a4m39vge [2013/02/25 23:23]
tracker
+++ 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]]
-  * Cvičící: Lukas M. Novosad
+  * Cvičící: Petr Felkel
 ===== Cvičení =====
   * [[courses/a4m39vge/uloha1|1. úloha]]
@@ Řádek 16: / Řádek 16: @@
 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
@@ Řádek 27: / Řádek 40: @@
   - 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:
-[[strana 1]], [[strana 2]]
+[[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 =====
 [[http://www.scribd.com/doc/7619913/Computational-Geometry-Algorithms-and-Applications-2d-Ed-De-Berg|Computational geometry: algorithms and applications ]]
 ~~DISCUSSION~~

courses/a4m39vge.1361831037.txt.gz · Poslední úprava: 2025/01/03 18:16 (upraveno mimo DokuWiki)

Nahoru