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