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