10 vztahy: Asymptotická složitost, BPP (třída složitosti), Největší společný dělitel, NP (třída složitosti), Párování grafu, Podmnožina, RP (třída složitosti), Teorie složitosti, Test prvočíselnosti, 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ý!!: P (třída složitosti) a Asymptotická složitost · Vidět víc »
BPP (třída složitosti)
V teorii složitosti je BPP jednou z významných tříd složitosti.
Nový!!: P (třída složitosti) a BPP (třída složitosti) · Vidět víc »
Největší společný dělitel
Největší společný dělitel (značený NSD, D, příp. gcd z anglického greatest common divisor) dvou celých čísel je největší číslo takové, že beze zbytku dělí obě čísla, tzn.
Nový!!: P (třída složitosti) a Největší společný dělitel · 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ý!!: P (třída složitosti) a NP (třída složitosti) · Vidět víc »
Párování grafu
Párování grafu je v teorii grafů taková podmnožina hran grafu, že žádné dvě hrany z této množiny nemají společný vrchol.
Nový!!: P (třída složitosti) a Párování grafu · Vidět víc »
Podmnožina
B je podmnožina A, A je nadmnožina B V matematice se jako podmnožina množiny A označuje taková množina B, o jejíchž všech prvcích platí, že jsou zároveň i prvky množiny A. Obdobně se může množina A označit jako nadmnožina množiny B. Tato fakta značíme B \subseteq A, případně A \supseteq B. Relace „být podmnožinou“ se nazývá také inkluze.
Nový!!: P (třída složitosti) a Podmnožina · Vidět víc »
RP (třída složitosti)
V teorii složitosti je RP jednou z významných tříd složitosti.
Nový!!: P (třída složitosti) a RP (třída složitosti) · Vidět víc »
Teorie složitosti
Teorie složitosti je odvětvím teorie počítání v informatice a matematice, které se zaměřuje na klasifikaci výpočetních problémů dle jejich vlastní složitosti a určení vztahů mezi nimi.
Nový!!: P (třída složitosti) a Teorie složitosti · Vidět víc »
Test prvočíselnosti
Mersennova prvočísla Test prvočíselnosti je algoritmus z oboru teorie čísel, kterým lze určit, zda je zadané přirozené číslo prvočíslem.
Nový!!: P (třída složitosti) a Test prvočíselnosti · 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ý!!: P (třída složitosti) a Turingův stroj · Vidět víc »