Topic outline

  • Splošne informacije

    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 P18 (zimski semester) in P21 (letni semester).

    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. 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:

    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.

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

  • 1. srečanje, 21. 10. - 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
    • 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, 4. 11. - Osnovne podatkovne strukture

    Predavatelj: Jure Slak

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

  • COCI #2 - 16. 11.

    • 3. srečanje, 18. 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, 2. 12. - Osnove strategije reševanja problemov

      Predavatelj: Tomaž Hočevar

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

      • COCI #3 - 14. 12.

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

          Predavatelj: Luka Fuerst

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

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

          Predavatelj: Vid Kocijan

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

        • COCI #4 - 18. 1.

          • 7. srečanje, 20. 1. - Osnovni algoritmi na grafih

            Predavatelj: Janez Brank

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

          • COCI #5 - 8. 2.

            • 8. srečanje, 10. 2. - Najkrajše poti v grafih

              Predavatelj: Janez Brank

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

              • 9. srečanje, 2. 3. - Minimalna vpeta drevesa

                Predavatelj: Tim Poštuvan

                Opis: Union-Find, minimalno vpeto drevo, Kruskal, Prim.

                • COCI #6 - 7. 3.

                  • FIT - 14. 3.

                    Festival inovativnih tehnologij (ZOTKS)

                    https://www.zotks.si/programiranje/novice/računalniško-programiranje

                    • 10. srečanje, 16. 3. - Napredne podatkovne strukture

                      Predavatelj: Tim Poštuvan

                      Opis: binarno iskalno drevo, trie, druge razširjene podatkovne strukture, še posebej segment tree

                      • RTK - 28. 3.

                        RTK - Tekmovanje ACM iz računalništva in informatike

                        http://rtk.ijs.si/

                        https://putka-rtk.acm.si/competitions/rtk_2019_3/

                        • 11. srečanje, 6. 4. - Geometrija

                          Predavatelj: Vid Kocijan

                          Opis: Geometrija: ploščine, vektorski produkt, konveksna ovojnica, kompresija koordinat, presečišča, sweep line.

                        • 12. srečanje, 20. 4. - Uporabe DFS

                          Predavatelj: Filip Koprivec

                          Opis: Topološko urejanje, močno povezane komponente, mostovi in prerezna vozlišča.

                        • 13. srečanje, 4. 5. - Dinamično programiranje 3

                          Predavatelj: Tomaž Hočevar

                          Opis: Napredno dinamično programiranje: bitmask DP - TSP, Steiner tree, Convex-hull optimization, Divide and conquer optimization.

                        • 14. srečanje, 18. 5. - Izbrana poglavja

                          Predavatelj: Tomaž Hočevar

                          Opis: Fenwick tree, Lowest common ancestor, Bipartite matching, Heavy-light decomposition, Centroid decomposition

                        • končno izbirno tekmovanje - 23. 5.