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