Teorija računalniške kompleksnosti - Test
A) Analiza virov, potrebnih za reševanje računalniških problemov B) Oblikovanje strojne opreme za računalnike C) Razvoj novih programskih jezikov D) Psihološki vidiki interakcije med človekom in računalnikom
A) Zapis Big O B) Grške črke C) Binarna koda D) Rimske številke
A) EXP B) NP C) PSPACE D) BPP
A) Raziskovalna B) Razširjen C) Eksponentni čas D) Strokovnjak
A) Ustvarjanje hitrejših računalnikov B) Ustvarjanje naključnih številk C) Razvrstitev računalniških problemov glede na njihovo težavnost D) Gradnja superračunalnikov
A) NP-popolna B) PSPACE C) EXPSPACE D) BQP
A) NP-popolna B) EXPTIME C) P D) BPP
A) Kvantni algoritmi B) Problem P proti NP C) Vzporedno računalništvo D) Popolnost NP
A) Matematična enačba, ki je ne moremo rešiti. B) Težava z strojno opremo računalnikov. C) Naloga, ki jo računalnik reši z uporabo algoritma. D) Teoretično vprašanje, na katerega ni mogoče dobiti odgovora.
A) Šestnajstična abeceda B) Skupina vseh znakov ASCII C) Binarna abeceda {0, 1} D) Skupina vseh malih črk
A) Uporaba samo decimalne notacije B) Kodiranje z uporabo naravnega jezika C) Nekatera konkretna izbira načina kodiranja vhodnih podatkov D) Ni potrebno nobeno kodiranje
A) Izračun največjega pretoka v omrežju. B) Določanje števila vozlišč v grafu. C) Ugotavljanje, ali je dani graf povezan ali ne. D) Iskanje najkrajše poti v grafu.
A) Preverjanje, ali je graf bipartiten. B) Določanje, ali sta dva grafa izomorfna. C) Ugotavljanje, ali je število praštevilo. D) Problem potujočega prodajalca.
A) besede B) biti C) znaki D) biti
A) Naprava za manipulacijo fizičnih predmetov. B) Praktična tehnologija za računalništvo. C) Teoretični model za splošno računanje. D) Zgodnja oblika računalniške opreme.
A) Gödelove nepopolnostne teoreme. B) Teorem Cooka-Levina. C) Teorem P proti NP. D) Teza Churcha-Turinga.
A) Nedeterministični Turingov stroj. B) Deterministični Turingov stroj. C) Kvantni Turingov stroj. D) Verjetnostni Turingov stroj.
A) Omejeni so na polinomski čas. B) Zahtevajo fizično realizabilnost. C) Uporabljajo naključne bite za izračune. D) Delujejo deterministično.
A) Aksiomi kompleksnosti po Blumu B) Aksiomi za razliko med P in NP C) Aksiomi Turingove popolnosti D) Teorem Cook-Levin
A) Kompleksnost kvantne prepletenosti B) Kompleksnost odločitvenih dreves C) Komunikacijska kompleksnost D) Kompleksnost vezij
A) Prostorska kompleksnost B) Komunikacijska kompleksnost C) Kompleksnost vezij D) Časovna kompleksnost
A) Amortizirana analiza B) Kompleksnost v najboljšem primeru C) Kompleksnost v povprečnem primeru D) Kompleksnost v najhujšem primeru
A) FP B) EXPTIME C) NP D) PSPACE
A) Cook-Levinov izrek B) Problem P proti NP C) Savitchov izrek D) Izrek o hierarhiji časovne zahtevnosti
A) VSE B) NP C) P D) EXPTIME
A) Cook-Levinov izrek B) Savitchov izrek C) Teorem o hierarhiji časa D) Teorem o hierarhiji prostorov
A) QMA B) AC C) BPP D) NC
A) AC B) BPP C) RP D) QMA
A) NC B) QMA C) BPP D) IP
A) RP B) BPP C) NC D) #P
A) Zmanjšanje v polinomskem času. B) Zmanjšanje v eksponentnem času. C) Zmanjšanje v logaritemskem času. D) Zmanjšanje v linearnem času.
A) co-NP B) BQP C) NP D) PP
A) P ne bi bilo enako NP. B) co-P ne bi bilo enako co-NP. C) NP ne bi bilo enako co-NP. D) co-P bi bilo enako co-NP.
A) PP B) L C) NC D) NL
A) PH B) BQP C) MA D) PP
A) Končni avtomatni sistemi. B) Digitalna obdelava signalov. C) Kontinuirani dinamični sistemi in diferencialne enačbe. D) Verjetnostni algoritmi.
A) Neprekinjene funkcije. B) Kvantna stanja. C) Boolove izrazi. D) Diskretni grafi.
A) Richard E. Stearns B) Juris Hartmanis C) Alan Turing D) Gabriel Lamé
A) 1945 B) 1950 C) 1965 D) 1936
A) Juris Hartmanis B) Leonid Levin C) Gabriel Lamé D) Edmonds
A) Raymond Smullyan B) John Myhill C) Hisao Yamada D) Boris Trakhtenbrot
A) Izračuni v realnem času B) Osnovni množici C) Mere kompleksnosti D) Linearno omejeni avtomat
A) Raymond Smullyan B) Boris Trakhtenbrot C) Hisao Yamada D) John Myhill
A) 1955 B) 1956 C) 1971 D) 1960
A) "Turingov stroj" B) "Funkcija signalizacije" C) "Računska kompleksnost" D) "Polinomski čas"
A) 1965 B) 1967 C) 1972 D) 1971
A) 15 B) 10 C) 21 D) 30
A) Garey, Michael R.; Johnson, David S. B) Downey, Rod; Fellows, Michael C) Wuppuluri, Shyam; Doria, Francisco A. D) Arora, Sanjeev; Barak, Boaz
A) Cook, Stephen; Fortnow, Lance B) Downey, Rod; Fellows, Michael C) Wuppuluri, Shyam; Doria, Francisco A. D) Papadimitriou, Christos; Sipser, Michael
A) Cook, Stephen B) Mertens, Stephan C) Fortnow, Lance; Homer, Steven D) Khalil, Hatem; Ulery, Dana
A) Sanjeev Arora B) Christos Papadimitriou C) Boaz Barak D) Michael Sipser
A) Oded Goldreich B) Sanjeev Arora; Boaz Barak C) Christos Papadimitriou D) Michael R. Garey; David S. Johnson
A) Sanjeev Arora; Boaz Barak B) Oded Goldreich C) Christos Papadimitriou D) Michael R. Garey; David S. Johnson |
Ustvarjeno z That Quiz —
kjer je izdelava in reševanje testov narejena enostavno za matematiko in ostale predmete.