Weekly outline

  • Splošne informacije

    Priprave na računalniške olimpijade CEOI, BOI, EGOI in IOI potekajo ob ponedeljkih od 16:00 do 19:00 na FRI, Večna pot 113. Učilnica bo oznanjena vnaprej, če ni drugače, bo to P19 ob 16:15. Izjemoma bodo priprave tudi prek Zooma.

    Namenjene so dijakom in dijakinjam, ki se želijo udeležiti tekmovanj iz programiranja in algoritmov (državnih ali mednarodnih) ter njihovim mentorjem.

    Vsakim pripravam bo sledilo nekaj domačih nalog, ki prispevajo h končnemu rezultatu. 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 skozi celo leto potekala tudi izbirna tekmovanja, ki bodo upoštevana pri izboru za CEOI in EGOI. Prvi del predstavljajo tekmovanja COCI (Croatian Open Competition in Informatics), drugi del tekmovanja najtežjih skupin na tekmovanjih FIT in RTK, tretji del pa predstavlja končno izbirno tekmovanje.

    Organizatorji priprav so:

    • dr. Jure Slak, jure.slak@gmail.com, Google. (ex. Institut Jožef Stefan in Fakulteta za matematiko in fiziko)
    • doc. dr. Tomaž Hočevar, tomaz.hocevar@fri.uni-lj.si, Fakulteta za računalništvo in informatiko
    • doc. dr. Nino Bašić, nino.basic@famnit.upr.si, Fakulteta za matematiko, naravoslovje in informacijske tehnologije
    • dr. Janez Brank, janez.brank@ijs.si, Institut Jožef Stefan
    • doc. dr. Luka Fürst, luka.fuerst@fri.uni-lj.si, Fakulteta za računalništvo in informatiko
    • Filip Koprivec, filip.koprivec@fmf.uni-lj.si, Institut Jožef Štefan in Fakulteta za matematiko in fiziko
    • Bor Grošelj Simić, bgs@turminal.net, Fakulteta za matematiko in fiziko

    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.

    Za vprašanja je na voljo tudi kanal #priprave na Slack-u za tekmovalno programiranje: https://tekm-prog.slack.com/

  • 1. srečanje, 9. 10. [zoom] - Uvod, Osnovni algoritmi na celih številih

    Predavatelj: Jure Slak

    Opis:

    Literatura:

    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
    Nam ni uspelo, in bo prišlo na vrsto kdaj drugič:
    • 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


  • 2. srečanje, 23. 10. - Osnovne podatkovne strukture

    Predavatelj: Bor Grošelj Simić

    Opis: Osnovne podatkovne strukture: vrsta, sklad, vrsta s prednostjo, povezani seznam, map, set, heap, časovne zahtevnosti operacij

  • COCI #1 - 4. 11.

  • 3. srečanje, 6. 11. - Osnovni algoritmi na seznamih in nizih

    Predavatelj: Janez Brank

    Opis: 

    Osnovni algoritmi na seznamih: 

    • urejanje: [bubble, selection, insertion]-sort, [quick, merge, heap]-sort, [counting, bucket, radix]-sort
    • bisekcija

    Predprocesiranje seznamov:

    • kumulativne vsote: poizvedbe na intervalih, spremembe na intervalih
    • korenska dekompozicija (sqrt decomposition, dekompozicija poizvedb)
    • redka tabela (sparse table)
    Osnovni algoritmi na nizih: 

    • iskanje podniza: hashing (Rabin-Karp), z-funkcija, KMP

  • 4. srečanje, 20. 11. - Osnove strategije reševanja problemov

    Predavatelj: Nino Bašić

    Opis: polni pregled (brute-force, rekurzija), deli in vladaj, požrešni algoritmi

  • 5. srečanje, 4. 12. - Dinamično programiranje 1

    Predavatelj: Jure Slak

    Opis: Dinamično programiranje, najdaljše naraščajoče podzaporedje, problem nahrbtnika

  • 6. srečanje, 18. 12. - Osnovni algoritmi na grafih

    Predavatelj: Vid Kocijan

    Opis: Osnovni algoritmi na grafih, pregled v širino, pregled v globino, štetje komponent.

  • 7. srečanje, 8. 1. - Dinamično programiranje 2

    Predavatelj: Janez Brank

    Opis: najdaljše skupno podzaporedje, urejevalna razdalja, dinamično programiranje na drevesih.

  • 8. srečanje, 22. 1. - Najkrajše poti v grafih

    Predavatelj: Filip Koprivec

    Opis: Najkrajše poti, Dijkstra, Bellman-Ford, Floyd-Warshall.