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