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