https://www.512.cz/index.php?action=history&feed=atom&title=Algoritmick%C3%A1_%C5%99e%C5%A1itelnost_probl%C3%A9m%C5%AF 2026-10-20T18:21:03Z Historie editací této stránky MediaWiki 1.17.0 https://www.512.cz/index.php?title=Algoritmick%C3%A1_%C5%99e%C5%A1itelnost_probl%C3%A9m%C5%AF&diff=451&oldid=prev 2015-05-21T18:36:09Z

<p>typo</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, 18:36</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'>&minus;</td><td style="background: #ffa; color:black; font-size: smaller;"><div>Problém definujeme jako binární relaci mezi množinou instancí problému I (tj. množinou všech možností vstupu) a množinou <del class="diffchange diffchange-inline">rešení </del>S. <del class="diffchange diffchange-inline">Dve </del>instance mohou mít stejné <del class="diffchange diffchange-inline">rešení</del>, <del class="diffchange diffchange-inline">stejne </del>tak jedna muže mít více <del class="diffchange diffchange-inline">rešení</del>. Algoritmická <del class="diffchange diffchange-inline">rešitelnost </del>zkoumá, zda pro všechny formulovatelné problémy lze nalézt algoritmus <del class="diffchange diffchange-inline">rešení</del>.</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>Problém definujeme jako binární relaci mezi množinou instancí problému I (tj. množinou všech možností vstupu) a množinou <ins class="diffchange diffchange-inline">řešení </ins>S. <ins class="diffchange diffchange-inline">Dvě </ins>instance mohou mít stejné <ins class="diffchange diffchange-inline">řešení</ins>, <ins class="diffchange diffchange-inline">stejně </ins>tak jedna muže mít více <ins class="diffchange diffchange-inline">řešení</ins>. Algoritmická <ins class="diffchange diffchange-inline">řešitelnost </ins>zkoumá, zda pro všechny formulovatelné problémy lze nalézt algoritmus <ins class="diffchange diffchange-inline">řešení</ins>.</div></td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'>&#160;</td><td style="background: #eee; color:black; font-size: smaller;"></td></tr> <tr><td class='diff-marker'>&minus;</td><td style="background: #ffa; color:black; font-size: smaller;"><div>Ve 30.<del class="diffchange diffchange-inline">l. </del>20.<del class="diffchange diffchange-inline">st. </del>objevil Alan Turing formální opis algoritmu - <del class="diffchange diffchange-inline">Turinguv </del>stroj, ve spojení s Alonzem Churchem <del class="diffchange diffchange-inline">vytvorili </del>Churchovu-Turingovu tezi a sice, že každý algoritmus (ne problém!) lze vykonat Turingovým strojem. Tezi lze vyvrátit nalezením algoritmu nevykonatelného TS. Moderní programovací jazyky pak byly navrženy tak, aby libovolný program šlo <del class="diffchange diffchange-inline">prevést </del>na TS a naopak. Problém, který nelze <del class="diffchange diffchange-inline">vyrešit </del>pomocí TS, tedy ani pomocí programu, je pak algoritmicky <del class="diffchange diffchange-inline">nerešitelný</del>.</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>Ve 30. <ins class="diffchange diffchange-inline">letech </ins>20. <ins class="diffchange diffchange-inline">století </ins>objevil Alan Turing formální opis algoritmu - <ins class="diffchange diffchange-inline">Turingův </ins>stroj, ve spojení s Alonzem Churchem <ins class="diffchange diffchange-inline">vytvořili </ins>Churchovu-Turingovu tezi a sice, že každý algoritmus (ne problém!) lze vykonat Turingovým strojem. Tezi lze vyvrátit nalezením algoritmu nevykonatelného TS. Moderní programovací jazyky pak byly navrženy tak, aby libovolný program šlo <ins class="diffchange diffchange-inline">převést </ins>na TS a naopak. Problém, který nelze <ins class="diffchange diffchange-inline">vyřešit </ins>pomocí TS, tedy ani pomocí programu, je pak algoritmicky <ins class="diffchange diffchange-inline">neřešitelný</ins>.</div></td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'>&#160;</td><td style="background: #eee; color:black; font-size: smaller;"></td></tr> <tr><td class='diff-marker'>&minus;</td><td style="background: #ffa; color:black; font-size: smaller;"><div><del class="diffchange diffchange-inline">Vytvoríme</del>-li takový rozhodovací problém (<del class="diffchange diffchange-inline">rešení </del>je ano/ne), který pro každý rozhodovací algoritmus a <del class="diffchange diffchange-inline">alespon </del>jeden jeho vstup dává pro tento vstup <del class="diffchange diffchange-inline">opacnou odpoved</del>, než daný algoritmus se stejným vstupem, takový problém není <del class="diffchange diffchange-inline">rešitelný </del>žádným z <del class="diffchange diffchange-inline">techto </del>algoritmu a je tedy nerozhodnutelný. &#160;</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins class="diffchange diffchange-inline">Vytvoříme</ins>-li takový rozhodovací problém (<ins class="diffchange diffchange-inline">řešení </ins>je ano/ne), který pro každý rozhodovací algoritmus a <ins class="diffchange diffchange-inline">alespoň </ins>jeden jeho vstup dává pro tento vstup <ins class="diffchange diffchange-inline">opačnou odpověď</ins>, než daný algoritmus se stejným vstupem, takový problém není <ins class="diffchange diffchange-inline">řešitelný </ins>žádným z <ins class="diffchange diffchange-inline">těchto </ins>algoritmu a je tedy nerozhodnutelný. &#160;</div></td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'>&#160;</td><td style="background: #eee; color:black; font-size: smaller;"></td></tr> <tr><td class='diff-marker'>&minus;</td><td style="background: #ffa; color:black; font-size: smaller;"><div>První takový problém - problém zastavení - našel sám Turing: program má o všech <del class="diffchange diffchange-inline">vytvoritelných </del>programech rozhodnout, zda pro každý ze vstupu</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>První takový problém - problém zastavení - našel sám Turing: program má o všech <ins class="diffchange diffchange-inline">vytvořitelných </ins>programech rozhodnout, zda pro každý ze vstupu</div></td></tr> <tr><td class='diff-marker'>&minus;</td><td style="background: #ffa; color:black; font-size: smaller;"><div>daný program zastaví (tehdy vrací jeho výstup v <del class="diffchange diffchange-inline">podobe prirozeného císla </del>+ 1) nebo nezastaví (pak vrací 0). Takový program to ale nedokáže rozhodnout sám o sobe (pokud by byl <del class="diffchange diffchange-inline">vytvoritelný</del>, <del class="diffchange diffchange-inline">patril </del>by mezi zkoumané programy také a musel by ve svém výstupu vrátit <del class="diffchange diffchange-inline">svuj </del>výstup + 1, což nejde).</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>daný program zastaví (tehdy vrací jeho výstup v <ins class="diffchange diffchange-inline">podobě přirozeného čísla </ins>+ 1) nebo nezastaví (pak vrací 0). Takový program to ale nedokáže rozhodnout sám o sobe (pokud by byl <ins class="diffchange diffchange-inline">vytvořitelný</ins>, <ins class="diffchange diffchange-inline">patřil </ins>by mezi zkoumané programy také a musel by ve svém výstupu vrátit <ins class="diffchange diffchange-inline">svůj </ins>výstup + 1, což nejde).</div></td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'>&#160;</td><td style="background: #eee; color:black; font-size: smaller;"></td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background: #eee; color:black; font-size: smaller;"><div>{{fav-kiv-bzinf}}</div></td><td class='diff-marker'>&#160;</td><td style="background: #eee; color:black; font-size: smaller;"><div>{{fav-kiv-bzinf}}</div></td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background: #eee; color:black; font-size: smaller;"><div>[[Kategorie:fav-kiv-bzinf]]</div></td><td class='diff-marker'>&#160;</td><td style="background: #eee; color:black; font-size: smaller;"><div>[[Kategorie:fav-kiv-bzinf]]</div></td></tr> </table>

78.80.247.252 https://www.512.cz/index.php?title=Algoritmick%C3%A1_%C5%99e%C5%A1itelnost_probl%C3%A9m%C5%AF&diff=413&oldid=prev 2014-02-20T06:37:23Z

<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 9:</td> <td colspan="2" class="diff-lineno">Řádka 9:</td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'>&#160;</td><td style="background: #eee; color:black; font-size: smaller;"></td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background: #eee; color:black; font-size: smaller;"><div>{{fav-kiv-bzinf}}</div></td><td class='diff-marker'>&#160;</td><td style="background: #eee; color:black; font-size: smaller;"><div>{{fav-kiv-bzinf}}</div></td></tr> <tr><td colspan="2">&#160;</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://www.512.cz/index.php?title=Algoritmick%C3%A1_%C5%99e%C5%A1itelnost_probl%C3%A9m%C5%AF&diff=206&oldid=prev 2011-08-23T23:38:49Z

<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 7:</td> <td colspan="2" class="diff-lineno">Řádka 7:</td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background: #eee; color:black; font-size: smaller;"><div>První takový problém - problém zastavení - našel sám Turing: program má o všech vytvoritelných programech rozhodnout, zda pro každý ze vstupu</div></td><td class='diff-marker'>&#160;</td><td style="background: #eee; color:black; font-size: smaller;"><div>První takový problém - problém zastavení - našel sám Turing: program má o všech vytvoritelných programech rozhodnout, zda pro každý ze vstupu</div></td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background: #eee; color:black; font-size: smaller;"><div>daný program zastaví (tehdy vrací jeho výstup v podobe prirozeného císla + 1) nebo nezastaví (pak vrací 0). Takový program to ale nedokáže rozhodnout sám o sobe (pokud by byl vytvoritelný, patril by mezi zkoumané programy také a musel by ve svém výstupu vrátit svuj výstup + 1, což nejde).</div></td><td class='diff-marker'>&#160;</td><td style="background: #eee; color:black; font-size: smaller;"><div>daný program zastaví (tehdy vrací jeho výstup v podobe prirozeného císla + 1) nebo nezastaví (pak vrací 0). Takový program to ale nedokáže rozhodnout sám o sobe (pokud by byl vytvoritelný, patril by mezi zkoumané programy také a musel by ve svém výstupu vrátit svuj výstup + 1, což nejde).</div></td></tr> <tr><td colspan="2">&#160;</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">&#160;</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://www.512.cz/index.php?title=Algoritmick%C3%A1_%C5%99e%C5%A1itelnost_probl%C3%A9m%C5%AF&diff=70&oldid=prev 2011-08-08T15:06:02Z

<p>Založena nová stránka: Problém definujeme jako binární relaci mezi množinou instancí problému I (tj. množinou všech možností vstupu) a množinou rešení S. Dve instance mohou mít stej...</p> <p><b>Nová stránka</b></p><div>Problém definujeme jako binární relaci mezi množinou instancí problému I (tj. množinou všech možností vstupu) a množinou rešení S. Dve instance mohou mít stejné rešení, stejne tak jedna muže mít více rešení. Algoritmická rešitelnost zkoumá, zda pro všechny formulovatelné problémy lze nalézt algoritmus rešení.<br /> <br /> Ve 30.l. 20.st. objevil Alan Turing formální opis algoritmu - Turinguv stroj, ve spojení s Alonzem Churchem vytvorili Churchovu-Turingovu tezi a sice, že každý algoritmus (ne problém!) lze vykonat Turingovým strojem. Tezi lze vyvrátit nalezením algoritmu nevykonatelného TS. Moderní programovací jazyky pak byly navrženy tak, aby libovolný program šlo prevést na TS a naopak. Problém, který nelze vyrešit pomocí TS, tedy ani pomocí programu, je pak algoritmicky nerešitelný.<br /> <br /> Vytvoríme-li takový rozhodovací problém (rešení je ano/ne), který pro každý rozhodovací algoritmus a alespon jeden jeho vstup dává pro tento vstup opacnou odpoved, než daný algoritmus se stejným vstupem, takový problém není rešitelný žádným z techto algoritmu a je tedy nerozhodnutelný. <br /> <br /> První takový problém - problém zastavení - našel sám Turing: program má o všech vytvoritelných programech rozhodnout, zda pro každý ze vstupu<br /> daný program zastaví (tehdy vrací jeho výstup v podobe prirozeného císla + 1) nebo nezastaví (pak vrací 0). Takový program to ale nedokáže rozhodnout sám o sobe (pokud by byl vytvoritelný, patril by mezi zkoumané programy také a musel by ve svém výstupu vrátit svuj výstup + 1, což nejde).</div>

Tester