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