Praktische Informatik 1

1.3 Alphabete, Wörter, Bäume, Graphen

Unter einem Alphabet A versteht man eine endliche Menge von Zeichen A={a₁, …, a_n}. Das bekannteste Beispiel ist sicher das lateinische Alphabet mit den Zeichen A, B, C, …, Z. Aber bereits davon gibt es verschiedene Varianten, man denke nur an das deutsche Alphabet mit Umlauten ä, ö, ü und der Ligatur ß. Im Laufe der Zeit haben sich bei den Völkern Hunderte von Alphabeten gebildet, von Keilschriften und Hieroglyphen bis hin zu Runen- und Geheimschriften (http://www.schriftgrad.de/). Das chinesische Alphabet umfasst etwa 56000 Zeichen, im Alltag kann man mit 6.000 Schriftzeichen schon relativ gut auskommen; der chinesische Zeichensatz für Computer enthält 7.445 Schriftzeichen. Der ASCII-Zeichensatz enthält 128 bzw. (in der erweiterten Form Latin-1) 256 Druckzeichen, siehe Tabelle. Der Unicode- oder UCS-Zeichensatz umfasst etwa 100.000 Zeichen http://de.wikipedia.org/wiki/Unicode. Man beachte, dass in manchen Alphabeten das Leerzeichen als ein Zeichen enthalten ist; als Ersatzdarstellung wählt man häufig eine Unterstrich-Variante. Ein für die Informatik wichtiges Alphabet ist die Menge B der Wahrheitswerte.

Eine (endliche) Folge wA^* von Zeichen über einem Alphabet A heißt Wort oder Zeichen­reihe (string) über A. Normalerweise schreibt man, wenn es sich um Wörter handelt, statt w = (a₁,a₂,…,a_n) kurz w = "a₁a₂…a_n", manchmal werden die Anführungszeichen auch wegge­lassen. Die leere Zeichenreihe wird mit dem Symbol oder mit "" bezeichnet. Über Wörtern ist die Konkatenation (Hintereinanderschreibung) als Operation definiert: Wenn v = a₁a₂…a_n und w = b₁b₂…b_m, dann ist v_°w = a₁a₂…a_nb₁b₂…b_m. Da die Operation _° assoziativ ist ((u _° v) _° w = u _° (v _° w)), wird das Operationssymbol _° manchmal auch einfach weggelassen.Die leere Zeichenreihe ist bezüglich _° ein neutrales Element (w _° = _° w = w).

Eine Menge mit einer assoziativen Operation und einem neutralem Element nennt man auch Monoid; da die Menge A^* (mit der Operation _° und dem neutralen Element) keinen weiteren Einschränkungen unterliegt, heißt sie auch der freie Monoid über A (wenn a₁a₂…a_n = b₁b₂…b_m, mit (a_i, b_i ∈A), so ist n=m und a₁= b₁ und… und a_n= b_n).
Die Menge der Wörter über einem gegebenen Alphabet lässt sich auch induktiv erzeugen:

• 
  A^*
  
• 
  Wenn aA und wA^*, so ist (a_°w)A^*.
  

Hierbei bezeichnet (a_°w) diejenige Zeichenreihe, die als erstes Zeichen a enthält und danach das Wort w. Alternativ dazu hätten wir Wörter induktiv durch das Anfügen (append) von Zeichen an Zeichenreihen erzeugen können. Diese Charakterisierung der Menge der Zeichenreihen erlaubt es, induktive Beweise zu führen und rekursive Funktionen über Wörtern zu definieren.
Sei first(w) die partielle Funktion, die zu einem nichtleeren Wort dessen erstes Zeichen liefert, und rest(w) die Funktion, die das Wort ohne das erste Zeichen liefert. Programmiersprachlich etwa
def first(w){w[0]}

def rest(w){w.substring(1)}
Hier sind ein paar rekursiv definierte Funktionen über Wörtern.
def laenge(w){if(w=="") return(0) else return(1+laenge(rest(w)))}
liefert die Länge eines Wortes. In Groovy/Java schreibt man "" für die leere Zeichenreihe ε, und + für das Konkatenationssymbol _°.
def invertiere(w){

if(w=="") return(w) else return(invertiere(rest(w))+first(w))}
liefert das umgedrehte Wort, also etwa ’negaldnurG’ zu ’Grundlagen’.
def ersetze(w,a,b){

if(w=="") return(w) else

if(first(w)==a) return(b+ersetze(rest(w),a,b)) else

return(first(w)+ersetze(rest(w),a,b))}
ersetzt jedes a in w durch b, z.B. ergibt ersetze("hallo",'l','r')=="harro".
Wir werden später noch ähnliche solche Funktionen kennen lernen.

Wenn w=u_°v, so sagen wir, dass u ein Anfangswort von w ist. Wenn w=v1_°u_°v2, so nennen wir u ein Teilwort von w. Auch die Anfangswortrelation lässt sich leicht induktiv definieren:

def anfangswort(w,u){

if(u=="") return(true)

else if(first(w)!= first(u)) return(false)

else return(anfangswort(rest(w), rest(u)))}
Auf Alphabeten ist häufig eine totale Ordnungsrelation erklärt; meist wird diese durch die Reihenfolge der Aufschreibung der Zeichen unterstellt. Wenn A ein Alphabet mit einer totalen Ordnungsrelation  ist, so kann  zur lexikographischen Ordnung auf A^* ausgeweitet werden:

Sei x= x₁x₂…x_n und y= y₁y₂…y_m. Dann gilt x y, wenn

• 
  x ein Anfangswort von y ist, oder
  
• 
  es gibt ein Anfangswort z von x und y (x=z_°x’, y=z_°y’) und first(x’) y’).
  

(a < b bedeutet a  b und nicht a = b)

Beispiele für lexikographisch geordnete Wörter über dem lateinischen Alphabet sind

"ANTON" < "BERTA", "AACHEN" < "AAL", "AAL" < "AALBORG" und < "A".
Es ist nicht schwer zu sehen, dass die lexikographische Ordnung eine totale Ordnung ist. Die Buchstaben des deutschen Alphabets sind nicht linear geordnet (a und ä stehen nebeneinander, ß ist nicht eingeordnet), daher entspricht die Reihenfolge der Wörter in einem deutschen Lexikon nicht der lexikographischen Ordnung.

Bäume

Bäume sind – neben Tupeln, Folgen und Wörtern – eine weitere in der Informatik sehr wichtige Datenstruktur. In der induktiven Definition von Zeichenreihen besteht ein Wort w aus der Konkatenation von first(w) mit rest(w). Ein Binärbaum ist dadurch gekennzeichnet, dass es zwei verschiedene „Reste“ gibt: den linken und den rechten Unterbaum. Daraus ergibt sich folgende induktive Definition der Menge der Binärbäume über einem gegebenen Alphabet A:

• 
  A^
  
• 
  Wenn aA und lA^ und rA^, so ist (a,l,r)A^.
  

a heißt Wurzel, l und r sind Unterbäume des Baumes (a,l,r). Die Wurzeln von l und r heißen die Kinder oder Nachfolger von a. Ein Baum y ist Teilbaum eines Baumes x, wenn x=y oder y Teilbaum eines Unterbaumes von x ist. Wenn y nichtleerer Teilbaum von x ist, so sagen wir, die Wurzel von y ist ein Knoten von x. Ein Knoten ohne Nachfolger (d.h. ein Teilbaum der Gestalt (a,,) ) heißt Blatt.
Als Beispiel für Bäume betrachten wir Formelbäume über dem Alphabet (x,y,z,+,*). Die Formel x*y + x*z (mit „Punkt-vor-Strich-Regelung“) kann durch den Baum (+,(*,(x,,),(y,,)),(*,(x,,),(z,,))) repräsentiert werden. Übersichtlicher ist eine graphische Darstellung:

Wir werden später verschiedene Algorithmen, die auf Bäumen basieren, kennen lernen.

Es ist klar, dass sich die obige Definition direkt auf Binärbäume über einer beliebigen Grundmenge verallgemeinern lässt. Eine weitere nahe liegende Erweiterung sind n-äre Bäume, bei denen jeder Knoten entweder keinen oder n Nachfolger hat. Wenn wir erlauben, dass jeder Knoten eine beliebige (endliche) Zahl von Nachfolgern haben kann, sprechen wir von endlich verzweigten Bäumen.

Aufrufbäume

Eine spezielle Art von (endlich verzweigten) Bäumen sind die Aufrufbäume einer rekursiven Funktion. Die Wurzel eines Aufrufbaumes ist der Name der Funktion mit den Eingabewerten. Die Nachfolger jeden Knotens sind die bei der Auswertung aufgerufenen Funktionen mit ihren Eingabewerten.

Beispiel:

(In diesem Baum haben wir die Funktionen „==“ und „if“ nicht weiter berücksichtigt.)

Beim verkürzten Aufrufbaum lässt man alle Knoten weg außer denen, die die rekursive Funktion selbst betreffen.

Beispiel:


Unter der Aufrufkomplexität einer rekursiven Funktion verstehen wir die Anzahl der Knoten im verkürzten Aufrufbaum. Die Zeit, die benötigt wird, um eine rekursive Funktion zu berechnen, hängt im Wesentlichen von der Aufrufkomplexität ab. Als Beispiel betrachten wir die Aufrufkomplexität der Fibonacci-Funktion. Aus obigem Beispiel ist sofort klar:

Die rekursive Formulierung hilft leider noch nicht, die Aufrufkomplexität abzuschätzen. Per Induktion nach n zeigen wir:. Für n=1,2 ist dies klar, für n>2 gilt

Mit der früher bewiesenen Gleichung von Binet erhalten wir

.

Eine Wertetabelle für einige Zahlenwerte ist nachfolgend angegeben. Daraus folgt: wenn in einer Sekunde 10.000 Aufrufe erfolgen, benötigt die Rechnung für n=100 etwa 2,2 Milliarden Jahre! (üblicherweise ist vorher der Speicher erschöpft oder ein Zahlbereichsüberlauf eingetreten,).

n	3	5	10	20	30	40	50	60	70	80	90	100
fibComp(n)	3	9	109	13529	1.6*10^6	2*10^8	2.5*10^10	3*10^12	3.8*10^14	4.6*10^16	5.7*10^18	7*10^20

Graphen

Während ein Wort in der Informatik nur eine spezielle Art von Folgen ist, versteht man unter einem Graphen nur eine spezielle Art von Relationen: Ein Graph ist die bildliche Darstellung einer binären Relationen über einer endlichen Grundmenge. Die Elemente der Grundmenge werden dabei in Kreisen (Knoten) gezeigt. Zwischen je zwei Knoten zeichnet man einen Pfeil (eine Kante), falls das betreffende Paar von Elementen in der Relation enthalten ist. Beispiel:

Dies ist die Relation {(A,B),(B,C),(C,B),(C,A),(B,D),(C,D)}. Für symmetrische Relationen weisen die Pfeile immer in beide Richtungen; man spricht hier von ungerichteten Graphen.

Eine Alternative zur obigen Definition besteht darin, einen Graphen als Tupel (V,E) zu definieren, wobei V eine endliche Menge von Knoten (vertices) und E eine endliche Menge von Kanten (edges) ist, so dass zu jeder Kante genau ein Anfangs- und ein Endknoten gehört.

Knoten, die nicht Endknoten sind, heißen Quelle, Knoten, die nicht Anfangsknoten sind, heißen Senke im Graphen. Knoten, die weder Anfangs- noch Endknoten sind, heißen isoliert.

Eine dritte Art der Definition von Graphen ist durch die so genannte Adjazenzmatrix: Nach dieser Auffassung ist ein Graph eine endliche Matrix (Tabelle) mit booleschen Werten. Die Zeilen und Spalten der Tabelle sind dabei mit der Grundmenge beschriftet; ein Eintrag gibt an, ob das entsprechende Paar (Zeile, Spalte) in der Relation enthalten ist oder nicht.

	A	B	C	D
A		X
B			X	X
C	X	X		X
D

Im Gegensatz zu Bäumen können Graphen Zyklen enthalten, daher existiert keine einfache induktive Definition. Umgekehrt können endlich verzweigte Bäume als zyklenfreie Graphen mit nur einer Quelle betrachtet werden.