https://www.512.cz/index.php?feed=atom&target=94.112.246.82&title=Speci%C3%A1ln%C3%AD%3AP%C5%99%C3%ADsp%C4%9Bvky%2F94.112.246.82 2026-10-25T18:58:39Z Z FAV wiki MediaWiki 1.17.0 https://www.512.cz/index.php?title=Probl%C3%A9m,_algoritmus,_program 2016-08-17T07:48:17Z

<p>94.112.246.82: /* Algoritmus */</p> <hr /> <div>== Problém ==<br /> <br /> '''Problém:''' Otázka či stav, pro jejíž zodpovězení hledáme řešení, případně existenci řešení. Takovýto stav je nežádoucí a je tedy na nás jej změnit (problém vyřešit)<br /> <br /> '''Postup:''' Zjistíme, že problém nastal (nelze situaci zvládnout známými postupy), zadefinujeme problém (vstupy a výstupy), nalezneme způsob žešení, zjistíme, zda je způsob řešení efektivní a případně optimalizujeme způsob řešení. <br /> <br /> <br /> Rozhodovací problémy lze dělit do tříd složitosti<br /> * P (polynomiální) - problém je řešitelný pomocí (deterministického) [http://cs.wikipedia.org/wiki/Turing%C5%AFv_stroj Turingova stroje] 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ý &quot;uhodne&quot; kterou větví se vydat, případně mu něco &quot;napoví&quot; 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 /> [[Soubor:Problemy.gif]]<br /> <br /> <br /> Vztah mezi P a NP je jedním ze sedmi problémů tisíciletí, které vypsal Clayův matematický ústav 24. května 2000, za rozhodnutí vztahu nabízí 1 000 000 dolarů.<br /> <br /> Pro zasmání: http://www.abclinuxu.cz/clanky/komiks-xkcd-287-np-uplnost<br /> <br /> == Algoritmus ==<br /> <br /> '''Algoritmus:''' Obecný postup pro nalezení řešení, ověřený že funguje. Jde o konečnou sekvenci známých operací (některé definice říkají, že tyto operace musí být elementární) které vedou k vyřešení problému.<br /> <br /> * Každý bod algoritmu musí být jednoznačně určen a musí být proveditelný (pochopitelný strojem)<br /> * Algoritmus musí mít konečný počet kroků, tedy musí skončit po konečném počtu operací (narozdíl od výpočetní metody)<br /> * Algoritmus má 0 - N vstupů<br /> * Algoritmus má 1 - N výstupů<br /> <br /> == Program ==<br /> <br /> <br /> '''Výpočetní metoda:''' &quot;Algoritmus&quot;, který není konečný (event-driven systémy jako třeba automat na kávu, snímače JIS karet, digitální hodinky...)<br /> <br /> '''Program:''' Výpočetní metoda (interaktivní aplikace) či algoritmus (dávkové aplikace) zapsaný v souladu s pravidly programovacího jazyka tak, aby bylo možné algoritmus přenést a použít na počítači či jiném stroji. Programovací jazyk je nástroj programátora pro snazší programování, převede se na strojový jazyk, kterému počítač rozumí. Součástí programu může být i popis použitých datových struktur, se kterými algoritmus či výpočetní metoda pracuje.<br /> <br /> {{fav-kiv-bzinf}}<br /> [[Kategorie:fav-kiv-bzinf]]</div>

94.112.246.82 https://www.512.cz/index.php?title=Probl%C3%A9m,_algoritmus,_program 2016-08-16T18:23:37Z

<p>94.112.246.82: /* Problém */</p> <hr /> <div>== Problém ==<br /> <br /> '''Problém:''' Otázka či stav, pro jejíž zodpovězení hledáme řešení, případně existenci řešení. Takovýto stav je nežádoucí a je tedy na nás jej změnit (problém vyřešit)<br /> <br /> '''Postup:''' Zjistíme, že problém nastal (nelze situaci zvládnout známými postupy), zadefinujeme problém (vstupy a výstupy), nalezneme způsob žešení, zjistíme, zda je způsob řešení efektivní a případně optimalizujeme způsob řešení. <br /> <br /> <br /> Rozhodovací problémy lze dělit do tříd složitosti<br /> * P (polynomiální) - problém je řešitelný pomocí (deterministického) [http://cs.wikipedia.org/wiki/Turing%C5%AFv_stroj Turingova stroje] 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ý &quot;uhodne&quot; kterou větví se vydat, případně mu něco &quot;napoví&quot; 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 /> [[Soubor:Problemy.gif]]<br /> <br /> <br /> Vztah mezi P a NP je jedním ze sedmi problémů tisíciletí, které vypsal Clayův matematický ústav 24. května 2000, za rozhodnutí vztahu nabízí 1 000 000 dolarů.<br /> <br /> Pro zasmání: http://www.abclinuxu.cz/clanky/komiks-xkcd-287-np-uplnost<br /> <br /> == Algoritmus ==<br /> <br /> '''Algoritmus:''' Obecný postup pro nalezení řešení, ověřený že funguje. Jde o konečnou sekvenci známých operací (některé definice říkají, že tyto operace musí být elementýrní) které vedou k vyřešení problému.<br /> <br /> * Každý bod algoritmu musí být jednoznačně určen a musí být proveditelný (pochopitelný strojem)<br /> * Algoritmus musí mít konečný počet kroků, tedy musí skončit po konečném počtu operací (narozdíl od výpočetní metody)<br /> * Algoritmus má 0 - N vstupů<br /> * Algoritmus má 1 - N výstupů<br /> <br /> <br /> <br /> == Program ==<br /> <br /> <br /> '''Výpočetní metoda:''' &quot;Algoritmus&quot;, který není konečný (event-driven systémy jako třeba automat na kávu, snímače JIS karet, digitální hodinky...)<br /> <br /> '''Program:''' Výpočetní metoda (interaktivní aplikace) či algoritmus (dávkové aplikace) zapsaný v souladu s pravidly programovacího jazyka tak, aby bylo možné algoritmus přenést a použít na počítači či jiném stroji. Programovací jazyk je nástroj programátora pro snazší programování, převede se na strojový jazyk, kterému počítač rozumí. Součástí programu může být i popis použitých datových struktur, se kterými algoritmus či výpočetní metoda pracuje.<br /> <br /> {{fav-kiv-bzinf}}<br /> [[Kategorie:fav-kiv-bzinf]]</div>

94.112.246.82