Priprave na računalniške olimpijade (18/19)
Osnutek odseka
-
Priprave na računalniške olimpijade CEOI, BOI in IOI potekajo v prostorih Fakultete za računalništvo in informatiko, Večna pot 113, 1000 Ljubljana, ob ponedeljkih od 16:00 do 19:00 v učilnici P2 (zimski semester) oz. P21 (poletni semester). Vsakim pripravam bodo sledile 3 domače naloge, od tega je vsaj ena obvezna in jo morate rešiti do naslednjega tedna. Domače naloge morate implementirati samostojno, zaželeno pa je, da se pogovarjate o težavah in idejah, ki ste jih imeli pri njihov reševanju.Tekom priprav bodo organizirana tudi tri izbirna tekmovanja: prvo poskusno in dve izbirni. Rezultati na izbirnih tekmovanjih skupaj z rezultati iz najtežjih skupin na tekmovanjih FIT in RTK bodo upoštevani pri izboru za CEOI.
Organizatorji priprav so:
- Jure Slak, jure.slak@ijs.si, Institut Jožef Štefan in Fakulteta za matematiko in fiziko
- dr. Tomaž Hočevar, tomaz.hocevar@fri.uni-lj.si, Fakulteta za računalništvo in informatiko
- dr. Janez Brank, janez.brank@ijs.si, Institut Jožef Štefan
- Vid Kocijan, vid.kocijan@gmail.com, University of Oxford
- Filip Koprivec, filip.koprivec@student.fmf.uni-lj.si, Institut Jožef Štefan in Fakulteta za matematiko in fiziko
- prof. Andrej Brodnik, andrej.brodnik@fri.uni-lj.si, Fakulteta za računalništvo in informatiko UL in Fakulteta za matematiko, naravoslovje in informacijske tehnologije UP
Za vprašanja glede organizacije se obrnite na Jureta Slaka, za vprašanja glede sistema za domače naloge in izbirnih tekmovanj na Tomaža Hočevarja, za vprašanja glede snovi pa na tistega, ki je vodil konkretne priprave.
Udeleženci si morajo narediti tudi račun na platformi ministrstva za šolstvo: https://platforma.skoz.si/, se prijaviti na projekt "Priprave na računalniške olimpijade" in po vsakih pripravah oddati en stavek s poročilom.
-
-
Če se imate namen udeležiti priprav za olimpijade, se prosim zabeležite na zgornjem obrazcu, da bomo lahko bolje načrtovali priprave.
-
Po vsakem srečanju morate oddati dva stavka s poročilom, kaj ste na predavanju počeli.
- Jure Slak, jure.slak@ijs.si, Institut Jožef Štefan in Fakulteta za matematiko in fiziko
-
Predavatelj: Jure Slak
Opis:
Literatura:
- IOI syllabus: https://people.ksp.sk/~misof/ioi-syllabus/ioi-syllabus.pdf
- Knjiga (s preveč snovi): Competitve programming 3
Osnovni algoritmi na celih številih:
- delo s števkami
- številski sistemi
- iskanje deliteljev
- testiranje praštevilskosti za eno število
- testiranje praštevilskosi za veliko števil: Eratostenovo rešeto
- razcep veliko števil na prafaktorje s pomočjo Eratostenovega rešeta
- razcept enega števila na prafaktorje, število deliteljev števila
- Evklidov algoritem, največji skupni delitelj, najmanjši skupni večkratnik
- Operacije na bitih: &, |, ^, ~, <<, >>, nastavljanje enega bita, preverjanje ali je i-ti bit prižgan ugasnjen
- Hitro potenciranje in ideja o obravnavi števil po potencah dvojke
-
Predavatelj: Jure Slak
Opis: Osnovne podatkovne strukture: vrsta, sklad, vrsta s prednostjo, povezani seznam, map, set, heap, časovne zahtevnosti operacij
-
Predavatelj: Tomaž Hočevar
Opis:
Osnovni algoritmi na seznamih:
- urejanje: [bubble, selection, insertion]-sort, [quick, merge, heap]-sort, bucket-sort
- bisekcija
Predprocesiranje seznamov:
- kumulativne vsote: poizvedbe na intervalih, spremembe na intervalih
- korenska dekompozicija (sqrt decomposition)
- redka tabela (sparse table)
- iskanje podniza: hashing (Rabin-Karp)
-
Predavatelj: Tomaž Hočevar
Opis: Osnovne strategije reševanja problemov (polni pregled in rekurzija, deli in vladaj, požrešni algoritmi). -
Predavatelj: Janez Brank
Opis: Dinamično programiranje, koncept optimalne podstrukture in stanja, osnovni primeri, določanje časovne in prostorske zahtevnosti, 0/1 nahrbtnik, menjave kovancev.
-
Predavatelj: Vid Kocijan
Opis: Osnovni algoritmi na grafih, pregled v širino, pregled v globino, štetje komponent.
-
Predavatelj: Janez Brank
Opis: Dinamično programiranje, najdaljše skupno podzaporedje, urejevalna razdalja, najdaljše naraščajoče podzaporedje.
-
Predavatelj: Filip Koprivec
Opis: Najkrajše poti, Dijkstra, Floyd-Warshall.
-
Predavatelj: Filip Koprivec
Opis: Union-Find, minimalno vpeto drevo, Kruskal, Prim.
-
Festival inovativnih tehnologij (ZOTKS)
-
Predavatelj: Tomaž Hočevar
Opis: binarno iskalno drevo, trie, druge razširjene podatkovne strukture, še posebej segment tree
-
RTK - Tekmovanje ACM iz računalništva in informatike
-
Predavatelj: Vid Kocijan
Opis: Topološko urejanje, močno povezane komponente, mostovi in prerezna vozlišča.
-
Predavatelj: Jure Slak
Opis: Geometrija: ploščine, vektorski produkt, konveksna ovojnica, kompresija koordinat, presečišča, sweep line.
-
Predavatelj: Janez Brank
Opis: Napredno dinamično programiranje, bitmask DP, TSP.
-
Predavatelj: Tomaž Hočevar in Jure Slak
Opis: Fenwick tree, Lowest common ancestor, Bipartite matching, Master theorem