Predmet: Priprave na računalniške olimpijade - SŠ dijaki, mentorji (22/23)

Tedenski povzetek

Splošne informacije
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 P20 ob 16:15. Izjemoma bodo priprave tudi prek Zooma.

Namenjene so dijakom, 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
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/
- Razpored predavanj in tekmovanj URL
  (Google calendar: https://calendar.google.com/calendar/embed?src=1vlc7un27t1nhdg6n8j3h43eos%40group.calendar.google.com&ctz=Europe%2FBelgrade)
- Prijavnica na delavnice URL
  Če se imate namen udeležiti priprav za olimpijade, se prosim zabeležite na zgornjem obrazcu, da bomo lahko bolje načrtovali priprave.
- Slack channel o tekmovalnem programiranju URL
  (invite link za 30 dni, začenši 7. 10. 2022: https://join.slack.com/t/tekm-prog/shared_invite/zt-1hki82xwi-q~OHqOZ96MZG_kY3WLdFRA)
- Domače naloge URL
- Plagiatorstvo Stran
- Točkovanje URL
  Tekmovalci skozi celotne priprave nabirajo točke za skupno razvrstitev, na podlagi katere bomo predlagali ekipe za mednarodne olimpijade. Točkovanje je sestavljeno iz spodaj naštetih uteženih komponent. Točke, ki se upoštevajo pri posamezni komponenti, so delež maksimalnega možnega števila točk, ki ga tekmovalec lahko doseže.
  domače naloge (10%)
  COCI (20%); štejejo 3 kola z najvišjim doseženim številom točk
  FIT/ZOTKS (20%); najtežja skupina
  RTK (25%); najtežja skupina
  izbirno (25%)
- Tekmovalni sistem URL
- ZOOM link za priprave (izjemoma) URL
- COCI URL
1. srečanje, 10. 10. - Uvod, Osnovni algoritmi na celih številih
1. srečanje, 10. 10. - Uvod, Osnovni algoritmi na celih številih
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
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, 24. 10. - Osnovne podatkovne strukture
2. srečanje, 24. 10. - Osnovne podatkovne strukture
Predavatelj: Jure Slak
Opis: Osnovne podatkovne strukture: vrsta, sklad, vrsta s prednostjo, povezani seznam, map, set, heap, časovne zahtevnosti operacij
COCI #1 - 5. 11.
COCI #1 - 5. 11.
- COCI URL
3. srečanje, 7. 11. - Osnovni algoritmi na seznamih in nizih
3. srečanje, 7. 11. - Osnovni algoritmi na seznamih in nizih
Predavatelj: Tomaž Hočevar
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
- Posnetek predavanj (lani) URL
- Posnetek predavanj (predlani) URL
4. srečanje, 21. 11. - Osnove strategije reševanja problemov
4. srečanje, 21. 11. - Osnove strategije reševanja problemov
Predavatelj: Nino Bašić

Opis: polni pregled (brute-force, rekurzija), deli in vladaj, požrešni algoritmi
- Posnetek predavanj (lani) URL
- Posnetek predavanj (predlani) URL
COCI #2 - 3. 12.
COCI #2 - 3. 12.
Ni na voljo
5. srečanje, 5. 12. - Dinamično programiranje 1
5. srečanje, 5. 12. - Dinamično programiranje 1
Predavatelj: Janez Brank
Opis: Dinamično programiranje, najdaljše naraščajoče podzaporedje, problem nahrbtnika
6. srečanje, 19. 12. - Dinamično programiranje 2
6. srečanje, 19. 12. - Dinamično programiranje 2
Predavatelj: Vid Kocijan
Opis: najdaljše skupno podzaporedje, urejevalna razdalja, dinamično programiranje na drevesih.
7. srečanje, 9. 1. - Osnovni algoritmi na grafih
7. srečanje, 9. 1. - Osnovni algoritmi na grafih
Predavatelj: Jure Slak
Opis: Osnovni algoritmi na grafih, pregled v širino, pregled v globino, štetje komponent.
COCI #3 - 14. 1.
COCI #3 - 14. 1.
- COCI URL
ZOTKS šolsko tekmovanje v programiranju - 13. 1. 2023
ZOTKS šolsko tekmovanje v programiranju - 13. 1. 2023
https://www.zotks.si/programiranje/razpis
8. srečanje, 23. 1. - Najkrajše poti v grafih
8. srečanje, 23. 1. - Najkrajše poti v grafih
Predavatelj: Janez Brank
Opis: Najkrajše poti, Dijkstra, Bellman-Ford, Floyd-Warshall.
RTK šolsko tekmovanje, 27. 1. 2023
RTK šolsko tekmovanje, 27. 1. 2023
RTK - Tekmovanje ACM iz računalništva in informatike

http://rtk.ijs.si
COCI #4 - 11. 2.
COCI #4 - 11. 2.
Ni na voljo
9. srečanje, 13. 2. - Minimalna vpeta drevesa
9. srečanje, 13. 2. - Minimalna vpeta drevesa
Predavatelj: Luka Fürst
Opis: Union-Find, minimalno vpeto drevo, Kruskal, Prim.
10. srečanje, 27. 2. Napredne podatkovne strukture
10. srečanje, 27. 2. Napredne podatkovne strukture
Predavatelj: Tomaž Hočevar
Opis: binarno iskalno drevo, trie, druge razširjene podatkovne strukture, še posebej segment tree
- Posnetek predavanj (lani) URL
- Posnetek predavanj (predlani) URL
ZOTKS državno tekmovanje v programiranju - 12. 3. 2023
ZOTKS državno tekmovanje v programiranju - 12. 3. 2023
https://www.zotks.si/programiranje/razpis
COCI #5 - 11. 3
COCI #5 - 11. 3
Ni na voljo
11. srečanje, 13. 3. - Geometrija
11. srečanje, 13. 3. - Geometrija
Predavatelj: Nino Bašić

Opis: Geometrija: ploščine, skalarni produkt, vektorski produkt, konveksna ovojnica, kompresija koordinat, presečišča, sweep line.
RTK - 25. 3.
RTK - 25. 3.
Ni na voljo
12. srečanje, 27. 3. - Uporabe DFS
12. srečanje, 27. 3. - Uporabe DFS
Predavatelj: Luka Fürst
Opis: Topološko urejanje, močno povezane komponente, mostovi in prerezna vozlišča.
- Prosojnice Datoteka
- Programi Datoteka
13. srečanje, 11. 4. - Dinamično programiranje 3
13. srečanje, 11. 4. - Dinamično programiranje 3
Pozor: srečanje je izjemoma v torek.
Predavatelj: Tomaž Hočevar
Opis: Napredno dinamično programiranje: bitmask DP - TSP, Steiner tree, Convex-hull optimization, Divide and conquer optimization.
- Longest Increasing Subsequence Datoteka
- Travelling Salesman Problem Datoteka
14. srečanje, 24. 4. - Izbrana poglavja
14. srečanje, 24. 4. - Izbrana poglavja
Ni na voljo
končno izbirno tekmovanje - 6. 5.
končno izbirno tekmovanje - 6. 5.
Tekmovanje bo potekalo na sistemu https://putka-rtk.acm.si od 9:00 do 13:00.
- Tekmovalni sistem URL

Priprave na računalniške olimpijade - SŠ dijaki, mentorji (22/23)

Tedenski povzetek

Splošne informacije

1. srečanje, 10. 10. - Uvod, Osnovni algoritmi na celih številih

2. srečanje, 24. 10. - Osnovne podatkovne strukture

COCI #1 - 5. 11.

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

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

COCI #2 - 3. 12.

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

6. srečanje, 19. 12. - Dinamično programiranje 2

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

COCI #3 - 14. 1.

ZOTKS šolsko tekmovanje v programiranju - 13. 1. 2023

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

RTK šolsko tekmovanje, 27. 1. 2023

COCI #4 - 11. 2.

9. srečanje, 13. 2. - Minimalna vpeta drevesa

10. srečanje, 27. 2. Napredne podatkovne strukture

ZOTKS državno tekmovanje v programiranju - 12. 3. 2023

COCI #5 - 11. 3

11. srečanje, 13. 3. - Geometrija

RTK - 25. 3.

12. srečanje, 27. 3. - Uporabe DFS

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

14. srečanje, 24. 4. - Izbrana poglavja

končno izbirno tekmovanje - 6. 5.