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