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