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