A) Új programozási nyelvek kifejlesztése B) Az ember-számítógép interakció pszichológiai vonatkozásai C) Hardvertervezés számítógépek számára D) A számítási problémák megoldásához szükséges erőforrások elemzése
A) Bináris kód B) Big O jelölés C) Római számok D) Görög betűk
A) PSPACE B) EXP C) BPP D) NP
A) P vs NP probléma B) NP-teljesség C) Kvantum algoritmusok D) Párhuzamos számítástechnika
A) Számítási problémák osztályozása a bennük rejlő nehézség alapján B) Gyorsabb számítógépek létrehozása C) Véletlen számok generálása D) Szuperszámítógépek építése
A) NP-teljes B) BQP C) PSPACE D) EXPSPACE
A) Szakértő B) Felderítő C) Kibővített D) Exponenciális idő
A) BPP B) NP-teljes C) P D) EXPTIME
A) Egy megoldhatatlan elméleti kérdés. B) Egy olyan feladat, amelyet egy számítógép egy algoritmus segítségével old meg. C) Egy hardveres probléma a számítógépekben. D) Egy olyan matematikai egyenlet, amely nem oldható meg.
A) Az ASCII karakterek halmaza B) A bináris betűhalmaz: {0, 1} C) A kisbetűk halmaza D) A hexadecimális betűhalmaz
A) Egy konkrét bemeneti kódolási módszer. B) Nincs szükség semmilyen kódolásra. C) Kódolás természetes nyelven. D) Csak tizedes számjegyek használata.
A) A gráfban található csomók (pontok) számának meghatározása. B) Megállapítani, hogy egy adott gráf összefüggő-e vagy sem. C) A legrövidebb út megtalálása egy gráfban. D) A hálózatban a maximális áramlás kiszámítása.
A) Ellenőrizni, hogy egy gráf kétosztályú-e. B) Az utazóeladó-probléma. C) Megállapítani, hogy két gráf izomorf-e. D) Megállapítani, hogy egy szám prím-e.
A) Bájt B) Szó C) Bit D) Karakter
A) Egy általános számítási modell. B) Egy gyakorlati számítástechnikai technológia. C) Egy korai formája a számítógép hardverének. D) Egy olyan eszköz, amely fizikai tárgyak manipulálására szolgál.
A) A Church-Turing tézis. B) Gödel teljes nem-teljességi tézisei. C) A Cook-Levin tétel. D) A P kontra NP tétel.
A) Determinisztikus Turing-gép. B) Valószínűségi Turing-gép. C) Nem-determinisztikus Turing-gép. D) Kvantum-Turing-gép.
A) Ök determinisztikusan működnek. B) Véletlenszámokat használnak a számításokhoz. C) Fizikai megvalósításra van szükségük. D) Polinom időre korlátozódnak.
A) P vs NP axiómák B) Cook-Levin tétel C) Blum komplexitási axiómák D) Turing-teljesség axiómái
A) Döntési fa komplexitása B) Kvantum összefonódás komplexitása C) Áramkör komplexitása D) Kommunikációs komplexitás
A) Időbeli komplexitás B) Kommunikációs komplexitás C) Memóriahasználat komplexitása D) Áramköri komplexitás
A) Legjobb esetbeli komplexitás B) Legrosszabb esetbeli komplexitás C) Átlagos esetbeli komplexitás D) Amortizációs elemzés
A) PSPACE B) EXPTIME C) NP D) FP
A) Cook-Levin-tétel B) Savitch-tétel C) A P kontra NP probléma D) Időhierarchia-tétel
A) P B) EXPTIME C) NP D) ÖSSZES
A) Időhierarchia-tétel B) Cook-Levin tétel C) Térhierarchia-tétel D) Savitch tézise
A) NC B) AC C) BPP D) QMA
A) BPP B) QMA C) RP D) AC
A) IP B) QMA C) BPP D) NC
A) #P B) RP C) NC D) BPP
A) Exponenciális időben végrehajtható redukció. B) Polinomidőben végrehajtható redukció. C) Logaritmikus időben végrehajtható redukció. D) Lineáris időben végrehajtható redukció.
A) BQP B) NP C) co-NP D) PP
A) A co-P nem lenne egyenlő a co-NP-vel. B) A P nem lenne egyenlő az NP-vel. C) A co-P egyenlő lenne a co-NP-vel. D) Az NP nem lenne egyenlő a co-NP-vel.
A) PP B) L C) NC D) NL
A) BQP B) MA C) PH D) PP
A) Véges állapotú gépek. B) Digitális jelprocesszorok. C) Valószínűségi algoritmusok. D) Kontinuum dinamikai rendszerek és differenciálegyenletek.
A) Diszkrét gráfok. B) Kvantumállapotok. C) Booli kifejezések. D) Folyamatos függvények.
A) Gabriel Lamé B) Richard E. Stearns C) Juris Hartmanis D) Alan Turing
A) 1936 B) 1945 C) 1965 D) 1950
A) Gabriel Lamé B) Juris Hartmanis C) Leonid Levin D) Edmonds
A) Raymond Smullyan B) John Myhill C) Hisao Yamada D) Boris Trakhtenbrot
A) Reálidejű számítások B) Komplexitási mértékek C) Alapvető halmazelmélet D) Lineárisan korlátozott automaták
A) Raymond Smullyan B) Hisao Yamada C) Boris Trakhtenbrot D) John Myhill
A) 1955 B) 1971 C) 1956 D) 1960
A) "Turing-gép" B) "Polinom idő" C) "Számítási komplexitás" D) "Jelzési függvény"
A) 1965 B) 1967 C) 1971 D) 1972
A) 21 B) 30 C) 10 D) 15
A) Arora, Sanjeev; Barak, Boaz B) Wuppuluri, Shyam; Doria, Francisco A. C) Garey, Michael R.; Johnson, David S. D) Downey, Rod; Fellows, Michael
A) Downey, Rod; Fellows, Michael B) Papadimitriou, Christos; Sipser, Michael C) Wuppuluri, Shyam; Doria, Francisco A. D) Cook, Stephen; Fortnow, Lance
A) Mertens, Stephan B) Fortnow, Lance; Homer, Steven C) Cook, Stephen D) Khalil, Hatem; Ulery, Dana
A) Boaz Barak B) Sanjeev Arora C) Christos Papadimitriou D) Michael Sipser
A) Sanjeev Arora; Boaz Barak B) Michael R. Garey; David S. Johnson C) Christos Papadimitriou D) Oded Goldreich
A) Christos Papadimitriou B) Sanjeev Arora; Boaz Barak C) Oded Goldreich D) Michael R. Garey; David S. Johnson |