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