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