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