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) |
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 Seminarski rad |
Predispitna Da |
Obavezna Da |
Broj poena 20.00 |
| Predmetna aktivnost Usmeni deo ispita |
Predispitna Ne |
Obavezna Da |
Broj poena 70.00 |
| Predmetna aktivnost Prisustvo na predavanjima |
Predispitna Da |
Obavezna Da |
Broj poena 10.00 |
