Vodič · Algoritmi
Algoritmi – vodič kroz oblasti
Algoritam je tačno opisan postupak za rešavanje problema. Ovde su lekcije iz algoritama i struktura podataka, od sortiranja i binarne pretrage do grafova i dinamičkog programiranja – sa objašnjenjima, programima u C++-u i zadacima sa rešenjima.
Svaka oblast ima svoj vodič sa predloženim redosledom lekcija. Materijal je namenjen talentovanim učenicima od 5. razreda, takmičarima i srednjoškolcima.
- 5–8. razred i srednja škola
- C++
- Priprema za takmičenja
1 Osnovni algoritmi
Prve oblasti: rade se odmah posle nizova i funkcija.
Sortiranje
Izbor, umetanje, merge sort, quick sort, funkcija sort.
Otvori lekciju →Binarna pretraga
Pretraga u sortiranom nizu, lower_bound, binarna pretraga po rešenju.
Otvori lekciju →Matematički algoritmi
NZD, prosti brojevi, brzo stepenovanje, teorija brojeva, kombinatorika.
Otvori lekciju →Složenost algoritama
O-notacija, formule umesto petlji, ubrzavanje rešenja.
Otvori lekciju →2 Strukture podataka
Kako čuvati podatke da bi operacije bile brze.
3 Rekurzija, dinamičko programiranje i napredne tehnike
Načini razmišljanja kojima se rešava većina takmičarskih zadataka.
Rekurzija i bektreking
Rekurzivne funkcije, bektreking, permutacije, Sudoku.
Otvori lekciju →Dinamičko programiranje
Memoizacija, Knapsack, LCS, DP na mreži.
Otvori lekciju →Napredne tehnike
Dva pokazivača, prefiksne sume, monotoni stek, metoda događaja, bitovske maske, podeli pa vladaj, pohlepni algoritmi.
Otvori lekciju →4 Grafovi i stabla
Pretrage, najkraći putevi, minimalna razapinjuća stabla i napredni algoritmi na grafovima.
Predloženi redosled
Korisni spoljni resursi
- CSES Problem Set – odeljak „Sorting and Searching“, zadaci sa automatskom proverom
- Petlja – zbirke zadataka na srpskom sa automatskom proverom
- USACO Guide – plan učenja algoritama po nivoima (engleski)
- cp-algorithms – enciklopedija takmičarskih algoritama (engleski)
Algoritmi: Vodič kroz osnovne i napredne tehnike
Ova sekcija obuhvata najvažnije oblasti iz oblasti algoritama: matematičke algoritme, strukture podataka, sortiranje, rekurziju, dinamičko programiranje, grafove i napredne tehnike. Materijal je namenjen srednjoškolcima, takmičarima i svima koji žele dublje razumevanje algoritamskih principa.
Šta možete očekivati u ovom tutorijalu
Tutorijal je strukturisan tako da vas postepeno vodi od osnovnih pojmova do naprednih tehnika. Svaka podsekcija sadrži:
- Teoriju — jasna objašnjenja ključnih koncepata i analize složenosti (vremenska i memorijska).
- Ilustrovane primere — mali primeri koji pokazuju korak-po-korak kako algoritam radi.
- Implementacije — gotovi kodovi (pseudokod, Python/C++/Java) koji se mogu lako testirati i modificirati.
- Zadatke za vežbu — problemi različitih težina sa komentarima za rešenja i optimizacije.
- Savet i upotreba — kada je koji pristup prikladan, tipične greške i optimizacione tehnike.
Napomena: neke teme (posebno napredne teme i kompletna obrada grafova i stabala) su planirane, ali još uvek nisu u potpunosti obrađene — biće dodate redovno.
Matematički algoritmi
- Uvod u matematičke algoritme
- Fibonačijev niz
- Prosti brojevi i faktorizacija
- Euklidov algoritam (NZD)
- Brzo stepenovanje
- Teorija brojeva za takmičenja
- Kombinatorika: brojanje rasporeda i izbora
Strukture podataka
- Uvod u strukture podataka
- Vektori i liste
- DSU – Disjoint Set Union
- Osnovne strukture podataka
- Red sa prioritetom (priority_queue)
- Fenwick stablo (BIT)
- Segmentno stablo
Sortiranje
Rekurzija i bektreking
Vodič: Rekurzija i bektreking
- Uvod u rekurziju
- Faktorijel, stepen i NZD – rekurzivno
- Rekurzivni algoritmi
- Hanojske kule
- Bektreking
- Permutacije i kombinacije
- Sudoku rešavač
Dinamičko programiranje
Vodič: Dinamičko programiranje
- Uvod u dinamičko programiranje
- Fibonačijev niz, memoizacija i DP
- Problem ranca (Knapsack)
- Najduži zajednički podniz (LCS)
- DP na mreži
Grafovi i stabla
Ova sekcija sadrži osnovne i napredne lekcije o grafovima i stablima, uključujući pretrage, najkraće puteve,
minimalna razapinjuća stabla i algoritme koji su baza za takmičenja iz informatike.
Preporučena putanja učenja:
Mapa učenja – Grafovi i stabla
- BFS i DFS — osnove kretanja kroz graf
- Topološko sortiranje (usmereni grafovi)
- Otkrivanje ciklusa u usmerenim grafovima (DAG)
- Dijkstra — najkraći put (bez negativnih grana)
- Bellman-Ford i Floyd-Warshall — najkraći putevi
- Primov algoritam — MST
- Kruskalov algoritam — MST + DSU
- Eulerovi putevi i ciklusi
- Mostovi i artikulisani čvorovi (Tarjan)
- SCC — Komponente jake povezanosti
- Dinamika u DAG-u — primene i rešavanje zadataka
Napredne tehnike
- Binarna pretraga na odgovoru
- Podeli pa vladaj
- Gramzivi (pohlepni) algoritmi
- Fenwick stablo (BIT)
- Segmentno stablo
- Tehnika dva pokazivača (u pripremi)
- Prefiksni i sufiksni zbirovi (u pripremi)
Kratki primeri (da dobijete bolju sliku)
Donosimo dva kratka, konkretna primera sa objašnjenjem i implementacijom — da biste odmah videli kako se teorija primenjuje:
Primer 1 — Euklidov algoritam za najveći zajednički delilac (NZD)
Ideja: NZD(a, b) = NZD(b, a % b). Algoritam je jednostavan, brzo konvergira i radi u O(log min(a,b)).
// Pseudokod (Python-utsecanje)
def gcd(a, b):
while b != 0:
a, b = b, a % b
return a
# Primer: gcd(48, 18) -> 6
Primer 2 — DFS (pretraživanje grafa) i broj povezanih komponenti
Ideja: koristimo rekurziju ili stack da posetimo sve čvorove u komponenti. Kompleksnost O(N + M) za graf sa N čvorova i M grana.
// Pseudokod (Python-utsecanje)
# graf predstavljen kao adjacency lista: graph[v] = [susedi]
visited = set()
def dfs(v):
stack = [v]
while stack:
x = stack.pop()
if x in visited: continue
visited.add(x)
for nei in graph[x]:
if nei not in visited:
stack.append(nei)
# Brojanje povezanih komponenti:
count = 0
for v in all_vertices:
if v not in visited:
dfs(v)
count += 1