Kategorie: Mathematik > Informatik
Datum & Land: 01/01/1996, De.
Wörter: 29

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, dam...

Adjazenzliste
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.

Adjazenzmatrix
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 Verbindun...

aufspannender Baum
Die Menge derjenigen Kanten, die beim Traversieren durchlaufen wurden, nennt man aufspannende Bäume. was wird traversiert; Hinweis auf Traversierung mittels Tiefen- und Breitensuche

Backtracking
[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 d...

Baum
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, eb...

Binärbaum
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-And-Bound
[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. ...

Breitensuche
über Datenstruktur LIFO + Struktogramm

Dijkstra-Algorithmus
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...

Dreiecksmatrix
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.

erreichbar
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.

Floyd-Warshall-Algorithmus
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, daz...

geordneter Binärbaum
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.

Globale Optimierung
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ö...

Grad eines Knotens
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.

Graph
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 gericht...

greedy
[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...

Index
Adjazenzliste Adjazenzmatrix aufspannender Baum Backtracking Baum Binärbaum Branch-And-Bound Breitensuche Dijkstra-Algorithmus Dreiecksmatrix erreichbar Floyd-Warshall-Algorithmus geordneter Binärbaum Globale Optimierung Grad eines Knotens Graph greedy Kreis/Zyklus Lokale Optimierung Matrixmultiplikation Strassen-Algorithmus Suchraum Tiefensuche tr...

Kreis/Zyklus
Ein Kreis ist ein Weg in einem Graphen mit gleichem Anfangs- und Endpunkt.

Lokale Optimierung
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.

Matrixmultiplikation ("normal")
Leider mag der Konverter für HTML nicht alle Befehle der Matheumgebung. Schaut Euch deshalb an dieser Stelle die ausdruckbare PostScript-Datei an.

Strassen-Algorithmus
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...

Suchraum
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ösu...

Tiefensuche
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 U...

transponierte Matrix
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

Weg/Pfad
Die Liste der zu passierenden Kanten auf der Strecke zwischen zwei verbundenen Knoten nennt man Weg bzw. Pfad. genauer; Bezug zu Graph

zusammenhängende und stark zusammenhängende Graphen
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.

zyklenfreier Weg/Graph
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 h...