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 je bil v sredo, 10. februarja 2010, ob 10h.
pdf
- 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
(rok za oddajo je bil 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 (23.02.10), Poštena delitev in delitev brez zavisti
[pdf
tex]
- Maša Baščarević (09.03.10), Implementacija algoritma za iskanje delitve brez zavisti
[[pdf
tex+java]]
- Mateja Slak (11.03.10), Problem trdnih zakonov
[pdf]
- Darko Ostojić (16.03.10), O kriteriju za optimalnost b-toka
[[pdf]]
(-) Lea Klinc (23.03.10), Metoda "Out of kilter"
(-) Mateja Kovačič (30.03.10), Sudoku in celoštevilsko linearno programiranje
(-) Gašper Košmrlj (30.03.10), Celoštevilsko linearno programiranje in igra Lights Out
(-) Maks Mržek (06.04.10), Celoštevilsko linearno programiranje in igra življenja
(-) Jasna Zadnik (13.04.10), Popolnoma unimodularne matrike
(-) Boštjan Kovač (13.04.10), Analiza algoritma za iskanje najcenejšega razvoza
(-) Ana Kozinc (??.04.10), Hitchcockov problem razvoza
(-) Iztok Mežnar (??.??.10), Povprečno najlažji cikel v grafu
(-) Barbara Strniša (??.??.10), Primeri programov za Turingov stroj
(-) Jure Jerovšek (??.??.10), Reševanje optimizacijskih nalog s pomočjo odločitvenih različic
(-) Bojana Jagodic (??.??.10), Naloge o NP-polnosti, 1. del
(-) Mojca Longar (??.??.10), Naloge o NP-polnosti, 2. del
(-) Antonija Pršlja (??.??.10), NP-polnost, "črne škatle" in še kaj
(-) Živa Stepančič (??.??.10), Obstoj trirazsežnega prirejanja je NP-poln problem
(-) Ajda Korošec (??.??.10), Odločitveni problem Praštevilo je v razredu P
(-) Jerica Valjavec (??.??.10), Nekaj nalog s starih kolokvijev in izpitov
(-) Polona Kenič (??.??.10), Analiza prve naloge s prvega kolokvija
(-) Maša Petrovčič (??.??.10), Geometrijska različica Farkaseve leme
Teme za predstavitve:
[-] 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
[-] Implementacija algoritma Goldberg-Tarjan in predstavitev kode
[-] Učinkovita izvedba algoritma Goldberg-Tarjan
[-] Fujishigejev algoritem za maksimalni pretok (del razdelka 8.4 iz knjige Korte, Vygen)
[-] Drevesa Gomoryja in Huja ter minimalni prerezi v grafu (del razdelka 8.6 iz knjige Korte, Vygen)