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