Grundlagen der Informatik zusammengefasst

Während des Durchlaufes lässt man jeden zweiten Knoten auf seinen bisherigen Großvater zeigen.

Diese Methoden haben beide dieselben amortisierten Kosten wie die oberste Kompressionsmethode (Knoten unter die Wurzel schreiben). Alle Kompressionsmethoden beschleunigen zukünftige Find(x)-Operationen.

Union-Find-Datenstrukturen ermöglichen die Ausführung der Operationen mit den folgenden Laufzeiten (n = |S|):

Einfache Implementierung mit einer Liste L , worst-case: Find: O(1), Union: O(n)

Implementierung mit Bäumen:

• ohne Heuristiken: Find O(n), Union O(1)

• mit Union-By-Size, worst-case: Find O(log n) , Union O(1)

• mit Union-By-Size, Pfadkompression, worst-case: Find O(log n), Union O(1)

• mit Union-By-Size, Pfadkompression, Folge von f Find- und u Union-Operationen: o( u+ (n+f) * (log*(n)))

Ein planarer Graph lässt sich in der Ebene darstellen, ohne dass sich die Kanten kreuzen. Die Menge der durch die Kanten begrenzten Flächenstücke ist A.

Für alle planaren, zusammenhängenden Graphen G=(V,E) gilt: |V| - |E| + |A| = 2

Anwendung:

• Platinenlayout

• Rohrleitungsnetze

• Teils: Bahn- und Straßennetze

Ein beliebiger, planarer, zusammenhängender Graph lässt sich immer so mit vier Farben färben, dass benachbarte Gebiete unterschiedliche Farben haben.

Anwendung:

• Funkzellenplanung bei Mobilfunknetzen

1930: Alan Turing definiert Maschine mit

• sämtlichen Fähigkeiten von Computern

• exakte Beschreibung von: Berechenbar / Nicht berechenbar

1969: Stephen Cook unterscheidet

• effizient mit Computer lösbar

• Prinzipiell lösbar (aber zu zeitaufwendig)

Modell für Hard- und Software:

• z.B. Entwurf / Prüfung digitaler Schaltkreise

• z.B. lexikalische Analyse von Compilern

• z.B. Textsuche

Eine Zeichenreihe ist eine endliche Folge von Symbolen eines bestimmten Alphabets.

Die leere Zeichenreihe ist eine Zeichenreihe, die kein Symbol enthält. Sie wird durch das
Symbol „ε“ dargestellt.

Synonyme: Zeichenkette, String, Wort

Symbol: ω

Beispiele:

Σ ={0,1} --> 0110110 oder 10111

Σ = {a,b,c,...z} --> hallowelt

Σ = {0,1,...9} --> 2014

Länge einer Zeichenreihe: |ω|= Anzahl der Symbole in einer Zeichenreihe

Ist die Menge aller Zeichenreihen der bestimmten Länge k über Σ heißt Σ^k❑❑❑, d.h. Die Länge eines "Wortes" gebildet aus Symbolen der Zeichenkette hat die exakte Länge k.

Beispiele:

Σ={0,1}

Σ°={ ε }

Σ^1={0,1} (Worte, nicht Symbole)

Σ²={00,01,10,11}

Σ³={000,001,010,011,100,....111}...usw.

Die Menge aller Zeichenreihen BELIEBIGER Länge eines Alphabets Σ heißt Σ*.
Die Menge ohne ε über einem Alphabet Σ heißt Σ+.

Beispiel

Σ* = {ε, 0, 1, 00, 01, 10, 11, 000, ... } =Σ0 ∪ Σ1 ∪ Σ2 ∪ Σ3 ∪ Σ4 ∪ ... Σ+ = {0, 1, 00, 01, 10, 11, 000, ... } =Σ1 ∪ Σ2 ∪ Σ3 ∪ Σ4 ∪ ...

Konkatenation beschreibt eine Neubildung eines Wortes mittels Zusammensetzen von Wörtern zu einem neuen Wort durch Aneinanderhängen der Symbolfolgen.

Die Konkatenation von Zeichenreihen in der Informatik beruht auf demselben Prinzip. Bei gegebenen Zeichenreihen, welche eine endliche Folge von Symbolen eines bestimmten Alphabets Σ sind, werden diese Zeichenreihen aneinandergehängt.

Beispiel:

|K|=f, f= DameKönig Zeichenreihen K und S über
|S|=i, i = AssZwei Σ, in diesem Fall Groß- und Kleinbuchstaben
Konkatenation:KS= DameKönigAssZwei
SK=AssZweiDameKönig

Jede Teilmenge von Σ^* wird Sprache genannt. Im oberen Beispiel sind sowohl DameKönig, AssZwei als auch deren Konkatenationen Teilmengen und somit Sprachen über dem Alphabet Σ.
K und S sind somit Sprachen über Σ.
Hierbei muss weder |K| noch |S| alle Symbole aus Σ nutzen. Wenn K oder S nur einen Teil der Symbole von Σ verwenden, ist L auch eine Sprache über Σ^~.

Eine zulässige Sprache wird definiert durch die Grammatik, welche Wortbildungsregeln und Satzbauregeln beinhaltet.

Ein deterministischer endlicher Automat (kurz DEA) hat eine endliche Menge Q, eine endliche Menge von Eingabesymbolen Σ, eine Übergangsfunktion δ(q,a)=p (q,p ε Q, a ε Σ), eine Menge von finaler / akzeptierender Zustände F ⊆ Q und einen Startzustand q0.
Somit gilt für DEA A = (Q, Σ, δ, q0, F)

Wichtig ist, daß die Zahl der Zustände des DEA endlich ist.

Da die Übergangsfunktion sehr schwer leserlich ist, ist es empfehlenswert ein Übergangsdiagramm zu nutzen um die Funktionsweise des jeweiligen DEA zu verstehen.

Bei der erweiterten Übergangsfunktion wird nicht nur ein Symbol betrachtet sondern ein ganzes Wort. Der Automat berechnet den Zustand mittels wiederholter Anwendung der normalen Übergangsfunktion. Dies bringt eine enorme Arbeitserleichterung.

Die Sprache eines DEA nennt man L(A). Sie wird definiert durch L(A) = {ω | δ*(q0,w) ε F} .
Dies bedeutet die Menge der Zeichenreihen, die A vom Startzustand in den akzeptierten Endzustand führt.

Ist L für einen DEA L(A) dann heißt L reguläre Sprache.

Die Abkürzung „NEA“ steht für Nichtdeterministischer endlicher Automat.
Hierbei handelt es sich um einen Automaten, der zufällig mehrere Zustände annehmen kann. Es wird mit regulären Sprachen gearbeitet, die eine formale Sprache ist, welche einigen Einschränkungen unterliegt. Ein NEA kann auf jeden Fall in ein DEA überführt werden, was aber nicht unbedingt produktiv wäre, da der NEA übersichtlicher ist.

Die passende Formel für einen NEA lautet:

A =(Q,∑,δ,q0,F)

„A” steht für den Automaten.
„∑” für die endliche Menge von Eingangssymbolen.
„δ“ für eine Übergangsfunktion (δ(q,a)=p
(q ∊ Q, p ⊆ Q, a ∊ ∑)).
„Q“ für die Menge akzeptierender Zustände.
„F“ für die Menge Endzustände
„q0“ steht dann noch für den Startzustand.

Da jeder DEA auch als NEA aufgefasst werden kann, ist dies einsichtig. Wenn ein NEA in einen DEA umgewandelt werden soll, benutzt man ein Verfahren, dass sich Potenzmengenkonstruktion nennt.

Hier gilt:

δ'(q, a) = {
{δ(q, a)} : falls δ(q, a)
∅ : sonst.

Wenn NEA gegeben ist: N=(QN,∑,δN,q0,FN),
DEA gesucht ist: D=(QD,∑,δD,{q0},FN)
und L(D)=L(N), können wir einen QD konstruieren.
Da ist dann QD eine Potenzmenge von QN
➝ |QN|=n ➜ |QD|=2n
Alle Zustände, die von q0 nicht erreicht werden können, fallen weg.
Bei der Konstruktion eines FD, werden alle Teilmengen S des QN von FD umfasst, solange sie mindestens einen akzeptierenden Zustand des NEA N enthalten.

Bei der Konstruktion von δD: (∀ S ⊆ QN ∧ a ∊ ∑) gilt:

δD(S,a) = U δN (p,a) p∈s

Es gibt verschieden Operationen, welche auf Spachen angewendet werden können:

Wenn L und M eine Sprache sind, so ist

• L ∪ M die Vereinigung

• LM die Konkatenation

• L* die Kleenesche Hülle

Sei die Sprache L={a,b} und die Sprache M={c,d},
so ist die Vereinigungsmenge L ∪ M ={a,b,c,d}.

Seien L, M Sprachen, dann ist ∀ v∊L, w∊M
LM die Menge aller Zeichenketten vw.

Beispiel:
L={001, 10, 111},

M={ε, 001}
➝LM = {001, 10, 111, 001001, 10001, 111001}

Die (Kleensche) Hülle (auch Stern) einer
Sprache L heißt L* und beschreibt die Menge
aller Zeichenreihen, die durch Verkettung einer
beliebigen Anzahl von Zeichenreihen aus L
gebildet werden.

Beispiel:

• Sei L={0,1}, dann enthält L* alleZeichenketten aus 0en und 1en.

• Sei L={0,11}, dann enthält L* alleZeichenreihen aus 0en und 1en, in denendie 1en paarweise auftreten:0, 011, 1111 aber nicht: 01011 oder 101.

Anwendungsbeispiel:

L={0,11}

• L0= {ε}

• L1= {0,11}

• L2= {00, 011, 110, 1111}

• L3= {000, 0011, 0110, 01111,1100, 11011, 11110, 111111}

Ln={a,b}

L: Name der Sprache

n: Anzahl der Wiederholungen von Worten der Sprache L

z.B. L2 enthält aa, ab, ba oder bb, aber niemals aaa oder aba

{a,b}: In der Klammern stehen die Worte der Sprache, z.B. Buchstaben oder Zahlen.

1. Sei L die Menge aller aus Nullenbestehenden Zeichenketten, dann ist L* = L.

2. Sei L={ε}, dann ist L*={ε}. Damit hat L eine endliche Hülle.

Reguläre Ausdrücke beschreiben bestimmte Zeichenketten. Sie können beispielsweise verwendet werden, um Texte zu durchsuche oder Eingaben zu validieren .

ε und ∅ (leere Menge) sind reguläre Ausdrücke und beschreiben die Sprache L(ε) = ε bzw. L(∅) = ∅.
Für alle a Σ ist a ein regulärer Ausdruck der Sprache L(a) = a.

Desweiteren gilt für reguläre Ausdrücke:
Sind X und Y reguläre Ausdrücke so sind auch
(X+Y)(Alternative auch (X|Y))
(XY) (Verkettung/Konkatenation)
(X*) (Kleensche Hülle)
reguläre Ausdrücke.

Dabei hat der *-Operator Vorrang vor dem Verkettungsoperator, der wiederrum Vorrang vor dem Vereinigungsoperator hat.

• „ . “ = beliebiges Zeichen

• [abc] = a+b+c

• [1-9] = [123456789]

• \ = Escaping

Zeichenklassen

• [:digit:] = [0-9]

• [:alpha:] = [A-Za-z]

• [:alnum:] = [0-9A-Za-z]

Operatoren

• |: = Vereinigung

• ?: = Zeichen kommt einmal oder garnicht vor

• +: = Zeichen kommt ein oder mehr mal vor

• *: = Kleensche Hülle

• {n}: = Zeichen kommt genau n mal vor

Die Unix Regular Expressions haben die gleiche Mächtigkeit (die gleichen Zeichenketten können erkannt werden) wie normale Regular Expressions.

Reguläre Sprachen werden von DEAs bzw NEAs entschieden und können durch Reguläre Ausdrücke beschrieben werden.

Um zu erkennen ob eine Sprache regulär ist, muss man sich die Frgae stellen:
Gibt es einen (deterministischer endlicher Automat) DEA?
Ein Endlicher Automat hat endliche Zahl von Zuständen. Sei das k. Wenn die Eingabe 0^k ist muss ein Zustand q das zweite Mal erreicht sein.

Dies beschreibt in der eine Eigenschaft bestimmter Klassen formaler Sprachen.
In vielen Fällen lässt sich anhand des Lemmas nachweisen, dass eine formale Sprache nichtregulär bzw. nicht kontextfrei ist.

Für jede reguläre Sprache L gibt es eine natürliche Zahl , sodass gilt: Jedes Wort z in L mit Mindestlänge n hat eine Zerlegung mit den folgenden drei Eigenschaften:

1. Die beiden Wörter u und v haben zusammen höchstens die Länge n

2. Das Wort v ist nicht leer.

3. Für jede natürliche Zahl (mit 0) i ist das Wort uv^2w in der Sprache L , d. h. die Wörter uw , uvw , uvvw , uvvvw , usw. sind alle in der Sprache .

Neben den regulären Sprachen gibt es auch nicht-reguläre Sprachen, die dieses Lemma erfüllen. Eine notwendige und hinreichende Bedingung für reguläre Sprachen liefern der Satz von Myhill-Nerode oder Jaffes Pumping-Lemma.

Die Gültigkeit des Lemmas basiert darauf, dass es zu jeder regulären Sprache einen deterministischen endlichen Automaten gibt, der die Sprache akzeptiert.