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