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