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