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