Welche der folgenden Aussagen zur Entscheidbarkeit beziehungsweise Unentscheidbarkeit ist richtig?
Keine der Aussagen.
Eine Menge oder ihr Komplement sind rekursiv aufzählbar.
Das Zugehörigkeitsproblem (MP) einer Turingmaschine ist entscheidbar.
Wenn A rekursiv ist, dann ist ∼A nicht rekursiv aufzählbar
Es gibt eine rekursiv aufzählbare Menge, die nicht rekursiv ist.
Welche der folgenden Aussagen zu Turingmaschinen und regulären Sprachen ist richtig?
Um eine nichtdeterministische Turingmaschine in eine deterministische umzuwandeln, wenden wir die Teilmengenkonstruktion an.
Bei einer Turingmaschine, die einen DEA simuliert, bewegen sich die Leseköpfe immer in unterschiedliche Richtungen.
Die Klasse der Sprachen, die von einer 1-Band-Turingmaschine akzeptiert werden, ist echt kleiner als die Klasse der Sprachen, die von einer 3-Band-Turingmaschine akzeptiert werden.
Jeder ϵ-NEA kann in eine deterministische Turingmaschine umgewandelt werden.
Welches der folgenden Gesetze über reguläre Ausdrücke gilt im Allgemeinen nicht? (Hierbei bezeichnen D, E, F reguläre Ausdrücke und wir schreiben abkürzend E ≡ F, wenn L(E) = L(F).)
E∅ ≡ ∅
(ϵ)* ≡ ϵ
((E + F)D) ≡ (ED + F D)
(F(DE)) ≡ ((F D)E)
(E + F) ≡ (F + E)
(D(E + F)) ≡ (DE + F D)
Welche der folgenden Sprachen (über dem Alphabet {a, b}) ist regulär?
Keine der angeführten Sprachen.
{a^i b^j | i > 0, j > 0, i != j}
{w | w ∈ L(a*) und die Länge von w ist eine Primzahl}
{w | w ∈ L((a*b*)*) und w enth¨alt ungleich viele a’s wie b’s}
{a^n b^n | n >= 1}
{x | x enthält eine gerade Anzahl von a’s und eine ungerade Anzahl von b’s}
Wozu dient der chinesische Restsatz?
zur Lösung keines der angeführten Berechnungsprobleme
zum schnellen Potenzieren von Restklassen
zum Ziehen von Quadratwurzeln aus Restklassen
zum Invertieren von Restklassen
zum Lösen eines Kongruenzensystems
Seien f: M → N und g: N → M injektive Abbildungen. Was besagt der Satz von Bernstein?
keine der angeführten Aussagen
Die Hintereinanderausführung von g nach f ist injektiv.
Die Hintereinanderausführung von f nach g ist injektiv.
Die Hintereinanderausführung von g nach f ist bijektiv.
Die Hintereinanderausführung von f nach g ist bijektiv.
Es existiert eine bijektive Abbildung von M nach N.
Angenommen die Wahrscheinlichkeit für ein EM-Team ein Spiel zu gewinnen liegt bei 1/4. Was ist die Wahrscheinlichkeit, dass dieses Team alle Spiele in der Vorrunde (=drei Spiele) verliert.
1/64
3/64
9/64
18/64
27/64
keine der angeführten Zahlen
Ein Computer verarbeitet Jobs einen nach dem anderen. Wieviele Möglichkeiten gibt es, die Reihenfolge von sieben Jobs festzulegen?
1024
256
128
720
5040
Sei N mit der natürlichen Ordnung <= und N^2 mit der komponentenweisen Ordnung über <= versehen. Wieviele unmittelbare Vorgänger hat das Paar (2, 2) in N^2?
keine der angeführten Werte
0
9
8
1
2
Seien f und g Funktionen von natürlichen Zahlen, die positive reelle Werte annehmen. Welche der folgenden Aussagen ist äquivalent zur Aussage f ∈ o(g)?
lim inf n→∞ |f(n)|/|g(n)| = 0
lim sup n→∞ |f(n)|/|g(n)| = 0
lim inf n→∞ |f(n)|/|g(n)| > 0
lim sup n→∞ |f(n)|/|g(n)| < ∞
lim n→∞ |f(n)|/|g(n)| = 0
Welche der folgenden Aussagen zur Entscheidbarkeit beziehungsweise Unentscheidbarkeit ist falsch?
Wenn A und ∼A rekursiv aufzählbar sind, dann ist ∼A rekursiv.
Es existiert keine rekursive Menge, deren Komplement nicht rekursiv ist
Das Zugehörigkeitsproblem (MP) einer Turingmaschine ist unentscheidbar.
Das Halteproblem für ϵ-NEA ist entscheidbar.
Jede rekursiv aufzählbare Menge ist nicht rekursiv.
Die Teilmengenkonstruktion wandelt eine nichtdeterministische Turingmaschine in eine deterministische um.
Bei einer 3-Band Turingmaschine, die einen DEA simuliert, bewegen sich die Leseköpfe immer in unterschiedliche Richtungen.
Die Klasse der Sprachen, die von einer Mehrband-Turingmaschine akzeptiert werden, ist echt größer als die Klasse der Sprachen, die von einer 1-Band-Turingmaschine akzeptiert werden.
Jede Turingmaschine kann in einen äquivalenten ϵ-NEA umgewandelt werden.
(D + E)* ≡ (D*E*)*
(∅)* ≡ ϵ
((DE)F) ≡ (D(EF))
((D + E) + F) ≡ (D + (E + F))
(D + E)+ ≡ (D+E+)+
Welche der folgenden Sprachen ist nicht regulär?
{a^i b^j | i > 0, j > 0}
{x | x ist ein beliebiges Wort über {a, b} außer aa und aaa}
{x | x ∈ {0, 1}* enthält zumindest drei 1en}
(L(a*) ∩ L(ab*)) \ L(a(b + c)*d*)
{x$y | x, y ∈ {a, b}* and l(x) < l(y) <= 4711}
{x | x ist ein regulärer Ausdruck über {a, b}}
Sei x eine ganze Zahl. Wieviele Multiplikationen braucht man, um die Potenz x^63 zu berechnen, wenn man die Methode des schnellen Potenzierens verwendet?
6
5
32
12
11
62
10
Welcher der folgenden Algorithmen ist ein Divide-and-Conquer-Algorithmus?
keiner der angeführten Algorithmen
der Algorithmus von Kruskal
der Algorithmus von Floyd
der Algorithmus von Warshall
der erweiterte euklidische Algorithmus
der euklidische Algorithmus
der Merge-Sort-Algorithmus
Angenommen die Implementierung eines oft verwendeten Moduls ist fehlerhaft und mit einer Wahrscheinlichkeit von 20% gerät das Unterprogramm in einen kritischen Zustand, was auch die aufrufende Funktion beieinträchtigt. Was ist die Wahrscheinlicheit, dass das ganze Programm fehlerfrei läuft, auch wenn das Modul dreimal aufgerufen wird?
0,8%
3,2%
12,8%
60%
51,2%
Wieviele Funktionen f: {0, 1}^2 → {0, 1}^2 gibt es, die surjektiv aber nicht injektiv sind?
232
24
Welche der folgenden partiell geordneten Mengen ist nicht wohlfundiert?
keine der angeführten Mengen
die Menge der natürlichen Zahlen mit der Teilbarkeitsordnung
die Menge der natürlichen Zahlen mit der natürlichen Ordnung
die Menge der Paare natürlicher Zahlen mit der lexikographischen Ordnung
die Menge der binären Wörter mit der graduiert-lexikographischen Ordnung
die Menge der binären Wörter mit der lexikographischen Ordnung
Welche der folgenden Funktionen liegt in Ω(2n)?
keine der angeführten Funktionen
log n
n log n
n^2
n!
Welche der folgenden Aussagen zur Komplexitätstheorie ist falsch?
Keine der angeführten Aussagen.
Das Problem Maze is vollständig für die Klasse NLOGSPACE.
Jedes Problem in P kann durch einen Polynomzeit Verifikator gelöst werden.
Der Begriff der Vollständigkeit einer Klasse ist parametrisch in der angewandten Definition von Reduktion.
Es ist nicht bekannt, ob die Komplexitätsklasse NP unter Komplement abgeschlossen ist.
Es gibt einen Algorithmus der das TSP Problem in Platz O(n^2) entscheidet.
Die Klasse NP ist genau die Klasse der Probleme, die Nicht in Polynomieller Zeit auf einer Turingmaschine gelöst werden können.
Welche der folgenden Berechnungsmodelle sind nicht äquivalent zu Turingmaschinen?
Keines der angegebenen Berechnungsmodellen.
Nichtdeterministische Turingmaschinen mit beliebig vielen Bändern.
Registermaschinen mit beliebig vielen Registern.
Turingmaschinen mit einem beidseitig unbeschränkten Band.
Turingmaschinen mit polynomiell beschränkten Bändern.
Welche der folgenden Aussagen über reguläre Ausdrücke gilt im Allgemeinen nicht? (Hierbei bezeichnen D, E, F reguläre Ausdrücke und wir schreiben abkürzend E ≡ F, wenn L(E) = L(F).)
(D(E + F)) ≡ (DF + DE)
D(D*) ≡ D+
(D*)* ≡ D*
(E*F*)* ≡ (E + F)*
(E + ϵ)F* ≡ EF* + F*
(E + F)*F ≡ (E*F)*
Welche der folgenden Aussagen zu regulären Sprachen ist richtig?
Jeder reguläre Ausdruck kann in einen DEA, nicht jedoch in einen ϵ-NEA umgewandelt werden.
Es gibt einen deterministischen Automaten A, sodass L(A) nicht durch einen regulären Ausdruck beschrieben werden kann.
Die regulären Sprachen sind unter Komplement und Schnitt, nicht aber unter Mengendifferenz abgeschlossen.
Die regulären Sprachen sind nur unter Komplement, Vereinigung, Schnitt und Mengendifferenz abgeschlossen.
Die regulären Sprachen sind (unter anderem) unter Komplement, Vereinigung, Schnitt und Mengendifferenz abgeschlossen.
Welche der folgenden Sprachen (über dem Alphabet {a, b, c}) kann durch einen regulären Ausdruck beschrieben werden?
{a^n b^m | wobei n <= m}
{c^n a^m | m = n + 3}
{a^n bbb c^n+1 | n keine Primzahl}
{a^n b^n | wobei n >= 7}
{b^n c^m a^n | wobei n >= 1, m >= 0 }
{a^n b^m c^k | wobei n, m >= 0, k >= 1}
Welche Komplexität hat der binäre euklidische Algorithmus für Zahlen mit n Binärziffern?
keine der angeführten Komplexitäten
Ω(n^3) Bitoperationen
Θ(n^2 log n) Bitoperationen
O(log n) Bitoperationen
O(n log n) Bitoperationen
O(n) Bitoperationen
O(n^2) Bitoperationen
Wieviele Äquivalenzrelationen gibt es auf einer Menge mit drei Elementen?
3
7
Sei G ein Baum mit n > 0 Ecken. Wieviele Kanten hat G?
keiner der angeführten Ausdrücke
(n + 1)^2
(n - 1)^2
n + 1
n
n - 1
Sei M eine Menge mit einer wohlfundierten partiellen Ordnung ≤ . Welche der folgenden Aussagen ist allgemein richtig?
Jedes Element von M hat nur endlich viele Nachfolger.
Jedes Element von M hat nur endlich viele Vorgänger
Jede nichtleere Teilmenge von M besitzt ein größtes Element.
Jede nichtleere Teilmenge von M besitzt ein kleinstes Element.
Jede nichtleere Teilmenge von M besitzt ein maximales Element.
Es gibt keine unendliche absteigende Kette in M.
Welche der folgenden Funktionen liegt in O(n log n)?
n√n
2^n/1001
n^2/1001
2n log n + 3
Welche der folgenden Aussagen zur Komplexitätstheorie ist richtig?
Für eine nichtdeterministiche TM ist der Speicherplatz als die Summe der gelesenen Bandzeichen definiert, die in allen möglichen Berechnungen gelesen wird.
Es gibt keinen Algorithmus der das TSP Problem in Zeit 2^O(n) entscheidet.
Die Komplexitätsklasse NP ist nicht unter Vereinigung abgeschlossen.
Angenommen wir können einen (deterministischen) Algorithmus angeben, der das Problem TSP in polynomieller Zeit löst, dann haben P != NP gezeigt.
Ein logarithmischer Umwandler ist eine deterministische TM mit einem Eingangsband, einem Arbeitsband, und einem Ausgabeband, sodass auf dem Arbeitsband maximal O(log n) viel Platz verbraucht werden darf, wobei n die Länge der Eingabe misst.
Wenn A rekursiv ist, dann ist ∼A nicht rekursiv aufzählbar.
Welche der folgenden Aussagen über reguläre Ausdrücke gilt? (Hierbei bezeichnen D, E, F beliebige reguläre Ausdrücke und wir schreiben abkürzend E ≡ F, wenn L(E) = L(F).)
(E + ϵ)F* ≡ EF+
ϵ + LL* ≡ L*Lϵ.
D + (E + F) ≡ (D + E)F
E∅ ≡ E
(E + ∅) ≡ (E + ϵ)
Welche der folgenden Sprachen (über dem Alphabet {0, 1}) kann durch einen regulären Ausdruck beschrieben werden?
{0^n 1^m | wobei n != m}
{1^n 0^m | wobei n < m}
{0^n 10^n+1 | n eine Primzahl}
{0^n 1^n | wobei n >= 0}
{0^n 1^n | wobei 10 <= n}
{0^n 0^n | wobei n >= 0}
Die entscheidende Eigenschaft eines ϵ-NEA A ist, dass A zählen kann.
Eine reguläre Sprache kann entweder von einem endlichen Automaten oder von einem regulären Ausdruck beschrieben werden, nicht jedoch von beidem.
Alle Programmiersprachen sind regulär.
Zu jeder reguläre Sprache L existiert ein eindeutiger und minimaler deterministischer endlicher Automat A, sodass L die Sprache von A ist.
Welche der folgenden Restklassen modulo 119 ist nicht invertierbar?
keine der angeführten Restklassen
118
36
55
37
102
Welche der folgenden Mengen ist nicht abzählbar?
N^n
Z
Q
{0, 1}*
{0, 1}^N
Wieviele Möglichkeiten gibt es, die symbolischen Zustände A, B, C, D eines endlichen Automaten durch Bitpaare zu codieren, sodass verschiedene Zustände auch verschiedene Bitpaare bekommen?
64
16
Sei M eine endliche Menge mit einer partiellen Ordnung ≤. Welche der folgenden Aussagen ist allgemein richtig?
Für zwei Elemente x und y von M gilt x ≤ y oder y ≤ x.
Jede Teilmenge von M besitzt ein größtes Element.
Jede Teilmenge von M besitzt ein maximales Element.
Seien f und g Funktionen von natürlichen Zahlen, die positive reelle Werte annehmen. Welche der folgenden Aussagen ist äquivalent zur Aussage f ∈ O(g)?
lim n→∞ |f(n)| / |g(n)| = 0
lim inf n→∞ |f(n)| / |g(n)| = 0
lim sup n→∞ |f(n)| / |g(n)| = 0
lim inf n→∞ |f(n)| / |g(n)| > 0
lim sup n→∞ |f(n)| / |g(n)| < ∞
