Algoritmi

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.

To survive in the brave new digital world students have to get acquainted with the programming toolbox and make at least a byte shovel. The word is about algorithms and data structures, which in computer science are basic tools to transfer ideas and dreams into reality.

If one does not want to reinvent the wheel, it is wise to know at least the frequently used algorithms and some well tested and successful methods for development of new algorithms. In general, it seems that standing on the shoulders of giants is the best strategy for a quick progress. In high altitude one sees farther, so one should know about spatial data structures and climb the k-d, R, and van Emde-Boats trees. The course will drop comparison sort and make some assumptions to sort in linear time. Standard toolbox includes algorithms from computational geometry and use of linear programming and hash functions. When exact methods do not work, local search, heuristic problem solving and biologically inspired methods can be a solution. Knowing what tool (algorithm) to use in which circumstances is also essential, so one has to compare different algorithms. Will my new algorithm run a few seconds, a few minutes, or a few millennia? The course will offer a way to answer these questions through the analysis of computational complexity, in particular with probabilistic and amortized analysis. Luckily, nowadays processors have more and more cores, so knowledge of parallel and distributed algorithms comes handy.

The students who haven’t learnt enough of algorithms in their first degree study will be offered additional contents as a self-study at the beginning of the semester.

Practical part is in the form of programming assignments, solving problems, and web quizzes. Assistant is available for consultations. The grade of practical work is a joint grade of three assignments, which have to be finished on time and graded with at least 50% of points. The precondition for passing practical work is achieving at least 50% of points in web quizzes.

The final course grade consists of practical work grade (50%) and written exam (50%), in both parts one has to achieve at least 50% of points. Oral exam is optional.