MathOS cup
Srednjoškolsko ekipno natjecanje iz matematike i programiranja
Sadržaji - sekcija programiranje
Osnove
- input i output
- upravljanje poljima i stringovima
- sortiranje
- binarni zapis broja
- definicija prefiksa i sufiksa
Teorija brojeva
- definicija prostog broja
- definicija dijelitelja i kako ih pronaći
- definicija prostog faktora
- osnovne matematičke operacije i jednakosti npr.
- √x
- (a + b)2 = a2 + 2ab + b2
- ax+y = axay
- (a+b+c)%m = ((a+b)%m+c)%m (modulo operacije)
- GCD i LCM
Kombinatorika
- definicija faktorijela
- Fibonaccijevi brojevi
- binomni koeficijent nCr
- definicija polinoma
- Hash stringa
Grafovi
- definicija grafa
- definicija stabla
- definicija usmjerenog grafa
- kako učitati graf i kako učitati stablo
- BFS i DFS
- najkraći put pomoću BFS
- bojanje grafa u dvije boje
- postojanje ciklusa u grafu
- broj povezanih komponenata u neusmjerenom grafu
- DSU/Union-Find struktura
- Minimalno razapinjuće stablo (MST)
Tehnike za dizajn algoritama
- brute-force/exhaustive search
- greedy algoritmi
- divide and conquer (binary search i ostali)
- backtracking
- dynamic programming
- branch and bound algoritmi
- randomizirani algoritmi
Geometrija
- točke u ravnini
- jednadžba pravca
- udaljenost dvije točke
- Eulidska udaljenost i Manhattan udaljenost
- udaljenost točke od pravca
- definicija konveksnog poligona
- površina trokuta, pravokutnika i kruga
- kut između dva pravca