Računska topologija je dokaj novo področje, nekje med računalništvom in matematiko. Na matematični strani je tesno povezano s topologijo. Topologija pa je bolj ohlapna oblika geometrije, kjer nas velikosti, razdalje, koti in druge številske lastnosti objektov pravzaprav ne zanimajo. Zanimajo pa nas bolj kvalitativni opisi oblik kot so število ločenih kosov, številov tunelov in lukenj različnih oblik ipd. Zaradi tega so se topološki prijemi pokazali kot zelo koristni pri problemih, kjer je prevelika natančnost nepotrebna ali celo škodljiva. Topološke metode uporabljamo na primer pri analizi velikhi podatkovnih množic, pri modeliranju omrežij, rekonstrukciji obljektov iz vzorca točk, načrtovanju poti robotov in razdeljevanju poslov med procesorji.
Velik poudarek pri predmetu bo na študentiskih projektih. Opisali bomo več tipičnih problemov, ki so primerni za topološko modeliranje in analizo in ob njihovem reševanju spoznali osnovne topološke pojme, strukture in algoritme, ki jih bomo tudi preizkusili na konkretnih podatkih.
Za opravljen predmet mora študent rešiti tri samostojne domače naloge (ena DN ob koncu vsakega izmed naslednjih mesecev: marec, april, maj), en skupinski projekt (v maju) in uspešno opraviti teoretični izpit v enem od razpisanih izpitnih rokih.
- nosilec: Neža Mramor-Kosta
- nosilec: Žiga Virk
Strokovnjaki s področja računalništva navdih za reševanje aktualnih problemov iščejo v različnih virih. Povsem logično je, da inspiracijo za marsikatero rešitev najdejo v naravi, saj so zaradi evolucije organizmi v naravi razvili izjemne metode za reševanje različnih problemov, s katerimi se soočajo vsak dan. Posledica tega je, da mnogo zelo znanih algoritmov za reševanje kompleksnih problemov posnema obnašanje organizmov v naravi. Tako na primer eden od algoritmov za iskanje najkrajše poti posnema obnašanje mravelj, sistem za hitro vzpostavitev mobilnega brezžičnega omrežja pa imitira letenje ptic v jati. Cilj predmeta je študentom predstaviti uporabo znanj o delovanju narave in živih organizmov pri izgradnji računalniških sistemov ali algoritmov. Poleg konkretnega znanja bodo študenti dobili tudi teoretično ozadje, s čimer se bodo lažje prilagajali hitrim spremembam v današnji računalniški industriji. Spretnosti, pridobljene pri predmetu, so prenosljive, saj so predstavljene metode uporabne na zelo širokem spektru področij. Z naučenimi tehnikami si bodo študenti lahko pomagali tudi pri ostalih predmetih študija oziroma pri morebitni nadaljnji računalniški karieri, tako na doktorskem študiju kot v industriji.
Pregled vsebine predavanj:
1.
Lectures overview:
1. Introductory lecture (motivation, fuzzy logic, biomimicry, collective behaviour)
2. Cinder++ (C++ API for creative coding, OpenGL)
3.-7. Fuzzy logic (fuzzy sets, membership functions, FIS, time and fuzzy logic, fuzzy arithmetic, fuzzy type 2, use cases)
8-12. Autonomous agents and collective behaviour (modelling and simulation of collective behaviour, particle systems, boids, SPP model, animats, modelling perception, drives, action selection, verification)
13-15. Artificial life and artificial worlds (learning agents, learning collective behaviour, framstics, stickyfeet, fuzzy evolution and fuzzy genetic algorithms)
Lab work:
Group project in modelling and simulation related to the topics covered in the course.- nosilec: Iztok Lebar Bajec
Pri matematični analizi in in linearni algebri smo doslej nabrali veliko znanja, za katerega so nam povedali, da je zelo uporabno na različnih področjih. Vendar, ko želimo to znanje dejansko uporabiti, velikokrat naletimo na velikokrat nepremostljive težave: integrala ne znamo izračunati, funkcija, ki smo jo mukoma izračunali, je prezapletena za uporabo v realnem času, pa tudi rešitev diferencialne enačbe se nam le stežka posreči. Pri predmetu Numerična matematika si bomo najprej s praktičnega vidika (pa tudi z nekaj teorije bomo to podprli) ogledali, kako lahko učinkovito rešujemo sisteme linearnih, nelinearnih in diferencialnih enačb, računamo vrednosti integralov in odvodov ter kako lahko z enostavnejšimi funkcijami nadomestimo zapletene. Vseskozi bomo na praktičnih primerih preizkušali, kako s pomočjo računalnika to naše novo znanje lahko koristno uporabimo.
- nosilec: Bojan Orel
- nosilec: Aljaž Zalar
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ž