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) Projektowanie sprzętu komputerowego
B) Analiza zasobów wymaganych do rozwiązywania problemów obliczeniowych
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) Greckie litery
B) Notacja Big O
C) Kod binarny
D) Cyfry rzymskie
- 3. Która klasa złożoności zawiera problemy decyzyjne, które są efektywnie weryfikowalne?
A) BPP
B) EXP
C) PSPACE
D) NP
- 4. Z czym związane jest twierdzenie Cooka-Levina w teorii złożoności obliczeniowej?
A) Algorytmy kwantowe
B) Problem P vs NP
C) Obliczenia równoległe
D) NP-zupełność
- 5. Jaka klasa złożoności reprezentuje najtrudniejsze problemy w NP?
A) NP-zupełny
B) P
C) EXPTIME
D) BPP
- 6. Jaki jest główny cel teorii złożoności obliczeniowej?
A) Aby stworzyć szybsze komputery
B) Aby wygenerować liczby losowe
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) Czas wykładniczy
B) Eksploracyjny
C) Rozszerzony
D) Ekspert
- 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) NP-zupełny
B) EXPSPACE
C) PSPACE
D) BQP
|