Računalništvo 3 (2009/2010)
Predavatelj: Martin Juvan
Asistent: Martin Juvan
O predmetu in obveznostih:
klik
Kolokvija:
(zimski izpitni rok je bil v četrtek, 28. januarja 2010, ob 10h v predavalnici 2.03
- rezultati)
- 1. kolokvij bo v sredo, 10. februarja 2010, ob 10h v predavalnici 2.05.
- 2. kolokvij bo konec maja ali v začetku junija 2010.
Domače naloge: seznam.
- 1. domača naloga: pdf
(rok za oddajo je bil torek, 13. oktobra 2009, do 13.15h)
- 2. domača naloga: pdf
(rok za oddajo je bil četrtek, 12. novembra 2009, do 11.15h)
- 3. domača naloga: pdf
(rok za oddajo je bil torek, 15. decembra 2009, do 13.15h)
- 4. domača naloga: pdf
(novi rok za oddajo je ponedeljek, 22. februarja 2010, do 12h)
Kolokviji in izpiti:
2008/09:
k1,
k2,
i1,
i2,
i3,
i4.
2007/08:
k1,
k2,
i1,
i2,
i3,
i4.
2006/07:
k1,
k2+i1,
i2,
i3,
i4,
i5.
2005/06:
k1,
k2+i1,
i2,
i3,
i4,
i5.
Gradiva:
- optimizacijske naloge in primeri:
pdf (definicije),
pdf+pdf (konveksnost).
- metoda simpleksov:
pdf.
- dualnost pri linearnem programiranju:
pdf (osnovna teorija),
pdf (Farkaseva lema).
- matrične igre:
pdf.
- maksimalni pretok:
pdf (definicije),
pdf+pdf (Ford-Fulkerson),
pdf (Goldberg-Tarjan).
- pokritja in prirejanja v dvodelnih grafih:
- madžarska metoda:
- naloga kitajskega poštarja:
- razvoz z omejitvami:
- ...
Gradiva z vaj:
kraljice kot ILP (nb),
slovarji ipd. (pdf),
dualno dopolnjevanje (pdf),
farkas (pdf),
razvoz (pdf)
Predstavitve:
(gradivo, navedeno v oklepajih, ni bilo natančno pregledano)
- Vesna Rebselj (20.10.09), Konveksne množice
[[pdf
tex]]
- David Gajser (20.10.09), Verižni ulomki
[popravljeno: pdf
tex]
- Ines Pogačar (27.10.09), Poliedri
[[pdf
tex]]
[popravljeno: pdf
tex]
- Jernej Rus (03.11.09), Največja krogla v konveksnem poliedru
[[pdf
nb]]
- Anja Ekar (03.11.09), Problem razvoza in metoda simpleksov za omrežja
[pdf+pdf+pdf
rar]
- Mojca Berden (10.11.09), Zgodovina linearnega programiranja
[[pdf+pdf]]
[popravljeno: pdf
tex+jpgs]
- Kaja Puhan (17.11.09), Konveksne funkcije
[pdf
tex+pdfs]
- Urša Šolinc (08.12.09), Dolžina zapisa rešitev linearnega programa
[[pdf]]
- Urša Remžgar (05.01.10), Najkrajše poti in Bellman-Fordov algoritem
[[pdf+ppt]]
(-) Tamara Brudar (??.02.10), Poštena delitev in delitev brez zavisti
Teme za predstavitve:
- Povprečno najlažji cikel v grafu (razdelek 7.3 iz knjige Korte, Vygen)
- Fujishigejev algoritem za maksimalni pretok (del razdelka 8.4 iz knjige Korte, Vygen)
- Učinkovita izvedba algoritma Goldberg-Tarjan
- Implementacija algoritma Goldberg-Tarjan in predstavitev kode
- Drevesa Gomoryja in Huja ter minimalni prerezi v grafu (del razdelka 8.6 iz knjige Korte, Vygen)
[-] Konveksne ovojnice in poliedri (razdelek 3.4 iz knjige Korte, Vygen)
[-] Farkaseva lema in sorodne trditve
[-] Dokazi Farkaseve leme
[-] Primer Kleeja in Mintyja
[-] Iskanje strogega sedla matrike
[-] Mengerjevi izreki
[-] Tutteov izrek o obstoju popolnega prirejanja v grafu