====== Kombinatorická optimalizace ======

  * Stránky předmětu: https://moodle.dce.fel.cvut.cz/course/view.php?id=21
  * Přednášející: [[http://support.dce.felk.cvut.cz/pub/hanzalek/|Zdeněk Hanzálek]]
  * Cvičící: Zdeněk Hanzálek, Přemysl Šůcha, Jan Kelbel, Jiří Trdlička, Michal Kutil, Zdeněk Baumelt, Roman Čapek


===== Cvičení =====

==== 2014/2015 ====
[[courses/a4b35ko/ukol-2015-5|warehousing]] | [[courses/a4b35ko/ukol-2015-6|bradley]]

**!!! Můžete sem prosím dát někdo zadání z testů ze cvičení ? Díkes !!!**

**Praktický test** - jde o výpočet toku v síti (na test bylo něco málo přes hodinu času a bylo možné používat libovolné materiály, jinak říkali ze každé cvičeni bude mít jiné zadáni){{:courses:ko_prakticky_test_2015.pdf|}}

 2. zadání: knapsack - dány 2 batohy, předměty s váhou a cenou; Naplnit batohy co nejcenějšíma předmětama, pomocí ILP, každý předmět může být jen v jednom batohu. 


[[courses/a4m35ko/ilpbin|ILP binární formule]]

==== 2013/2014 ====
  - [[courses/a4b35ko/ukol-2014-1|optimized data storing]]
  - [[courses/a4b35ko/ukol3|call center scheduling]]
  - [[courses/a4b35ko/ukol4|function approximation]]
  - [[courses/a4b35ko/ukol5|binary image reconstruction]]
==== starší/2013 ====
[[courses/a4b35ko/ukol1|1. úkol]] | [[courses/a4b35ko/ukol2|2. úkol]] | [[courses/a4b35ko/ukol3|3. úkol (call centre)]] | [[courses/a4b35ko/ukol4|4. úkol (func approx)]] | [[courses/a4b35ko/ukol5|5. úkol (bin. image)]] | [[courses/a4b35ko/ukol6|6. úkol]] | [[courses/a4b35ko/ukol7|7. úkol]]

===== Testy =====

**2014/15 LS: ** [[courses/a4b35ko/test1_2015|1. test - přednáška ve 4. týdnu]] | [[courses/a4b35ko/test2_2015|2. test - přednáška v 8. týdnu]] | [[courses/a4b35ko/test3|Praktický test - cvičení]] | [[courses/a4b35ko/test3_15-prednaska|3 test - přednáška v 12. týdnu]] \\

**2013/14 LS: ** [[courses/a4b35ko/test1_2014|1. test - přednáška ve 4. týdnu]] | [[courses/a4b35ko/test2_2014|2. test - přednáška v 8. týdnu]] | [[courses/a4b35ko/test3-prednaska|3 test - přednáška v 12. týdnu]] \\
[[courses/a4b35ko/test1|1 test - přednáška ve 4. týdnu]] | [[courses/a4b35ko/test2|2 test - přednáška v 8. týdnu]] | [[courses/a4b35ko/test3|3 test - cvičení v 10. týdnu]] | [[courses/a4b35ko/test3-2012|3 test - cvičení v 10. týdnu (2012)]]

===== Semestrálka =====

[[courses/a4b35ko/cutting_2d|2D optimalní řezný problém]]

{{:courses:rozvhovani-semestralka.zip| Rozvrh zdravotních sester ILP}}

{{:courses:a4b35ko:jirkamatlagrange.zip| Lagrange relaxace }}
===== Zkouška =====

=== Tabulka úloh podle kategorie: ===
[[https://drive.google.com/folderview?id=0B3ni6NWH7Es4eW9tcE15dUpEMjA&usp=sharing|Prehledna tabulka uloh podle kategorie]] k 9.6.2014, je tam i adresar do ktereho muzete pridavat vypracovane ulohy k dane kategorii


=== Hanzálkův nástin písemné zkoušky: ===
  * 6 až 7 otázek nebo příkladů jako v semestru
  * aspoň po 1 otázce z ILP, cest, toků a rozvrhů
  * 1 až 2 otázky na batoh, TSP nebo programování s omezujícími podmínkami
  * 2, možná až 3 iterace algoritmu
  * 3, možná jen 2 formulace úlohy
  * 1 teoretická otázka, třeba Bellmanova rovnice

=== Termín 25.5.2010 (prosím o doplnění) ===
  * ILP - formulace - nějaké investice, viz druhá přednáška
  * Toky - matice 3x3 suma sloupců a řádků a najít maximální tok, když číslo zaokrouhlím nahoru nebo dolu a zda tok bude vždy celočíselný
  * Rozvrhování - Rothkopf
  * Rozvrhování - Transformace PSm,1|temp|Cmax -> PS1|temp|Cmax
  * Constraint Programming - hranová konzistence AC-3
  * Iterace Dijskry - to byl asi nejlehčí příklad
  * Teorie - důkaz NP-obtížnosti TSP pomocí polynomiálního převodu z problému Hamiltonovské kružnice na instanci TSP


=== Termín 1.6.2010 ===
  * ILP - formulace optimalizace výroby s podmínkami na fixní náklady atd. (12 bodů)
  * SPT - najít nejlepší umístění skladu v závislosti na vzdálenostech k spotřebitelům a váhám nákladu (8 bodů)
  * Toky - nalezení přípustného toku, když jsou nenulová spodní omezení (9 bodů)
  * Knapsack - vyřešit instanci pomocí dynamického programování (9 bodů)
  * Sch I. - vyřešit rozvrhování na jednom procesoru pomocí Bratleye (9 bodů)
  * Sch II. - vyřešit rozvrhování pomocí úrovňového algoritmu (9 bodů)
  * TSP - důkaz, že je NP-hard přes převod na Hamiltonovskou kružnici (8 bodů)


=== Termín 15.6.2010 ===
  * ILP - formulace investice do nemovitostí (12 bodů)
  * Toky - nalezení maximálního toku a minimálního řezu v zadaném grafu (9 bodů)
  * SPT - pomoci Floydova algoritmu najít nejdelší cesty v grafu (9 bodů)
  * CP - úvodní propagace před běhěm algoritmu, nakreslit částečná řešení stromu pro prohledávání a propagaci, napsat konečné řešení nebo rozhodnout, zda-li řešení existuje (10 bodů)
  * Sch I. - převod 1|rj, dj|Cmax na PS1|temp|Cmax (6 bodů)
  * Sch II. - ILP formulace 1|prec|suma wi*Ci + k čemu lze v algoritmu větví a mezí použít částečné řešení J^LP(zbylých úloh) (10 bodů)
  * Knapsack - popsat pseudokódem 2-aproximační algoritmus a vysvětlit proč je 2-aproximační (8 bodů)

=== Termín 24.5.2011 ===
  * [[courses/a4m35ko/zkouska24052011|Zadání a řešení]]

=== Termín 31.5.2011 ===
  * [[courses/a4m35ko/zkouska31052011|Zadání a řešení]]
  * [[courses/a4m35ko/bonus|Bonus]] - stihnul jsem vyfotit pár jiných zadání

=== Termín 14.6.2011 ===
  * převod 1|rj, dj|Cmax na PS1|temp|Cmax
  * Bratleyův algoritmus + podmínka optimality
  * Knapsack - vyřešit instanci pomocí dynamického programování
  * Christofidesův algoritmus - pseudokód + faktor aproximace
  * Ford-Fulkersonův algoritmus na maximální tok a minimální řez
  * Příklad SPT3 z přednášky: Nejspolehlivější spojení
  * [[courses/a4m35ko/bonus|ILP]] - investice na burze

=== Termín 24.5.2012 ===
  * ILP - formulace problému TSP s časovým oknem. Kromě standardní instance jsou ještě dány vektory e a l definující nejmenší resp největší čas příjezdu od města.
  * SPT - přelévání nádob - graf, kriteriální funkce pro nejmenší počet přelití, kriteriální funkce pro nejmenší množství vylité vody 
  * Sched - úrovňový algoritmus
  * Sched - formulace Psm,1|temp|Cmax pomocí ILP
  * Toky - navrhnout síť pro toky pro řešení zaokrouhlování v tabulce + říct, jestli to bude celočíselné a proč
  * CP - AC-3 algoritmus
  * knapsack - napsat pseudokód pro 2-aproximační knapsack a dokázat, že faktor 2

=== Termín 5.6.2012 ===
  * ILP - 4 loupežníci - rozhodnout, zda lze lup rozdělit tak, že mezi maximálním dílem a minimálním dílem je rozdíl nejvýše 10% celkové ceny lupu
  * SPT - Nejspolehlivější spojení
  * Sched - Rozvrh na dva procesory pomocí dyn.prog. (Rothkopf)
  * Sched - Metoda větví a mezí s LP pro 1 |prec|suma wjCj a jak na LP prořezávání
  * Toky - Ford-Fulkerson - zadaný počáteční přípustný tok, udělat 4 iterace, určit maximální tok a minimální řez
  * CP - Prohledávání a propagace
  * TSP - Pravděpodobná neexistence r-aproximačního algoritmu pro obecný TSP

=== Termín 19.6.2012 ===

  * [[courses/a4m35ko/bonus|ILP]] - investice na burze
  * Dijkstra - Pomoci dijkstrova algoritmu spoctete vektory l(v) a p(v) pro kazdy v z V(G), je-li l(v) delkou nejkratsi cesty z vrcholu 1 a p(v) je predposledni vrchol na teto ceste (predchudce). Nedefinovane prvky vektoru p(v) oznacte otaznikem. Zaznamenejte 8 iteraci algoritmu.
{{:courses:dijkstra.png?300|}}
  * LP - Formulujte nejlevnejsi multikomoditni toky - [[courses/a4m35ko/zkouska24052011|Multikomoditni toky]]
  * Knapsack - n=4, c={10, 20, 30, 10}, w={21, 35, 52, 17}, W=100. Na zaklade principu algoritmu dyn. programovani vysvetlete, zda vami nalezene reseni je jedine optimalni nebo existuje i jine optimalni reseni.
  * Slozitost TSP pomoci HK.
  * Urovnovy algoritmus + Gantuv diagram.
{{:courses:urovnovyalg.png?300|}}
  * List scheduling - Pseudokodem popiste List scheduling, aproximacni algoritmus pro P|prec|Cmax. Uvedte aproximacni faktor tohoto algoritmu pro nesetrideny list uloh. Myslenka LPT algoritmu + odpovidajici aproximacni faktor.

=== Termín 21.5.2013 ===
  * ILP investice na burze.
  * Nejspolehlivější spojení - uvést převod do nejkratších cest, navrhnout svůj algoritmus a říct, jestli bude fungovat s p > 1.
  * Dining - toky. Jsou n rodin a q stolů. Potřebujeme,aby za jedním stolem neseděli členy stejné rodiny. Formulovat jako úlohu hledání maximálního toku v síti. (příklad 6.1 na s. 198 v [AMO93])
  * Knapsack - n=4, c={10, 2, 0, 30, 10}, w={21, 35, 52, 17}, W=100. Na zaklade principu algoritmu dyn. programovani vysvetlete, zda vami nalezene reseni je jedine optimalni nebo existuje i jine optimalni reseni.
  * TSP - Pravděpodobná neexistence r-aproximačního algoritmu pro obecný TSP.
  * úrovňový algoritmus.
  * Formulovat časem-indexovaný model pro PS 1 |temp| Cmax jako ILP.

=== Termín 4.6.2013 ===
  * ILP výrobní plán (fixní náklady, sudý počet jednoho výrobku, big M)
  * Vyjádřit problém obsazení směn řidičů tak, aby se dal vyřešit pomocí algoritmů na nejkratší cesty. (příklad 4.13 na s. 127 v [AMO93])
  * Nalezení počátečního přípustného toku pro Ford-Fulkersonův Algoritmus převést na rozhodovací problém přípustného toku v síti. (popsat algoritmus)
  * Knapsack - Kombinace 2-Aproximačního algoritmu a dynamického programování. Napsat pseudokód.
  * Dokázat složitost Christofidesova algoritmu.
  * Vytvořit rozvrh pomocí Rothkopfa
  * Převod PSm, 1 |temp| Cmax na PS1 |temp| Cmax a určení zda je daná instance rozvrhnutelná.

=== Termín 18. 6. 2013 ===
  * CP: AC-3 algoritmus (iterace) 8b
  * SCHEDULING: PSm,1|temp|Cmax (formulace) 7b
  * SCHEDULING: Bratleyho algoritmus (iterace) 7b
  * KNAPSACK: 2-aproximační algoritmus (pseudokód a důkaz faktoru) 7b
  * FLOWS: Distinct Representatives, př. 6.2 na str. 170 v [AMO93] (formulovat jako úlohu maximálního toku) 7b
  * SPT: Bellman-Fordův algoritmus (princip optimality a důkaz správnosti algoritmu) 7b
  * ILP: 4 Partition Problem (formulace) 7b

=== Termín 27. 5. 2014 ===
  * ILP: Investice do n domů s příjmy z nájmů. Maximalizovat profit při omezení výše investice.
  * SPT: Důkaz správnosti Dijkstry
  * FLOWS: Zaokrouhlování čísel/řádků/sloupců v 3x3 matici
  * TSP: Christofides + o jaký aproximační faktor se jedná
  * SCHEDULING: Formulace PSm, 1|temp|Cmax pomocí ILP
  * SCHEDULING: Úrovňový algoritmus + ganttův graf
  * CP: Iterace AC-3 algoritmu

=== Termín 3. 6. 2014 ===
  * ILP: Finanční portfolio
  * FLOWS: Nalezení počátečního přípustného toku pro Ford-Fulkersonův Algoritmus převést na rozhodovací problém přípustného toku v síti. (popsat algoritmus)
  * FLOWS: Distinct Representatives, př. 6.2 na str. 170 v [AMO93] (formulovat jako úlohu maximálního toku)
  * SPT - Nejspolehlivější spojení
  * Knapsack - n=4, c={10, 20, 30, 10}, w={21, 35, 52, 17}, W=100. Na zaklade principu algoritmu dyn. programovani vysvetlete, zda vami nalezene reseni je jedine optimalni nebo existuje i jine optimalni reseni.
  * TSP: Christofides - o jaký aproximační faktor se jedná + důkaz 
  * SCHEDULING: Převod PSm, 1 |temp| Cmax na PS1 |temp| Cmax a určení zda je daná instance rozvrhnutelná.

=== Termín 24. 6. 2014 ===
  * ILP: Nějaká výroba 5 produktů - formulace
  * ILP: 1|prec|wjCj - formulace, k čemu se dá použít relaxované LP řešení při řešení ILP
  * FLOWS: 4 iterace Ford-Fulkersona a najít minimální řez
  * SPT: Formulace problému tak, aby šel vyřešit Dijkstrou. Máme rozvážkovou službu, která rozváží v době 9-16. K dispozici jsou různé časy směn (9-11, 9-13, 12-14, 12-16, 12-17, 14-16, 15-17... takhle přesně to nebylo, ale tenhle styl).
  * SPT: 5 výroků a říct zda platí nebo ne. Pokud platí, dokázat, pokud ne, udělat protipříklad. Výroky typu "když zvýšíme cenu hrany v grafu o násobek k, délka nejkratší cesty se také zvýší k-krát", "Dijkstrův algoritmus nalezne vždy nejkratší cestu s nejmenším počtem hran")
  * SCHEDULING: Převod 1|rj,dj|Cmax na PS1|temp|Cmax
  * TSP: Pravděpodobná neexistence r-aproximačního algoritmu

=== Termín 26. 5. 2015 ===
  * ILP: Finanční portfolio
  * ILP: 1|prec|wjCj - formulace, k čemu se dá použít relaxované LP řešení při řešení ILP
  * FLOWS: Zaokrouhlování čísel/řádků/sloupců v 3x3 matici
  * SPT: Najít nejdelší cesty Floydem
  * SPT: Nejspolehlivější spojení
  * SCHEDULING: Rozvrhnout tasky pomocí Hornova algoritmu, nakreslit gantův diagram a spočítat Lmax
  * TSP: Pravděpodobná neexistence r-aproximačního algoritmu, převod na Hamilt. kružnici

=== Termín 3. 6. 2015 ===
  * SPT: Důkaz správnosti Dijkstry
  * SPT: Formulace problému tak, aby šel vyřešit Dijkstrou. Máme řidiče autobusu a směny v době 9-17. K dispozici jsou různé časy směn (9-11, 9-13, 12-14, 12-16, 12-17, 14-16, 15-17 cca) a ke směnám ceny. Je to někde v knížce Network Flows - Ahuja, Magnanti, Orlin.
  * TSP/ILP: Formulace TSP s time windows pomocí ILP
  * CP: Hranová konzistence nějakého zadání (AC-3)
  * SCH: Převod PSm 1|temp|Cmax na PS 1|temp|Cmax a určení zda je daná instance rozvrhnutelná.
  * Knapsack: Dyn. programování, mělo se řešit doplňováním cen do tabulky. 5 předmětů, ceny 1, 6, 18, 22, 28, hmotnosti 1, 3, 5, 6, 7 (cca).
  * FLOWS: ILP formulace multikomoditních toků.

=== Termín 15. 6. 2015 ===
  * ILP: Real estate investment, klasicky budovy s XORem a dalsi podminky vcetne 2 ze 3 musi platit.
  * SCH: Rothkopf, solve P||Cmax by dynamic prog. p=(2,2,1,2), UB=7, R=2
  * SCH: Formulate PS1|temp|Cmax as time-indexed ILP
  * TSP: Derive approx. factor of Christofides alg. (Nestaci napsat factor. Je potreba napsat, proc ma takovy factor.)
  * FLO: Ford-Fulkerson algorithm, 3 iterace vcetne odecitani pres zpetnou hranu + urcit hrany minimum cut
  * FLO: Dinning problem - max flow problem, Nekolik rodin je na veceri. Je potreba rozhodit cleny rodin tak, aby nesedeli dva clenove jedne rodiny u stejneho stolu. Je potreba urcit, kdy je reseni feasible.
  * SPT: Investment oportunities, Mr. Dow Jones - prednasky SPT na slajdu 29/42

=== Termín 31. 5. 2016 ===
  * ILP: Nakup reklam, zadana tabulka zisku hlasovacich hlasu na zaklade poctu vysilani reklamy, nakoupit muzeme maximalne 3 reklamy.
  * SPT: Nejspolehlivejsi spojeni, vektor spolehlivosti p rozsah (0,1), vysledne spojeni je produkt vsech spolehlivosti po ceste a)prevod ulohy nejspolehlivejsiho spojeni, aby sel resit Dijkstrou b) Modifikace Dijkstry aby resil tuhle ulohu c) bude a) a b) fungovat, kdyz bude p v rozsahu (0,inf)
  * SPT: Dukaz spravnosti Dijkstry
  * ILP: Scheduling with temp constraints
  * Knapsack: a) Dyn. programovani b) existuje vice optimalnich reseni?
  * FLO: Ford-Fulkerson algorithm, 3 iterace vcetne odecitani pres zpetnou hranu + urcit hrany minimum cut
  * SCH: Převod PSm 1|temp|Cmax na PS 1|temp|Cmax a určení zda je daná instance rozvrhnutelná.

=== Termín 3.6.2016 ===
  * ILP: Toy production, maximalize profit , 2 factories, only one is working, 2 type of toys, different production speed per factory and toy type and toy type production initialisation cost
  * SPT: Investment oportunities, Mr. Dow Jones - prednasky SPT na slajdu 29/42
  * Knapsack: Popsat pseudokódem 2-aproximační algoritmus a vysvětlit proč je 2-aproximační
  * Flow: matice 3x3 suma sloupců a řádků a najít maximální tok, když číslo zaokrouhlím nahoru nebo dolu a zda tok bude vždy celočíselný
  * CP: Hranová konzistence nějakého zadání (AC-3)
  * SCH: vyřešit rozvrhování na jednom procesoru pomocí Bratleye
  * SCH: Formulate PS1|temp|Cmax as time-indexed ILP

=== Termín 13.6.2016 ===
  * ILP: \\
max f(x1); \\
f(x1) = 7 + 5*x1 iff x1 > 0;\\
f(x1) = 0 iff x1 = 0;\\
abs(x1 - x2) = 0 OR 6 \\
x1, x2 >= 0; x1, x2 < = 100 \\ 
  * SPT: Formulace problému tak, aby šel vyřešit Dijkstrou. Máme řidiče autobusu a směny v době 9-17. K dispozici jsou různé časy směn (9-11, 9-13, 12-14, 12-16, 12-17, 14-16, 15-17 cca) a ke směnám ceny. 
  * FLOW: Flow s lower bound != 0 prevest na Flow s lower bound == 0
  * TSP: důkaz NP-obtížnosti TSP pomocí polynomiálního převodu z problému Hamiltonovské kružnice na instanci TSP
  * Knapsack: n=4, c={10, 20, 30, 10}, w={21, 35, 52, 17}, W=100. Na zaklade principu algoritmu dyn. programovani vysvetlete, zda vami nalezene reseni je jedine optimalni nebo existuje i jine optimalni reseni.
  * SCH: PSm 1|temp|Cmax as ILP

=== Termín 27.6.2016 ===
  * ILP: max z = součet absolutních hodnot s x1 x2 x3 x4 \\ x1,2,3,4 >= 0 \\ if x1=0 and x3=0 then x4!=0 \\ if x1=0 and x2=0 then x3=0 nebo něco podobného
  * Tvrzení o sítích a cestcáh - zda jsou pravdivé a proč
  * Dinning problem jako max flow
  * Vyřešit Chetto, Silly, Bouchentouf algorithm
  * Rothkopf
  * Jaký faktor má Christofides, odůvodnit podle jeho postupu (byl zahrnut v zadání)
  * AC-3 kondenzace

=== Termín 31.5.2017 ===
  * ILP skolni jidelna - největší chyták byla podmínka, že libovolná kombinace jídel v jeden týden musí mít celkově alespoň p_min proteinů
  * ILP osklive prepinani funkci - stejne, jako 13.6.2016
  * SPT prelevani vody (podle slov Hanzálka jsme měli i nakreslit ručně graf)
  * Flows - zadan tok, udelat iterace Ford-Fulkersona + rict, kolik maximalne iteraci je potreba pro jakoukoliv volbu zlepsujicich cest
  * TSP pravdepodobna neexistence r-approx TSP
  * CSP iterace AC-3
  * scheduling prevod multiprocessor scheduling na PSm,1|temp|Cmax

=== Termín 7.6.2017 ===
  * SCHED: temporalni omezeni, nakrestli graf a jestli je rozvrhnutelne
  * ILP: vyresit Branch and Bounds jako LP solver, do ctvereckovaneho papiru
  * TSP: odvodit faktor Christofidesova algoritmu, byl tam napsany ten algoritmus a musel se vysvetlit ten faktor
  * Knapsack: vyresit dynamickym programovanim, n=7, W=5, Je reseni unikatni? Jaka bude slozitost pokud W<=10n?
  * FLOW: zaokrouhlovani v 3x3 matici, Budou vysledne toky celociselne?
  * TSP: smeny ridicu autobusu
  * ILP: formulovat jako ILP nejake rozvrhovani Tn tasku na Rm resources, min Cmax s binarnim parametrem ze nektere 2 tasky nesmi bezet na stejnem R

=== Termín 21.6.2017 ===
  * ILP: maximalizace souctu dvou absolutnich hodnot, formulovat
  * ILP: iterace BaB
  * SPT: formulace ulohy, maximalizace zisku pri ceste z A do B, mezi nekterymi dvojicemi mest po ceste si lze privydelat dorucenim zasilky, prime spojeni mezi vsemi mesty, naklady ~ ujeta vzdalenost
  * Knapsack: vyresit dynamickym programovanim, c =[...], w = [...], W <= 100, Je reseni unikatni?
  * FLOW: vyber reprezentantu klubu ve vekovych skupinach a dalsi podminky
  * SCHED: EDD dukaz optimality
  * CSP: iterace AC-3

=== Termín 29.5.2018 ===
  * ILP: maximalizace souctu dvou absolutnich hodnot, formulovat
  * SPT: dokazat Dijkstru. Byl tam pseudokod celeho algoritmu.
  * Knapsack: vyresit dynamickym programovanim, c =[2,2,2,4,3], w = [1,1,2,3,4], W = 5, Je reseni unikatni? Jaka se casova slozitost pokud W <= 10*n
  * TSP: Dokazat aproximacni faktor Christofidesova alg. Byl tam pseudokod celeho algoritmu.
  * FLOW: family dining problem
  * SCHED: Chetto, Silly, Bouchentouf algorithm pro 1|pmtn,prec|r,d|L_max. Vyresit jednu instanci a vypsat hodnoty hlavnich promennych v kazde iteraci algoritmu.
  * SCHED: formulovat Time-indexed ILP model for PS1 |temp| C_max

=== Termín 05.6.2018 ===
  * ILP: stejne jako 13.6.2016, akorat jsou x1,x2 z <0,20>
  * SPT: Formulace problému tak, aby šel vyřešit Dijkstrou (zadani na slajdu 6 (7 v prohlizeci) http://www.ifp.illinois.edu/~angelia/ge330fall09_shortpath_l17.pdf )
  * TSP: Pravděpodobná neexistence r-aproximačního algoritmu, převod na Hamilt. kružnici
  * CP: Hranová konzistence nějakého zadání (AC-3) - stejne jako 24.5.2011
  * SCH: Rozvrhnout tasky pomocí Hornova algoritmu, nakreslit gantův diagram a spočítat Lmax
  * SCH: Project scheduling with temporal constraints
  * FLOWS: ILP formulace multikomoditních toků.

=== Termín 19. 6. 2018 ===
	* ILP: Školní Jídelna 

	Počet jídel M = {1, …,100}, 
	pracovních dnů D= {1, …,5}, 
	c_m - cena jídla, 
	v_m {0,1} - jeslti je jídlo veganské, 
	p_m - počet proteinů v jídle, 
	p^min - minimální počet proteinů za celý týden. 
	Podmínky: 
  	- každý den 4 jídla, 
  	- alespoň 1 veganské, 
  	- minimalizace costu za celý týden, 
  	- každé jídlo max jednou za celý týden. 
         - Pocet porci kazdeho jidla z menu je presne 120 
  	- Jakákoliv kombinace z jídel v menu za ten týden (1 jídlo denně), musí mít v součtu alespoň p_min proteinů 

	* SPT: Max reliability Dijkstra
	* Flows: Iterace Ford Fulkerson, najít mincut flow
	* Knapsack: 2-approx knapsack pseudokod a dokázat faktor
	* TSP: Christofides - napsat pseudokod, říct faktor (nemusel se dokazovat)
	* SCHED: Rothkopf p=(2,2,1,2), Cmax=5
	* SCHED: ILP formulace - 1|prec|Cmax, jak může LP relaxace pomoci při řešení algoritmem Branch and Bounds

Tip: Ke všemu napište aspoň něco, i když nevíte, něco zkuste - když to má alespoň trochu správnou myšlenku, tak člověk dostane nějaký body a ono se to nasčítá.

===== Studijni materiály =====

Kvalitny strucny prehlad toho co je dolezite na skuskach, co sa casto opakuje: {{:courses:ko.pdf|}}

  * [[http://www.uloz.to/8005026/grafy-a-jejich-aplikace-jiri-demel-pdf|knizka Grafy a jejich aplikace, Jiri Demel]]; (jsou tam napriklad ty ulohy na nejkratsi cestu delane na tabuli o prednasce)

  * [[http://uloz.to/xafkfn6N/grafy-a-jejich-aplikace-jiri-demel-abbyy-briss-pdf|knizka Grafy a jejich aplikace, Jiri Demel, OCR verze prohnane pres ABBYY finereader a orezane programem briss]]; (jsou tam napriklad ty ulohy na nejkratsi cestu delane na tabuli o prednasce)

  * [[http://d1.filetram.com/direct/download/file/7402207843|kniha Network Flows]] (odkazovano ze slidu + stejne priklady jako ve slidech), [[http://jorlin.scripts.mit.edu/Solution_Manual.html|řešení]] příkladů z knihy

  * [[http://www.cse.unl.edu/~goddard/Courses/CSCE310J/Lectures/Lecture8-DynamicProgramming.pdf|Knapsack pomocí dynamického programování v detailním příkladu]] (Pozor, je zde varianta dělaná přes váhy, na přednášce to bylo přes ceny)

  * [[http://stm-wiki.cz/index.php/Y35OIS|OIS=uplne stejny predmet]] na stm-wiki

  * Prelevani vody 
{{:voda.jpg?240|Prelevani vody - nejmensi cesta}}

  * Poznámky k tokům kolegy Antonína Šulce
{{:courses:dsc00110.jpg?240|}}
{{:courses:dsc00111.jpg?240|}}
{{:courses:dsc00112.jpg?240|}}
{{:courses:dsc00113.jpg?240|}}

  * [[https://docs.google.com/spreadsheet/ccc?key=0As6_MV5SlwbZdEw2U2ZyTDFqcTVkTGJKUmhBSlh1RFE|Tabulka algoritmů z přednášek]] (pro ty, co se jim pletou všechny dohromady :-) )

~~DISCUSSION~~