Geometrijski algoritmi

2021/2022

Kurs Geometrijski algoritmi je izborni kurs na master akademskim studijama na Matematičkom fakultetu u okviru koga se izučavaju sledeće teme:

  • Alat gclc
  • Konveksni omotač
  • Preseci duži
  • DCEL
  • Monotono particionisanje. Triangulacija
  • Voronojevi dijagrami
  • Delone trijangulacija

Predmetni nastavnik:

Asistent:

NASTAVA

Nastava se sastoji iz dva časa predavanja i tri časa vezbi nedeljno.

ISPIT

Ispit se može polagati na dva načina.

  • Sa predispitnim obavezama
    • Projekat u GCLC-u: 10 poena
    • Projekat (implementacija nekog algoritma): 30 poena
    • Predstavljanje naučnog rada: 10 poena
    • Rad na vežbama: 10 poena
    • Završni teorijski test: 40 poena
    • Prag za prolaz: 16 poena
  • Bez predispitnih obaveza
    • Završni praktični ispit na računaru: 50 poena (Prag za prolaz: 20 poena)
    • Završni teorijski test: 50 poena (Prag za prolaz: 20 poena)
    • Teorijski deo ispita se radi 1 sat i sastoji se od 20 teorijskih pitanja.

PREDISPITNE OBAVEZE

Pogledati detaljno na stranici posvećenoj vežbama

Polaganje praktičnog ispita bez predispitnih obaveza
Ukupno 100 bodova, skalira se na 50 poena.
Zadatak Poeni
Radi se 2 sata
Nije se moguće predomisliti. Odnosno ukoliko seminarski nisu izabrani u toku semestra nije moguće naknadno izabrati seminarski.
Implementacija algoritma.
Dobija se kostur koji koristimo na vežbama i deo algoritma, a deo treba dopisati. Dolazi sve rađeno na vežbama ili nešto što veoma liči na to. 		40 bodova
Implementirana i vizacija napisanog algoritma i ona radi. 10 bodova
Napisan naivan algoritam. 15 bodova
Napisano poređenje između naivne i efikasne implementacije. 10 bodova
Kod uredno napisan. Napisan jedan UnitTest. 10 bodova
Zadatak iz GCLC-a. Uz zadatak se dobija uputstvo za GCLC (manual.pdf). 15 bodova


GCLC seminarski
(10 poena)
# Rok Zadatak
1 03.11.2021. Tema je izabrana (uz obavezan dogovor sa profesorom) i upisana u tabelu.
2 29.11.2021. Rad je okačen na git i u tabelu je upisan link na rad.
3 01.12.2021. Prezentacija rada na času predavanja.
Ukoliko se ne ispoštuje neki od rokova, moguće je osvojiti maksimalno 7 od 10 poena.


Prezentacija rada iz časopisa
(10 poena)[5 rezime + 5 odbrana]
# Rok za izradu Zadatak
1 15.12.2021. Rad je izabran (uz obavezan dogovor sa profesorom) i upisan u tabelu.
Časopisi za izbor radova: Uputstvo za izradu seminarskog
2 31.12.2021. Profesoru je poslat dokument sa rezimeom pročitanog rada (asistenta staviti u cc).
3 12.01.2022. Prezentacija rada na času.
Ukoliko se ne ispoštuje neki od rokova, moguće je osvojiti maksimalno 7 poena od 10.


Projekat
(30 poena)
# Rok za izradu Zadatak
1 15.12.2021. Tema je izabrana (uz obavezan dogovor sa profesorom i/ili asistentkinjom) i upisana u tabelu.

Opcija I:
Napisati implementaciju algoritma. Pri tome, algoritam neće predstavljati projekat za sebe, već treba da bude deo jednog zajedničkog projekta (sve što se radi na vežbama je takođe deo tog istog projekta). Dodatna uputstva Nije dozvoljeno pisati postojeće implementacije, odnosno implementacije algoritama rađenih na vežbama ili rađenih prošle godine u okviru seminarskog.
Ideje za nove implementacije mogu se pronaći u literaturi ili u časopisima.

Opcija II: Koristiti postojeće implementacije algoritama rađenih na vežbama (ili u okviru seminarskog ranijih godine) i primeniti na neki konkretan problem. Uraditi veoma ozbiljno grafički korisnički iterfejs. Primeniti na realne probleme. Može se koristiti bilo koja tehnologija.

Bodovanje (ovo je pre svega za opciju I bodovanje, ali se (u zavisnosti od izbora seminraskog) može primeniti i na opciju II):
  • Implementacija Vašeg algoritma (15 poena)
  • Implementacija algoritma grube sile i poređenje vremena izvršavanja u zavisnosti od veličine ulaza (5 poena)
  • Dokument sa opisom algoritma i implementacije (5 poena)
  • Unit testovi (5 poena)
2 14.01.2022. Odbrana projekta. Svi studenti koji odbrane projekat u ovom terminu će dobiti bonus od 5 poena. Ukoliko želite da branite projekat u ovom terminu, potrebno je da projekat bude gotov do 31.12. i da o tome obavestite asistentkinju. Moguće su manje izmene koda do odbrane.
3 januar/februar/jun1/jun2/septembar ispitni rok Odbrana projekta. Potrebno je da projekat bude gotov 7 dana pre odbrane i da o tome obavestite asistentkinju.
Ukoliko se ne ispoštuje neki od rokova, moguće je osvojiti maksimalno 25 poena od 30.

Početak semestra

Srećan početak nastave!

7.10.2021.