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