Za računalničarjevo preživetje v krasnem novem digitalnem svetu je nujno, da čimprej najde orodjarno ter da si tudi sam izdela vsaj kakšno bitno lopato. Govorimo o algoritmih in podatkovnih strukturah. To so za računalnikarja orodja, s katerimi uresniči svoje še tako divje ideje.

Dobro je poznati  pogosto rabljene algoritme ter preizkušene in uspešne načine razvoja  novih. Z višine se vidi več in dalj, zato bomo pri tem predmetu ukvarjali s prostorskimi podatki, iskali z in plezali na k-d, R in van Emde Boats drevesa. Poglobljeno bomo spoznali funkcije razprševanja, urejanje s predpostavkami, lokalno preiiskovanje, hevristične metode reševanja problemov, biološko navdahnjene metode, računsko geometrijo in uporabo linearnega programiranja. Da bi znali algoritme med seboj primerjati in da vedeli, katerih problemov se je sploh smiselno lotevati, bomo spoznali verjetnostno in amortizirano analizo algoritmov. In ker imajo dandanašnji procesorji vse več jeder, jih bomo izkoristili z večnitnimi algoritmi, nekaj pozornosti pa bomo namenili tudi distribuiranim algoritmom.

Tistim, ki na prvostopenjskem študiju še niso osvojili dovolj algoritmičnega znanja, bodo manjkajoče osnove ponujene kot samostojno dodatno delo na začetku semestra.

Vaje pri predmetu potekajo v obliki reševanja nekaterih nalog in posvetovanj z asistentom o seminarskem delu (3 seminarske naloge, 5 spletnih kvizov). Oceno vaj predstavlja skupna ocena seminarskih nalog, pri vseh pa je potrebno doseči več kot polovico točk. Pogoj za pozitivno oceno vaj je tudi doseženih polovica vseh točk na kvizih.

Ocena pri predmetu je sestavljena kot povprečje ocene vaj in ocene pisnega izpita, pri katerem je potrebno doseči več kot polovico točk. Oceno je mogoče izboljšati z ustnim izpitom.

Študenti opravljajo tri seminarje, ki so enakomerno razporejeni po semestru, tri kolokvije (neobvezno) in končni izpit.

 

Pri predmetu se bomo spoznali s principi in navodili načrtovanja uporabniških vmesnikov (UV) in s komunikacijo med možgani in računalnikom preko zamišljanja motoričnih aktivnosti oziroma neinvazivnim vmesnikom možgani računalnik (VMR). Teme so naslednje: sposobnosti človeka (spomin in učenje, zaznavanje, poznavanje), vrste komunikacije pri UV (vhodni modeli, modeli in metafore), principi načrtovanja UV (Normanovi namigi, Mandelovi principi, Nielsenovi principi), navodila načrtovanja UV (izbor in aranžiranje grafičnih gradnikov za interakcijo, grafično načrtovanje, povratna informacija in interakcije, izbor in načrtovanje ikon), elektroencefalogram (EEG) in komunikacija možgani računalnik, mednarodna referenčna podatkovna baza za načrtovanje VMR (EEGMMI DS - EEG Motor Movement/Imagery DataSet), načrtovanje neinvazivnega VMR, spektralna analiza signalov EEG (močnostni spekter, avtoregresivna metoda, časovno frekvenčne predstavitve, parametrično modeliranje), izločanje značilk v časovnem in frekvenčnem prostoru, izbor značilk, klasificiranje zamišljanih motoričnih aktivnosti, VMR s strojnim učenjem, VMR aplikacije (pomikanje kurzorja, črkovanje, komunikacija za hendikepirane). Uporabljena okolja bodo NetBeans in Matlab. Obveznosti pri predmetu obsegajo dve seminarski nalogi, kviz med laboratorijskimi vajami, kviz med predavanji in končni izpit.

Predmet bo vseboval naslednje vsebine:

•    Uvod
    Računska zahtevnost odločitvenih in optimizacijskih problemov
    NP-polni in NP-težki problemi
    Hevristični algoritmi, kakovost suboptimalnih rešitev,  (ne)obstoj zagotovila za kakovost
•    Približno reševanje NP-težkih probl.
    Aproksimacijski algoritmi
    Kakovost približnih rešitev
    Razred APX
    Tehnika z vrzeljo
    Aproksimacijske sheme
    Razreda PTAS in FPTAS
    Meje približnega reševanja
•    Razvoj aproksimacijskih algoritmov
    Požrešna metoda
    Osredotočanje na podporobleme
    Zaporedno razdeljevanje
    Dinamično programiranje
•    Naključnostno reševanje NP-težkih probl.
    Las Vegas in Monte Carlo algoritmi
    Razredi RP, co-RP,  ZPP, PP, BPP
•    Razvoj naključnostnih algoritmov
    Naključno vzorčenje
    Zagotavljanje obilice prič
    Naključno preurejanje vhoda
    Zgoščanje
    Enakomerno porazdeljevanje bremen

Računalničarji moramo poleg osnov programiranja pridobiti tudi vpogled v drugačne programerske tehnike, kot sta proceduralno in objektno-usmerjeno programiranje. V zadnjih letih se izrazito uveljavlja funkcijski način programiranja, ki omogoča učinkovito razgradnjo programa na skupek neodvisnih funkcij, s katerimi je možno program izvajati tudi paralelno in s tem hitreje.

Pri predmetu se bomo učili funkcijskega pristopa k programiranju v jezikih Standardni ML in Racket. Spoznali bomo pojme, kot so tipizacija, leksikalni in dinamični doseg, funkcijska ovojnica, razvili pa bomo tudi interpreter za lasten programski jezik. Naš cilj bo pridobiti globje razumevanje v delovanje programskih jezikov in s tem doseči mojstrstvo pri programiranju.

Predpogoj za razumevanje snovi predmeta je poznavanje osnov programiranja v proceduralnih jezikih (Java, C++, Python) in razumevanje koncepta rekurzije.

Predmetno delo vključuje tedenske enakomerno zahtevne domače naloge, dve seminarski nalogi (rok za oddajo prve je v sredini semestra, druge pa ob koncu semestra) in končni izpit.