Predmet: Kombinatorni i geometrijski algoritmi (17.D0M32Z )
Studijski programi predmeta:
Stepen i vrsta studija | Naziv |
---|---|
Doktorske studije | Matematika u tehnici (Godina: 2, Semestar: Zimski) |
Doktorske studije | Matematika u tehnici (Godina: 1, Semestar: Zimski) |
Kategorija | Naučno-stručni |
Uža naučna oblast |
|
ESPB | 10 |
Usvajanje znanja iz oblasti teorije geometrijskih algoritama, kao i njihova primena na rešavanje standardnih geometrijskih problema.
Očekuje se da uspešan student usvoji osnovne koncepte skladištenja geometrijskih objekata korišćenjem odgovarajućih struktura podataka, kao i efikasnih algoritama koji se na njih mogu primeniti. Takođe, od studenta se očekuje da bude sposoban da modifikuje poznate algoritme i prilagodi ih za rešavanje novih problema.
Strukture podataka za skladištenje geometrijskih objekata. Determinističke metode za rad sa skupovima tačaka, podeli-i-osvoji, čišćenje. Najbliži par, najdalji par. Metode slučajnog uzorka. Teorema uzorka, teorema momenta. Verovatnosni algoritmi, onlajn algoritmi, dinamički algoritmi. Konveksna obvojnica, politopi. Razni algoritmi nadogradnje za računanje konveksne obvojnice. Konveksna obvojnica u dve dimenzije. Veza sa sortiranjem niza. Konveksna obvojnica skupa lopti. Najmanja lopta koja sadrži skup tačaka. Trijangulacije u dve dimenzije, sa i bez ograničenja. Deloni trijangulacije, trijangulacije u tri dimenzije. Simpleks i kompleks. Čuvanje galerije. Binarne podele prostora, Molerov algoritam. Kvadrvo i oktdrvo. Uređenja hiperravni, razuđenost. Teorema zone. Konstrukcija nadogradnjom. Uređenja pravih u ravni, dualnost, uređenja duži u ravni.
Predavanja su auditorna. Na predavanjima se izlažu osnovni principi, kao i mogućnosti primene usvojenih algoritamskih tehnika na rešavanje raznih geometrijskih problema. Student je obavezan da napiše seminarski rad.
Autori | Naziv | Godina | Izdavač | Jezik |
---|---|---|---|---|
2002 | Engleski | |||
2008 | Engleski |
Predmetna aktivnost | Predispitna | Obavezna | Broj poena |
---|---|---|---|
Predmetna aktivnost Usmeni deo ispita |
Predispitna Ne |
Obavezna Da |
Broj poena 70.00 |
Predmetna aktivnost Seminarski rad |
Predispitna Da |
Obavezna Da |
Broj poena 20.00 |
Predmetna aktivnost Prisustvo na predavanjima |
Predispitna Da |
Obavezna Da |
Broj poena 10.00 |