A) Psychologiczne aspekty interakcji człowiek-komputer B) Opracowywanie nowych języków programowania C) Analiza zasobów wymaganych do rozwiązywania problemów obliczeniowych D) Projektowanie sprzętu komputerowego
A) Notacja Big O B) Kod binarny C) Cyfry rzymskie D) Greckie litery
A) BPP B) NP C) EXP D) PSPACE
A) EXPSPACE B) NP-zupełny C) BQP D) PSPACE
A) Aby zbudować superkomputery B) Aby stworzyć szybsze komputery C) Klasyfikacja problemów obliczeniowych na podstawie ich trudności D) Aby wygenerować liczby losowe
A) Czas wykładniczy B) Rozszerzony C) Ekspert D) Eksploracyjny
A) P B) NP-zupełny C) BPP D) EXPTIME
A) NP-zupełność B) Obliczenia równoległe C) Algorytmy kwantowe D) Problem P vs NP
A) Problem sprzętowy w komputerach. B) Zadanie rozwiązywane przez komputer przy użyciu algorytmu. C) Teoretyczne pytanie, na które nie można znaleźć odpowiedzi. D) Równanie matematyczne, którego nie można rozwiązać.
A) Zbiór znaków ASCII B) Szesnastkowy zestaw znaków C) Zbiór wszystkich małych liter D) Dwójkowy zestaw znaków {0, 1}
A) Kodowanie przy użyciu języka naturalnego. B) Konkretny sposób kodowania danych wejściowych. C) Używanie wyłącznie notacji dziesiętnej. D) Nie jest wymagane żadne kodowanie.
A) Określenie, czy dany graf jest spójny, czy nie. B) Obliczenie maksymalnego przepływu w sieci. C) Określenie liczby wierzchołków w grafie. D) Znalezienie najkrótszej ścieżki w grafie.
A) Sprawdzanie, czy graf jest dwudzielny. B) Problem komiwojażera. C) Określanie, czy dwa grafy są izomorficzne. D) Sprawdzanie, czy liczba jest liczbą pierwszą.
A) Znaki B) Bity C) Bajty D) Słowa
A) Wczesna forma sprzętu komputerowego. B) Praktyczna technologia obliczeniowa. C) Teoretyczny model ogólnych obliczeń. D) Urządzenie do manipulowania obiektami fizycznymi.
A) Niewerifikowalność twierdzeń Gödla. B) Teza Churcha-Turinga. C) Twierdzenie P vs NP. D) Twierdzenie Cooka-Levina.
A) Maszyna Turinga deterministyczna. B) Maszyna Turinga niedeterministyczna. C) Maszyna Turinga probabilistyczna. D) Maszyna Turinga kwantowa.
A) Wykorzystują losowe bity do obliczeń. B) Wymagają możliwości fizycznej realizacji. C) Działają deterministycznie. D) Są ograniczone do czasu wielomianowego.
A) Aksjomaty dotyczące problemu P vs NP B) Aksjomaty złożoności Bluma C) Twierdzenie Cooke'a-Levina D) Aksjomaty kompletności Turinga
A) Złożoność komunikacyjna B) Złożoność splątania kwantowego C) Złożoność drzew decyzyjnych D) Złożoność obwodów
A) Złożoność obwodów B) Złożoność czasowa C) Złożoność przestrzenna D) Złożoność komunikacyjna
A) Złożoność w najgorszym przypadku B) Złożoność w przypadku średnim C) Analiza amortyzowana D) Złożoność w najlepszym przypadku
A) PSPACE B) EXPTIME C) FP D) NP
A) Problem P vs NP B) Twierdzenie Cooka-Levina C) Twierdzenie Savitcha D) Twierdzenie o hierarchii czasowej
A) WSZYSTKIE B) P C) NP D) EXPTIME
A) Twierdzenie o hierarchii czasu B) Twierdzenie Savitcha C) Twierdzenie Cooka-Levina D) Twierdzenie o hierarchii przestrzeni
A) QMA B) AC C) BPP D) NC
A) RP B) QMA C) BPP D) AC
A) QMA B) BPP C) NC D) IP
A) #P B) NC C) RP D) BPP
A) Redukcja w czasie logarytmicznym. B) Redukcja w czasie wielomianowym. C) Redukcja w czasie wykładniczym. D) Redukcja w czasie liniowym.
A) BQP B) PP C) co-NP D) NP
A) co-P byłoby równe co-NP. B) P nie byłoby równe NP. C) co-P nie byłoby równe co-NP. D) NP nie byłoby równe co-NP.
A) PP B) NL C) NC D) L
A) PP B) MA C) BQP D) PH
A) Systemy dynamiczne i równania różniczkowe. B) Maszyny stanowe. C) Przetwarzanie sygnałów cyfrowych. D) Algorytmy probabilistyczne.
A) Grafy dyskretne. B) Stany kwantowe. C) Funkcje ciągłe. D) Wyrażenia logiczne.
A) Richard E. Stearns B) Juris Hartmanis C) Alan Turing D) Gabriel Lamé
A) 1965 B) 1950 C) 1945 D) 1936
A) Edmonds B) Leonid Levin C) Gabriel Lamé D) Juris Hartmanis
A) Raymond Smullyan B) Hisao Yamada C) Boris Trakhtenbrot D) John Myhill
A) Automaty liniowo ograniczone B) Obliczenia w czasie rzeczywistym C) Podstawowe zbiory D) Miary złożoności
A) John Myhill B) Hisao Yamada C) Boris Trakhtenbrot D) Raymond Smullyan
A) 1960 B) 1956 C) 1971 D) 1955
A) „Maszyna Turinga” B) „Funkcja sygnalizująca” C) „Czas wielomianowy” D) „Złożoność obliczeniowa”
A) 1971 B) 1967 C) 1965 D) 1972
A) 21 B) 15 C) 30 D) 10
A) Garey, Michael R.; Johnson, David S. B) Wuppuluri, Shyam; Doria, Francisco A. C) Downey, Rod; Fellows, Michael D) Arora, Sanjeev; Barak, Boaz
A) Papadimitriou, Christos; Sipser, Michael B) Cook, Stephen; Fortnow, Lance C) Downey, Rod; Fellows, Michael D) Wuppuluri, Shyam; Doria, Francisco A.
A) Cook, Stephen B) Fortnow, Lance; Homer, Steven C) Khalil, Hatem; Ulery, Dana D) Mertens, Stephan
A) Sanjeev Arora B) Christos Papadimitriou C) Michael Sipser D) Boaz Barak
A) Oded Goldreich B) Christos Papadimitriou C) Sanjeev Arora; Boaz Barak D) Michael R. Garey; David S. Johnson
A) Christos Papadimitriou B) Oded Goldreich C) Michael R. Garey; David S. Johnson D) Sanjeev Arora; Boaz Barak |