- 1. Teoria złożoności obliczeniowej jest gałęzią informatyki teoretycznej, która koncentruje się na klasyfikacji problemów obliczeniowych w oparciu o ich nieodłączną trudność i ilość wymaganych zasobów, takich jak czas i przestrzeń. Zajmuje się ona zrozumieniem wydajności algorytmów, analizą wykonalności rozwiązywania problemów na różnych typach maszyn i określaniem ograniczeń mocy obliczeniowej. Badając teorię złożoności obliczeniowej, naukowcy starają się zbadać granice obliczeń oraz zidentyfikować możliwości i ograniczenia komputerów w rozwiązywaniu różnego rodzaju problemów.
Na czym skupia się teoria złożoności obliczeniowej?
A) Analiza zasobów wymaganych do rozwiązywania problemów obliczeniowych
B) Psychologiczne aspekty interakcji człowiek-komputer
C) Projektowanie sprzętu komputerowego
D) Opracowywanie nowych języków programowania
- 2. Która notacja jest powszechnie używana do oznaczania złożoności algorytmów?
A) Kod binarny
B) Cyfry rzymskie
C) Greckie litery
D) Notacja Big O
- 3. Która klasa złożoności zawiera problemy decyzyjne, które są efektywnie weryfikowalne?
A) NP
B) EXP
C) PSPACE
D) BPP
- 4. Z czym związane jest twierdzenie Cooka-Levina w teorii złożoności obliczeniowej?
A) Algorytmy kwantowe
B) Obliczenia równoległe
C) NP-zupełność
D) Problem P vs NP
- 5. Jaka klasa złożoności reprezentuje najtrudniejsze problemy w NP?
A) P
B) EXPTIME
C) BPP
D) NP-zupełny
- 6. Jaki jest główny cel teorii złożoności obliczeniowej?
A) Aby wygenerować liczby losowe
B) Aby stworzyć szybsze komputery
C) Aby zbudować superkomputery
D) Klasyfikacja problemów obliczeniowych na podstawie ich trudności
- 7. Co oznacza "EXP" w teorii złożoności obliczeniowej?
A) Rozszerzony
B) Ekspert
C) Eksploracyjny
D) Czas wykładniczy
- 8. Jaka klasa złożoności jest używana do klasyfikowania problemów, które mogą być rozwiązane przez komputer kwantowy w czasie wielomianowym?
A) BQP
B) EXPSPACE
C) PSPACE
D) NP-zupełny
|