Fórum Root.cz
Práce => Studium a uplatnění => Téma založeno: Samufaj 08. 06. 2015, 12:56:08
-
Zdravím,
učím se na státnice a už mám odst těch slintů od jednoho nejmenovaného dědka z naši VŠ co debilně vede teoretickou informatiku.
Need help:
NP-těžké problémy - tyhle jsou jasné, patří tam problém obchodního cestujícího (OC). Nezbývá-li nám nic jiného, než vyzkoušet všechna možná řešení která mohou nastat, je problém NP-těžký. Každý problém je transformovatelný na problém OC.
NP-úplné problémy - sem patří problém OC v rozhodovací verzi (Existuje v grafu cesta menší než délky X?) - nemusíme procházet všechna řešení, složitost není nutně n! jako při hledání nejkratší cesty.
NP problémy - tady tu třídu už nevím jak bych zdůvodnil, osobně bych ji spojil s třídou NP-úplných. Patří zde problém izomorfismu dvou grafů (jsou dva grafy navzájem izomorfní?) nicméně nevidím zde v principu žádný rozdíl oproti problému OC v rozhodovací verzi
P problémy - tyhle jsou jasné, jsou to problémy typu třídění, víme u nich jak dlouho budou trvat.
Ví někdo jak vysvětlit, proč OC v rozhodovací verzi patří do NP-úplných, ale izomorfismus dvou grafů patří do NP?
-
http://en.wikipedia.org/wiki/File:P_np_np-complete_np-hard.svg to bude tim, ze se pocita s jeste nespocitanym. nikdo nevi jak to je s (ne)rovnosti P a NP
-
Je to trochu jinak :
NP znamená, že je dokáže řešit nedeterministický Turingův stroj v polynomiálním čase. Já si to představuju pomocí křišťálové koule, která u každého ifu řekne, kudy se vydat. Bez koule je třeba vyzkoušet všechny možnosti a to je exponenciální počet možných kombinací. Obchodní cestující, barvení grafu a podobně jsou NP.
P znamená polynomiální čas u detetministického stroje. Složitost kvadratická, kubická a i vyšší mocniny patří do P. Nedeterministický TS zvládne i tohle, takže P je podmnožina NP.
Těžký/úplný není o jednom problému, ale o převádění problémů mezi sebou.
NP-těžký - jakýkoliv NP problém jde převést na tenhle. NP-těžký problém může být NP nebo i náročnější.
NP-úplný - NP-těžký problém, který je sám NP. Všechny NP-úplné jsou i NP-těžké. Obchodní cestující, barvení grafu, atd. jsou všechny NP-úplné, protože jsou samy NP.
U isomorfismu grafů se momentálně neví, jak to přesně je. Nedeteministický TS to řešit umí, takže je určitě NP nebo lepší. Ještě nikdo nedokázal, jestli to náhodou nejde i deterministickým TS. Možná je to jen P, akorát se to ještě neví. Čeká se buď na to, že někdo najde algoritmus v P, nebo na to že někdo zvládne převést nějaký NP-úplný problém na hledání izomorfismu a pak bude jasné, že je to NP-úplné.
-
A samozřejmě jak psal njn, možná P odpovídá NP. Tohle se taky ještě neví. Pak by celý tenhle binec krásne splaskl. :)
Teď koukám, že jsem ten nedeterministický TS popsal asi trochu matoucím způsobem. Z té koule se tahají možnosti, kudy se má ten algoritmus vydat. Takže bude z koule tahat třeba barvy při barvení grafu nebo města u obchodního cestujícího.
-
P vs. NP and the Computational Complexity Zoo:
https://www.youtube.com/watch?v=YX40hbAHx3s (https://www.youtube.com/watch?v=YX40hbAHx3s)
-
NP-těžký - jakýkoliv NP problém jde převést na tenhle. NP-těžký problém může být NP nebo i náročnější.
Jen dodám, že se v tomto případě jedná o převody pomocí DTS v polynomiálním čase.
U isomorfismu grafů se momentálně neví, jak to přesně je. Nedeteministický TS to řešit umí, takže je určitě NP nebo lepší. Ještě nikdo nedokázal, jestli to náhodou nejde i deterministickým TS. Možná je to jen P, akorát se to ještě neví. Čeká se buď na to, že někdo najde algoritmus v P, nebo na to že někdo zvládne převést nějaký NP-úplný problém na hledání izomorfismu a pak bude jasné, že je to NP-úplné.
Pokud se P nerovná NP, pak existují problémy, které jsou v NP, nejsou v P a nejsou ani NP-úplné.
-
Těžké problémy - http://ksp.mff.cuni.cz/viz/kucharky/tezke-problemy
-
NP-těžké problémy - tyhle jsou jasné, patří tam problém obchodního cestujícího (OC). Nezbývá-li nám nic jiného, než vyzkoušet všechna možná řešení která mohou nastat, je problém NP-těžký. Každý problém je transformovatelný na problém OC.
Pozor - to o transformovani neplati. NP-tezky je aj halting problem, ale netransformujes ho na problem OC. NP-tezky = aspon tak tazky, ako najnarocnejsie problemy v NP.
NP-úplné problémy - sem patří problém OC v rozhodovací verzi (Existuje v grafu cesta menší než délky X?) - nemusíme procházet všechna řešení, složitost není nutně n! jako při hledání nejkratší cesty.
NP uplne = najnarocnejsie problemy v NP. Kazdy problem v NP je prevoditelny na NP uplny problem (tym sa da dokazat, ze problem je v NP).
NP problémy - tady tu třídu už nevím jak bych zdůvodnil, osobně bych ji spojil s třídou NP-úplných. Patří zde problém izomorfismu dvou grafů (jsou dva grafy navzájem izomorfní?) nicméně nevidím zde v principu žádný rozdíl oproti problému OC v rozhodovací verzi
NP problemy bud definujes cez nedeterministicky Turingov stroj (ako to robil JSH) ale podla mna je to jednoduchsie vidiet cez overenie riesenia. NP problemy su tie, ktorych riesenie dokazes overit v polynomialnom case.
Oznacim najkratsiu cestu v grafe a opytam sa, ci je tam najkratsia cesta kratsia ako x. To overis lahko.
P problémy - tyhle jsou jasné, jsou to problémy typu třídění, víme u nich jak dlouho budou trvat.
Ten dodatok "vim, jak dlouho budou trvat" tam radsej nedavaj. Ich trvanie sa da obmedzit polynomom velkosti vstupu.
U NP vseobecne sa zatial vie len obmedzenie exponencialou, ale pri P=NP to bude rovnako polynom.
Naviac vieme odhadnut len vypoctovu zlozitost konkretnych algoritmov ("skolske" nasobenie matic bezi v Θ(n^3)) - zlozitost problemu v niektorych pripadoch konkretne nevieme. Nasobenie matic sa urcite neda spravit v case mensom ako Ω(n^2), lebo treba precitat cely vstup. Ci to ale bude O(n^2.38) alebo O(n^2.2), to sa nevie.
-
Pozor - to o transformovani neplati. NP-tezky je aj halting problem, ale netransformujes ho na problem OC. NP-tezky = aspon tak tazky, ako najnarocnejsie problemy v NP.
ehm, halting problem, ze je NP-tezky? Aspon mas pravdu, ze ho netransformujes na TSP no ;)
http://en.wikipedia.org/wiki/Halting_problem
-
ehm, halting problem, ze je NP-tezky?
Áno, halting problem je NP-ťažký. Je to rozhodovací problém, ktorý neleží v triede NP, ale každý NP-úplný problém sa dá redukovať na ňho.
-
Naviac vieme odhadnut len vypoctovu zlozitost konkretnych algoritmov ("skolske" nasobenie matic bezi v Θ(n^3)) - zlozitost problemu v niektorych pripadoch konkretne nevieme. Nasobenie matic sa urcite neda spravit v case mensom ako Ω(n^2), lebo treba precitat cely vstup. Ci to ale bude O(n^2.38) alebo O(n^2.2), to sa nevie.
U matic a podobných zrovna bacha. Je rozdíl mezi n v "praktických" a "teoretických" výpočtech složitosti. U praktických popisů je n třeba velikost čísla na vstupu, nebo počet řádků čtvercové matice. Ale pokud to bereme čistě teoreticky, tak je to vždycky počet symbolů na pásce, tzn. nějaká nedůležitá konstanta krát počet bitů nebo bytů vstupu.
Extrémně zákeřný příklad jsou algoritmy, co mají na vstupu jediné číslo. Počet bitů je logaritmus čísla, takže i blbý TS, co jen inkrementuje čísla od 0 do zadaného udělá exponenciální počet kroků.
-
@pali: sorry, nejak jsem si popletl definice, uz je mi to jasny :-[
-
Tak teď jsem z toho ještě víc jelen.
Když na to půjdu logicky:
NP-těžké problémy jsou všechny problémy, u kterých musíme zkoušet všechny možnosti které mohou nastat, protože neznáme žádnou fintu k jejich vyřešení.
NP-úplné problémy jsou všechny NP-těžké problémy, u kterých nehledáme nejlepší řešení, ale chceme dostatečné řešení (např. cesta v grafu kratší než X)
NP problémy opět nedkokážu vysvětlit, prostě mi tu nezapadá. Co třeba problémy, u kterých částečně známe fintu? Např. hamiltonovský cyklus, u kterého jsme schopni vyvodit ihned výsledek.
P problémy jsou NP-těžké problémy, pro které známe algoritmus který je vyřeší v polynomiálním čase. Např. i obyčejné třídění, kdyby průměrné IQ bylo houpacího koně, bychom řešili zkoušením všech možnosti, kterých by bylo n!. (ptali bychom se: je nyní množina setřízena od nejmenšího po největší?)
Mě prostě ty definice nedávají smysl, očekával bych od nich trochu logiky.
-
(sorry za ty chyby v textu, píšu to narychlo)
-
A taky mi tu nehraje, proč je problém OC NP-úplný, ten problém přece nemá nedeterministickou časovou složitost, protože na základě počtu uzlů jsme hned schopni říct, kolik přesně se má vyzkoušet cest, bude jich n! - na tom přece není nic nedeterministického. Prostě mi to rozdělení do těch tříd celkově nedává smysl.
-
(pardon, má tam být NP-těžký)
-
Tak snad na tu třídu NP jsem přišel: patří tam problém hemiltonovského cyklu, ten tedy nebude NP-úplný, protože známe částečně způsob, jak určit, že v grafu hemilt. cyklus existuje (viz wiki, je to něco s uzly) - kdežto třeba u problému OC v rozhodovací verzi žádnou neznáme a proto je NP-úplný.
A když se mě na to u státnic zeptají, tak jim to tak řeknu, protože já se omáčku kolem toho, co nedává smysl, šrotit nehodlám :-\
-
A když se mě na to u státnic zeptají, tak jim to tak řeknu, protože já se omáčku kolem toho, co nedává smysl, šrotit nehodlám :-\
Uff, šíleně to motáš. Tvé "definice" založené na tom, zda musíme projít všechny možnosti, jsou spíše zavádějící. Docela by mne zajímalo, zda má ten předmět někde slidy, abychom se mohli podívat, co je důvodem tvého zmatení. Být tebou, držel bych se toho, co ti tu napsali lidé přede mnou.
Můžeme to zkusit vzít postupně, soustřeďme se nyní pouze na rozhodovací problémy - tedy takové, pro které existuje odpověď ano/ne.
Máme dva výpočetní modely:
1. (Deterministický) Turingův stroj (TS) - ten má svůj stav, vstupní pásku a nějaké pracovní pásky (nad kterými se pohybují hlavy). Přechodová funkce na základě stavu stroje a symbolů pod hlavami definuje pokračování, tj. nový stav stroje, co se má zapsat na pracovní pásky a kam se mají pohnout hlavy (doleva, doprava, nikam). Výsledek je ano, pokud stroj skončí v přijímacím stavu. Pokud skončí v jiném stavu (anebo se zacyklí) výsledek je ne.
2. Nedeterministický Turingův stroj (NTS) - Ten je stejný jako TS, ale přechodová funkce vrací množinu možných pokračování (a ne jen jedno jako u TS). Jak psal JSH, představ si to pro zjednodušení klidně tak, že NTS má navíc orákulum, které NTS řekne, které z těchto možných pokračování vybrat (aby se nejrychleji dostal k výsledku).
Problémy P jsou pak takové, které TS vyřeší v polynomiálním čase (TS udělá polynomiálně mnoho kroků) vzhledem k velikosti vstupních dat.
Problémy NP jsou pak takové, které NTS vyřeší v polynomiálním čase (NTS udělá polynomiálně mnoho kroků) vzhledem k velikosti vstupních dat.
Z toho plyne, že problém, který je P, je zároveň NP, protože na TS se klidně můžeš dívat jako na takový degenerovaný NTS, ve kterém přechodová funkce všude vrací jednoprvkové (či prázdné) množiny možných pokračování.
To, zda každý problém, který je v NP, je také v P, se neví. Předpokládá se (a doufá se), že tomu tak není, tj. že existují problémy, které jsou NP, ale nejsou P.
Tak a teď co to je NP-těžký problém: Problém X je NP-těžký, pokud každý problém Y, který je NP, lze (v polynomiálním čase) převést na řešení problému X.
Možná ti může dělat trochu problém, že v definici je psáno, že na něj musí být převoditelný každý NP problém. V praxi se využívá toho, že pokud o problému Z víš, že je NP-těžký, a pokud umíš problém Z (v polynomiálním čase) převést na řešení problému W, pak W je také NP-těžký. To je dáno tím, že pokud ti někdo dá libovolný problém Y (z NP), tak ten lze (protože o Z víš, že je NP-těžký) převést na Z, který už umíš převést na W - tedy celkově umíš každý problém Y (z NP) převést na W.
Pozor na to, že problémy, které jsou NP-těžké, nemusí být řešitelné v polynomiálním čase na NTS. Tedy NP-těžké problémy nemusí být NP!
Kvůli tomu je zde závěrečná definici: NP-úplné jsou takové problémy, které jsou NP-těžké a zároveň jsou NP. Jak zde už někdo psal, NP-úplné problémy jsou z ty nejtěžší z NP, protože každý problém z NP lze na ně (v polynomiálním čase) převést.
Moc jsem to po sobě nečetl, ale snad to dává nějaký smysl.
-
Mrkni na skripte Demlove, mohlo by ti to pomoct:
http://math.feld.cvut.cz/demlova/teaching/tal/predn_tal.html
-
Tak teď jsem z toho ještě víc jelen.
Když na to půjdu logicky:
NP-těžké problémy jsou všechny problémy, u kterých musíme zkoušet všechny možnosti které mohou nastat, protože neznáme žádnou fintu k jejich vyřešení.
NP-úplné problémy jsou všechny NP-těžké problémy, u kterých nehledáme nejlepší řešení, ale chceme dostatečné řešení (např. cesta v grafu kratší než X)
NP problémy opět nedkokážu vysvětlit, prostě mi tu nezapadá. Co třeba problémy, u kterých částečně známe fintu? Např. hamiltonovský cyklus, u kterého jsme schopni vyvodit ihned výsledek.
P problémy jsou NP-těžké problémy, pro které známe algoritmus který je vyřeší v polynomiálním čase. Např. i obyčejné třídění, kdyby průměrné IQ bylo houpacího koně, bychom řešili zkoušením všech možnosti, kterých by bylo n!. (ptali bychom se: je nyní množina setřízena od nejmenšího po největší?)
Mě prostě ty definice nedávají smysl, očekával bych od nich trochu logiky.
Ty definice logické jsou, chyba je v "uživateli".
-
A když se mě na to u státnic zeptají, tak jim to tak řeknu, protože já se omáčku kolem toho, co nedává smysl, šrotit nehodlám :-\
Uff, šíleně to motáš. Tvé "definice" založené na tom, zda musíme projít všechny možnosti, jsou spíše zavádějící. Docela by mne zajímalo, zda má ten předmět někde slidy, abychom se mohli podívat, co je důvodem tvého zmatení. Být tebou, držel bych se toho, co ti tu napsali lidé přede mnou.
Můžeme to zkusit vzít postupně, soustřeďme se nyní pouze na rozhodovací problémy - tedy takové, pro které existuje odpověď ano/ne.
Máme dva výpočetní modely:
1. (Deterministický) Turingův stroj (TS) - ten má svůj stav, vstupní pásku a nějaké pracovní pásky (nad kterými se pohybují hlavy). Přechodová funkce na základě stavu stroje a symbolů pod hlavami definuje pokračování, tj. nový stav stroje, co se má zapsat na pracovní pásky a kam se mají pohnout hlavy (doleva, doprava, nikam). Výsledek je ano, pokud stroj skončí v přijímacím stavu. Pokud skončí v jiném stavu (anebo se zacyklí) výsledek je ne.
2. Nedeterministický Turingův stroj (NTS) - Ten je stejný jako TS, ale přechodová funkce vrací množinu možných pokračování (a ne jen jedno jako u TS). Jak psal JSH, představ si to pro zjednodušení klidně tak, že NTS má navíc orákulum, které NTS řekne, které z těchto možných pokračování vybrat (aby se nejrychleji dostal k výsledku).
Problémy P jsou pak takové, které TS vyřeší v polynomiálním čase (TS udělá polynomiálně mnoho kroků) vzhledem k velikosti vstupních dat.
Problémy NP jsou pak takové, které NTS vyřeší v polynomiálním čase (NTS udělá polynomiálně mnoho kroků) vzhledem k velikosti vstupních dat.
Z toho plyne, že problém, který je P, je zároveň NP, protože na TS se klidně můžeš dívat jako na takový degenerovaný NTS, ve kterém přechodová funkce všude vrací jednoprvkové (či prázdné) množiny možných pokračování.
To, zda každý problém, který je v NP, je také v P, se neví. Předpokládá se (a doufá se), že tomu tak není, tj. že existují problémy, které jsou NP, ale nejsou P.
Tak a teď co to je NP-těžký problém: Problém X je NP-těžký, pokud každý problém Y, který je NP, lze (v polynomiálním čase) převést na řešení problému X.
Možná ti může dělat trochu problém, že v definici je psáno, že na něj musí být převoditelný každý NP problém. V praxi se využívá toho, že pokud o problému Z víš, že je NP-těžký, a pokud umíš problém Z (v polynomiálním čase) převést na řešení problému W, pak W je také NP-těžký. To je dáno tím, že pokud ti někdo dá libovolný problém Y (z NP), tak ten lze (protože o Z víš, že je NP-těžký) převést na Z, který už umíš převést na W - tedy celkově umíš každý problém Y (z NP) převést na W.
Pozor na to, že problémy, které jsou NP-těžké, nemusí být řešitelné v polynomiálním čase na NTS. Tedy NP-těžké problémy nemusí být NP!
Kvůli tomu je zde závěrečná definici: NP-úplné jsou takové problémy, které jsou NP-těžké a zároveň jsou NP. Jak zde už někdo psal, NP-úplné problémy jsou z ty nejtěžší z NP, protože každý problém z NP lze na ně (v polynomiálním čase) převést.
Moc jsem to po sobě nečetl, ale snad to dává nějaký smysl.
No super, díky, teď už mi to dává smysl že je to relativně k TS. Záhada století vyřešena :-)
-
Ale ještě ti tam chybí NP-úplné problémy, to jsou pak jaké?
-
Ale ještě ti tam chybí NP-úplné problémy, to jsou pak jaké?
Nechybí, píšu o nich úplně dole.
-
Moc jsem to po sobě nečetl, ale snad to dává nějaký smysl.
Zapomněl jsi ještě na jeden důležitý teorém (tzv. Prýmkův):
Každá ptákovina, kterou:
- tě ve škole učí semestr až dva
- vůbec jí po těch dvou semestrech nerozumíš
- a budeš ji potřebovat jenom ke státnicím a pak už nikdy v životě
je v polynomiálním čase převoditelná na 36 řádků naprosto srozumitelného, jasného textu, který teprve ti umožní ty státnice udělat.
;)
-
Ještě bych možná doporučil kouknout se na tento obrázek:
(http://upload.wikimedia.org/wikipedia/commons/thumb/a/a0/P_np_np-complete_np-hard.svg/1000px-P_np_np-complete_np-hard.svg.png)
Předpokládá se, že asi P != NP a tedy platí ta varianta vlevo.
-
Moc jsem to po sobě nečetl, ale snad to dává nějaký smysl.
Zapomněl jsi ještě na jeden důležitý teorém (tzv. Prýmkův):
Každá ptákovina, kterou:
- tě ve škole učí semestr až dva
- vůbec jí po těch dvou semestrech nerozumíš
- a budeš ji potřebovat jenom ke státnicím a pak už nikdy v životě
je v polynomiálním čase převoditelná na 36 řádků naprosto srozumitelného, jasného textu, který teprve ti umožní ty státnice udělat.
;)
Jo taky nechápu proč už se neučí složitosti kvantových algoritmů. Tam aspoň ještě je co objevovat.
-
Moc jsem to po sobě nečetl, ale snad to dává nějaký smysl.
Zapomněl jsi ještě na jeden důležitý teorém (tzv. Prýmkův):
Každá ptákovina, kterou:
- tě ve škole učí semestr až dva
- vůbec jí po těch dvou semestrech nerozumíš
- a budeš ji potřebovat jenom ke státnicím a pak už nikdy v životě
je v polynomiálním čase převoditelná na 36 řádků naprosto srozumitelného, jasného textu, který teprve ti umožní ty státnice udělat.
;)
Jen aby ten polynomiální čas nebyl třeba O(n^1000000)...
-
Jen aby ten polynomiální čas nebyl třeba O(n^1000000)...
Jak vidíš, Kuba to zvládl v celkem krátkém čase :)
-
Tady je to poměrně dobře zpracované:
http://math.feld.cvut.cz/demlova/teaching/tal/p-tal5dohr.pdf (http://math.feld.cvut.cz/demlova/teaching/tal/p-tal5dohr.pdf)
-
Každá ptákovina, kterou:
- tě ve škole učí semestr až dva
- vůbec jí po těch dvou semestrech nerozumíš
- a budeš ji potřebovat jenom ke státnicím a pak už nikdy v životě
Jestli jsi studoval na škole, kde se tohle učilo semestr až dva, tak celkem chápu odpor k univerzitám :)
-
Každá ptákovina, kterou:
- tě ve škole učí semestr až dva
- vůbec jí po těch dvou semestrech nerozumíš
- a budeš ji potřebovat jenom ke státnicím a pak už nikdy v životě
Jestli jsi studoval na škole, kde se tohle učilo semestr až dva, tak celkem chápu odpor k univerzitám :)
Ten semestr až dva se totiž učí matematický aparát okolo, aby pomocí toho aparátu šlo studovaný problém vůbec vydefinovat. :)
-
Ten semestr až dva se totiž učí matematický aparát okolo, aby pomocí toho aparátu šlo studovaný problém vůbec vydefinovat. :)
Ano. A jelikož valná část studentů se tím aparátem neprokouše, nenaučí se vůbec nic, v tom je ta pointa :)
-
Předpokládá se, že asi P != NP a tedy platí ta varianta vlevo.
A až se tenhle kruciální problém vyřeší, tak bude konečně levnější pivo? :-*
-
No super, díky, teď už mi to dává smysl že je to relativně k TS. Záhada století vyřešena :-)
Jakub to asi nejlip. Mozna lepe nez tvuj ucitel. Dulezite je ze problemy lze prevatet. Tzn. jeden problem vyresis prevedenim na jiny. Pro NP-uplne problemy jde ukazat takovy cyklus, ze kazdy z nich lze prevest na nejaky jiny. A pokud by jeden z jich byl efektivne resitelny tak by byly resitelne vsechny. Asi "nejzajimavejsi" problem z tohodle pohledu je problem kachlikovani koupelny, na ktery lze prevest vypocet TS.
-
Asi "nejzajimavejsi" problem z tohodle pohledu je problem kachlikovani koupelny, na ktery lze prevest vypocet TS.
Pozor, problém vykachličkovania kúpeľne je obmedzený a teda to nebude výpočet TS, ale výpočet lineárne obmedzeného TS (LBA).
-
Moc jsem to po sobě nečetl, ale snad to dává nějaký smysl.
Zapomněl jsi ještě na jeden důležitý teorém (tzv. Prýmkův):
Každá ptákovina, kterou:
- tě ve škole učí semestr až dva
- vůbec jí po těch dvou semestrech nerozumíš
- a budeš ji potřebovat jenom ke státnicím a pak už nikdy v životě
je v polynomiálním čase převoditelná na 36 řádků naprosto srozumitelného, jasného textu, který teprve ti umožní ty státnice udělat.
;)
Myslel jsem, ze tzv. Prymkova veta zni: je-li obsah ctverce nad preponou, pak alespon 30% prispevku ve vlakne je Mirka Prymka.
Kazdopadne, abychom se drzeli tematu, pomuze znalost P/NP problematiky k lepsimu vydelku? Dokaze absolvent vyresit alespon P problemy behem zkusebni doby?
-
Kazdopadne, abychom se drzeli tematu, pomuze znalost P/NP problematiky k lepsimu vydelku? Dokaze absolvent vyresit alespon P problemy behem zkusebni doby?
Ne. V praxi na řešení P/NP problémů nedojde za celý život absolventa. Otázka rozhodnutelnosti nebo problém zastavení je v praxi degenerován na otázku zda algoritmus vyplivne výsledek před spotřebováním přidělených prostředků (čas, RAM, HDD)
-
Kazdopadne, abychom se drzeli tematu, pomuze znalost P/NP problematiky k lepsimu vydelku? Dokaze absolvent vyresit alespon P problemy behem zkusebni doby?
Krom toho, že pak absolvent tuší třeba to, proč se ty všudypřítomné šifry blbě louskají, to nejspíš až tak využitelné není.
Ale pokud si vezmu třeba náplň TINu na FITu, tak tam je P vs. NP taková třešnička na dortu a zabírá to kousek poslední přednášky. Většinu semestru se berou podstatně praktičtější věci jako regulární výrazy a bezkontextové gramatiky. Je to sice teorie, ale úplně odtržená od reality fakt není.
-
Kazdopadne, abychom se drzeli tematu, pomuze znalost P/NP problematiky k lepsimu vydelku? Dokaze absolvent vyresit alespon P problemy behem zkusebni doby?
Krom toho, že pak absolvent tuší třeba to, proč se ty všudypřítomné šifry blbě louskají, to nejspíš až tak využitelné není.
Ale pokud si vezmu třeba náplň TINu na FITu, tak tam je P vs. NP taková třešnička na dortu a zabírá to kousek poslední přednášky. Většinu semestru se berou podstatně praktičtější věci jako regulární výrazy a bezkontextové gramatiky. Je to sice teorie, ale úplně odtržená od reality fakt není.
no a v tom bych videl uplne ten nejzasadnejsi problem, protoze presto, ze absolvent zna teorii nazpamet a zkouskou proleze - latku nechape v souvislostech. presne jako zdejsi traged co se ptal. neuvedomuje si, ze jsou k dispozici (dnes uz i komercne) silnejsi metody nez jen turinguv stroj i kdyz teda zatim maji jen mizernou vyuzitelnost kvuli nedokonalemu zvladnuti technologie.
-
neuvedomuje si, ze jsou k dispozici (dnes uz i komercne) silnejsi metody nez jen turinguv stroj
Citation needed!
-
Ne. V praxi na řešení P/NP problémů nedojde za celý život absolventa. Otázka rozhodnutelnosti nebo problém zastavení je v praxi degenerován na otázku zda algoritmus vyplivne výsledek před spotřebováním přidělených prostředků (čas, RAM, HDD)
Spíš když už si z toho chceme utahovat, viděl bych největší pikantnost v tom, že vzhledem k tomu, že jde o asymptotickou složitost, může být v praxi algoritmus A složitosti O(2N) klidně vždy rychlejší než algoritmus B složitosti O(1), páč nás jak na potvoru zajímá jenom zpracování dostatečně malých vstupů ;)