Formale Grundlagen

Question 1

Welche Eigenschaften muss eine Gruppe haben?

Answer 1

1. Abgeschlossenheit
2. Das Assoziativgesetz muss anwendbar sein
3. Ein neutrales Element muss existieren
4. Ein inverses Element muss existieren
   (5. Das Kommutativgesetz muss anwendbar sein)

Question 2

Was bedeutet Abgeschlossenheit bei Gruppen?

Answer 2

Zwei Elemente in der Menge müssen wenn diese verknüpft werden wieder ein Teil der Menge ergeben

Z.B. 1+2=3 somit ist die Menge der natürlichen Zahlen bei Addition eine Gruppe

Question 3

Was ist das Assoziativgesetz?

Answer 3

Das die Reihenfolge in der Teilmengen zusammengerechnet werden keinen Unterschied macht

Question 4

Was ist das neutrale Element?

Answer 4

Bei einem neutralen Element ist das Ergebnis einer Berechnung aus diesem mit einem Element der Menge immer das Element mit welchem das neutrale Element verrechnet wurde

Question 5

Was ist ein inverses Element?

Answer 5

Das inverse Element ist vorhanden, wenn das Ergebnis einer Berechnung aus einem Element der Menge mit einem Identischen Element mit umgedrehten Vorzeichen das neutrale Element ergiebt

Question 6

Was ist der Unterschied zwischen einer Gruppe und einer kommutativen Gruppe?

Answer 6

Bei einer kommutativen Gruppe gilt das Kommutativgesetz wärend es bei einer normalen Gruppe nicht zutreffen muss

Question 7

Was besagt das Kommutativgesetz?

Answer 7

Das Ergebnis einer Multiplikation ist unabhängig davon in welcher Reihenfolge die Elemente bei der Berechnung stehen

Question 8

Was ist ein Körper?

Answer 8

Ein Körper ist eine Gruppe mit zwei Verknüpfungen

Question 9

Wann ist eine Gruppe ein Körper?

Answer 9

1. Erste Verknüpfung muss ne Abelsche Gruppe sein
2. Zweite Verknüpfung muss ne Abelsche Gruppe ohne Nullelement sein
3. das Distributivgesetz muss anwendbar sein

Question 10

Was ist ein Einselement?

Answer 10

Der Unterschied zwischen Null- und Einselement ist, das das Ergebnis nicht 0 sondern 1 ist

Question 11

Was besagt das Distributivgesetz?

Answer 11

Das Ergebnis einer doppelten Verknüpfung ist das selbe, egal ob die erste und die zweite Verknüpfung voneinander getrennt sind oder nicht

z.B. a(b+c) = ab+ac

Question 12

Was ist ein K-Vektorraum?

Answer 12

Ein K-Vektorraum ist ein Körper, mit einem zusätzlichem Körper, dabei muss (V,+) eine kumutative Gruppe sein und ……..

Question 13

Was ist ein Untervektorraum?

Answer 13

Ein Untervektorraum ist eine Teilmenge eines Vektorraums, welche zusammen mit dem Körper ein neuen Vektorraum bildet

Question 14

Was bedeutet adjazenz?

Answer 14

Adjazenz bedeutet, das zwei Ecken über eine Kante direkt miteinander verbunden sind

Question 15

Was bedeutet Inzidenz?

Answer 15

Inzidenz bedeutet, das sich ein Knoten und eine Kante berühren.

Question 16

Was ist eine Adjazenzmatrix?

Answer 16

Eine Adjazenzmatrix ist eine binäre Matrix, welche die Nachbarn eines jeden Knoten darstellt

Question 17

Was ist eine Inzidenz Matrix?

Answer 17

Bei einer Inzidenz Matrix wird die Beziehung zwischen Kanten und Knoten in einer Matrix dargestellt.Bei gerichteten Grappen gilt: Bei Ausgang wird eine -1 genommen und bei Eingang eine 1

Question 18

Wie berechnet man den Durchschnitt eines Graphen?

Answer 18

Der Durchschnitt eines Graphen ist der schnellste Weg zwischen den beiden am weitesten auseinander liegenden Ecken eines Graphen

Question 19

Was bedeutet Isomorph?

Answer 19

Das zwei Graphen strukturell identisch sind nur anders dargestellt werden

Question 20

Was ist ein deterministischer endlicher Automat?

Answer 20

Ein DEA ist ein Algorithmus, mit dem ein Wort auf Existenz in einer vorher angegebenen Sprache durch Nachstellung überprüft wird.

Question 21

Wie funktioniert der Dijkstra Algorithmus?

Answer 21

Dabei wird der Weg mit den geringsten Kosten ermittlert, indem eine Tabelle erstellt wird bei der zuerst die Iteration angegeben wird und darauf alle Knoten. In den Zellen der Knoten werden dabei immer die Kosten angegeben die mindestens benötigt werden um zu ihnen zu kommen und von welchem Knoten man diesen erreicht.

Das führt man nach und nach für jeden Knoten durch wobei die Reihenfolge durch die Kosten bestimmt wird.

Question 22

Wie funktioniert der Prim Algorithmus?

Answer 22

Beim Prim Algorithmus wird der Weg durch den Algorithmus mit den geringsten Kosten dargestellt, indem von einem Knoten aus immer der Weg mit den geringsten Kosten gewählt wird, bis alle Knoten einmal erreicht wurden. Dann werden die Kosten der Pfade zu einer gesamtsumme zusammengerechnet.

Question 23

Wie funktioniert der Kruskal Algorithmus?

Answer 23

Beim Kruskal Algorithmus wird ein minimaler Spannbaum in einem Graphen aufgestellt, indem die Kanten nach und nach der Gewichtung nach markiert werden. Dabei ist die Reihenfolge der Knoten irrelevant allerdings darf kein Zyklus entstehen und alle Knoten müssen angebunden sein.

Question 24

formale Definition Abgeschlossenheit

Answer 24

∀a,b ∈ M : aob ∈ M

Question 25

formale Definition Assoziativgesetz

Answer 25

∀a, b, c ∈ M : (aob)oc = ao(boc)

Question 26

formale Definition neutrales Element

Answer 26

∃n∈M ∀a∈M : noa = aon = a

Question 27

formale Definition Inverses Element

Answer 27

∀a∈M ∃a^-1∈M : aoa^-1 = a^-1oa = n

Question 28

formale Definition Kommutativgesetz

Answer 28

∀a, b∈M : aob = boa

Question 29

formale Definition Distributivgesetz

Answer 29

∀a, b, c∈M : ao(bo2c) = aobo2aoc
(bo2c)oa = boao2coa
z.B. a(b+c) = ab+a*c

Question 30

Flussdiagramme

Answer 30

Haben eine Quelle (S) und eine Senke (T)

Haben eine “Flussrichtung” (Kantenrichtung von S nach T)

Flussmenge darf nicht höher sein als Kantengewichtung

Question 31

Typ 0 Sprache

Answer 31

keine Einschränkung

Question 32

Typ 1 Sprache

Answer 32

Kontextsensitiv: |w1| ≤ |w2|

Question 33

Typ 2 Sprache

Answer 33

Kontextfrei: weV (es muss aus einer Variable ein Terminal ableitbar sein)

Question 34

Typ 3 Sprache

Answer 34

Regulär: jede Variable muss aus einer Kombination der Bedingungen bestehen, dass es aus einem Terminal oder aus einem Terminal und einer Variable bestehen