Teorie výpočetní složitosti - Kvíz
A) Vývoj nových programovacích jazyků B) Návrh hardwaru pro počítače C) Psychologické aspekty interakce člověka a počítače D) Analýza zdrojů potřebných k řešení výpočetních problémů
A) Binární kód B) Římské číslice C) Notace „velké O“ D) Řecké písmena
A) NP B) BPP C) PSPACE D) EXP
A) Vytvořit rychlejší počítače B) Generovat náhodná čísla C) Klasifikovat výpočetní problémy podle jejich inherentní obtížnosti D) Postavit superpočítače
A) NP-úplná B) P C) EXPTIME D) BPP
A) Rozšířený B) Odborník C) Průzkumný D) Exponenciální čas
A) Problém P vs. NP B) NP-úplnost C) Paralelní výpočty D) Kvantové algoritmy
A) PSPACE B) NP-úplné C) BQP D) EXPSPACE
A) Matematická rovnice, kterou nelze vyřešit. B) Problém s hardwarem v počítačích. C) Úkol, který řeší počítač pomocí algoritmu. D) Nerozluštitelná teoretická otázka.
A) Množina znaků ASCII B) Hexadecimální abeceda C) Množina všech malých písmen D) Binární abeceda {0, 1}
A) Není potřeba žádné kódování B) Konkrétní volba způsobu kódování vstupu C) Používá se pouze desítková soustava D) Kódování pomocí přirozeného jazyka
A) Určení počtu uzlů v grafu. B) Nalezení nejkratší cesty v grafu. C) Výpočet maximálního toku v síti. D) Rozhodnutí, zda je daný graf souvislý, nebo ne.
A) Problém obchodního cestujícího. B) Zjištění, zda je číslo prvočíslo. C) Určení, zda jsou dva grafy izomorfní. D) Kontrola, zda je graf bipartitní.
A) Bajty B) Bity C) Slova D) Znaky
A) Raná forma počítačového hardwaru. B) Praktická výpočetní technologie. C) Zařízení pro manipulaci s fyzickými objekty. D) Teoretický model pro obecné výpočty.
A) Teorém P vs NP. B) Cookova–Levinova věta. C) Churchova–Turingova teze. D) Gödelovy věty o neúplnosti.
A) Nedeterministický Turingův stroj. B) Kvantový Turingův stroj. C) Deterministický Turingův stroj. D) Pravděpodobnostní Turingův stroj.
A) Vyžadují fyzickou realizovatelnost. B) Fungují deterministicky. C) Jsou omezeny na polynomiální čas. D) Používají náhodná čísla pro výpočty.
A) Axiomy složitosti podle Bluma B) Axiomy Turingovy úplnosti C) Axiomy P vs NP D) Cook-Levinova věta
A) Složitost kvantového provázání B) Složitost obvodu C) Složitost rozhodovacího stromu D) Komunikační složitost
A) Prostorová složitost B) Časová složitost C) Komunikační složitost D) Složitost obvodu
A) Základní teorie množin B) Lineární konečné automaty C) Míry složitosti D) Výpočty v reálném čase
A) Věta o časové hierarchii B) Problém P vs NP C) Savitchova věta D) Cookova-Levinova věta
A) AC B) NC C) BPP D) QMA
A) Tvrzení o časové hierarchii B) Savitchovo tvrzení C) Tvrzení o prostorové hierarchii D) Cook-Levinovo tvrzení
A) 1955 B) 1971 C) 1956 D) 1960
A) PH B) MA C) BQP D) PP
A) Michael R. Garey a David S. Johnson B) Oded Goldreich C) Christos Papadimitriou D) Sanjeev Arora a Boaz Barak
A) 1965 B) 1967 C) 1971 D) 1972
A) „Turingův stroj“ B) „Signalizační funkce“ C) „Výpočetní složitost“ D) „Polynomiální čas“
A) Redukce v polynomiálním čase. B) Redukce v exponenciálním čase. C) Redukce v logaritmickém čase. D) Redukce v lineárním čase.
A) 1936 B) 1945 C) 1950 D) 1965
A) Wuppuluri, Shyam; Doria, Francisco A. B) Arora, Sanjeev; Barak, Boaz C) Downey, Rod; Fellows, Michael D) Garey, Michael R.; Johnson, David S.
A) co-P by se rovnalo co-NP B) co-P by se nerovnalo co-NP C) P by se nerovnalo NP D) NP by se nerovnalo co-NP
A) QMA B) RP C) BPP D) AC
A) Gabriel Lamé B) Juris Hartmanis C) Alan Turing D) Richard E. Stearns
A) Boris Trakhtenbrot B) John Myhill C) Raymond Smullyan D) Hisao Yamada
A) NL B) PP C) L D) NC
A) EXPTIME B) NP C) FP D) PSPACE
A) Raymond Smullyan B) John Myhill C) Hisao Yamada D) Boris Trakhtenbrot
A) Diskrétní grafy. B) Spojité funkce. C) Kvantové stavy. D) Booleovské výrazy.
A) NP B) EXPTIME C) P D) ALL
A) Wuppuluri, Shyam; Doria, Francisco A. B) Downey, Rod; Fellows, Michael C) Cook, Stephen; Fortnow, Lance D) Papadimitriou, Christos; Sipser, Michael
A) Složitost v nejlepším případě B) Složitost v průměrném případě C) Amortizovaná analýza D) Složitost v nejhorším případě
A) co-NP B) NP C) PP D) BQP
A) Pravděpodobnostní algoritmy. B) Kontinuální dynamické systémy a diferenciální rovnice. C) Digitální zpracování signálů. D) Konečné automaty.
A) Mertens, Stephan B) Khalil, Hatem; Ulery, Dana C) Cook, Stephen D) Fortnow, Lance; Homer, Steven
A) NC B) BPP C) IP D) QMA
A) Christos Papadimitriou B) Oded Goldreich C) Michael R. Garey; David S. Johnson D) Sanjeev Arora; Boaz Barak
A) Gabriel Lamé B) Leonid Levin C) Juris Hartmanis D) Edmonds
A) Michael Sipser B) Boaz Barak C) Christos Papadimitriou D) Sanjeev Arora
A) #P B) RP C) BPP D) NC |
Vytvořeno pomocí That Quiz —
kde je vytváření a řešení testů snadné pro matematiku a další obory.