Christopher Kranebitter
Test por , creado hace más de 1 año

Informatik Test sobre Diskrete Mathematik Multiple Choice, creado por Christopher Kranebitter el 23/06/2017.

131
1
0
Christopher Kranebitter
Creado por Christopher Kranebitter hace más de 7 años
Cerrar

Diskrete Mathematik Multiple Choice

Pregunta 1 de 40

1

Welche der folgenden Aussagen zur Entscheidbarkeit beziehungsweise Unentscheidbarkeit
ist richtig?

Selecciona una de las siguientes respuestas posibles:

  • 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.

Explicación

Pregunta 2 de 40

1

Welche der folgenden Aussagen zu Turingmaschinen und regulären Sprachen ist
richtig?

Selecciona una de las siguientes respuestas posibles:

  • Keine der Aussagen.

  • 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.

Explicación

Pregunta 3 de 40

1

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).)

Selecciona una de las siguientes respuestas posibles:

  • E∅ ≡ ∅

  • (ϵ)* ≡ ϵ

  • ((E + F)D) ≡ (ED + F D)

  • (F(DE)) ≡ ((F D)E)

  • (E + F) ≡ (F + E)

  • (D(E + F)) ≡ (DE + F D)

Explicación

Pregunta 4 de 40

1

Welche der folgenden Sprachen (über dem Alphabet {a, b}) ist regulär?

Selecciona una de las siguientes respuestas posibles:

  • 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}

Explicación

Pregunta 5 de 40

1

Wozu dient der chinesische Restsatz?

Selecciona una de las siguientes respuestas posibles:

  • 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

Explicación

Pregunta 6 de 40

1

Seien f: M → N und g: N → M injektive Abbildungen. Was besagt der Satz von Bernstein?

Selecciona una de las siguientes respuestas posibles:

  • 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.

Explicación

Pregunta 7 de 40

1

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.

Selecciona una de las siguientes respuestas posibles:

  • 1/64

  • 3/64

  • 9/64

  • 18/64

  • 27/64

  • keine der angeführten Zahlen

Explicación

Pregunta 8 de 40

1

Ein Computer verarbeitet Jobs einen nach dem anderen. Wieviele Möglichkeiten gibt es, die Reihenfolge von sieben Jobs festzulegen?

Selecciona una de las siguientes respuestas posibles:

  • keine der angeführten Zahlen

  • 1024

  • 256

  • 128

  • 720

  • 5040

Explicación

Pregunta 9 de 40

1

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?

Selecciona una de las siguientes respuestas posibles:

  • keine der angeführten Werte

  • 0

  • 9

  • 8

  • 1

  • 2

Explicación

Pregunta 10 de 40

1

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)?

Selecciona una de las siguientes respuestas posibles:

  • keine der angeführten Aussagen

  • 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

Explicación

Pregunta 11 de 40

1

Welche der folgenden Aussagen zur Entscheidbarkeit beziehungsweise Unentscheidbarkeit
ist falsch?

Selecciona una de las siguientes respuestas posibles:

  • 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.

Explicación

Pregunta 12 de 40

1

Welche der folgenden Aussagen zu Turingmaschinen und regulären Sprachen ist richtig?

Selecciona una de las siguientes respuestas posibles:

  • 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.

  • Keine der Aussagen.

Explicación

Pregunta 13 de 40

1

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).)

Selecciona una de las siguientes respuestas posibles:

  • (D + E)* ≡ (D*E*)*

  • (∅)* ≡ ϵ

  • ((E + F)D) ≡ (ED + F D)

  • ((DE)F) ≡ (D(EF))

  • ((D + E) + F) ≡ (D + (E + F))

  • (D + E)+ ≡ (D+E+)+

Explicación

Pregunta 14 de 40

1

Welche der folgenden Sprachen ist nicht regulär?

Selecciona una de las siguientes respuestas posibles:

  • {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}}

Explicación

Pregunta 15 de 40

1

Sei x eine ganze Zahl. Wieviele Multiplikationen braucht man, um die Potenz x^63 zu berechnen, wenn man die Methode des schnellen Potenzierens verwendet?

Selecciona una de las siguientes respuestas posibles:

  • keine der angeführten Zahlen

  • 6

  • 5

  • 32

  • 12

  • 11

  • 62

  • 10

Explicación

Pregunta 16 de 40

1

Welcher der folgenden Algorithmen ist ein Divide-and-Conquer-Algorithmus?

Selecciona una de las siguientes respuestas posibles:

  • 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

Explicación

Pregunta 17 de 40

1

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?

Selecciona una de las siguientes respuestas posibles:

  • keine der angeführten Zahlen

  • 0,8%

  • 3,2%

  • 12,8%

  • 60%

  • 51,2%

Explicación

Pregunta 18 de 40

1

Wieviele Funktionen f: {0, 1}^2 → {0, 1}^2 gibt es, die surjektiv aber nicht injektiv sind?

Selecciona una de las siguientes respuestas posibles:

  • keine der angeführten Zahlen

  • 232

  • 256

  • 24

  • 0

Explicación

Pregunta 19 de 40

1

Welche der folgenden partiell geordneten Mengen ist nicht wohlfundiert?

Selecciona una de las siguientes respuestas posibles:

  • 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

Explicación

Pregunta 20 de 40

1

Welche der folgenden Funktionen liegt in Ω(2n)?

Selecciona una de las siguientes respuestas posibles:

  • keine der angeführten Funktionen

  • log n

  • n log n

  • n^2

  • n!

Explicación

Pregunta 21 de 40

1

Welche der folgenden Aussagen zur Komplexitätstheorie ist falsch?

Selecciona una de las siguientes respuestas posibles:

  • 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.

Explicación

Pregunta 22 de 40

1

Welche der folgenden Berechnungsmodelle sind nicht äquivalent zu Turingmaschinen?

Selecciona una de las siguientes respuestas posibles:

  • 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.

Explicación

Pregunta 23 de 40

1

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).)

Selecciona una de las siguientes respuestas posibles:

  • (D(E + F)) ≡ (DF + DE)

  • D(D*) ≡ D+

  • (D*)* ≡ D*

  • (E*F*)* ≡ (E + F)*

  • (E + ϵ)F* ≡ EF* + F*

  • (E + F)*F ≡ (E*F)*

Explicación

Pregunta 24 de 40

1

Welche der folgenden Aussagen zu regulären Sprachen ist richtig?

Selecciona una de las siguientes respuestas posibles:

  • Keine der Aussagen.

  • 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.

Explicación

Pregunta 25 de 40

1

Welche der folgenden Sprachen (über dem Alphabet {a, b, c}) kann durch einen
regulären Ausdruck beschrieben werden?

Selecciona una de las siguientes respuestas posibles:

  • {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}

Explicación

Pregunta 26 de 40

1

Welche Komplexität hat der binäre euklidische Algorithmus für Zahlen mit n Binärziffern?

Selecciona una de las siguientes respuestas posibles:

  • 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

Explicación

Pregunta 27 de 40

1

Wieviele Äquivalenzrelationen gibt es auf einer Menge mit drei Elementen?

Selecciona una de las siguientes respuestas posibles:

  • keine der angeführten Zahlen

  • 12

  • 8

  • 3

  • 7

  • 5

Explicación

Pregunta 28 de 40

1

Sei G ein Baum mit n > 0 Ecken. Wieviele Kanten hat G?

Selecciona una de las siguientes respuestas posibles:

  • keiner der angeführten Ausdrücke

  • (n + 1)^2

  • (n - 1)^2

  • n^2

  • n + 1

  • n

  • n - 1

Explicación

Pregunta 29 de 40

1

Sei M eine Menge mit einer wohlfundierten partiellen Ordnung ≤ . Welche der folgenden Aussagen ist allgemein richtig?

Selecciona una de las siguientes respuestas posibles:

  • keine der angeführten Aussagen

  • 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.

Explicación

Pregunta 30 de 40

1

Welche der folgenden Funktionen liegt in O(n log n)?

Selecciona una de las siguientes respuestas posibles:

  • keine der angeführten Funktionen

  • n!

  • n√n

  • 2^n/1001

  • n^2/1001

  • 2n log n + 3

Explicación

Pregunta 31 de 40

1

Welche der folgenden Aussagen zur Komplexitätstheorie ist richtig?

Selecciona una de las siguientes respuestas posibles:

  • Keine der angeführten Aussagen.

  • 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.

Explicación

Pregunta 32 de 40

1

Welche der folgenden Aussagen zur Entscheidbarkeit beziehungsweise Unentscheidbarkeit
ist richtig?

Selecciona una de las siguientes respuestas posibles:

  • 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.

Explicación

Pregunta 33 de 40

1

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).)

Selecciona una de las siguientes respuestas posibles:

  • (E + ϵ)F* ≡ EF+

  • ϵ + LL* ≡ L*Lϵ.

  • D + (E + F) ≡ (D + E)F

  • E∅ ≡ E

  • (E + ∅) ≡ (E + ϵ)

  • (∅)* ≡ ϵ

Explicación

Pregunta 34 de 40

1

Welche der folgenden Sprachen (über dem Alphabet {0, 1}) kann durch einen regulären Ausdruck beschrieben werden?

Selecciona una de las siguientes respuestas posibles:

  • {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}

Explicación

Pregunta 35 de 40

1

Welche der folgenden Aussagen zu regulären Sprachen ist richtig?

Selecciona una de las siguientes respuestas posibles:

  • Keine der angeführten Aussagen.

  • 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.

Explicación

Pregunta 36 de 40

1

Welche der folgenden Restklassen modulo 119 ist nicht invertierbar?

Selecciona una de las siguientes respuestas posibles:

  • keine der angeführten Restklassen

  • 118

  • 36

  • 55

  • 37

  • 102

Explicación

Pregunta 37 de 40

1

Welche der folgenden Mengen ist nicht abzählbar?

Selecciona una de las siguientes respuestas posibles:

  • keine der angeführten Mengen

  • N^n

  • Z

  • Q

  • {0, 1}*

  • {0, 1}^N

Explicación

Pregunta 38 de 40

1

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?

Selecciona una de las siguientes respuestas posibles:

  • keine der angeführten Zahlen

  • 64

  • 16

  • 256

  • 128

  • 32

  • 24

Explicación

Pregunta 39 de 40

1

Sei M eine endliche Menge mit einer partiellen Ordnung ≤. Welche der folgenden Aussagen ist allgemein richtig?

Selecciona una de las siguientes respuestas posibles:

  • keine der angeführten Aussagen

  • 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 nichtleere Teilmenge von M besitzt ein größtes Element.

  • Jede Teilmenge von M besitzt ein maximales Element.

  • Jede nichtleere Teilmenge von M besitzt ein maximales Element.

Explicación

Pregunta 40 de 40

1

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)?

Selecciona una de las siguientes respuestas posibles:

  • keine der angeführten Aussagen

  • 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)| < ∞

Explicación

Anterior
Siguiente