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