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