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