Teoria złożoności obliczeniowej
- 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) Projektowanie sprzętu komputerowego
C) Opracowywanie nowych języków programowania
D) Psychologiczne aspekty interakcji człowiek-komputer
- 2. Która notacja jest powszechnie używana do oznaczania złożoności algorytmów?
A) Notacja Big O
B) Kod binarny
C) Cyfry rzymskie
D) Greckie litery
- 3. Która klasa złożoności zawiera problemy decyzyjne, które są efektywnie weryfikowalne?
A) EXP
B) PSPACE
C) BPP
D) NP
- 4. 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) NP-zupełny
B) BQP
C) PSPACE
D) EXPSPACE
- 5. Jaki jest główny cel teorii złożoności obliczeniowej?
A) Aby wygenerować liczby losowe
B) Aby zbudować superkomputery
C) Klasyfikacja problemów obliczeniowych na podstawie ich trudności
D) Aby stworzyć szybsze komputery
- 6. Co oznacza "EXP" w teorii złożoności obliczeniowej?
A) Rozszerzony
B) Ekspert
C) Czas wykładniczy
D) Eksploracyjny
- 7. Jaka klasa złożoności reprezentuje najtrudniejsze problemy w NP?
A) P
B) BPP
C) NP-zupełny
D) EXPTIME
- 8. Z czym związane jest twierdzenie Cooka-Levina w teorii złożoności obliczeniowej?
A) NP-zupełność
B) Obliczenia równoległe
C) Problem P vs NP
D) Algorytmy kwantowe
|