Formale Grundlagen Flashcards
Welche Eigenschaften muss eine Gruppe haben?
- Abgeschlossenheit
- Das Assoziativgesetz muss anwendbar sein
- Ein neutrales Element muss existieren
- Ein inverses Element muss existieren
(5. Das Kommutativgesetz muss anwendbar sein)
Was bedeutet Abgeschlossenheit bei Gruppen?
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
Was ist das Assoziativgesetz?
Das die Reihenfolge in der Teilmengen zusammengerechnet werden keinen Unterschied macht
Was ist das neutrale Element?
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
Was ist ein inverses Element?
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
Was ist der Unterschied zwischen einer Gruppe und einer kommutativen Gruppe?
Bei einer kommutativen Gruppe gilt das Kommutativgesetz wärend es bei einer normalen Gruppe nicht zutreffen muss
Was besagt das Kommutativgesetz?
Das Ergebnis einer Multiplikation ist unabhängig davon in welcher Reihenfolge die Elemente bei der Berechnung stehen
Was ist ein Körper?
Ein Körper ist eine Gruppe mit zwei Verknüpfungen
Wann ist eine Gruppe ein Körper?
- Erste Verknüpfung muss ne Abelsche Gruppe sein
- Zweite Verknüpfung muss ne Abelsche Gruppe ohne Nullelement sein
- das Distributivgesetz muss anwendbar sein
Was ist ein Einselement?
Der Unterschied zwischen Null- und Einselement ist, das das Ergebnis nicht 0 sondern 1 ist
Was besagt das Distributivgesetz?
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
Was ist ein K-Vektorraum?
Ein K-Vektorraum ist ein Körper, mit einem zusätzlichem Körper, dabei muss (V,+) eine kumutative Gruppe sein und ……..
Was ist ein Untervektorraum?
Ein Untervektorraum ist eine Teilmenge eines Vektorraums, welche zusammen mit dem Körper ein neuen Vektorraum bildet
Was bedeutet adjazenz?
Adjazenz bedeutet, das zwei Ecken über eine Kante direkt miteinander verbunden sind
Was bedeutet Inzidenz?
Inzidenz bedeutet, das sich ein Knoten und eine Kante berühren.
Was ist eine Adjazenzmatrix?
Eine Adjazenzmatrix ist eine binäre Matrix, welche die Nachbarn eines jeden Knoten darstellt
Was ist eine Inzidenz Matrix?
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
Wie berechnet man den Durchschnitt eines Graphen?
Der Durchschnitt eines Graphen ist der schnellste Weg zwischen den beiden am weitesten auseinander liegenden Ecken eines Graphen
Was bedeutet Isomorph?
Das zwei Graphen strukturell identisch sind nur anders dargestellt werden
Was ist ein deterministischer endlicher Automat?
Ein DEA ist ein Algorithmus, mit dem ein Wort auf Existenz in einer vorher angegebenen Sprache durch Nachstellung überprüft wird.
Wie funktioniert der Dijkstra Algorithmus?
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.
Wie funktioniert der Prim Algorithmus?
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.
Wie funktioniert der Kruskal Algorithmus?
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.
formale Definition Abgeschlossenheit
∀a,b ∈ M : aob ∈ M
formale Definition Assoziativgesetz
∀a, b, c ∈ M : (aob)oc = ao(boc)
formale Definition neutrales Element
∃n∈M ∀a∈M : noa = aon = a
formale Definition Inverses Element
∀a∈M ∃a^-1∈M : aoa^-1 = a^-1oa = n
formale Definition Kommutativgesetz
∀a, b∈M : aob = boa
formale Definition Distributivgesetz
∀a, b, c∈M : ao(bo2c) = aobo2aoc
(bo2c)oa = boao2coa
z.B. a(b+c) = ab+a*c
Flussdiagramme
Haben eine Quelle (S) und eine Senke (T)
Haben eine “Flussrichtung” (Kantenrichtung von S nach T)
Flussmenge darf nicht höher sein als Kantengewichtung
Typ 0 Sprache
keine Einschränkung
Typ 1 Sprache
Kontextsensitiv: |w1| ≤ |w2|
Typ 2 Sprache
Kontextfrei: weV (es muss aus einer Variable ein Terminal ableitbar sein)
Typ 3 Sprache
Regulär: jede Variable muss aus einer Kombination der Bedingungen bestehen, dass es aus einem Terminal oder aus einem Terminal und einer Variable bestehen
