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