Klasifikace problémů - Historie editací

https://512.cz/index.php?action=history&feed=atom&title=Klasifikace_probl%C3%A9m%C5%AF Klasifikace problémů - Historie editací 2026-10-21T01:17:50Z Historie editací této stránky MediaWiki 1.17.0 https://512.cz/index.php?title=Klasifikace_probl%C3%A9m%C5%AF&diff=456&oldid=prev 78.80.247.252: formátování 2015-05-21T19:26:11Z

<p>formátování</p> <table style="background-color: white; color:black;"> <col class='diff-marker' /> <col class='diff-content' /> <col class='diff-marker' /> <col class='diff-content' /> <tr valign='top'> <td colspan='2' style="background-color: white; color:black;">← Starší verze</td> <td colspan='2' style="background-color: white; color:black;">Verze z 21. 5. 2015, 19:26</td> </tr><tr><td colspan="2" class="diff-lineno">Řádka 1:</td> <td colspan="2" class="diff-lineno">Řádka 1:</td></tr> <tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div>Rozhodovací problémy lze dělit do tříd složitosti</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>Rozhodovací problémy lze dělit do tříd složitosti<ins class="diffchange diffchange-inline">:</ins></div></td></tr> <tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div>P (polynomiální) - problém je řešitelný pomocí (deterministického) <del class="diffchange diffchange-inline">Turingova stroje (<</del>http://cs.wikipedia.org/wiki/Turing%C5%AFv_stroj<del class="diffchange diffchange-inline">>) </del>v Polynomiálním čase (např problém řazení), lze dokázat, že všechny problémy P jsou podmnožinou problémů skupiny NP (NP problém s jednou větví, NP problém bez hádání či nápovědy)</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div> </div></td></tr> <tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div>NP (nedeterministicky polynomiální)  - Polynomiální čas, ale nedeterministický Turingův stroj (takový, který může rozvětvit program v libovolném kroku na více větví, ve kterých hledá řešení současně (zcela paralelně), případně lze mluvit o stroji, který "uhodne" kterou větví se vydat, případně mu něco "napoví" kudy se má vydat, aby řešení bylo správné. Také lze mluvit o problémech, jejichž řešení lze ověřit  v polynomiálním čase (zpětný postup, zjištění, zda je nalezené řešení <del class="diffchange diffchange-inline">opdpovídající </del>problému), <del class="diffchange diffchange-inline">níkoliv </del>jej získat  - pokud bychom všechny větve umístili řekněme do zásobníku (zásobníkový <del class="diffchange diffchange-inline">Touringův </del>stroj), čas pro nalezení řešení by nutně nebyl polynomiální. Je otázkou, zda lze pro NP problémy najít P řešení.</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins class="diffchange diffchange-inline">'''</ins>P (polynomiální)<ins class="diffchange diffchange-inline">''' </ins>- problém je řešitelný pomocí (deterministického) <ins class="diffchange diffchange-inline">[</ins>http://cs.wikipedia.org/wiki/Turing%C5%AFv_stroj <ins class="diffchange diffchange-inline">Turingova stroje] </ins>v Polynomiálním čase (např<ins class="diffchange diffchange-inline">. </ins>problém řazení), lze dokázat, že všechny problémy P jsou podmnožinou problémů skupiny NP (NP problém s jednou větví, NP problém bez hádání či nápovědy)</div></td></tr> <tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div>NP-těžké - Problémy, na které lze v polynomiálním čase převést všechny problémy NP, nemusí však nutně v NP samy o sobě být (nemusí být ani rozhodovací)</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div> </div></td></tr> <tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div>NP-úplné - NP-těžké problémy, které jsou ve třídě NP, jde tedy o nejtěžší NP úlohy</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins class="diffchange diffchange-inline">'''</ins>NP (nedeterministicky polynomiální)<ins class="diffchange diffchange-inline">''' </ins> - Polynomiální čas, ale nedeterministický Turingův stroj (takový, který může rozvětvit program v libovolném kroku na více větví, ve kterých hledá řešení současně (zcela paralelně), případně lze mluvit o stroji, který "uhodne" kterou větví se vydat, případně mu něco "napoví" kudy se má vydat, aby řešení bylo správné. Také lze mluvit o problémech, jejichž řešení lze ověřit  v polynomiálním čase (zpětný postup, zjištění, zda je nalezené řešení <ins class="diffchange diffchange-inline">odpovídající </ins>problému), <ins class="diffchange diffchange-inline">nikoliv </ins>jej získat  - pokud bychom všechny větve umístili řekněme do zásobníku (zásobníkový <ins class="diffchange diffchange-inline">Turingův </ins>stroj), čas pro nalezení řešení by nutně nebyl polynomiální. Je otázkou, zda lze pro NP problémy najít P řešení.</div></td></tr> <tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div> </div></td></tr> <tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins class="diffchange diffchange-inline">'''</ins>NP-těžké<ins class="diffchange diffchange-inline">''' </ins>- Problémy, na které lze v polynomiálním čase převést všechny problémy NP, nemusí však nutně v NP samy o sobě být (nemusí být ani rozhodovací)</div></td></tr> <tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div> </div></td></tr> <tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins class="diffchange diffchange-inline">'''</ins>NP-úplné<ins class="diffchange diffchange-inline">''' </ins>- NP-těžké problémy, které jsou ve třídě NP, jde tedy o nejtěžší NP úlohy</div></td></tr> <tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr> <tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>[[Soubor:Np-problemy.jpg]]  </div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>[[Soubor:Np-problemy.jpg]]  </div></td></tr> </table>

78.80.247.252 https://512.cz/index.php?title=Klasifikace_probl%C3%A9m%C5%AF&diff=414&oldid=prev Acolade: kategorizace 2014-02-20T06:37:56Z

<p>kategorizace</p> <table style="background-color: white; color:black;"> <col class='diff-marker' /> <col class='diff-content' /> <col class='diff-marker' /> <col class='diff-content' /> <tr valign='top'> <td colspan='2' style="background-color: white; color:black;">← Starší verze</td> <td colspan='2' style="background-color: white; color:black;">Verze z 20. 2. 2014, 06:37</td> </tr><tr><td colspan="2" class="diff-lineno">Řádka 10:</td> <td colspan="2" class="diff-lineno">Řádka 10:</td></tr> <tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr> <tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>{{fav-kiv-bzinf}}</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>{{fav-kiv-bzinf}}</div></td></tr> <tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins style="color: red; font-weight: bold; text-decoration: none;">[[Kategorie:fav-kiv-bzinf]]</ins></div></td></tr> </table>

Acolade https://512.cz/index.php?title=Klasifikace_probl%C3%A9m%C5%AF&diff=205&oldid=prev Tester v 23. 8. 2011, 23:38 2011-08-23T23:38:34Z

<p></p> <table style="background-color: white; color:black;"> <col class='diff-marker' /> <col class='diff-content' /> <col class='diff-marker' /> <col class='diff-content' /> <tr valign='top'> <td colspan='2' style="background-color: white; color:black;">← Starší verze</td> <td colspan='2' style="background-color: white; color:black;">Verze z 23. 8. 2011, 23:38</td> </tr><tr><td colspan="2" class="diff-lineno">Řádka 8:</td> <td colspan="2" class="diff-lineno">Řádka 8:</td></tr> <tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr> <tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>A dále je tu složitost problémů, viz 6</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>A dále je tu složitost problémů, viz 6</div></td></tr> <tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins style="color: red; font-weight: bold; text-decoration: none;"></ins></div></td></tr> <tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins style="color: red; font-weight: bold; text-decoration: none;">{{fav-kiv-bzinf}}</ins></div></td></tr> </table>

Tester https://512.cz/index.php?title=Klasifikace_probl%C3%A9m%C5%AF&diff=129&oldid=prev Tester v 10. 8. 2011, 09:32 2011-08-10T09:32:28Z

<p></p> <table style="background-color: white; color:black;"> <col class='diff-marker' /> <col class='diff-content' /> <col class='diff-marker' /> <col class='diff-content' /> <tr valign='top'> <td colspan='2' style="background-color: white; color:black;">← Starší verze</td> <td colspan='2' style="background-color: white; color:black;">Verze z 10. 8. 2011, 09:32</td> </tr><tr><td colspan="2" class="diff-lineno">Řádka 5:</td> <td colspan="2" class="diff-lineno">Řádka 5:</td></tr> <tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>NP-úplné - NP-těžké problémy, které jsou ve třídě NP, jde tedy o nejtěžší NP úlohy</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>NP-úplné - NP-těžké problémy, které jsou ve třídě NP, jde tedy o nejtěžší NP úlohy</div></td></tr> <tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr> <tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div><del class="diffchange diffchange-inline"> </del></div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins class="diffchange diffchange-inline">[[Soubor:Np-problemy.jpg]] </ins></div></td></tr> <tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div> </div></td></tr> <tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>A dále je tu složitost problémů, viz 6</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>A dále je tu složitost problémů, viz 6</div></td></tr> </table>

Tester https://512.cz/index.php?title=Klasifikace_probl%C3%A9m%C5%AF&diff=71&oldid=prev Tester: Založena nová stránka: Rozhodovací problémy lze dělit do tříd složitosti P (polynomiální) - problém je řešitelný pomocí (deterministického) Turingova stroje (<http://cs.wikipedia.or... 2011-08-08T15:06:34Z

<p>Založena nová stránka: Rozhodovací problémy lze dělit do tříd složitosti P (polynomiální) - problém je řešitelný pomocí (deterministického) Turingova stroje (<http://cs.wikipedia.or...</p> <p><b>Nová stránka</b></p><div>Rozhodovací problémy lze dělit do tříd složitosti<br /> P (polynomiální) - problém je řešitelný pomocí (deterministického) Turingova stroje (<http://cs.wikipedia.org/wiki/Turing%C5%AFv_stroj>) v Polynomiálním čase (např problém řazení), lze dokázat, že všechny problémy P jsou podmnožinou problémů skupiny NP (NP problém s jednou větví, NP problém bez hádání či nápovědy)<br /> NP (nedeterministicky polynomiální) - Polynomiální čas, ale nedeterministický Turingův stroj (takový, který může rozvětvit program v libovolném kroku na více větví, ve kterých hledá řešení současně (zcela paralelně), případně lze mluvit o stroji, který "uhodne" kterou větví se vydat, případně mu něco "napoví" kudy se má vydat, aby řešení bylo správné. Také lze mluvit o problémech, jejichž řešení lze ověřit v polynomiálním čase (zpětný postup, zjištění, zda je nalezené řešení opdpovídající problému), níkoliv jej získat - pokud bychom všechny větve umístili řekněme do zásobníku (zásobníkový Touringův stroj), čas pro nalezení řešení by nutně nebyl polynomiální. Je otázkou, zda lze pro NP problémy najít P řešení.<br /> NP-těžké - Problémy, na které lze v polynomiálním čase převést všechny problémy NP, nemusí však nutně v NP samy o sobě být (nemusí být ani rozhodovací)<br /> NP-úplné - NP-těžké problémy, které jsou ve třídě NP, jde tedy o nejtěžší NP úlohy<br /> <br /> <br /> A dále je tu složitost problémů, viz 6</div>

Tester