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