navigation
hledat
Rozdíly
Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
|
courses:a4m35ko [2018/05/30 14:21] rozumden [Zkouška] |
courses:a4m35ko [2025/01/03 18:23] (aktuální) |
||
|---|---|---|---|
| Řádek 287: | Řádek 287: | ||
| * 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: 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 | * 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á. | ||
