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