Programiranje v višji prestavi (2013)

Oris teme

• Splošno
  

  Splošno

  • Forum

    Vsebinska in organizacijska obvestila.

  • Linux - osnovni konzolski ukazi Stran

    Osnovni ukazi za preživetje v Linuxu

  • UVa online judge URL

    Ogromna zbirka nalog Univerze v Valladolidu, Španija.

  • 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.

  • Literatura za radovedne: Priročnik za pripravo na tekmovanja iz programiranja (v angleščini) URL

    Steven S. Skiena, Miguel A. Revilla
    Programming Challenges - The programming Contest Training Manual (Springer, 2003)

• Ponedeljek: Osnovne podatkovne strukture, algoritmi in tehnike
  

  Ponedeljek: Osnovne podatkovne strukture, algoritmi in tehnike

  Matevž Jekovec

  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

  • Naloge Stran
  • Prosojnice Datoteka
• Torek: Algoritmi na grafih, 1. del
  

  Torek: Algoritmi na grafih, 1. del

  Nino Bašić

  Vsebina:

  • Kaj je graf?
  • Stopnja vozlišča, sprehodi, poti. Lema o rokovanju
  • Predstavitve grafov
    • Matrika sosednosti
    • Seznam sosedov
  • Eulerjev graf (Problem königsberških mostov)
  • Iskanje v globino (DFS)
  • Iskanje v širino (BFS)
  • Povezanost, povezane komponente
  • Dvodelni grafi
  • Usmerjeni grafi
  • Topološko urejanje

  • Naloge Stran
• Sreda: Algoritmi na grafih, 2. del
  

  Sreda: Algoritmi na grafih, 2. del

  Mitja Trampuš

  Vsebina:

  • Najkrajše poti
  • Floyd-Warshallov algoritem
  • Dijkstrov algoritem
  • Bellman-Fordov algoritem, detekcija neg. ciklov

  • Strongly connected components (krepko povezane komponente)
  • Link hopping (lowest common ancestor problem)
  • Ford-Fulkerson - max pretok, min prerez
  • Min cost max flow, dvodelno prirejanje
  • "Successive shortest path" algoritem
  • Prevod problema prirejanja na min cost max flow problem

  • Naloge Stran
• Četrtek: Dinamično programiranje
  

  Četrtek: Dinamično programiranje

  Janez Brank

  Vsebina:

  • Množenje matrik. Oklepajski izrazi. Delitev daljice
  • Najdaljše skupno podzaporedje (LCS). Urejevalna razdalja
  • Razdelitev na podzaporedja z najmanjšo vsoto (problem pisarjev)
  • Floyd-Warshallov algoritem
  • Najdaljše naraščajoče podzaporedje (LIS)
  • 0/1-nahbrtnik
  • Trgovski potnik

  • Naloge Stran
  • Prosojnice Datoteka
  • Prosojnice Datoteka
• Petek: Tekmovanje
  

  Petek: Tekmovanje

  Žiga Ham

  Tekmovanje dostopno v okolju UVa na naslovu:
  http://umt.boocode.com/viewcontest.php?id=1283