Modul razvija generalno rješavanje problema i logičko razmišljanje kroz algoritamsko i natjecateljsko programiranje, od prvih koraka u Logo jeziku do Python i C++ priprema za školska i međunarodna natjecanja. Osim programerskih vještina, polaznici programa redovito rade i na matematičkim vještinama koje su neophodne za visoku razinu znanja i uspjehe na natjecanjima.
Osnovni podaci
- Dob:
- Programiranje: Za mlađe i starije osnovnoškolce, te srednjoškolce
- Matematika: stariji osnovnoškolci i srednjoškolci
- Težište:
- Programiranje: programiranje i algoritmi; natjecanja izborno
- Matematika: logika, teorija brojeva, kombinatorika, grafovi
- Preduvjet:
- Programiranje: Digitalna pismenost (preporučeno)
- Matematika: osnovno programiranje
- MZO domena: B
- Infokup: Algoritmi (natjecateljski), Algoritmi (podrška)
- Obuhvat: 2 skupa ishoda učenja iz kurikula, 79 tema
- Napredovanje: grupe po razini znanja, ne po dobi
Ciljevi modula
Algoritamsko programiranje
- napisati prvi vidljivi program i malu igru
- koristiti varijable, petlje i funkcije u kodu
- riješiti algoritamski problem i procijeniti složenost
- (izborno) natjecati se na Infokupu i HONI-ju
Matematika za informatiku
- dokazati tvrdnju (indukcija, kontradikcija)
- primijeniti modularnu aritmetiku
- brojati (kombinatorika, uključi-isključi)
- povezati matematiku s algoritmima
Ishodi učenja
Algoritamsko programiranje. Polaznik rješava algoritamski problem, procjenjuje složenost rješenja i dokazuje ispravnost na zadanim testovima.
Matematika za informatiku. Polaznik dokazuje jednostavnu tvrdnju matematičkom indukcijom i primjenjuje modularnu aritmetiku u algoritamskom zadatku.
MZO ishodi (NN 22/2018)
Ishodi su mapirani na kurikulum Informatike iz Narodnih novina 22/2018. Kodovi su jedinstveni samo unutar smjera, pa je uz svaki naveden i smjer (OŠ - osnovna škola, gimn - gimnazija, PMG - prirodoslovno-matematička gimnazija).
- Algoritamsko programiranje: B.7.1, B.8.2, B.8.3 (OŠ); B.3.5, B.4.2.a (PMG)
- Matematika za informatiku: A.1.4, A.1.5 (gimn); B.3.5 (PMG), uz vezu na MZO Matematiku
Razine usvojenosti
Četiri razine opisuju što ovladavanje modulom znači u praksi. Polaznik napreduje po razini, ne po dobi.
Algoritamsko programiranje
- zadovoljavajuća: riješi jednostavan zadatak uz gotov primjer
- dobra: samostalno riješi standardni zadatak i objasni ga
- vrlo dobra: procijeni složenost i odabere prikladan algoritam
- iznimna: riješi natjecateljski/olimpijski set i dokaže ispravnost
Matematika za informatiku
- zadovoljavajuća: prati dani dokaz i primijeni formulu
- dobra: samostalno dokaže jednostavnu tvrdnju (indukcija)
- vrlo dobra: poveže tehniku s algoritmom i procijeni složenost
- iznimna: dokaže netrivijalan rezultat i primijeni ga na nov problem
Razrada
Razrada je složena po skupovima ishoda učenja i razinama znanja. Polaznik se upisuje na razinu koju je dosegao, neovisno o dobi. Klikni na temu za objašnjenje što ona pokriva.
Algoritamsko programiranje
51 tema · Za mlađe i starije osnovnoškolce, te srednjoškolce
Osnovna razina - USACO Bronze
složenost (Big-O)
procjena koliko je algoritam brz ili spor (O-notacija)
polja
nizovi (array): pohrana i obrada niza vrijednosti
simulacija
korak-po-korak izvođenje pravila zadatka u kodu
potpuna pretraga
brute force - isprobaj sve mogućnosti
sortiranje
slaganje podataka po redu i zašto to pomaže
skupovi i mape
set i dictionary: brzo traženje i brojanje
uvod u pohlepu
pohlepni (greedy) pristup - biraj lokalno najbolje
uvod u grafove
čvorovi i bridovi: kako prikazati mrežu/veze
Srednja razina - USACO Silver
prefiksne sume
brzo zbrajanje raspona preko unaprijed izračunatih zbrojeva
dva pokazivača
two pointers - dva indeksa koja prolaze niz
binarno pretraživanje (i po odgovoru)
polovljenje raspona; traženje najmanjeg valjanog odgovora
redovi prioriteta
priority queue/heap - uvijek izvuci najmanji ili najveći
BFS/DFS
obilazak grafa u širinu i u dubinu
flood fill
bojanje povezanog područja (kao ‘kanta’ u bojanju)
uvod u stabla
stablo - graf bez ciklusa, korijen i djeca
bitovne operacije
rad s bitovima (AND, OR, XOR, pomaci)
Napredna razina - USACO Gold
dinamičko programiranje
DP - razbij problem na podprobleme i pamti rješenja
bitmask DP
DP nad podskupovima prikazanim bitovima
range DP
DP nad svim podintervalima niza
digit DP
brojanje brojeva u rasponu s nekim svojstvom, znamenku po znamenku
teorija brojeva
prosti brojevi, djeljivost, modularna aritmetika
Dijkstra
najkraći put u grafu s težinama bridova
MST
minimalno razapinjuće stablo - najjeftinije povezivanje
DSU (union-find)
struktura za spajanje skupova i provjeru pripadnosti
topološko sortiranje
poredak zadataka koji poštuje ovisnosti
Fenwick/BIT
binarno indeksirano stablo za brze zbrojeve i izmjene
Eulerova tura
spljoštavanje stabla u niz radi upita nad podstablima
LCA
najniži zajednički predak dvaju čvorova u stablu
DP na stablu
dinamičko programiranje po strukturi stabla
polinomno hashiranje
brza usporedba nizova/podnizova preko hash-vrijednosti
Olimpijska razina - USACO Platinum / IOI silabus
geometrijske primitive
vektori, vektorski umnožak, orijentacija - temelj geometrije
segmentna stabla (lijena)
segment tree s lazy propagacijom za rasponske izmjene
rijetka i 2D segmentna stabla
segmentna stabla za velike/rijetke i 2D raspone
sqrt dekompozicija
podjela na blokove ~√n za brže upite
binarno podizanje
skokovi po potencijama dvojke - k-ti predak i LCA
HLD
heavy-light dekompozicija stabla za upite po putu
centroid dekompozicija
rekurzivna podjela stabla po težištu
spajanje malog u veliko (DSU na stablu)
small-to-large: efikasni upiti po podstablima
DP po podskupovima (SOS)
sum-over-subsets - DP preko svih podskupova
podijeli-pa-vladaj DP
optimizacija DP-a podjelom (divide & conquer)
trik konveksne ljuske
convex hull trick / Li Chao za optimizaciju DP-a
sweep line
pomični pravac koji obrađuje događaje po redu
konveksna ljuska
convex hull - najmanji omotač skupa točaka
uključi-isključi
inkluzija-ekskluzija u prebrojavanju
maksimalni protok
max-flow - najveći mogući protok kroz mrežu
sparivanje
matching - uparivanje u (bipartitnom) grafu
Iznad IOI silabusa - CEOI / Codeforces / fakultet
algoritmi nad nizovima (KMP, sufiksno polje, Aho-Corasick)
napredno traženje uzoraka u tekstu (iznad IOI silabusa)
FFT/NTT (množenje polinoma)
brza transformacija za množenje polinoma (iznad IOI silabusa)
teorija igara (Sprague-Grundy, Nim)
dobitne/gubitne pozicije i Grundyjevi brojevi (iznad IOI silabusa)
efikasni protoci (Dinic, MCMF)
brzi maksimalni protok i protok minimalne cijene (iznad IOI silabusa)
persistentne strukture
strukture koje pamte prošla stanja (verzije kroz vrijeme)
Matematika za informatiku
28 tema · stariji osnovnoškolci i srednjoškolci
Osnovna razina
logika i dokaz
iskazi, implikacije i kako izgleda valjan dokaz
skupovi, relacije, funkcije
osnovni matematički jezik za sve ostalo
relacije i parcijalni uređaji
relacije, ekvivalencije i parcijalni uređaji
GCD/Euklid
najveći zajednički djelitelj Euklidovim algoritmom
modularna aritmetika
računanje s ostacima (kao sat, ‘mod n’)
kombinatorika
prebrojavanje - koliko ima mogućnosti
pravila prebrajanja i bijekcije
pravila zbroja/umnoška i dokaz bijekcijom
Booleova algebra
logika istina/laž: I, ILI, NE
Srednja razina
jaka i strukturna indukcija
dokaz indukcijom, uključujući po strukturi
invarijante i stanja
veličina koja se ne mijenja - ključ za dokaz
rekurzije
rješavanje rekurzivnih relacija (npr. T(n))
linearne rekurzije
rješavanje linearnih rekurzivnih nizova
asimptotika (Master teorem)
procjena rasta i Master teorem (podijeli-pa-vladaj)
kongruencije i modularno potenciranje
jednadžbe po modulu i brzo stepenovanje
pigeonhole
Dirichletov princip - više golubova nego rupa
uključi-isključi
inkluzija-ekskluzija u prebrojavanju
teorija grafova
svojstva grafova: stupnjevi, povezanost, bojanje
uvod u vjerojatnost
šanse, događaji i osnovna pravila
uvjetna vjerojatnost i Bayes
uvjetna vjerojatnost, nezavisnost i Bayesov teorem
Napredna razina
funkcije izvodnice
generating functions za prebrojavanje i rekurzije
CRT i modularni inverz
kineski teorem o ostacima i dijeljenje po modulu
teorija brojeva (Fermat/Euler, RSA)
Mala Fermatova, Eulerov teorem, φ i ideja RSA
očekivanje i varijanca
prosjek i rasap slučajne veličine
koncentracijske nejednakosti (Markov, Čebišev, Chernoff)
koliko slučajna veličina odstupa od očekivanja
slučajne šetnje
random walk i njegova svojstva
matrično potenciranje
brzo računanje nizova preko matrica
dokazni pristup grafovima (Hallov teorem, sparivanje)
dokazi o bojenju, sparivanju i Hallovu teoremu
dokazi ispravnosti
formalni dokaz da algoritam radi točno