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.
- nosilec: Gašper Fijavž