Teorija računalniške kompleksnosti - Izpit
- 1. Teorija računske zahtevnosti je veja teoretične informatike, ki se osredotoča na razvrščanje računskih problemov glede na njihovo notranjo težavnost in količino potrebnih virov, kot sta čas in prostor. Ukvarja se z razumevanjem učinkovitosti algoritmov, analizo izvedljivosti reševanja problemov na različnih vrstah strojev in določanjem omejitev računske moči. S preučevanjem teorije računske zahtevnosti si raziskovalci prizadevajo raziskati meje računanja ter ugotoviti zmogljivosti in omejitve računalnikov pri reševanju različnih vrst problemov.
Na kaj se osredotoča teorija računalniške kompleksnosti?
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
- 2. Kateri zapis se običajno uporablja za označevanje zahtevnosti algoritmov?
A) Rimske številke
B) Grške črke
C) Binarna koda
D) Zapis Big O
- 3. Kateri razred kompleksnosti vsebuje probleme odločanja, ki jih je mogoče učinkovito preveriti?
A) EXP
B) BPP
C) PSPACE
D) NP
- 4. Kaj v teoriji računalniške kompleksnosti pomeni beseda EXP?
A) Eksponentni čas
B) Razširjen
C) Raziskovalna
D) Strokovnjak
- 5. Kaj je glavni cilj teorije računalniške kompleksnosti?
A) Ustvarjanje naključnih številk
B) Razvrstitev računalniških problemov glede na njihovo težavnost
C) Ustvarjanje hitrejših računalnikov
D) Gradnja superračunalnikov
- 6. V kateri razred zahtevnosti se uvrščajo problemi, ki jih lahko kvantni računalnik reši v polinomskem času?
A) EXPSPACE
B) PSPACE
C) NP-popolna
D) BQP
- 7. Kateri razred zahtevnosti predstavlja najtežje probleme v NP?
A) EXPTIME
B) P
C) BPP
D) NP-popolna
- 8. S čim je Cookov-Levinov izrek povezan v teoriji računalniške kompleksnosti?
A) Problem P proti NP
B) Kvantni algoritmi
C) Popolnost NP
D) Vzporedno računalništvo
|