A) Entwicklung neuer Programmiersprachen B) Analyse der für die Lösung von Rechenaufgaben erforderlichen Ressourcen C) Psychologische Aspekte der Mensch-Computer-Interaktion D) Hardware-Design für Computer
A) Römische Ziffern B) Griechische Buchstaben C) Binärer Code D) Big-O-Notation
A) NP B) PSPACE C) EXP D) BPP
A) Klassifizierung von Rechenproblemen auf der Grundlage ihrer inhärenten Schwierigkeit B) Schnellere Computer schaffen C) So erzeugen Sie Zufallszahlen D) Supercomputer bauen
A) BPP B) NP-komplett C) P D) EXPTIME
A) EXPSPACE B) PSPACE C) BQP D) NP-komplett
A) Experte B) Sondierung C) Exponentiale Zeit D) Erweitert
A) Quantenalgorithmen B) NP-Vollständigkeit C) P vs. NP Problem D) Paralleles Rechnen
A) Ein Hardwareproblem bei Computern. B) Eine mathematische Gleichung, die nicht lösbar ist. C) Eine Aufgabe, die von einem Computer mithilfe eines Algorithmus gelöst wird. D) Eine unlösbare theoretische Frage.
A) Das hexadezimale Alphabet B) Die Menge aller ASCII-Zeichen C) Die Menge aller Kleinbuchstaben D) Das binäre Alphabet {0, 1}
A) Keine Kodierung erforderlich B) Kodierung unter Verwendung natürlicher Sprache C) Eine konkrete Wahl der Eingabekodierung D) Verwendung der Dezimalnotation
A) Den kürzesten Pfad in einem Graphen finden. B) Die Anzahl der Knoten in einem Graphen bestimmen. C) Feststellen, ob ein gegebener Graph zusammenhängend ist oder nicht. D) Den maximalen Fluss in einem Netzwerk berechnen.
A) Feststellen, ob eine Zahl eine Primzahl ist. B) Feststellen, ob zwei Graphen isomorph sind. C) Das Problem des Handlungsreisenden. D) Überprüfen, ob ein Graph bipartit ist.
A) Bits B) Zeichen C) Bytes D) Wörter
A) Eine frühe Form von Computerhardware. B) Ein Gerät zur Manipulation von physikalischen Objekten. C) Ein theoretisches Modell für allgemeine Berechnungen. D) Eine praktische Technologie für das Rechnen.
A) Der Cook-Levin-Theorem. B) Das P-vs-NP-Theorem. C) Gödels Unvollständigkeitssätze. D) Die Church-Turing-These.
A) Quanten-Turing-Maschine. B) Nicht-deterministische Turing-Maschine. C) Wahrscheinlichkeits-Turing-Maschine. D) Deterministische Turing-Maschine.
A) Sie erfordern eine physikalische Realisierbarkeit. B) Sie verwenden Zufallsbits für Berechnungen. C) Sie sind auf polynomiale Zeit beschränkt. D) Sie arbeiten deterministisch.
A) Cook-Levin-Theorem B) Axiome im Zusammenhang mit der Frage P vs. NP C) Komplexitätsaxiome nach Blum D) Axiome für Turing-Vollständigkeit
A) Kommunikationskomplexität B) Schaltungs-Komplexität C) Komplexität der Quantenverschränkung D) Komplexität von Entscheidungsbäumen
A) Kommunikationskomplexität B) Speicherkomplexität C) Zeitkomplexität D) Schaltkreiskomplexität
A) PP B) co-NP C) NP D) BQP
A) Boris Trakhtenbrot B) John Myhill C) Raymond Smullyan D) Hisao Yamada
A) QMA B) RP C) AC D) BPP
A) 1936 B) 1945 C) 1965 D) 1950
A) Gabriel Lamé B) Richard E. Stearns C) Juris Hartmanis D) Alan Turing
A) Downey, Rod; Fellows, Michael B) Wuppuluri, Shyam; Doria, Francisco A. C) Cook, Stephen; Fortnow, Lance D) Papadimitriou, Christos; Sipser, Michael
A) ALLE B) EXPTIME C) NP D) P
A) Linear beschränkte Automaten B) Grundlegende Mengenlehre C) Komplexitätsmaße D) Echtzeitberechnungen
A) Zeit-Hierarchie-Theorem B) Savitchs Theorem C) Cook-Levin-Theorem D) Das P-gegen-NP-Problem
A) Probabilistische Algorithmen. B) Zustandsautomaten. C) Kontinuierliche dynamische Systeme und Differentialgleichungen. D) Digitale Signalverarbeitung.
A) Zeit-Hierarchie-Theorem B) Raumhierarchie-Theorem C) Savitchs Theorem D) Cook-Levin-Theorem
A) Oded Goldreich B) Christos Papadimitriou C) Sanjeev Arora; Boaz Barak 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
A) Arora, Sanjeev; Barak, Boaz B) Garey, Michael R.; Johnson, David S. C) Wuppuluri, Shyam; Doria, Francisco A. D) Downey, Rod; Fellows, Michael
A) PSPACE B) NP C) FP D) EXPTIME
A) co-P wäre nicht gleich co-NP. B) P wäre nicht gleich NP. C) NP wäre nicht gleich co-NP. D) co-P wäre gleich co-NP.
A) Hisao Yamada B) John Myhill C) Raymond Smullyan D) Boris Trakhtenbrot
A) 1972 B) 1971 C) 1965 D) 1967
A) Khalil, Hatem; Ulery, Dana B) Cook, Stephen C) Mertens, Stephan D) Fortnow, Lance; Homer, Steven
A) PP B) BQP C) MA D) PH
A) PP B) NL C) NC D) L
A) QMA B) BPP C) NC D) IP
A) 1956 B) 1955 C) 1960 D) 1971
A) 21 B) 15 C) 30 D) 10
A) Gabriel Lamé B) Edmonds C) Juris Hartmanis D) Leonid Levin
A) BPP B) NC C) QMA D) AC
A) „Rechenkomplexität“ B) „Polynomielle Zeit“ C) „Turing-Maschine“ D) „Signalfunktion“
A) Reduktion mit exponentieller Laufzeit. B) Reduktion mit polynomialer Laufzeit. C) Reduktion mit linearer Laufzeit. D) Reduktion mit logarithmischer Laufzeit.
A) Christos Papadimitriou B) Sanjeev Arora C) Michael Sipser D) Boaz Barak
A) Boolesche Ausdrücke. B) Diskrete Graphen. C) Stetige Funktionen. D) Quantenzustände.
A) Komplexität im besten Fall B) Komplexität im schlechtesten Fall C) Amortisierte Analyse D) Komplexität im Durchschnittsfall
A) #P B) BPP C) RP D) NC |