• Šifra predmeta:63532
  • Kreditne točke:6
  • Semester: poletni
  • Vsebina

Naj vas druga beseda v imenu ne prestraši. Diskretna matematika je tista matematična disciplina, ki se z računalniki najbolje razume. Uspešna rešitev diskretnega matematičnega problema nas včasih ne bo zadovoljila, med rešitvami bomo želeli poiskati takšno, ki jo lahko prepišemo v kar se da učinkovit algoritem (ali pa vsaj takšno, ki jo na najlažji način prepišemo v algoritem).

Znaten del tečaja se bomo ukvarjali s problemi na grafih, ki se pojavljajo povsod okrog nas, ne da bi se tega zavedali. Napredek v teoriji grafov kot matematični disciplini je tesno povezan z razvojem računalništva. Rdeči niti bosta v resnici dve: barvanja grafov in problem disjunktnih poti. Problemi barvanja splošnih grafov so tipično težki. Če pa imamo opravka, denimo, z ravninskimi grafi, lahko barvanje grafov postane z računskega stališča obvladljiv problem. Problemi disjunktnih poti (pa tudi njihovi sorodniki - pretoki in prirejanja) se lahko skuhajo na več načinov, s popolnoma različnim obnašanjem. V neusmerjenem ali usmerjenem grafu in z ločevanjem terminalov poti ali ne. Večina naših problemov pa bo postala enostavna v grafih, v katerih lahko že majhna skupina policajev ujame še tako hitrega roparja.

Spoznali pa bomo tudi nekaj osnovnih tem iz računske geometrije. Kako zapleten mnogokotnik razrezati na enostavne sestavne dele? Kako v galerijo postaviti varnostne kamere? V katere trgovine zahajajo prebivalci velikega mesta in kako določiti nadmorsko višino?

Pričakujemo predznanje iz algoritmov in podatkovnih struktur, tudi z malo bolj teoretičnega stališča - časovna in prostorska zahtevnost algoritmov. 

Predmetno delo vključuje tedenske domače naloge in končni izpit. 

 

  • Študijski programi
  • Porazdelitev ur na semester
45
ur
predavanj
30
ur
laboratorijskih vaj
  • Izvajalci
Nosilec predmeta
Prostor:R3.09 - Kabinet
Asistent
Prostor:R3.26 - Laboratorij LMMRI