Uvod
Dober programer ima učinkovitost pet do deset »povprečnih« programerjev. Predmet APS2 postavi mejo med povprečnim in odličnim programerjem.
V tem opisu vam bom poizkušal čim bolj koristno ter zanimivo predstaviti predmet Algoritmi in podatkovne strukture 2. Pa pojdimo od začetka: V prvem letniku smo pri programiranju 1 in 2 spoznavali osnove programiranja in sintakse v različnih programskih jezikih. Potrebno se je bilo naučiti prepoznati problem ter ga rešiti, vendar pa so bile te rešitve okorne ter zelo primitivne. Nismo se poglabljali v optimizacijo algoritma, hitrost programa, porabo pomnilnika in podobno. Nato pa sta prišla predmeta APS1 ter APS2, kjer nismo bili zadovoljni samo s tem, da program deluje, ampak je bila analiza problema obširnejša in rešitve posledično boljše, izvajanje pa hitrejše.
Predavanja in vaje
Tekom predmeta se študent spozna z naprednimi tehnikami programiranja. Spoznali smo se z več podatkovnimi strukturami ter algoritmi, ki so prilagojeni učinkovitemu reševanju specifičnih problemov. Ure pri profesorju Brodniku vsekakor niso bile dolgočasne, saj nas je z raznovrstnimi vprašanji vzpodbujal, da smo aktivno sodelovali. Pri predavanjih je vsekakor potrebno veliko pozornosti, saj je snovi kar veliko. Najprej smo se spoznali s teorijo, nato pa smo naredili tudi nekaj primerov na praktičnih podatkih. Na koncu smo dobili tudi nekaj neobveznih nalog in vprašanj, na katere smo lahko odgovorili na forumu. Medtem ko smo pri predavanjih bolj obdelali teorijo, pa smo pri vajah spoznali tudi praktične rešitve primerov. Tako predavanja kot vaje so bile dosledno izpeljane, snov pa je bila podana na zanimiv in praktičen način.
Snov
Začne se seveda z algoritmom ter njegovo definicijo. Spoznali smo, kako razčlenimo in analiziramo algoritem, zapisanem v psevdokodi. Skozi semester smo spoznali veliko različnih podatkovnih struktur, za katere sploh nisem vedel da obstajajo. Čeprav so številne strukture že implementirane v veliko programskih jezikih je za učinkovito uporabo le-teh potrebno globlje poznavanje delovanja, ki se odvijajo npr. pri dodajanju, odstranjevanju, iskanju elementov. Vsaka podatkovna struktura ima svoje prednosti in slabosti, na podlagi katerih se potem odločimo, katero bomo uporabili za rešitev našega problema, saj je običajno mogoča izvedba različnih podatkovnih struktur za isti problem. Za vsak algoritem in podatkovno strukturo smo najprej formalno dokazali njeno pravilno delovanje, analizirali časovno ter prostorsko zahtevnost izvajanja operacij ter premislili, ali je dobljena rešitev optimalna in kako bi strukturo lahko še izboljšali. Tekom predmeta smo spoznali različne algoritme za urejanje števil, skozi katere smo vadili dokazovanje pravilnosti, opozorjeni pa smo bili tudi na dva modela računanja – na prvega, pri katerem primerjamo elemente med seboj in na drugega, pri katerem računamo s ključi. Spoznali smo tudi napredne tehnike programiranja, kot je metoda deli in vladaj, požrešni algoritmi ter dinamično programiranje. Proti koncu semestra smo spoznali še algoritme na grafih: iskanje najkrajše poti med posameznimi ali vsemi pari vozlišč ter gradnja najmanjšega vpetega drevesa. Všeč mi je bilo, da večina snovi ni ostala samo na papirju, ampak smo različne algoritme in podatkovne strukture pri domačih nalogah tudi sprogramirali v Javi. Tako se ti snov še bolj vtisne v spomin. Naj omenim da se splača pregledati tudi literaturo, ki je navedena v spletni učilnici. Osebno so mi izjemno pomagali grafični prikazi algoritmov, saj tako lažje razumeš njihovo delovanje. Če se bodo pojavili problemi pri razumevanju, vsekakor priporočam tudi branje katere od navedenih knjig, kjer je snov zelo dobro razčlenjena in opisana. Tudi profesor ali asistenti vam bodo z veseljem pomagali, tako da se ne obotavljajte z vprašanji.
Obvezosti
Že v začetku naj vas opozorim da se pri tem predmetu SPLAČA sprotno delo! Če se potrudite lahko predmet zaključite že s kolokviji takoj ob koncu semestra.
Domače naloge
Domače naloge so sestavljene iz dveh delov: teorije ter praktičnega problema. Začne se s preprosto testno nalogo (0. naloga), kjer spoznamo sistem za oddajanje nalog Marmoset. Sistem omogoča samodejno ocenjevanje programerskih nalog. Nato sledi 6. domačih nalog. Naj poudarim, da se za uspešno opravljene domače naloge zahteva:
- Skupno povprečje nalog: 40%
- Vsaka naloga vsaj 20%
- Vsaka programerska podnaloga vsaj 20%
Vsaka domača naloga potrebuje kar nekaj raziskovanja ter programiranja, zato priporočam da se nalog lotite čim prej in ne čakate do zadnjega dne. Za vsako programersko nalogo dobimo oblikovan skelet naloge (imena metod, testi, itd...). Ko uspešno opravimo teste, priložene nalogi, v ZIP paketu naložimo projekt, nad katerim se najprej izvedejo t.i. »public« testi, ki so priloženi nalogi, nato pa še »release« testi, za katere ni znano, kaj točno naredijo. Ob napaki dobimo obvestilo v kateri metodi se je pojavila napaka, vendar je zelo težko na podlagi imena metode in skopega opisa napake sklepati kaj je šlo narobe. Zato je pomembno da v nalogah čim bolj preverjamo vhode ter predvidimo čim več možnosti, kjer bi se lahko pojavila napaka. Število izvedenih testov na dan je omejeno, zato je potrebna posebna natančnost, ko pride do napake in nalogo ponovno oddamo. Seštevek teh testov nam nato vrne oceno programerske naloge, ki skupaj s teoretičnimi nalogami tvori skupno oceno domače naloge. Osebno so mi bile domače naloge všeč, še posebej programerski problemi.
Zapiski
Tekom semestra je študent dolžan enkrat oddati zapiske predavanj ali vaj. Datum zapisovanja je potrebno rezervirati prej na Wikiju spletne učilnice. Z izbiro termina se splača pohiteti, saj moraš drugače vzeti tisti termin, ki je pač prost.
Kolokviji
Predmet vsebuje 2 kolokvija: na sredini semestra in proti koncu semestra. Pred vsakim kolokvijem potekajo tudi govorilne ure, ki se izvajajo preko interneta. Največja prednost takih govorilnih ur je vsekakor to, da si lahko njihov posnetek ogledamo tudi kasneje. Kolokvija sta sestavljena iz nekaj teoretičnih nalog in pa tudi praktičnih problemov, ki pestijo namišljeno osebo z imenom Peter Zmeda. Pri teh nalogah nam »napiflano« znanje ne pomaga veliko, zato je pomembno, da snov razumemo in premislimo o njej. Če sta kolokvija pozitivna, študentu ni potrebno opravljati izpita. Pogoja za opravljena kolokvija sta:
- Vsak kolokvij vsaj 40%
- Seštevek kolokvijev vsaj 50%
Literatura na kolokvijih je dovoljena, vsekakor pa je potrebno poznati postopke in teorijo, če hočemo uspešno rešiti naloge. Na Wiki spletne učilnice študenti lahko tudi vnesejo rešitve kolokvija, ki pridejo zelo prav pri učenju za izpit.
Pisni izpit
V kolikor nam predmeta ni uspelo opraviti s kolokviji, je potrebno pisati pisni izpit. Naloge v pisnem izpitu so zelo podobne nalogam iz kolokvijev. Tudi pri izpitu je dovoljena literatura.
Zaključek
Predmet APS2 vsekakor ni lahek, vendar z nekaj vloženega truda vsekakor ni prevelik zalogaj. Naj še enkrat poudarim, da je pri tem predmetu izredno pomembno sprotno delo. Po uspešno končanem predmetu vam vsekakor zagotavljam, da bo reševanje problemov bolj enostavno ter hitreje in da vaše programersko znanje ne bo več samo povprečno, ampak boste na dobri poti, da postanete tako dober programer, da se ga ne bi branil niti Google ^^.
Prevod knjige Open Data Structures v slovenščino
- V študijskem letu 2013/2014 smo začeli s prevodom prosto dostopnega učbenika za študente računalništva s področja podatkovnih struktur in algoritmov, Open Data Structures. Povezava do uradne strani.
- Navodila za namestitev odjemalca SVN na operacijskih sistemih Linux, MacOS X in Windows.
Prevod dopolnilnih spletnih strani knjige Algorithms v slovenščino
- V študijskem letu 2014/2015 smo začeli s prevodom prosto dostopnih dopolnilnih slpetnih strani učbenika Algorithms za študente s področja algoritmov in podatkovnih struktur.
- Povezava do slovenskih prevodov spletnih strani
- Povezava do izvornih spletnih strani
Seminarske naloge (dodatno delo pri predmetu APS2)
Miloš Keković - Vizualizacija statistike preskočnih seznamov (2017/2018)
Jakob Pavli - Primerjava hitrosti delovanja preskočnih seznamov in neuravnoteženih dvojiških iskalnih dreves nad naključnimi elementi (2015/2016)
Damjan Klemenčič - Primerjava iskanja z razpolavljanjem in interpolacijskega iskanja (2013/2014)
Matic Teršek - Uporaba metode Monte Carlo za izračun Pi-ja v okolju Hadoop (2013/2014)
Luka Golinar - Bellman Ford algorithm using Hadoop map reduce (2013/2014) [v angleščini]