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