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