  ̌      ̌   
P 46 (2018/2019) 328
Priprave na srednješolske
računalniške olimpijade
J S
Za srednjnešolce obstajajo tri mednarodne olim-
pijade v računalništvu in informatiki: Mednarodna
olimpijada v računalništvu in informatiki (IOI), Sre-
dnjeevropska olimpijada v računalništvu in infor-
matiki (CEOI) in Balkanska olimpijada v računalni-
štvu in informatiki (BOI).
Slovenija na teh tekmovanjih ni najbolj uspešna,
kajti doslej je na svetovni olimpijadi dosegla le 24
bronastih medalj in štiri srebrne, pa še od teh štirih
sta dve iz daljnega leta 1995, kar jo postavlja na 59.
mesto od 106 držav. Za primerjavo lahko vzamemo
sosednje države, npr. Hrvaško, ki ima 11 zlatih, 39
srebrnih in 35 bronastih medalj, in našo širšo regijo,
kjer so Poljska, Romunija, Bolgarija in Slovaška na
svetovni lestvici 4., 6., 7. in 8.1 Posebej je zaskrblju-
joče, da je Slovenija v devetdesetih letih prejšnjega
stoletja veljala za vzor na tem področju.
Z letošnjim letom je ACM Slovenije v sodelovanju
z uspešnimi tekmovalci iz preteklih let začel organi-
zirati celoletne priprave na olimpijade. Namen pri-
prav je, da preobrnemo trend slabih rezultatov in
v prihodnjih treh letih povečamo število dijakov, ki
bodo sposobni doseči vidnejše rezultate v svetov-
nem merilu, saj bo to imelo dvojni rezultat: najprej
1statistika na voljo na stats.ioinformatics.org/
countries/?sort=medals_desc.
se bo povečalo zanimanje za računalništvo in infor-
matiko med mladimi in tudi gospodarstvo bo prišlo
do kakovostnejšega kadra.
Priprave na olimpijade iz računalništva potekajo v
okviru projekta NAPOJ – Načrtovanje poučevanja Al-
goritmov in Programiranja ter Organizacija skupno-
sti, ki ga vodi Univerza v Ljubljani, Fakulteta za ra-
čunalništvo in informatiko v sodelovanju z drugimi
partnerji, vključno z Ministrstvom za izobraževanje,
znanost in šport. Projekt je bil izbran na razpisu
podjetja Google CS4HS (Computer Science for High
School).
Aktivno izobraževanje in priprave na olimpijade
potekajo skozi celo leto, podobno, kot to poteka v
Sloveniji pri matematični ali fizikalni olimpijadi, ali
pa kot to poteka v drugih državah (Poljska, Hrvaška)
pri olimpijadah iz računalništva in informatike. Več
o pripravah in snovi je na voljo na uradni strani2.
Srečujemo se na dva tedna na Fakulteti za računalni-
štvo in informatiko v Ljubljani, kjer se vsakič obrav-
nava del snovi iz »učnega načrta« za svetovno raču-
nalniško olimpijado3, po navadi motiviran s kakšno
nalogo iz preteklih tekmovanj. Vsakemu srečanju
sledi tudi domača naloga, kjer morajo tekmovalci na-
učeno znanje in programerske spretnosti izkazati na
treh različno težkih nalogah. Priprave so brezplačne
in se jih lahko udeleži kdorkoli.
Odziv dijakov in srednjih šol je bil pozitiven: tre-
nutno priprave obiskuje 34 dijakov iz 14 različnih
2moodle.lusy.fri.uni-lj.si/course/view.php?id=60
3people.ksp.sk/~misof/ioi-syllabus/ioi-syllabus.
pdf
  ̌      ̌   
P 46 (2018/2019) 3 29
srednjih šol iz vse Slovenije. Predznanje je precej
različno, nekaj dijakov je starih tekmovalcev z olim-
pijad, nekaj jih je še začetnikov. Tu pa se odpre še
en problem: za razliko od npr. matematičnega ken-
guruja in nadaljnjih tekmovanj, ki se jih dijaki ude-
ležujejo množično, je pri tovrstnih programerskih
tekmovanjih potrebna določena tehnična podkova-
nost in predznanje programiranja, ki ga večina ne
pridobi v času osnovne ali srednje šole. Kjub sis-
temskim problemom pa dijaki izkazujejo interes in
motivacijo za učenje in delo. Že sama udeležba na
olimpijadi je za marsikoga lepa nagrada, medalja pa
ima še večji pomen: odpira namreč vrata za vpis na
dobre svetovne univerze ali prakse pri tehnoloških
podjetjih.
Za kakršnekoli informacije glede priprav lahko pi-
šete organizatorju na naslov jure.slak@ijs.si,
razpored prihodnjih srečanj pa je prikazan v tabeli 1.
Srečanj se lahko udeleži vsak zainteresiran posluša-
lec, tudi če želi samo dobiti občutek, kako priprave
izgledajo.
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
3. 6. ob 16:00 še nedoločeno Izbrane naloge s starih tekmovanj
20. 5. ob 16:00 Janez Brank
Napredno dinamično programiranje, dinamično
programiranje z mitmaskami.
6. 5. ob 16:00 Jure Slak
Geometrija: ploščine, vektorski produkt, konveksna
ovojnica, kompresija koordinat,
presečišča, pometanje.
15. 4. ob 16:00 Vid Kocijan
Topološko urejanje, močno povezane komponente,
mostovi in prerezna vozlišča.
23. 3. ACM + IJS tekmovanje RTK
18. 3. ob 16:00 Tomaž Hočevar
Napredne podatkovne strukture: binarno iskalno
drevo, trie, druge razširjene podatkovne strukture,
še posebej drevo segmentov.
9. 3. ZOTKS tekmovanje FIT
4. 3. ob 16:00 Filip Koprivec
Podatkovna struktura Union-Find, minimalno vpeto
drevo, algoritma Kruskala in Prima.
11. 2. ob 16:00 Filip Koprivec
Najkrajše poti, Dijkstrov, Floyd-Warshallov
algoritem.
21. 1. ob 16:00 Janez Brank
Dinamično programiranje, najdaljše skupno
podzaporedje, urejevalna razdalja, najdaljše
naraščajoče podzaporedje.
7. 1. ob 16:00 Vid Kocijan
Osnovni algoritmi na grafih,
pregled v širino, pregled v globino, štetje komponent.
17. 12. ob 16:00 Janez Brank
Dinamično programiranje, koncept optimalne
podstrukture in stanja, osnovni primeri, določanje
časovne in prostorske zahtevnosti, 0/1 nahrbtnik.
datum predavatelj snov
TABELA 1.
Razpored prihodnjih srečanj in tekmovanj iz računalništva.
×××