Rozdíly

Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.

--- courses:a4m35ko [2015/05/28 19:54]
dothang [Zkouška]
+++ courses:a4m35ko [2025/01/03 18:23] (aktuální)
@@ Řádek 41: / Řádek 41: @@
 {{:courses:rozvhovani-semestralka.zip| Rozvrh zdravotních sester ILP}}
+{{:courses:a4b35ko:jirkamatlagrange.zip| Lagrange relaxace }}
 ===== Zkouška =====
@@ Řádek 193: / Řádek 194: @@
   * TSP: Pravděpodobná neexistence r-aproximačního algoritmu, převod na Hamilt. kružnici
-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á.
+=== 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)

courses/a4m35ko.1432835682.txt.gz · Poslední úprava: 2025/01/03 18:15 (upraveno mimo DokuWiki)

Nahoru