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