Logo
Uniepedie
Sdělení
Nyní na Google Play
Nový! Ke stažení Uniepedie na vašem zařízení se systémem Android™!
Nainstalovat
Rychlejší přístup než prohlížeči!
 

Problém P versus NP

Index Problém P versus NP

Eulerův diagram tříd složitosti pro obě možnosti rozhodnutí tohoto problému Problém P versus NP je důležitý otevřený problém v teoretické informatice; označuje se tak otázka, zda jsou třídy složitosti P a NP totožné.

14 vztahy: Asymptotická složitost, Determinismus, Kryptografie, Matematický důkaz, NP (třída složitosti), NP-úplnost, Otevřené problémy v matematice, P (třída složitosti), PostScript, Problém obchodního cestujícího, Problémy tisíciletí, Stephen Cook, Teoretická informatika, Turingův stroj.

Asymptotická složitost

Grafické porovnání různých tříd složitosti s ohledem na změnu velikosti vstupních dat. Při řešení úloh pomocí výpočetní techniky musíme mít nástroj, kterým dokážeme porovnat efektivitu a rychlost vykonávání jednotlivých algoritmů.

Nový!!: Problém P versus NP a Asymptotická složitost · Vidět víc »

Determinismus

Determinismus je filosofické přesvědčení, že každá událost nebo stav věcí je důsledkem předchozích událostí na principu kauzality a pevně daných zákonitostí.

Nový!!: Problém P versus NP a Determinismus · Vidět víc »

Kryptografie

Šifrovací stroj Enigma Kryptografie neboli šifrování je nauka o metodách utajování smyslu zpráv převodem do podoby, která je čitelná jen se speciální znalostí.

Nový!!: Problém P versus NP a Kryptografie · Vidět víc »

Matematický důkaz

Základů''. Jeden z nejstarších dochovaných matematických důkazů V matematice je důkaz demonstrace nutné pravdivosti nějakého tvrzení za určitých předpokladů (axiomů).

Nový!!: Problém P versus NP a Matematický důkaz · Vidět víc »

NP (třída složitosti)

NP (zkratka nedeterministicky polynomiální) je množina problémů, které lze řešit v polynomiálně omezeném čase na nedeterministickém Turingově stroji - na počítači, který umožňuje v každém kroku rozvětvit výpočet na n větví, v nichž se posléze řešení hledá současně.

Nový!!: Problém P versus NP a NP (třída složitosti) · Vidět víc »

NP-úplnost

NP-úplné (NP-complete, NPC) problémy jsou takové nedeterministicky polynomiální problémy, na které jsou polynomiálně redukovatelné všechny ostatní problémy z NP.

Nový!!: Problém P versus NP a NP-úplnost · Vidět víc »

Otevřené problémy v matematice

Termín otevřené problémy vyjadřuje dosud nevyřešené problémy, včetně těch neřešitelných.

Nový!!: Problém P versus NP a Otevřené problémy v matematice · Vidět víc »

P (třída složitosti)

V teorii složitosti je P jednou z nejzákladnějších tříd složitosti.

Nový!!: Problém P versus NP a P (třída složitosti) · Vidět víc »

PostScript

PostScript je programovací jazyk určený ke grafickému popisu tisknutelných dokumentů vyvinutý v roce 1985 firmou Adobe Systems Incorporated.

Nový!!: Problém P versus NP a PostScript · Vidět víc »

Problém obchodního cestujícího

Problém obchodního cestujícího (anglicky – TSP) je obtížný diskrétní optimalizační problém, matematicky vyjadřující a zobecňující úlohu nalezení nejkratší možné cesty procházející všemi vrcholy ohodnoceného grafu.

Nový!!: Problém P versus NP a Problém obchodního cestujícího · Vidět víc »

Problémy tisíciletí

Problémy tisíciletí (anglicky Millenium Prize Problems) je označení pro sedm matematických problémů, které v roce 2000 vyhlásil Clayův matematický institut jako nejdůležitější otevřené problémy soudobé matematiky.

Nový!!: Problém P versus NP a Problémy tisíciletí · Vidět víc »

Stephen Cook

Stephen Arthur Cook (* 14. prosince 1939 Buffalo, New York, USA) je americký informatik.

Nový!!: Problém P versus NP a Stephen Cook · Vidět víc »

Teoretická informatika

Teoretická informatika je oblast matematické informatiky a matematiky, která se zaměřuje na abstraktnější a matematické aspekty zpracování informací, které mají využití v počítačích a zpracování informací.

Nový!!: Problém P versus NP a Teoretická informatika · Vidět víc »

Turingův stroj

Umělecké znázornění Turingova stroje Turingův stroj (TS) je teoretický model počítače popsaný matematikem Alanem Turingem, který se používá pro modelování algoritmů v teorii vyčíslitelnosti.

Nový!!: Problém P versus NP a Turingův stroj · Vidět víc »

Přesměrování zde:

P versus NP, P vs. NP, P=NP.

OdchozíPřicházející
Ahoj! Jsme na Facebooku teď! »