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