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