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