Programiranje v višji prestavi (2012)
Osnutek odseka
-
-
-
V tem forumu pošiljamo vprašanja in se pogovarjamo o, recimo, rešitvah nalog in podobno.
-
-
-
Janezova "predavanja" še iz časov, ko smo priprave na tekmovanje imeli na mailing listi. Zelo pregledna razlaga večine tem, ki jih na poletni šoli srečali letos, in še nekaterih drugih.
-
-
Andrej Brodnik
Vsebina:
- Uvod
- Osnovne podatkovne strukture: sklad, vrsta, slovar, vrsta s prednostjo, množica
- Drevesa za okus
- Delo z nizi
- Veliki O in prijatelji
- Urejanje (sorting)
- Osnovne tehnike načrtovanja algoritmov
-
Mitja Trampuš
Vsebina:
- Kaj je graf
- Cestna omrežja, prijateljstva
- Drevo, cikel, usmerjen graf, utežen graf
- Predstavitve grafov
- Matrika sosednosti
- Seznam sosedov
- Implicitna predstavitev (npr. premikanje po gridu)
- DFS (iskanje v globino) z rekurzijo
- Pazi na cikle
- DFS z ročno vodenim stackom
- BFS (iskanje v širino)
- Povezanost v neusmerjenih grafih. Komponente za povezanost
- Dvodelnost in 2-obarvljivost
- Intermezzo: Lahki nalogi za začetnike
- Facebook friend suggest
- Height map grid, iz zgornjega levega vogala izvira voda. Bo pritekla v spodnji desni vogal?
- Premer drevesa
- DAG (usmerjen acikličen graf) in topološko urejanje
- Najmanjše vpeto drevo (Minimum spanning tree)
- Najkrajše poti
- Bellman-Fordov algoritem
- Dijkstrov algoritem
- Warshall-Floydov algoritem (bo razložil Janez v četrtek)
- Eulerjev obhod
- Problem trgovskega potnika (Travelling salesperson problem). Hamiltonov obhod (opis problema, NP-težkost)
- Kaj je graf
-
Nino Bašić
Vsebina:
-
Janez Brank
Vsebina:
- Množenje matrik. Oklepajski izrazi. Delitev daljice
- Najdaljše skupno podzaporedje (LCS). Urejevalniška razdalja
- Floyd-Warshallov algoritem
- Najdaljše naraščajoče podzaporedje (LIS)