navigation
hledat
Rozdíly
Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
|
courses:a4m35ko [2016/06/27 10:36] veseljo5 [Zkouška] |
courses:a4m35ko [2025/01/03 18:23] (aktuální) |
||
|---|---|---|---|
| Řádek 251: | Řádek 251: | ||
| * Jaký faktor má Christofides, odůvodnit podle jeho postupu (byl zahrnut v zadání) | * Jaký faktor má Christofides, odůvodnit podle jeho postupu (byl zahrnut v zadání) | ||
| * AC-3 kondenzace | * 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á. | ||
