Problém, algoritmus, program
Z FAV wiki
(Rozdíly mezi verzemi)
(Založena nová stránka: 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 (pro...) |
(→Algoritmus) |
||
| (Není zobrazeno 12 mezilehlých verzí od 4 uživatelů.) | |||
| Řádka 1: | Řádka 1: | ||
| − | 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) | + | == Problém == |
| − | 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 | + | |
| + | '''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) | ||
| + | |||
| + | '''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í. | ||
| + | |||
Rozhodovací problémy lze dělit do tříd složitosti | Rozhodovací problémy lze dělit do tříd složitosti | ||
| − | P (polynomiální) - problém je řešitelný pomocí (deterministického) | + | * 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) |
| − | 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í. | + | * 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í. |
| − | 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í) | + | * 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í) |
| − | NP-úplné - NP-těžké problémy, které jsou ve třídě NP, jde tedy o nejtěžší NP úlohy | + | * NP-úplné - NP-těžké problémy, které jsou ve třídě NP, jde tedy o nejtěžší NP úlohy |
| + | |||
| + | [[Soubor:Problemy.gif]] | ||
| + | |||
| + | |||
| + | 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ů. | ||
| + | Pro zasmání: http://www.abclinuxu.cz/clanky/komiks-xkcd-287-np-uplnost | ||
| + | |||
| + | == Algoritmus == | ||
| + | |||
| + | '''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. | ||
| + | * Každý bod algoritmu musí být jednoznačně určen a musí být proveditelný (pochopitelný strojem) | ||
| + | * 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) | ||
| + | * Algoritmus má 0 - N vstupů | ||
| + | * Algoritmus má 1 - N výstupů | ||
| − | + | == Program == | |
| − | |||
| − | + | '''Výpočetní metoda:''' "Algoritmus", který není konečný (event-driven systémy jako třeba automat na kávu, snímače JIS karet, digitální hodinky...) | |
| − | Algoritmus | + | |
| − | + | ||
| − | + | ||
| − | Výpočetní metoda | + | '''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. |
| − | + | {{fav-kiv-bzinf}} | |
| + | [[Kategorie:fav-kiv-bzinf]] | ||
Aktuální verze z 17. 8. 2016, 07:48
[editovat] Problém
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)
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í.
Rozhodovací problémy lze dělit do tříd složitosti
- P (polynomiální) - problém je řešitelný pomocí (deterministického) 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)
- 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í.
- 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í)
- NP-úplné - NP-těžké problémy, které jsou ve třídě NP, jde tedy o nejtěžší NP úlohy
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ů.
Pro zasmání: http://www.abclinuxu.cz/clanky/komiks-xkcd-287-np-uplnost
[editovat] Algoritmus
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.
- Každý bod algoritmu musí být jednoznačně určen a musí být proveditelný (pochopitelný strojem)
- 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)
- Algoritmus má 0 - N vstupů
- Algoritmus má 1 - N výstupů
[editovat] Program
Výpočetní metoda: "Algoritmus", který není konečný (event-driven systémy jako třeba automat na kávu, snímače JIS karet, digitální hodinky...)
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.
