Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Einführung in die Theoretische Informatik > Einführung > Flashcards

Einführung Flashcards

1
Q

Was ist ein Alphabet?

A

Endliche, nicht-leere Menge an Objekten, genannt Symbole

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Was ist ein Argument?

A

Eine Eingabe einer Funktion

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Was ist eine binäre Relation?

A

Eine Relation dessen Urbildmenge eine Menge aus Paaren ist

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Was ist eine Bool’sche Operation?

A

Eine Operation auf bool’schen Werten

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Was ist ein Kartesisches Produkt?

A

Eine Operation auf Mengen die eine Menge aus allen Tupeln der Elemente der Mengen erzeugt

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Was ist ein Komplement?

A

Eine Operation auf eine Menge die eine Menge aus allen nicht vorhandenen Elementen erzeugt

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Was ist eine Konkatenation?

A

Eine Operation die Wörter aneinanderreiht

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Was ist eine Konjunktion?

A

Bool’sche UND Operation

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Was ist ein zusammenhängender Graph?

A

Ein Graph mit Pfaden die alle Knoten paarweise verbinden

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Was ist ein Zyklus?

A

Ein Pfad der im selben Knoten startet und endet

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Was ist ein gerichteter Graph?

A

Eine Sammlung von Punkten und Pfeilen die Paare von Punkten verbinden

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Was ist eine Disjunktion?

A

Bool’sche ODER Operation

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Was ist eine Urbildmenge?

A

Die Menge aller möglichen Eingaben einer Funktion

Auch: Quellmenge

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Was ist eine Kante?

A

Eine Linie in einem Graphen

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Was ist ein Element?

A

Ein Objekt in einer Menge

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Was ist eine Leere Menge?

A

Eine Menge ohne Elemente

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Was ist ein Leeres Wort?

A

Ein Wort mit der Länge null

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Was ist eine Äquivalenzrelation?

A

Eine binäre Relation die reflexiv, symmetrisch und transitiv ist

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Was ist eine Funktion?

A

Eine Operation die Eingaben in Ausgaben übersetzt

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Was ist ein Graph?

A

Eine Sammlung von Punkten und Linien die Paare von Punkten verbinden

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Was ist ein Schnitt?

A

Eine Operation auf Mengen die eine Menge aus allen gemeinsamen Elementen erzeugt

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

Was ist ein k-Tupel?

A

Eine Liste von k Objekten

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

Was ist eine Sprache?

A

Eine Menge an Wörtern

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

Was ist ein Element?

A

Ein Objekt in einer Menge (Duplikat)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

Was ist ein Knoten?

A

Ein Punkt in einem Graphen

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

Was ist ein geoordnetes Paar?

A

Eine Liste aus zwei Elementen

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

Was ist ein Pfad?

A

Eine Sequenz von Knoten in einem Graphen die durch Kanten verbunden sind

28
Q

Was ist ein Prädikat?

A

Eine Funktion mit dem Bildbereich {TRUE, FALSE}

29
Q

Was ist eine Eigenschaft?

A

Ein Prädikat

30
Q

Was ist ein Bildbereich?

A

Die Menge aus der die Ausgaben einer Funktion gewählt werden

31
Q

Was ist eine Relation?

A

Ein Prädikat, typischerweise wenn die Urbildmenge eine Menge an k-Tupeln ist

32
Q

Was ist eine Sequenz?

A

Eine Liste von Objekten

33
Q

Was ist eine Menge?

A

Eine Gruppe von Objekten

34
Q

Was ist ein einfacher Pfad?

A

Ein Pfad ohne Wiederholung

35
Q

Was ist eine Einelementige Menge?

A

Menge mit einem Element

36
Q

Was ist ein Wort?

A

Eine endliche Liste an Symbolen aus einem Alphabet

37
Q

Was ist ein Symbol?

A

Ein Element eines Alphabets

38
Q

Was ist ein Baum?

A

Ein zusammenhängender Graph ohne einfache Zyklen

39
Q

Was ist eine Vereinigung?

A

Eine Operation auf Mengen die alle Elemente in eine Menge kombiniert

40
Q

Was ist ein Ungeordnetes Paar?

A

Eine Menge mit zwei Elementen

41
Q

Was ist eine Ecke?

A

Ein Punkt in einem Graphen

42
Q

Wie ist ein Deterministischer endlicher Automat definiert?

A
43
Q

Wie ist eine erkannte (akzeptierte) Sprache definiert?

A
44
Q

Was bedeutet eine erfolgreiche Rechnung?

A

Im Kontext der Endlichen Automaten bedeutet eine erfolgreiche Rechnung das Akzeptieren von Wörtern.

45
Q

Wie ist eine reguläre Sprache definiert?

A

Eine Sprache heißt reguläre Sprache (auch reguläre Menge), wenn sie von einem endlichen Automaten erkannt wird.
Die Familie aller regulären Sprachen wird mit REG bezeichnet.

46
Q

Sei M ein DFA, was ist L(M)?

A

Eine Menge von Wörtern (die von M erkannte Sprache) und
außerdem ist L(M) ∈ REG

REG enthält also Mengen!

47
Q

Wann ist ein DFA vollständig?

A

jede Eingabe kann gelesen werden

48
Q

Wann ist ein DFA initial zusammenhängend?

A

jeder Zustand ist erreichbar

49
Q

Wie Zeigt man, dass ein Automat zu einer Sprache gehört und andersherum?

A
50
Q

Was ist damit gemeint?

A

Wie viele Zweien sind in dem Wort?
3

51
Q

Wie werden Sequenzen notiert?

A

Mit runden Klammern. Zum Beispiel:
(7, 21, 57)

52
Q

Ist die Reihenfolge bei Sequenzen wichtig?

A

Ja, anders als bei Mengen

53
Q

Sind Wiederholungen bei Sequenzen von Interesse?

A

Ja, anders als bei Mengen

54
Q

Wie werden endliche Sequenzen genannt?

A

Tupel

55
Q

Wie wird die Menge der möglichen Eingaben für eine Funktion genannt?

A

Urbildmenge/Domain

56
Q

Wie wird die Menge der möglichen Ausgaben für eine Funktion genannt?

A

Bildmenge/range

57
Q

Wie wird eine Funktion genannt, die alle Elemente der range/Bildmenge nutzt?

A

the function is onto the range

58
Q

Wie werden die a’s genannt?

A

Argumente

59
Q

Wie wird eine Funktion mit k-Argumenten genannt?

A

k-ary-function

60
Q

Was ist eine Relation?

A

Eine Prädiktion, dessen Urbildmenge aus einer Menge von k-Tupel besteht

61
Q

Was ist der Grad eines Knotens?

A

Die Anzahl dessen Kanten?

62
Q

Wann ist eine Graph ein Subgraph?

A

Wenn er eine Teilmenge der Knoten von einem anderen Graphen hat und dabei die Kanten beibehält

63
Q

Was ist ein simpler Pfad?

A

Ein Pfad, der keine Knoten wiederholt

64
Q

Was ist ein simpler Zyklus?

A

Ein Zyklus, der mind. drei Knoten hat und keine wiederholt

65
Q

Wann ist ein Graph ein Baum?

A

Wenn er verbunden ist und keine simplen Zyklen hat

66
Q

Was ist die Shortlex/String order?

A

identical to lexicographic order, except that shorter strings precede longer strings.

67
Q

Wann ist ein Graph k-regulär?

A

We define a graph to be k-regular if every node in the graph has degree k.

Einführung in die Theoretische Informatik (5 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions