Optimalizacni metody NOPT048
-
- Matfyz(ák|ačka) level II
- Příspěvky: 70
- Registrován: 27. 1. 2010 23:14
- Typ studia: Informatika Mgr.
Optimalizacni metody NOPT048
tak som si povedal ze pred zaciatkom svojej pripravy na skusku by som mohol zriadit aspon tento samostatny topic nech sem vsetci pisu vsetko ohladom tohto predmetu, osobne ma velmi bude zaujimat priebeh skusok:D tak smelo piste
-
- Matfyz(ák|ačka) level I
- Příspěvky: 20
- Registrován: 26. 1. 2010 14:28
- Typ studia: Informatika Mgr.
- Bydliště: Praha
Re: Optimalizacni metody NOPT048
Mohu se zeptat těch lidí, co byli již na zkoušce, jak zkouška probíhala? Díky.
-
- Matfyz(ák|ačka) level II
- Příspěvky: 70
- Registrován: 27. 1. 2010 23:14
- Typ studia: Informatika Mgr.
Re: Optimalizacni metody NOPT048
tak konecne som sa dostal k nejakym informaciam..! mail od toho kto uz to ma za sebou:
1. cast
dostal jsem papir se tremi priklady.
a) byly zadany vrcholy polyedru a mel sem navrhnout LP, tak aby bylo optimum v jednom z vrcholu. (3D, ale vrcholy vraj len nula, jednickove suradnice)
b) udelat dva kroky simplexove metody
c) poznat totalne unimodulovane matice - 3 matice - odpovedi ANO/NE
2. cast
dostal jsem latku(cutting plane)... tak jsem mu neco rekl, ale vetu jsem nevyslovil, ani mu asi neslo o presne zneni, ale proste sem nevedel, o cem by ta veta mela byt. pote mi dal nahradni malou otazku.
1. cast
dostal jsem papir se tremi priklady.
a) byly zadany vrcholy polyedru a mel sem navrhnout LP, tak aby bylo optimum v jednom z vrcholu. (3D, ale vrcholy vraj len nula, jednickove suradnice)
b) udelat dva kroky simplexove metody
c) poznat totalne unimodulovane matice - 3 matice - odpovedi ANO/NE
2. cast
dostal jsem latku(cutting plane)... tak jsem mu neco rekl, ale vetu jsem nevyslovil, ani mu asi neslo o presne zneni, ale proste sem nevedel, o cem by ta veta mela byt. pote mi dal nahradni malou otazku.
-
- Matfyz(ák|ačka) level II
- Příspěvky: 70
- Registrován: 27. 1. 2010 23:14
- Typ studia: Informatika Mgr.
Re: Optimalizacni metody NOPT048
tak dnes som absolvoval skusku, prebiehala v celkom uvolnenej atmosfere. dole je prva cast s prikladmi a ptoom v druhej casti som dostal caratheodory vetu s dokazom plus vysvetlit v nej a v dokaze pouzite pojmy, ked mi to neslo tak uplne idealne tak som dostal este dokazat ze kazdy extremalny bod konvexneho omezeneho mnohostenu je jeho vrcholom. aj tam som zazmatkoval tak za dva
-
- Matfyz(ák|ačka) level II
- Příspěvky: 69
- Registrován: 4. 10. 2008 11:05
- Typ studia: Informatika Mgr.
- Login do SIS: 36138549
- Kontaktovat uživatele:
Re: Optimalizacni metody NOPT048
Tak to mam konecne taky za sebou. Priklady, ktere tu jsou ofocene jsem dostala s nejakou obmenou cisel. Mela jsem tam nejake chyby, ktere me ale nechal opravit. Nicmene nakonec spravne vyreseni vsech pocetnich prikladu (pro ty, co nemaji >50bodu) je nutna podminka pro postup do dalsi casti tykajici se teorie. Dostala jsem Caratheodory, coz bylo pro me dost stesti. Z ostatnich veci jsem jeste zaslechla otazky na vetu o dualite, Minkowski-Weyl, totalni unimodularita, blossom algoritmus, Farkasovo lemma, cutting planes,...takova vsehochut. Jinak teda musim rict, ze doc. Sgall pomerne hodne lpi na matematickem formalismu, ale zas kdyz se trefi do nejakeho fakt slabeho mista, tak da dalsi otazku a neni to uplne konec.
Co se tyce terminu, tak krome tech co jsou jiz vypsane budou dalsi spis jen po individualni domluve.
Co se tyce terminu, tak krome tech co jsou jiz vypsane budou dalsi spis jen po individualni domluve.
-
- Matfyz(ák|ačka) level I
- Příspěvky: 14
- Registrován: 13. 1. 2007 20:48
- Typ studia: Informatika Bc.
- Kontaktovat uživatele:
Re: Optimalizacni metody NOPT048
Já jsem měl v předotázkovém testu
1) Navrhnout LP pro maximální tok v síti. Síť byla nakreslená, takže LP neměl být obecně, ale pro danou síť. Já jsem to moc nepochopil, napsal jsem tedy obecný LP a nevadilo to.
2) Napsat k danému LP duální a podmínky komplementarity. V LP mix jedna rovnice a nerovnice, 3 proměnné, dvě nezáporné, jedna reálná.
3) Vyjmenovat vrcholy a fasety (nebo jejich nadroviny) konvexního obalu množiny { (2,1,0), (0,2,1), (1,0,2), (1,1,1) }
Bod (1,1,1) je konvexní kombinací zbylých s koeficitenty 1/3, takže to vrchol nebude. Podle vět z přednášky plyne přibližně že minimální množina bodů generující konv. obal jsou vrcholy polyedru, takže ty zbylé 3 body jsou vrcholy. Polyedr je trojújelník v prostoru, fasety leží na nadrovinách ve formě přímek.
Písemka se neodevzdávala, ale prostě když jsem to tak nějak měl, tak jsem to Sgallovi ukázal, on si to prohlédl, tak nějak poukázal na chyby a dal polonávodné otázky a nechal čas na dopracování.
Pak jsem dostal cutting planes, mohl jsem i napsat větu a důkaz, který je v té kapitole, ale nemusel jsem a taky jsem nenapsal Takže to byla v podstatě taková pohádka s definicemi a použitími...
Dál jsem dostal Caratheodoryho větu.
Nepřišlo mi, že by Sgall nějak bazíroval na matematickém formalismu, jak psala marion, spíš když něco do té věty nebo důkazu patří, tak to tam prostě musí být a musí to tam být dobře Není-li, tak na to poukáže, nechá čas na dopracování, pohoda. Když vám zadá něco těžkého a vám se to moc nelíbí a nevíte, co s tím, tak dostanete něco jiného a asi i bez nějaké větší ztráty hodnocení mi to přišlo Ale zase vám asi nedá něco jiného, když neumíte lehkou věc
Ve výsledku mi to přišlo takové pohodové, ale taky jsem tam neměl větší chyby.
K tomu, co zadával za otázky ještě doplním matroidy, které jsem doufal, že se moc zkoušet nebudou Ale přišlo mi, že tu otázku tomu člověku zadával takovým stylem, že kdyby se zkoušenému ty matroidy nelíbily, tak dostane něco jiného (jako já jsem nedokazoval cutting planes, ale caratheodoryho).
1) Navrhnout LP pro maximální tok v síti. Síť byla nakreslená, takže LP neměl být obecně, ale pro danou síť. Já jsem to moc nepochopil, napsal jsem tedy obecný LP a nevadilo to.
2) Napsat k danému LP duální a podmínky komplementarity. V LP mix jedna rovnice a nerovnice, 3 proměnné, dvě nezáporné, jedna reálná.
3) Vyjmenovat vrcholy a fasety (nebo jejich nadroviny) konvexního obalu množiny { (2,1,0), (0,2,1), (1,0,2), (1,1,1) }
Bod (1,1,1) je konvexní kombinací zbylých s koeficitenty 1/3, takže to vrchol nebude. Podle vět z přednášky plyne přibližně že minimální množina bodů generující konv. obal jsou vrcholy polyedru, takže ty zbylé 3 body jsou vrcholy. Polyedr je trojújelník v prostoru, fasety leží na nadrovinách ve formě přímek.
Písemka se neodevzdávala, ale prostě když jsem to tak nějak měl, tak jsem to Sgallovi ukázal, on si to prohlédl, tak nějak poukázal na chyby a dal polonávodné otázky a nechal čas na dopracování.
Pak jsem dostal cutting planes, mohl jsem i napsat větu a důkaz, který je v té kapitole, ale nemusel jsem a taky jsem nenapsal Takže to byla v podstatě taková pohádka s definicemi a použitími...
Dál jsem dostal Caratheodoryho větu.
Nepřišlo mi, že by Sgall nějak bazíroval na matematickém formalismu, jak psala marion, spíš když něco do té věty nebo důkazu patří, tak to tam prostě musí být a musí to tam být dobře Není-li, tak na to poukáže, nechá čas na dopracování, pohoda. Když vám zadá něco těžkého a vám se to moc nelíbí a nevíte, co s tím, tak dostanete něco jiného a asi i bez nějaké větší ztráty hodnocení mi to přišlo Ale zase vám asi nedá něco jiného, když neumíte lehkou věc
Ve výsledku mi to přišlo takové pohodové, ale taky jsem tam neměl větší chyby.
K tomu, co zadával za otázky ještě doplním matroidy, které jsem doufal, že se moc zkoušet nebudou Ale přišlo mi, že tu otázku tomu člověku zadával takovým stylem, že kdyby se zkoušenému ty matroidy nelíbily, tak dostane něco jiného (jako já jsem nedokazoval cutting planes, ale caratheodoryho).
Re: Optimalizacni metody NOPT048
Tak přidávám ještě svoje zadání:
Letošní zadání jsou teda stejný Sgall má 2 verze tuhle a tu, co už sem někdo dával, jenom mění čísla - sám mi to řekl, když jsem mu chtěl zadání vracet. Takže na počítání se stačí naučit těchhle pár úloh .
Letošní zadání jsou teda stejný Sgall má 2 verze tuhle a tu, co už sem někdo dával, jenom mění čísla - sám mi to řekl, když jsem mu chtěl zadání vracet. Takže na počítání se stačí naučit těchhle pár úloh .
Re: Optimalizacni metody NOPT048
Zkouška 28.5.2014
Příklady
1) Napsat lineární program, jehož přípustná řešení jsou zadané body (v 3D prostoru) a optimum je jeden z nich (byl zadán který).
- Sgall chtěl přesně spočítat nerovnosti, tj. vzít si trojice bodů, spočítat tečné nadroviny, z nich odvodit nerovnosti. Nestačilo tak nějak odhadnout a napsat nějaké nerovnice, protože z toho neni vidět, že je to přesně konvexní obal zadaných bodů. Nebylo nakonec nutné dopočítávat.
2) Udělat dva kroky Simplexové metody
- docela jednoduché, úloha byla neomezená.
Teorie
1) Formulovat a dokázat Caratheodoryho větu.
2) Formulovat a dokázat slabou větu o dualitě.
Pozn.: Je třeba dávat pozor na detaily, nestačí umět tak nějak znění vět a důkazů. Například je třeba vědět, že konvexní kombinace v Caratheodoryho větě začíná od indexu 0 (ne od 1 jak jsem se splet). Dál je třeba vědět, jaké předpoklady se používají v jaké rovnosti/nerovnosti důkazu slabé věty o dualitě, ptal se na definici dimenze množiny atd.
I když jsem měl oba důkazy správně, tak jsem dostal za 3 - říkal, že kdo dostane dobrou známku, tak musí mít dost jasno v základech.
Příklady
1) Napsat lineární program, jehož přípustná řešení jsou zadané body (v 3D prostoru) a optimum je jeden z nich (byl zadán který).
- Sgall chtěl přesně spočítat nerovnosti, tj. vzít si trojice bodů, spočítat tečné nadroviny, z nich odvodit nerovnosti. Nestačilo tak nějak odhadnout a napsat nějaké nerovnice, protože z toho neni vidět, že je to přesně konvexní obal zadaných bodů. Nebylo nakonec nutné dopočítávat.
2) Udělat dva kroky Simplexové metody
- docela jednoduché, úloha byla neomezená.
Teorie
1) Formulovat a dokázat Caratheodoryho větu.
2) Formulovat a dokázat slabou větu o dualitě.
Pozn.: Je třeba dávat pozor na detaily, nestačí umět tak nějak znění vět a důkazů. Například je třeba vědět, že konvexní kombinace v Caratheodoryho větě začíná od indexu 0 (ne od 1 jak jsem se splet). Dál je třeba vědět, jaké předpoklady se používají v jaké rovnosti/nerovnosti důkazu slabé věty o dualitě, ptal se na definici dimenze množiny atd.
I když jsem měl oba důkazy správně, tak jsem dostal za 3 - říkal, že kdo dostane dobrou známku, tak musí mít dost jasno v základech.
Re: Optimalizacni metody NOPT048
Zní to nějak nelehce. Prosímtě, z čeho ses to učil? Materiály na Sgallových stránkách mi připadají poměrně slabé, ale třeba se pletu..?opt píše:Zkouška 28.5.2014
-
- Matfyz(ák|ačka) level I
- Příspěvky: 3
- Registrován: 24. 11. 2011 17:25
- Typ studia: Informatika Mgr.
Re: Optimalizacni metody NOPT048
Ahoj,
tak ja jsem se to ucil z tech Sgallovych materialu na strankach a celkem to slo. Dneska jsem pak byl na zkousce, jako otazky matroidy a druha (opravna) pak Farkasovo lemma. Sgall byl celkem v pohode:).
tak ja jsem se to ucil z tech Sgallovych materialu na strankach a celkem to slo. Dneska jsem pak byl na zkousce, jako otazky matroidy a druha (opravna) pak Farkasovo lemma. Sgall byl celkem v pohode:).