Optimalizacni metody NOPT048

blabla
Matfyz(ák|ačka) level II
Příspěvky: 70
Registrován: 27. 1. 2010 23:14
Typ studia: Informatika Mgr.

Optimalizacni metody NOPT048

Příspěvek od blabla »

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
Acris
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

Příspěvek od Acris »

Mohu se zeptat těch lidí, co byli již na zkoušce, jak zkouška probíhala? Díky.
blabla
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

Příspěvek od blabla »

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.
blabla
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

Příspěvek od blabla »

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
Přílohy
IMG_6867.JPG
marion
Matfyz(ák|ačka) level II
Příspěvky: 69
Registrován: 4. 10. 2008 11:05
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Re: Optimalizacni metody NOPT048

Příspěvek od marion »

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.
shrill
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

Příspěvek od shrill »

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 :D 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).
Malta

Re: Optimalizacni metody NOPT048

Příspěvek od Malta »

Tak přidávám ještě svoje zadání:
Obrázek

Letošní zadání jsou teda stejný :wink: 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 :D.
opt

Re: Optimalizacni metody NOPT048

Příspěvek od opt »

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.
Alesax

Re: Optimalizacni metody NOPT048

Příspěvek od Alesax »

opt píše:Zkouška 28.5.2014
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..?
arahusky
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

Příspěvek od arahusky »

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:).
Odpovědět

Zpět na „Ostatní“