Abstract
Dieses Glossar wird von den Studis meines Tutoriums im Wintersemester 1995/96 angelegt. Zu verschiedenen Begriffen, die inhaltlich mit dem gelehrten Informatik 3-Stoff zusammenhängen, werden Definitionen erstellt.
Da noch nicht alle Punkte "mit Leben" gefüllt sind, ist hiermit jeder aufgerufen, Definitionen, Erklärungen und Bilder zu erstellen, damit das Glossar vervollständigt werden kann. Unvollständige Definitionen oder Hinweise für Euch habe ich in einer anderen Schriftart gesetzt - diese Teile sollen idealer Weise durch Formulierungen von Euch ersetzt werden. Ich bin dann bereit, Texte einzutippen oder einzubinden, falls sie schon als Datei vorliegen. Ferner lassen sich mit dem hier verwendeten LaTeX2e und Hyperlatex auch Bilder einbinden, die entweder als .gif-Datei oder auf Papier erstellt wurden! Also, ich hoffe, daß damit genügend Anreize geschaffen sind, weiter aktiv an dem Glossar mitzuarbeiten: Schickt mir einfach eine e-mail!
Eine Adjazenzliste dient genau wie die Adjazenzmatrix der Darstellung von Kantenbeziehungen in gerichteten und ungerichteten Graphen. Hierbei werden die Knoten in einer beliebigen Reihenfolge verkettet, und an jedem Knoten hängt eine Liste von Verwerisen auf die adjazenten Knoten.
Die Adjazenzmatrix ist die Darstellung von Kantenbeziehungen gerichteter und ungerichteter Graphen in Form einer booleschen Matrix. Bei n Knoten ergibt sich eine n×n-Matrix. Besteht eine Verbindung von Knoten A nach B, so wird an der Postion (A, B) eine "1" eingetragen, andernfalls eine Null. Da bei ungerichteten Graphen, sofern eine Verbindung zwischen A und B besteht, automatisch auch eine Verbindung zwischen B und A vorhanden ist, sind ihre Adjazenzmatrizen immer symmetrisch.
Bei Graphen mit bewerteten Kanten (wo also z.B. die Bewegung von einem Knoten
zu einem anderen mit bestimmten "Kosten" verbunden ist) benutzt man anstelle
einer boolschen Matrix eine Matrix mit einem Typ der die Kosten repräsentiert,
im allgemeinen CARDINAL's oder INTEGER's. Dabei ergibt sich folgendes Problem:
wie kennzeichne ich nun nicht vorhandene Kanten? Die Lösung ist einen
ausgezeichneten Wert zu bestimmen der als Kantenbewertung nicht
auftaucht. Ja nach Anwendungsfall bieten sich dazu -1 oder MAXINT an.
Die Menge derjenigen Kanten, die beim Traversieren durchlaufen wurden,
nennt man aufspannende Bäume.
was wird traversiert; Hinweis auf Traversierung mittels Tiefen- und Breitensuche
[backtrack engl. zurückverfolgen] Backtracking (Trial-and- Error-Verfahren) ist die Bezeichnung für ein Lösungsverfahren, bei dem man versucht, eine Teillösung eines Problems zu einer Gesamtlösung auszubauen. Für den baumartigen Suchraum heißt das, daß wir Schritt für Schritt einem Pfad in die Tiefe folgen. Wenn wir an ein Baumende gelangen, ohne die Lösung gefunden zu haben (Sackgasse), gehen
wir einen oder mehrere Schritte (Knoten) zurück, um einem anderen Pfad zu folgen.
Allgemeiner ausgedrückt: ist die Teillösung nicht mehr ausbaufähig, macht man Teilschritte rückgängig zu einer reduzierten Teillösung. Diese versucht man nun wiederum zur Gesamtlösung auszubauen.
Backtracking ist ein auf der Tiefensuche basierendes Lösungsverfahren.
Dabei werden Teilloesungen auf Grund einer lokalen Entscheidung systematisch
zur Gesamtlösung ausgebaut. Falls ein weiterer Ausbau einer Teillösung nicht
möglich ist (Sackgasse), werden ein oder mehrere Entscheidungen zurückgenommen. Die so verkleinerte Teillösung versucht man jetzt anhand von anderen
Entscheidungen wieder zu einer Gesamtlösung auszubauen.
Struktogramm aus Wirth: Algorithmen und Datenstrukturen
Ein Baum ist eine typische Datenstruktur zur Verwaltung von Information. Sie
heißt so ob der Tatsache, daß sie optische "Ahnlichkeit zu einem solchen
besitzt. Bäume sind i.a. dynamische Datenstrukturen. Die Analogie geht noch
weiter. Auch "unsere" Bäume besitzen eine Wurzel, "Aste und Blätter. Jeder
nicht leere Baum besitzt zumindest ein Knoten, eben die Wurzel. In einem
Knoten können (wie unten im Beispiel) Informationen gespeichert sein. Weiter
besitzt jeder Knoten eine (eventuell leere) Menge von Nachfolgern. Hat ein
Knoten keine Nachfolger, so spricht man von einem Blatt. Hat er Nachfolger, so
spricht man auch von "Asten. Die Anzahl der "Aste ist dabei beliebig. Besonders
häufig ist der binäre Baum, also ein Baum mit zwei Nachfolgern in jedem
Knoten. Eine wichtige Aufgabenstellung im Zusammenhang mit Bäumen ist die
Traversierung, also das Auffinden bestimmter Einträge, z.B. mittels
Tiefen- oder Breitensuche. Man kann Bäume im übrigen auch als
spezielle Graphen betrachten.
Hier eine superallgemeine Definition eines Baumes in MODULA-2. Dieser Baum
enthält in jedem Knoten den in data festgelegten Datentyp und dann
eine Liste von (beliebig vielen) Nachfolgeknoten. Ist ein Pointer NIL
so deutet dies das Ende der Liste bzw. des Astes an.
TYPE data = ...
Pdata = POINTER TO data;
child = RECORD OF
nextchild : Pchild;
thischild : Pbaum;
END;
Pchild = POINTER TO child;
baum = RECORD OF
value : Pdata;
childs : Pchild;
END;
Pbaum = POINTER TO baum;
Hier noch eine graphische Darstellung für einen Baum der oben definierten
Form:
Ein Baum ist eine endliche Menge von Knoten, für die gilt:
1. Ist die Knotenmenge leer, liegt ein leerer Baum vor.
2. a) Bei nicht leerer Knotenmenge existiert ein ausgezeichneterKnoten,die
Wurzel.
b) Die restlichen Knoten werden in disjunkte Mengen B1,...,Bn aufgeteilt,
wobei jede dieser Mengen ein Baum ist (subtrees).
(B1,....,Bn werden daher auch Unterbäume der Wurzel genannt.)
Die Reihenfolge der B1,...,Bn spielt zunächst keine Rolle. Wenn jedoch
für jeden Knoten die Teilbäume B1,...,Bn in einer festen Reihenfolge
stehen sollen, spricht man von geordneten Bäumen.
Blatt: Ein Knoten, der keine Nachfolger hat, heißt Blatt.
TYPE Baum = POINTER TO Knoten;
Knoten = RECORD Wurzel ------->(2)
Links, Rechts :Baum; Kante -----> / \
Wert: CHAR; / \
END; Blatt -----> (1) (5)
Ein binärer Baum zeichnet sich dadurch aus, daß jeder Knoten maximal zwei
Nachfolger hat. Hat er keinen, so handelt es sich um ein Blatt.
Nachfolgend ein Beispiel für die Definition eines binären Baumes mit INTEGER's
als Einträgen in MODULA-2:
TYPE BinTree = RECORD
value : INTEGER;
left,right : PBinTree;
END;
PBinTree = POINTER TO BinTree;
[branch engl. , bound engl. ]
Bei der Breitensuche ergibt sich sogenannte Branch-And-Bound
Algorithmen.
Bei der Breitensuche werden zunächst alle unmittelbaren Nachfolger eines
Knoten behandelt; die darunterliegenden, restlichen Unterbäume werden auf
später verschoben. Damit können in manchen Situationen unnütze Suchpfade
sehr früh gekappt werden.
genauer?; Achtung: Definition aus dem Skript, nicht Duden!
über Datenstruktur LIFO + Struktogramm
Der Algorithmus von Dijkstra dient zur Lösung des single-source shortest-path problem. Wichtig ist, daß im Falle eines gewichteten Graphen die
Gewichte alle positiv sind. Sonst existiert eventuell kein kürzester Weg. Die
Idee ist folgende. Sei N die Menge der Knoten und sei D ein Array mit
Entfernungen für jeden Knoten. Zu Beginn wissen wir nur, daß für den
Startknoten A der minimale Weg die Länge Null hat. Wir setzen also D[A]=0
(der Einfachheit halber indizieren wir das Array D über die Namen der
Knoten). Alle anderen Einträge in dem Array D setzen wir auf infty. Nun
weisen wir einer Variablen i den Knoten zu mit dem kleinsten Eintrag in D,
wir wählen also den Knoten den wir bis jetzt mit minimalem Aufwand erreichen
konnten. Für jede Kante vom Knoten in i zu einem anderen Knoten j prüfen
wir nun folgendes, wobei die Funktion edge(i,j) uns das Gewicht der Kante
liefere:
- Ist D[j] > D[i] + edge(i,j), kommen wir also über den Knoten in i
mit weniger Aufwand zu dem Knoten in j als mit allen bisher berechneten
Möglichkeiten, dann setzten wir D[j] = D[i] + edge(i,j).
- Falls obiges nicht der Fall ist, wir haben also schon einen kürzeren Weg
zum Knoten in j gefunden, dann ändern wir den Wert in D[j] natürlich
auch nicht.
Jetzt entfernen wir den Knoten aus der Menge N der Knoten und suchen uns wie
oben ein neues i. Der Algorithmus terminiert, wenn N leer ist, wir also
kein neues i mehr wählen können. Etwas mehr MODULA-like sieht das ganze so
aus:
N Menge der Knoten
D Array von Entfernungen
A Startknoten
i,j Variablen vom Typ Knoten
D[A] := 0;
D[i] := INFTY für alle i aus N außer A;
(*) wenn N leer ist dann ENDE;
wähle i aus N mit min(D[i]);
für jede Kante von i zu irgendeinem Knoten j aus N prüfe
wenn D[j] > D[i] + edge(i,j) dann
D[j] := D[i] + edge(i,j);
entferne i aus N;
zurück zu (*);
Weit ausführlichere Erläuterungen finden sich im Skript auf Seite 47ff und in
Aho/Ullman, Foundations of computer science, Seite483ff, wobei letzteres
äußerst lesenswert ist.
Unter einer Dreiecksmatrix versteht man eine Matrix die nur auf einer Seite
der Hauptdiagonalen Einträge besitzt die verscheiden von Null sind. Jenachdem
ob es sich dabei um die obere oder untere Hälfte handelt spricht man von einer
oberen oder unteren Dreiecksmatrix.
Ein Knoten k_n in einem Graphen heißt erreichbar bezüglich eines Startknotens
k_0, wenn eine Folge k_0,k_1,...,k_n von Knoten existiert wobei
jeweils gelten muß, daß zwischen k_i und k_{i+1} (für i=0...n-1)
eine Kante in dieser Richtung existiert.
Der Floyd-Warshall-Algorithmus dient zur Lösung des all pairs
shortest path problems, also dem Finden der Länge der jeweils kürzesten
Pfade zwischen allen Knoten in einem Graphen. Der Algorithmus existiert in
zwei Versionen, wobei die erste von Warshall lediglich die Existenz eines
Pfades zwischen zwei Knoten bestimmt und die zweite, von Floyd, dazu auch noch
die "Kosten" eines Pfades bestimmt, was ja nur in gewichteten Graphen von
Interesse ist. Die Laufzeit liegt in der Größenordnung O(n^3),
womit sie nicht besser ist als ein Anwenden des Dijkstra-Algorithmus auf
alle Paare. Allerdings ist der Floyd-Warshall-Algorithmus sehr einfach zu
implementieren.
Beide Algorithmen arbeiten mit Adjazenzmatrizen. Es sei zunächst die
Arbeitsweise des Algorithmus mit der Berechnung der Pfadlängen
beschrieben. Die Grundidee ist, nach und nach jeden Knoten u zu betrachten
und zwar so, daß man für alle Paare v, w von Knoten jetzt überprüft, ob
die Summe der Kosten für die Strecken v->u und u->w
kleiner ist als die bis jetzt berechneten Kosten k für die Strecke
v->w. Falls ja, so ersetzt man k durch diese Summe.
Es folgt eine MODULA-2 ähnliche Beispielimplementierung des
Algorithmus. NODE sei dabei der Typ der Knoten, aber der Einfachheit
halber identifizieren wir ihn mit den Zahlen 1...n. Sei weiter
adjm ein n×n Array, das die Adjazenzmatrix des betrachteten
Graphen
repräsentiert, in der Diagonalen stehen also Nullen und an allen anderen
Stellen das Gewicht der Kanten zwischen den Knoten oder INFTY, ein
ausgezeichneter Wert, falls keine Kante existiert. dist ist ein
ähnliches Array in dem wir die minimalen Entfernungen zwischen den Knoten
berechnen.
Zunächst wird der Inhalt von adjm nach dist kopiert, wir
initialisieren dist also mit dem, was wir schon wissen. Dann nahmen wir
in der äußeren Schleife mit u jeden Knoten ran und betrachten in den inneren
Schleifen mit v und w alle Paare von Knoten. Dann testen wir, ob der Pfad
von v nach w über u kürzer ist als der bisher in dist berechnete Wert
für diesen Pfad. Falls ja, so merken wir uns diesen Wert in dist.
PROCEDURE Floyd;
VAR u, v, w : NODE;
BEGIN
(* Initialisierung *)
FOR v := 1 TO n DO
FOR w:= 1 TO n DO
dist[v,w] := adjm[v,w];
END;
END;
FOR u := 1 TO n DO
FOR v := 1 TO n DO
FOR w := 1 TO n DO
(*) IF dist[v,w] > dist[v,u] + dist[u,w] THEN
dist[v,w] := dist[v,u] + dist[u,w];
END;
END;
END;
END;
END Floyd;
Wenn wir nur an der Frage interessiert sind, ob ein Pfad zwischen zwei Knoten
existiert reicht es aus die Arrays adjm und dist als boolesche
Matrizen zu implementieren. Die IF-Abfrage an der Stelle (*)
ändern wir dann zu
IF not dist[v,w] THEN
dist[v,w] := dist[v,u] and dist[u,w];
END;
Daß diese beiden Algorithmen das gewünschte leisten, macht man sich leicht an
einem Beispiel klar (nach Foundations of Computer Science, Aho/Ullman).
Ein binärer Baum heißt geordnet, wenn bezüglich einer Ordungsrelation
gilt, daß alle Elemente im linken (rechten)
Unterbaum kleiner als das Element im Knoten bezüglich der Relation sind und
alle Elemente im rechten (linken) Unterbaum größer.
Lokale Optimierung führt bekanntlich nicht immer zur global optimalen
Lösung. Wir müssen dazu die Menge aller potentiellen Lösungen betrachten
und unter diesen das Optimum bestimmen. Auch bei der globalen Optimierung
durchsuchen wir Schritt für Schritt den Suchraum. Wir setzen
jedoch voraus, daß der Suchraum keine Sackgassen enthält bzw. daß wir
Möglichkeiten haben, aus diesen zu entkommen, um weiter nach der optimalen
Lösung zu suchen. Für den baumartigen Suchraum sind zum Beispiel
Backtracking (mittels Tiefensuche) oder Branch-And-Bound (mittels Breitensuche)
Möglichkeiten zur globalen Optimierung.
Bei der globalen Optimierung wird aus der Menge aller möglichen Lösungen die
optimale Lösung anhand eines globalen Kriteriums bestimmt. Dies kann nötig
werden, weil lokale Entscheidungskriterien nicht mit Sicherheit die optimale
Lösung, wohl aber die Menge aller möglichen Lösungen liefern.
Als Grad eines Knotens bezeichnet man die Anzahl der von ihm ausgehenden und
bei ihm ankommenden Kanten. Bei ungerichteten Graphen macht das ja bekanntlich
keinen Unterschied. Bei gerichteten Graphen unterscheidet man noch zwischen
Eingangs- und Ausgangsgrad und unterscheidet so, ob eine Kante einen Knoten
verläßt oder zu ihm hinführt.
Ein Graph besteht aus einer Menge von Knoten und einer Menge von Kanten, die die Knoten miteinander verbinden. Man unterscheidet gerichtete und ungerichtete Graphen. Wenn zwei Knoten A und B durch eine Kante verbunden sind, ist es bei ungerichteten Graphen möglich, sowohl über diese Kante von A nach B zu gelangen, als auch von B nach A. Bei gerichteten Graphen erlaubt der Aufbau das Abschreiten nur in bestimmten Richtungen.
In der Informatik spielen Graphen eine große Rolle bei der Darstellung von Datenstrukturen.
formale Definition; knoten- und kantenbewertete Graphen; Beispiel
[engl. gierig, eifrig] Prinzip zur lokalen Optimierung, bei dem man den nächsten Schritt im Suchraum so wählt, daß ein maximaler Vorteil entsteht. Im Gegensatz zu Backtracking und Branch-and-Bound haben "greedy" Algorithmen meist nur linearen bis maximal quadratischen Aufwand. Bei einem ungünstigem Kriterium führen sie jedoch nicht immer zur global optimalen Lösung.
Beispiel zu greedy: Spannbaumproblem
Gegeben ist ein zusammenhängender, ungerichteter Graph, bei dem jede Kante
mit einem positiven Kostenwert versehen ist. Das Problem besteht darin,
einen Graphen zu konstruieren bei dem die Summe der Kosten aller seiner
Kanten minimal ist, der aber immer noch zusammenhängend ist.
Dieses Problem tritt in der Praxis zum Beispiel bei der Verdratung von
Terminals oder beim Aufbau von Netzwerken auf. Man löst es theorethisch,
indem man zuerst die kostengünstigste Kante wählt und dann bei jedem
weiteren Schritt von den übrigen Kanten die kostengünstigste auswählt. Die ausgewählte Kante darf
jedoch nicht zu einem Zyklus führen, sonst wird die nächstteurere ausgewählt.
Ein Kreis ist ein Weg in einem Graphen mit gleichem Anfangs- und Endpunkt.
Strategie zum Erreichen einer guten bis bestmöglichen Lösung für einen Algorithmus. Auf dem Weg durch den Suchraum wird bei jedem Schritt nach einem bestimmten Kriterium entschieden, in welche Richtung weitergesucht wird. Dieses Kriterium garantiert, daß die Suche möglichst zu einer global optimalen Lösung führt.
Leider mag der Konverter für HTML nicht alle Befehle der Matheumgebung. Schaut Euch deshalb an dieser Stelle die ausdruckbare PostScript-Datei an.
Der Strassen-Algorithmus entstand aus der Motivation, die Berechnung der
Matrixmultiplikation mit Rechenanlagen zu beschleunigen (rechnet man von Hand,
so verschwendet man Zeit...). Er ist nur anwendbar auf quadratische Matrizen
und spart Zeit dadurch, daß er mehr Additionen anstelle von Multiplikationen
benötigt, welche ja bekanntlich schneller zu berechnen sind. Der Beweis, warum
es geht wie unten beschrieben, findet sich in den Vorlesungsunterlagen,
Abschnitt 3, Seite 230f. Es gelingt mit dem Algorithmus das Produkt zweier
quadratischer Matrizen in der Zeitkomplexität O(n^{log 7})
zu
berechnen.
Zum Verfahren: Die Grundlage bildet die Möglichkeit das Produkt zweier
2×2 Matrizen mit 7 Multiplikationen und 15 Additionen zu
berechnen. Es gilt:
...Leider mag der Konverter für HTML nicht alle Befehle der Matheumgebung. Schaut Euch deshalb an dieser Stelle die ausdruckbare PostScript-Datei an.
Anzahl aller möglichen und unmöglichen Lösungen für ein Problem. Der Suchraum kann dabei nach bestimmten Kriterien vorsortiert sein. Um eine bestimmte Lösung zu finden, wird der Suchraum Schritt für Schritt durchsucht bis sie gefunden ist. Ist der Suchraum dabei baumartig aufgebaut, gehen wir zur Suche an den Kanten entlang, um den Pfad zu der Lösung zu finden.
Möglichkeit der Lösungsfindung in einem Suchbaum. Dabei betrachtet man
einen Knoten X, dessen Unterbäume nacheinander vollständig abgearbeitet
werden. Dabei kann jeder Unterbaum wieder Knoten enthalten, von dem mehrere
Unterbäume ausgehen, welche wiederum nacheinander vollständig
abgearbeitet werden usw. bis wir zu einer Lösung
gelangen oder alle Unterbäume von X bearbeitet sind, ohne eine Lösung zu
finden. Erst danach gilt der Knoten als "erledigt". Ein Verfahren zur
Tiefensuche ist zum Beispiel Backtracking.
über Datenstruktur FIFO + Struktogramm
Das transponierte einer Matrix A (man bezeichnet es üblicherweise durch
A^t) erhält man indem man die Zeilen der Matrix als Spalten schreibt. Es
gelten insbesondere folgende Regeln:
(A^t)^t = A
det A = det A^t
(A + B)^t = A^t + B^t
(AB)^t = B^t A^t
(lambdaA)^t = lambdaA^t
Die Liste der zu passierenden Kanten auf der Strecke zwischen zwei verbundenen Knoten nennt man Weg bzw. Pfad.
genauer; Bezug zu Graph
Ein ungerichteter Graph heißt zusammenhängend, wenn jeder Knoten von jedem anderen aus erreichbar ist. Ist der Graph gerichtet, spricht man bei gleicher Voraussetzung von stark zusammenhängenden Graphen.
Ein Pfad (oder Weg) heißt zyklenfrei, wenn er keine zwei gleichen Knoten
enthält. Ein Graph heißt zyklenfrei, wenn er nur zyklenfreie Pfade zuläßt. Bei
ungerichteten Graphen muß die Definition etwas geändert werden, da man ja die
Kanten in beide Richtungen durchlaufen kann und sofort einen Zyklus der Länge
zwei erzeugen kann. Ungerichtete Graphen heißen zyklenfrei, wenn es keine
Pfade mit mehr als zwei Kanten gibt, die zyklisch sind (d.h. also, wenn ich
nach den ersten Schritt von einem Knoten nicht gleich zurückgehe, kann ich ihn
nicht mehr erreichen).
xantippe@cs.tu-berlin.de