Minimaxove vety

[peci1]

Ahoj, dalsi bod nejasnosti v zadani okruhu ke statnicim. Matematika (IOI), okruh 18, Minimaxove vety.

Co tim maji na mysli? V opt. metodach jsme akorat meli cosi o teorii her na cvikach, a tam se neco jako minimaxova veta vyskytuje (dokazovali jsme ji jako domaci ukol). To by byla jedna veta. Vite nekdo o nejake dalsi?

Pak jsem jeste nasel minimaxovou vetu v kombagre, u toku v sitich (min tok <-> max rez). A nebo snad po nas chteji nektere z minimalizacnich/maximalizacnich uloh, kterych jsme na opt. metodach brali tolik? To snad ne... Ale to jsou ulohy, ze, a ne vety...

Nechodil jsem na kombagru II, nebylo tam neco, co by pod tenhle nadpis padlo?

Jaky mate nazor? Co je tim mineno?

[al-Quaknaa]

Ahoj,
máš pravdu, že je to poměrně široký pojem, ale IMHO se pod tím myslí věty typu "maximální tok == minimální řez". Loebl o tom povídal na Kombagře 1 a v kombinatorice je to opravdu častý jev. Říká se tomu taky "existence dobrých certifikátů", protože můžeš "doložit", že jsi našel maximální tok tím, že předložíš řez stejné velikosti (a naopak). Tahle vlastnost se vyskytuje i u dalších kombinatorických problémů. Když k tomu připočteš důležitost certifikátů ve složitosti (jedna z definic NP je, že existuje polynomiální certifikát /svědek kladné odpovědi), tak je zřejmé, proč si pro to vymysleli tenhle obecný název, minimaxové věty.

Stejně tak máš ale i pravdu, že minimaxový princip se objevuje i v teorii her. Klasické zadání teorie her je "maticová hra", což je matice s nějakými položkami, jeden hráč vybírá sloupec, druhý řádek, oba hrají naráz (jako kámen-nůžky-papír) no a jeden se snaží výslednou hodnotu minimalizovat, zatímco druhý maximalizovat. Podobně třeba u kombinatorických her když máš herní strom, tak se vždycky snažíš maximalizovat svůj zisk a zároveň minimalizovat svou potenciální ztrátu ("co nejbezpečněji získat co nejvíc").

Konečně tyhle dvě věci spolu i souvisejí, ale to je nějaká těžká optimalizační věta o tom, že maticové hry jsou v jistém smyslu ekvivalentní lineárnímu programování, ve kterém je minimaxová věta věta o dualitě (maximum úlohy má stejnou hodnotu jako minimum duální úlohy). Ale to se nebere na žádném z bc. předmětů, zcela určitě.

Pokud se mě na to někdo zeptá, tak jim asi řeknu všechno tohle, ale IMHO by ti mělo stačit to, co jsem řekl v prvním odstavci. Jinak já se sám chystám na státnice, takže nejsem nějak zvlášť kvalifikovaný na to odpovídat, kromě toho, že jdu na KAM a prakticky všechny předměty mimo povinné jsem měl od nich Snad to k něčemu bude.

[peci1]

Dik moc za prehledny shrnuti, tak aspon si muzu byt o neco jistejsi, ze ke kazdy interpretaci bych neco dokazal povedet =)

[Acris]

Ahoj,
mně imho přijde, že k tématu 18. otázky (Optimalizační metody) více sedí to s teorií her. (Sice tedy toky a řezy s lineárním programováním souvisejí také, ale je to podle mne více grafová/ads otázka.) Jinak ta věta, že maticová hra dvou hráčů s nulovým součtem má optimální strategii pro řádkového i sloupcového hráče a že se ta optima rovnají, se bere třeba na Základech spojité optimalizace, což je povinně volitelný bc předmět. Ale ten důkaz je v podstatě to (alespoň ta myšlenka použití duality), co bylo loni jako jedna z úloh na Optimalizačních metodách (myslím, že mám někde své řešení, které mohu asi poskytnout), tedy tato část není sama o sobě nijak těžká, pokud má už člověk dokázané ty věty o dualitě. Ale možná, že to, co psal al-Quaknaa, je ještě nějaká obecnější tvrzení, nejen pro maticové hry (dvou hráčů) s nulovým součtem.
Jinak souhlasím, že je jinak divné, že se to nikde v povinných/doporučených předmětech moc nebralo a ani člověk neví jistě, co je tím všechno myšleno.

[al-Quaknaa]

Já jsem normální optimed neměl; ještě v prváku jsem absolvoval předmět "úvod do matematického programování a polyedrální kombinatoriky", kde se probíraly podobné záležitosti, ale úplně stejné to nebylo. Takže nevím. S tou větou jsem to spletl -- ta těžká věta, kterou jsem měl na mysli, se týká PCP věty (což se týká složitosti a konstantně velkých a randomizovaně polynomiálně ověřitelných certifikátů pro NP problémy) a jmenuje se Yaův princip. Z téhle stránky už vede link na Von Neumannovu Minmaxovou větu, o čem se asi povídalo na optimedu. Já mám tyhle věci z Pravděpodobnostních algoritmů a ačkoliv mi přijdou mnohem zajímavější, než řešení transakcí, mikrokódu a překladačů, budu je muset v zájmu státnic asi na chvíli vytěsnit...

Ještě poznámka k těm tokům a jestli spadají spíš do ADS -- právě na tom matematickém programování se toky řeší v podstatě jako první LP úloha a spousta kombinatorických úloh se zkoumá z pohledu LP, buď proto, že se dají přímo použít nějaké výsledky o té úloze vyjádřené v LP, nebo protože je ta kombinatorická úloha NP-těžká a používá se LP relaxace celočíselné varianty úlohy k nalezení aproximace... Tím jen chci říct, že i ta hranice, kterou jsem udělal v tom prvním příspěvku, je poněkud hloupá a všechno to se vším souvisí V zásadě bych na to odpověděl tak, že minmaxové věty vždycky zkoumají nějaký problém, který je ve své povaze duální (hráč 1 vs hráč 2, úloha LP a její duál, tok a řez, ...) a říká, že se řešení pro oba hráče rovnají, ale přibližují se k nim z opačných stran. A pak bych uvedl jakýkoliv příklad z těch výše (nejspíš ty toky, protože tam si jsem nejjistější).

[Lukas Mach]

ta těžká věta, kterou jsem měl na mysli, se týká PCP věty ([...]) a jmenuje se Yaův princip.

Mozna jsem mimo, protoze nemam v pameti cely obsah tohohle vlakna, ale tady je neco ne uplne spravne. PCP veta a Yauv princip je neco jineho a ani nevim o tom, ze by nejak souvisely (s vyjimkou toho, ze nam to Sgall rekl v ramci jedne dvoj-prednasky).

[al-Quaknaa]

Lukáš má pravdu, popletl jsem to. Zmínky o PCP větě ignorujte, ta s tím nesouvisí.