navigation
hledat
Rozdíly
Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
|
courses:a4m35ko [2015/06/17 21:57] jendan [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:rozvhovani-semestralka.zip| Rozvrh zdravotních sester ILP}} | ||
| + | {{:courses:a4b35ko:jirkamatlagrange.zip| Lagrange relaxace }} | ||
| ===== Zkouška ===== | ===== Zkouška ===== | ||
| Řádek 210: | Řádek 211: | ||
| * 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. | * 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 | * 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á. | 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 ===== | ===== 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://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) | ||
