Programiranje v višji prestavi (2012)

Oris teme

• Splošno
  

  Splošno

  • Forum novic

    Splošne novice in najave.
    
    
  • Vprašanja in odgovori Forum

    V tem forumu pošiljamo vprašanja in se pogovarjamo o, recimo, rešitvah nalog in podobno.

  • Linux - osnovni konzolski ukazi Stran

    Osnovni ukazi za preživetje v Linuxu.

  • UVa online judge URL

    Ogromna zbirka nalog Univerze v Valladolidu.

  • Janez Brank: Teorija Datoteka

    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.

• Ponedeljek: Osnovne podatkovne strukture, algoritmi in tehnike
  

  Ponedeljek: Osnovne podatkovne strukture, algoritmi in tehnike

  Andrej Brodnik

  Vsebina:
  

  1. Uvod
  2. Osnovne podatkovne strukture: sklad, vrsta, slovar, vrsta s prednostjo, množica
  3. Drevesa za okus
  4. Delo z nizi
  5. Veliki O in prijatelji
  6. Urejanje (sorting)
  7. Osnovne tehnike načrtovanja algoritmov

  • Prosojnice Datoteka
  • Naloge Stran
• Torek: Najnujnejše o grafih
  

  Torek: Najnujnejše o grafih

  Mitja Trampuš

  Vsebina:
  

  1. Kaj je graf
     • Cestna omrežja, prijateljstva
     • Drevo, cikel, usmerjen graf, utežen graf
  2. Predstavitve grafov
     • Matrika sosednosti
     • Seznam sosedov
     • Implicitna predstavitev (npr. premikanje po gridu)
  3. DFS (iskanje v globino) z rekurzijo
     • Pazi na cikle
  4. DFS z ročno vodenim stackom
  5. BFS (iskanje v širino)
  6. Povezanost v neusmerjenih grafih. Komponente za povezanost
  7. Dvodelnost in 2-obarvljivost
  8. Intermezzo: Lahki nalogi za začetnike
     • Facebook friend suggest
     • Height map grid, iz zgornjega levega vogala izvira voda. Bo pritekla v spodnji desni vogal?
  9. Premer drevesa
  10. DAG (usmerjen acikličen graf) in topološko urejanje
  11. Najmanjše vpeto drevo (Minimum spanning tree)
  12. Najkrajše poti
      • Bellman-Fordov algoritem
      • Dijkstrov algoritem
      • Warshall-Floydov algoritem (bo razložil Janez v četrtek)
  13. Eulerjev obhod
  14. Problem trgovskega potnika (Travelling salesperson problem). Hamiltonov obhod (opis problema, NP-težkost)

  • Naloge Stran
• Sreda: Dinamično programiranje – 1. del
  

  Sreda: Dinamično programiranje – 1. del

  Nino Bašić

  Vsebina:
  

  1. Trikotnik števil (The Triangle, IOI 1994)
  2. Računanje binomskega koeficienta in Stirlingovih števil 2. vrste
  3. Preštevanje particij naravnih števil
  4. Linearna razdelitev (UVa 714 - Copying Books)
  5. 0/1 nahrbtnik. Coin Change
  6. Problem trgovskega potnika. Maksimalno prirejanje v grafih
  7. UVa 108 - Maximum Sum

  • Naloge Stran
• Četrtek: Dinamično programiranje – 2. del
  

  Četrtek: Dinamično programiranje – 2. del

  Janez Brank

  Vsebina:

  1. Množenje matrik. Oklepajski izrazi. Delitev daljice
  2. Najdaljše skupno podzaporedje (LCS). Urejevalniška razdalja
  3. Floyd-Warshallov algoritem
  4. Najdaljše naraščajoče podzaporedje (LIS)

  • Folije Datoteka
  • Naloge Stran
• Petek: Izkušnje s tekmovanj
  

  Petek: Izkušnje s tekmovanj

  Žiga Ham

  • Prosojnice URL
• Petek: Tekma
  

  Petek: Tekma

  • Tekma Stran
• Tema 7
  

  Tema 7
• Tema 8
  

  Tema 8
• Tema 9
  

  Tema 9
• Tema 10
  

  Tema 10