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