Eesti Informaatikaolümpiaad

Informaatikaolümpiaadi orienteeruv õppekava

Sellel kaval põhinevad (orienteeruvalt) EIO õppesessioonid, nii et on võimalik endale valida sobiv rühm.

Samuti saab siit iga huviline aimu, milliseid teadmisi võib võistlustel vaja minna. Samas lihtsalt kõikide siintoodud algoritmide päheõppimisega kaugele ei jõua. Olulisem on treenida mõtlemisoskust: algoritmid on vaid mõtete suunamiseks.

Sessioon	Loeng	Teemad
Algajad I	Keerukus, näidete varal	sorteerimine kahendotsing
	Standardteek	STL konteinerid, sh `lower_bound` sisend-väljund
	Linuxi ellujäämiskursus
	Jõumeetod	variantide läbivaatus, eriti rekursioon
	Graafid	BFS ja DFS lühimad teed erikujulised graafid - puud, kahealuselised topoloogiline sorteerimine
Algajad II	Arvuteooria	jäägid algarvud, Eratosthenese sõel SÜT, (laiendatud) Eukleidese algoritm kiire astendamine, pöördelemendid mooduli järgi
Algajad II	DP: lektori valikul mõned tüüpülesanded/teemad, näiteks:	Prefiksisummad Fibonacci / "trepist ronimine" Raha vahetamine Paremale-alla teekonnad ruudustikus
Edasijõudnud I	DP: lektori valikul mõned tüüpülesanded/teemad, näiteks:	Knapsack Pikim ühine osajada, edit distance Pikim kasvav osajada (?) DP puu peal, ümberjuuretamine
Edasijõudnud I	Graafid	lühimad teed (BFS, Dijkstra, Floyd-Warshall) DSU minimaalne toesepuu
Edasijõudnud II	Testimine, silumine	stress testing gdb, `-fsanitize=address`, valgrind
	Kombinatoorika	permutatsioonid, kombinatsioonid: loendamine, genereerimine stars-and-bars valem leksikograafiliselt K-s vähim
	Andmestruktuurid	Fenwicki puu lõikude puu ilma ja koos laiskade uuendustega sweepline kasutamine andmestruktuuridega
Valikvõistluste sessioonid	Puud (lektori valikul üks tärniga teemadest)	ümbernummerdamine LCA ja kahendhüpped väikesemast suuremasse ühendamine* tsentroidid* HLD*
	DP: lektori valikul mõned tüüpülesanded/teemad, näiteks:	bitmaskidega DP mängud? digit DP
	Bitsetid ja muu bitinikerdamine
Suvelaager: mõned alltoodud teemadest	Graafid	DFS-puu, sillad, artikulatsioonipunktid tugevalt sidusad komponendid, 2-SAT
	Andmestruktuurid	oma operatsioonid lõikude puus persistentsus treap jm tasakaalus kahendpuud andmestruktuuride dünamiliseerimine (dynamic connectivity jm)
	Ruutjuurelised võtted	massiivi tükeldamine päringute tükeldamine väikeste ja suurte eraldi vaatlemine Mo algoritm
	Geomeetria	geomeetrilised primitiivid (vektorarvutus jne) kumer kate
	Convex hull trick (LineContainer või Li-Chao puu)
	Tekstialgoritmid	räsimine KMP sufiksistruktuurid
	Elimineerimisprintsiip (inclusion-exclusion principle)
	Maatriksite astendamine lineaarrekurrentside lahendamiseks