Quiz
Diskrete Mathematik Multiple Choice
Questions in this quiz (40)
1Welche der folgenden Aussagen zur Entscheidbarkeit beziehungsweise Unentscheidbarkeit
ist richtig?- AKeine der Aussagen.
- BEine Menge oder ihr Komplement sind rekursiv aufzählbar.
- CDas Zugehörigkeitsproblem (MP) einer Turingmaschine ist entscheidbar.
- DWenn A rekursiv ist, dann ist ∼A nicht rekursiv aufzählbar
- EEs gibt eine rekursiv aufzählbare Menge, die nicht rekursiv ist.
2Welche der folgenden Aussagen zu Turingmaschinen und regulären Sprachen ist
richtig?- AKeine der Aussagen.
- BUm eine nichtdeterministische Turingmaschine in eine deterministische umzuwandeln, wenden wir die Teilmengenkonstruktion an.
- CBei einer Turingmaschine, die einen DEA simuliert, bewegen sich die Leseköpfe immer in unterschiedliche Richtungen.
- DDie 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.
- EJeder ϵ-NEA kann in eine deterministische Turingmaschine umgewandelt werden.
3Welches 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).)
- AE∅ ≡ ∅
- B(ϵ)* ≡ ϵ
- C((E + F)D) ≡ (ED + F D)
- D(F(DE)) ≡ ((F D)E)
- E(E + F) ≡ (F + E)
- F(D(E + F)) ≡ (DE + F D)
4Welche der folgenden Sprachen (über dem Alphabet {a, b}) ist regulär?
- AKeine der angeführten Sprachen.
- B{a^i b^j | i > 0, j > 0, i != j}
- C{w | w ∈ L(a*) und die Länge von w ist eine Primzahl}
- D{w | w ∈ L((a*b*)*) und w enth¨alt ungleich viele a’s wie b’s}
- E{a^n b^n | n >= 1}
- F{x | x enthält eine gerade Anzahl von a’s und eine ungerade Anzahl von b’s}
5Wozu dient der chinesische Restsatz?
- Azur Lösung keines der angeführten Berechnungsprobleme
- Bzum schnellen Potenzieren von Restklassen
- Czum Ziehen von Quadratwurzeln aus Restklassen
- Dzum Invertieren von Restklassen
- Ezum Lösen eines Kongruenzensystems
6Seien f: M → N und g: N → M injektive Abbildungen. Was besagt der Satz von Bernstein?
- Akeine der angeführten Aussagen
- BDie Hintereinanderausführung von g nach f ist injektiv.
- CDie Hintereinanderausführung von f nach g ist injektiv.
- DDie Hintereinanderausführung von g nach f ist bijektiv.
- EDie Hintereinanderausführung von f nach g ist bijektiv.
- FEs existiert eine bijektive Abbildung von M nach N.
7Angenommen 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.
- A1/64
- B3/64
- C9/64
- D18/64
- E27/64
- Fkeine der angeführten Zahlen
8Ein Computer verarbeitet Jobs einen nach dem anderen. Wieviele Möglichkeiten gibt es, die Reihenfolge von sieben Jobs festzulegen?
- Akeine der angeführten Zahlen
- B1024
- C256
- D128
- E720
- F5040
9Sei 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?
- Akeine der angeführten Werte
- B0
- C9
- D8
- E1
- F2
10Seien f und g Funktionen von natürlichen Zahlen, die positive reelle Werte annehmen.
Welche der folgenden Aussagen ist äquivalent zur Aussage f ∈ o(g)?- Akeine der angeführten Aussagen
- Blim inf n→∞ |f(n)|/|g(n)| = 0
- Clim sup n→∞ |f(n)|/|g(n)| = 0
- Dlim inf n→∞ |f(n)|/|g(n)| > 0
- Elim sup n→∞ |f(n)|/|g(n)| < ∞
- Flim n→∞ |f(n)|/|g(n)| = 0
11Welche der folgenden Aussagen zur Entscheidbarkeit beziehungsweise Unentscheidbarkeit
ist falsch?- AWenn A und ∼A rekursiv aufzählbar sind, dann ist ∼A rekursiv.
- BEs existiert keine rekursive Menge, deren Komplement nicht rekursiv ist
- CDas Zugehörigkeitsproblem (MP) einer Turingmaschine ist unentscheidbar.
- DDas Halteproblem für ϵ-NEA ist entscheidbar.
- EJede rekursiv aufzählbare Menge ist nicht rekursiv.
12Welche der folgenden Aussagen zu Turingmaschinen und regulären Sprachen ist richtig?
- ADie Teilmengenkonstruktion wandelt eine nichtdeterministische Turingmaschine in
eine deterministische um. - BBei einer 3-Band Turingmaschine, die einen DEA simuliert, bewegen sich die Leseköpfe
immer in unterschiedliche Richtungen. - CDie 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. - DJede Turingmaschine kann in einen äquivalenten ϵ-NEA umgewandelt werden.
- EKeine der Aussagen.
- ADie Teilmengenkonstruktion wandelt eine nichtdeterministische Turingmaschine in
13Welches 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).)
- A(D + E)* ≡ (D*E*)*
- B(∅)* ≡ ϵ
- C((E + F)D) ≡ (ED + F D)
- D((DE)F) ≡ (D(EF))
- E((D + E) + F) ≡ (D + (E + F))
- F(D + E)+ ≡ (D+E+)+
14Welche der folgenden Sprachen ist nicht regulär?
- A{a^i b^j | i > 0, j > 0}
- B{x | x ist ein beliebiges Wort über {a, b} außer aa und aaa}
- C{x | x ∈ {0, 1}* enthält zumindest drei 1en}
- D(L(a*) ∩ L(ab*)) \ L(a(b + c)*d*)
- E{x$y | x, y ∈ {a, b}* and l(x) < l(y) <= 4711}
- F{x | x ist ein regulärer Ausdruck über {a, b}}
15Sei x eine ganze Zahl. Wieviele Multiplikationen braucht man, um die Potenz x^63 zu berechnen, wenn man die Methode des schnellen Potenzierens verwendet?
- Akeine der angeführten Zahlen
- B6
- C5
- D32
- E12
- F11
- G62
- H10
16Welcher der folgenden Algorithmen ist ein Divide-and-Conquer-Algorithmus?
- Akeiner der angeführten Algorithmen
- Bder Algorithmus von Kruskal
- Cder Algorithmus von Floyd
- Dder Algorithmus von Warshall
- Eder erweiterte euklidische Algorithmus
- Fder euklidische Algorithmus
- Gder Merge-Sort-Algorithmus
17Angenommen 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?- Akeine der angeführten Zahlen
- B0,8%
- C3,2%
- D12,8%
- E60%
- F51,2%
18Wieviele Funktionen f: {0, 1}^2 → {0, 1}^2 gibt es, die surjektiv aber nicht injektiv sind?
- Akeine der angeführten Zahlen
- B232
- C256
- D24
- E0
19Welche der folgenden partiell geordneten Mengen ist nicht wohlfundiert?
- Akeine der angeführten Mengen
- Bdie Menge der natürlichen Zahlen mit der Teilbarkeitsordnung
- Cdie Menge der natürlichen Zahlen mit der natürlichen Ordnung
- Ddie Menge der Paare natürlicher Zahlen mit der lexikographischen Ordnung
- Edie Menge der binären Wörter mit der graduiert-lexikographischen Ordnung
- Fdie Menge der binären Wörter mit der lexikographischen Ordnung
20Welche der folgenden Funktionen liegt in Ω(2n)?
- Akeine der angeführten Funktionen
- Blog n
- Cn log n
- Dn^2
- En!
21Welche der folgenden Aussagen zur Komplexitätstheorie ist falsch?
- AKeine der angeführten Aussagen.
- BDas Problem Maze is vollständig für die Klasse NLOGSPACE.
- CJedes Problem in P kann durch einen Polynomzeit Verifikator gelöst werden.
- DDer Begriff der Vollständigkeit einer Klasse ist parametrisch in der angewandten
Definition von Reduktion. - EEs ist nicht bekannt, ob die Komplexitätsklasse NP unter Komplement abgeschlossen
ist. - FEs gibt einen Algorithmus der das TSP Problem in Platz O(n^2) entscheidet.
- GDie Klasse NP ist genau die Klasse der Probleme, die Nicht in Polynomieller Zeit
auf einer Turingmaschine gelöst werden können.
22Welche der folgenden Berechnungsmodelle sind nicht äquivalent zu Turingmaschinen?
- AKeines der angegebenen Berechnungsmodellen.
- BNichtdeterministische Turingmaschinen mit beliebig vielen Bändern.
- CRegistermaschinen mit beliebig vielen Registern.
- DTuringmaschinen mit einem beidseitig unbeschränkten Band.
- ETuringmaschinen mit polynomiell beschränkten Bändern.
23Welche 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).)
- A(D(E + F)) ≡ (DF + DE)
- BD(D*) ≡ D+
- C(D*)* ≡ D*
- D(E*F*)* ≡ (E + F)*
- E(E + ϵ)F* ≡ EF* + F*
- F(E + F)*F ≡ (E*F)*
24Welche der folgenden Aussagen zu regulären Sprachen ist richtig?
- AKeine der Aussagen.
- BJeder reguläre Ausdruck kann in einen DEA, nicht jedoch in einen ϵ-NEA umgewandelt werden.
- CEs gibt einen deterministischen Automaten A, sodass L(A) nicht durch einen
regulären Ausdruck beschrieben werden kann. - DDie regulären Sprachen sind unter Komplement und Schnitt, nicht aber unter Mengendifferenz
abgeschlossen. - EDie regulären Sprachen sind nur unter Komplement, Vereinigung, Schnitt und Mengendifferenz
abgeschlossen. - FDie regulären Sprachen sind (unter anderem) unter Komplement, Vereinigung,
Schnitt und Mengendifferenz abgeschlossen.
25Welche der folgenden Sprachen (über dem Alphabet {a, b, c}) kann durch einen
regulären Ausdruck beschrieben werden?- A{a^n b^m | wobei n <= m}
- B{c^n a^m | m = n + 3}
- C{a^n bbb c^n+1 | n keine Primzahl}
- D{a^n b^n | wobei n >= 7}
- E{b^n c^m a^n | wobei n >= 1, m >= 0 }
- F{a^n b^m c^k | wobei n, m >= 0, k >= 1}
26Welche Komplexität hat der binäre euklidische Algorithmus für Zahlen mit n Binärziffern?
- Akeine der angeführten Komplexitäten
- BΩ(n^3) Bitoperationen
- CΘ(n^2 log n) Bitoperationen
- DO(log n) Bitoperationen
- EO(n log n) Bitoperationen
- FO(n) Bitoperationen
- GO(n^2) Bitoperationen
27Wieviele Äquivalenzrelationen gibt es auf einer Menge mit drei Elementen?
- Akeine der angeführten Zahlen
- B12
- C8
- D3
- E7
- F5
28Sei G ein Baum mit n > 0 Ecken. Wieviele Kanten hat G?
- Akeiner der angeführten Ausdrücke
- B(n + 1)^2
- C(n - 1)^2
- Dn^2
- En + 1
- Fn
- Gn - 1
29Sei M eine Menge mit einer wohlfundierten partiellen Ordnung ≤ . Welche der folgenden Aussagen ist allgemein richtig?
- Akeine der angeführten Aussagen
- BJedes Element von M hat nur endlich viele Nachfolger.
- CJedes Element von M hat nur endlich viele Vorgänger
- DJede nichtleere Teilmenge von M besitzt ein größtes Element.
- EJede nichtleere Teilmenge von M besitzt ein kleinstes Element.
- FJede nichtleere Teilmenge von M besitzt ein maximales Element.
- GEs gibt keine unendliche absteigende Kette in M.
30Welche der folgenden Funktionen liegt in O(n log n)?
- Akeine der angeführten Funktionen
- Bn!
- Cn√n
- D2^n/1001
- En^2/1001
- F2n log n + 3
31Welche der folgenden Aussagen zur Komplexitätstheorie ist richtig?
- AKeine der angeführten Aussagen.
- BFür eine nichtdeterministiche TM ist der Speicherplatz als die Summe der gelesenen Bandzeichen definiert, die in allen möglichen Berechnungen gelesen wird.
- CEs gibt keinen Algorithmus der das TSP Problem in Zeit 2^O(n) entscheidet.
- DDie Komplexitätsklasse NP ist nicht unter Vereinigung abgeschlossen.
- EAngenommen wir können einen (deterministischen) Algorithmus angeben, der das Problem TSP in polynomieller Zeit löst, dann haben P != NP gezeigt.
- FEin 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.
32Welche der folgenden Aussagen zur Entscheidbarkeit beziehungsweise Unentscheidbarkeit
ist richtig?- AKeine der Aussagen.
- BEine Menge oder ihr Komplement sind rekursiv aufzählbar.
- CDas Zugehörigkeitsproblem (MP) einer Turingmaschine ist entscheidbar.
- DWenn A rekursiv ist, dann ist ∼A nicht rekursiv aufzählbar.
- EEs gibt eine rekursiv aufzählbare Menge, die nicht rekursiv ist.
33Welche 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).)
- A(E + ϵ)F* ≡ EF+
- Bϵ + LL* ≡ L*Lϵ.
- CD + (E + F) ≡ (D + E)F
- DE∅ ≡ E
- E(E + ∅) ≡ (E + ϵ)
- F(∅)* ≡ ϵ
34Welche der folgenden Sprachen (über dem Alphabet {0, 1}) kann durch einen regulären Ausdruck beschrieben werden?
- A{0^n 1^m | wobei n != m}
- B{1^n 0^m | wobei n < m}
- C{0^n 10^n+1 | n eine Primzahl}
- D{0^n 1^n | wobei n >= 0}
- E{0^n 1^n | wobei 10 <= n}
- F{0^n 0^n | wobei n >= 0}
35Welche der folgenden Aussagen zu regulären Sprachen ist richtig?
- AKeine der angeführten Aussagen.
- BDie entscheidende Eigenschaft eines ϵ-NEA A ist, dass A zählen kann.
- CEine reguläre Sprache kann entweder von einem endlichen Automaten oder von
einem regulären Ausdruck beschrieben werden, nicht jedoch von beidem. - DAlle Programmiersprachen sind regulär.
- EZu jeder reguläre Sprache L existiert ein eindeutiger und minimaler deterministischer
endlicher Automat A, sodass L die Sprache von A ist.
36Welche der folgenden Restklassen modulo 119 ist nicht invertierbar?
- Akeine der angeführten Restklassen
- B118
- C36
- D55
- E37
- F102
37Welche der folgenden Mengen ist nicht abzählbar?
- Akeine der angeführten Mengen
- BN^n
- CZ
- DQ
- E{0, 1}*
- F{0, 1}^N
38Wieviele 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?- Akeine der angeführten Zahlen
- B64
- C16
- D256
- E128
- F32
- G24
39Sei M eine endliche Menge mit einer partiellen Ordnung ≤. Welche der folgenden Aussagen ist allgemein richtig?
- Akeine der angeführten Aussagen
- BFür zwei Elemente x und y von M gilt x ≤ y oder y ≤ x.
- CJede Teilmenge von M besitzt ein größtes Element.
- DJede nichtleere Teilmenge von M besitzt ein größtes Element.
- EJede Teilmenge von M besitzt ein maximales Element.
- FJede nichtleere Teilmenge von M besitzt ein maximales Element.
40Seien f und g Funktionen von natürlichen Zahlen, die positive reelle Werte annehmen. Welche der folgenden Aussagen ist äquivalent zur Aussage f ∈ O(g)?
- Akeine der angeführten Aussagen
- Blim n→∞ |f(n)| / |g(n)| = 0
- Clim inf n→∞ |f(n)| / |g(n)| = 0
- Dlim sup n→∞ |f(n)| / |g(n)| = 0
- Elim inf n→∞ |f(n)| / |g(n)| > 0
- Flim sup n→∞ |f(n)| / |g(n)| < ∞
Information
- Description
- Informatik Quiz on Diskrete Mathematik Multiple Choice, created by Christopher Kranebitter on 23/06/2017.
- Author
- Christopher Kranebitter
- Language
- Deutsch
- Views
- 145
- Tags
- Rating
- No ratings yet Rate this quiz