Algorithmen und Datenstrukturen
Dr. Beatrice Amrhein
9. Februar 2015
ii
¨
Zur umfassenden Ausbildung eines Software-Ingenieurs gehoren
grundlegende Kenntnisse der wichtigsten Datenstrukturen und wie man diese verarbeitet (Algorithmen). Das Kennen von geeigneten Datenstrukturen hilft dem Programmierer, die Informationen richtig zu organisieren und besser strukturierte
Programme zu schreiben.
Lerninhalte
-
Abstrakte Datentypen, Spezifikation
¨ von Algorithmen,
Komplexitat
Algorithmen-Schemata: Greedy, Iteration, Rekursion
¨
Wichtige Datenstrukturen: Listen, Stacks, Queues, Baume,
Heaps
Suchen und Sortieren, Hash-Tabellen
¨ Sprachen, Pattern Matching
Endliche Automaten, regulare
Kontextfreie Grammatiken, Parser
Lernziele
Die Studierenden kennen die wichtigsten Datenstrukturen mit ihren Methoden. Sie kennen die klassi¨
¨
¨
¨
schen Algorithmen und konnen
sie anwenden. Ausserdem knnen
sie Komplexitatsabsch
atzungen
von
Algorithmen vornehmen.
Informationen zum Unterricht
Grundlage ist ein Skript, das die wichtigsten Lerninhalte umfasst.
Unterrichtssprache: Deutsch (Fachliteratur zum Teil in Englisch)
¨
¨
Umfang: 12 halbtagige
Blocke
a` 4 Lektionen
Dozentin: Beatrice Amrhein,
Empfohlene Literatur:
- Reinhard Schiedermeier Programmieren mit Java, Eine methodische Einfuhrung.
Pearson Studi¨
um ISBN 3-8273-7116-3.
- Robert Sedgewick Algorithms in Java. Addison-Wesley Professional; 2002 ISBN 978-0-20136120-9
- M. T. Goodrich & R. Tamassia Algorithm Design: Foundations, Analysis, and Internet Examples.
John Wiley & Sons, Inc.
ISBN: 0-471-38365-1.
- Gunter Saake, Kay-Uwe Sattler Algorithmen und Datenstrukturen, Eine Einfuhrung
mit Java.
¨
dpunkt, 2004. ISBN 3-89864-255-0.
Inhaltsverzeichnis
1
Einfuhrung
¨
1-1
1.1 Die wichtigsten Ziele dieses Kurses . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1-1
1.2 Einige Begriffe: Datenstrukturen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1-2
1.3 Einige Begriffe: Algorithmen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1-9
1.4 Algorithmen Schema: Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1-12
1.5 Algorithmen Schema: Greedy (die gierige Methode) . . . . . . . . . . . . . . . . . . . . 1-12
1.6 Algorithmen Schema: Rekursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1-15
¨
1.7 Ubung
1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1-20
2
3
¨ von Algorithmen
Komplexitat
¨
2.1 Komplexitatstheorie
. . . . . . . .
¨
2.2 Komplexitatsanalyse
. . . . . . . .
¨ . . . . .
2.3 Asymptotische Komplexitat
¨
2.4 Ubung
2 . . . . . . . . . . . . . .
2-1
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
2-1
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
2-2
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
2-5
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
2-9
Datentypen: Listen, Stacks und Queues
3-1
3.1 Array Listen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3-1
3.2 Doppelt verkettete Listen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3-5
3.3 Stacks und Queues
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-11
3.4 Iteratoren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-13
¨
3.5 Ubung
3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-14
4
¨
Datentypen: Baume,
Heaps
4-1
¨
4.1 Baumdurchlaufe
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4-4
¨ Suchbaume
¨
4.2 Binare
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4-8
¨
4.3 B-Baume
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4-10
4.4 Priority Queues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4-15
¨
4.5 Ubung
4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4-21
5
Suchen
5-1
5.1 Grundlagen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5-1
5.2 Lineare Suche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
¨ Suche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.3 Binare
5-2
5-3
5.4 Hashing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5-5
¨
5.5 Ubung
5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5-14
6
Sortieren
6-1
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6-2
6.2 Insertion Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6-4
6.3 Divide-and-Conquer Sortieren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6-5
6.4 Quicksort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6-6
6.1 Selection Sort
iv
Inhaltsverzeichnis
6.5 Sortieren durch Mischen (Merge Sort) . . . . . . . . . . . . . . . . . . . . . . . . . . . 6-9
¨
6.6 Ubung
6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6-12
7
Pattern Matching
7-1
¨ Ausdrucke
7.1 Beschreiben von Pattern, Regulare
¨
. . . . . . . . . . . . . . . . . . . . . .
7-1
7.2 Endliche Automaten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7-3
¨
7.3 Automaten zu regularen
Ausdrucken
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 7-7
¨
¨
7.4 Ubung
7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7-10
8
Top Down Parser
8.1 Kontextfreie Grammatik
8-1
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8-2
8.2 Top-Down Parser . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8-7
¨
8.3 Ubung
8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8-14
9
Kryptologie
9-1
9.1 Grundlagen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9-2
9.2 Einfache Verschlusselungmethoden
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
¨
9-3
9.3 Vernamchiffre, One Time Pad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9-5
9.4 Moderne symmetrische Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9-6
9.5 Asymmetrische Verfahren: Public Key Kryptosysteme . . . . . . . . . . . . . . . . . . . 9-7
¨
9.6 Ubung
9 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9-12
1
Einfuhrung
¨
1.1 Die wichtigsten Ziele dieses Kurses
Die wichtigsten Ziele des Algorithmen und Datenstrukturen Kurses sind:
¨
• Die Studierenden kennen die wichtigsten Datenstrukturen, konnen
damit arbeiten, und kennen deren
Vor- und Nachteile sowie deren Anwendungsgebiete.
¨
• Die Studierenden erhalten die Grundlagen, um wahrend
der Design Phase die richtigen Datenstruk¨
turen auszuwahlen
und dann richtig einzusetzen.
¨
• Die Studierenden kennen die wichtigsten Komplexitatsklassen
und deren Einfluss auf das Laufzeitverhalten eines Systems.
¨
• Die Studierenden kennen die klassischen Algorithmen und konnen
diese anwenden. Sie kennen
•
¨
deren Einsatzgebiete (wann soll welcher Algorithmus benutzt werden) und kennen die Komplexitat
¨
dieser Algorithmen (in Abhangigkeit
der darunterliegenden Datenstrukturen).
¨
¨
Die Studierenden erhalten einen Uberblick
uber
verschiedene Vorgehensweisen bei Problemlosun¨
¨
¨
gen und kennen deren Starken
und Schwachen.
1-2
1 Einfuhrung
¨
1.2 Einige Begriffe: Datenstrukturen
Definition: Daten sind Information, welche (maschinen-) lesbar und bearbeitbar sind und in einem Bedeutungskontext stehen. Die Information wird dazu in Zeichen oder Zeichenketten codiert. Die Codierung
¨ klarer Regeln, der sogenannten Syntax.
erfolgt gemass
Daten sind darum Informationen mit folgenden Eigenschaften:
¨ den semantischen Teil (die Bedeutung) des Datenobjekts.
1. Die Bezeichnung erklart
2. Die Wertemenge bestimmt die Syntax (die Form oder Codier-Regel) des Datenobjekts.
3. Der Speicherplatz lokalisiert das Datenobjekts im Speicher und identifiziert dieses eindeutig.
Definition: Ein Datentyp ist eine (endliche) Menge (der Wertebereich des Typs) zusammen mit einer
Anzahl Operationen.
Der Wertebereich eines Datentyps bestimmt, was fur
¨ Werte ein Objekt dieses Typs annehmen kann. Die
Elemente des Wertebereichs bezeichnet man auch als Konstanten des Datentyps.
¨
Dazu gehoren
die Methoden oder Operatoren, welche auf dem Wertebereich definiert sind und somit
¨
auf Objekte dieses Typs angewandt werden konnen.
Beispiel:
Der Wertebereich des Datentyps int besteht aus
Auf diesem Datentyp gibt es die Operationen
Es ist wichtig, dass wir zwischen der (abstrakten) Beschreibung eines Datentyps (Spezifikation) und
¨
dessen Implementierung unterscheiden. Wenn wir komplizierte Probleme losen
wollen, mussen
wir von
¨
¨
den Details abstrahieren konnen.
Wir wollen nicht wissen (mussen)
wie genau ein Datentyp implementiert
¨
¨
ist, sondern bloss, wie wir den Datentyp verwenden konnen
(welche Dienste er anbietet).
1.2 Einige Begriffe: Datenstrukturen
1-3
Jedes Objekt besitzt einen Datentyp, der bestimmt, welche Werte dieses Objekt annehmen kann und welche Operationen auf diesen Werten erlaubt sind. In allen Programmiersprachen gibt es nun Variablen,
¨
¨
welche diese Objekte reprasentieren
konnen.
Es stellt sich nun die Frage, ob auch den Variablen zwingend ein Datentyp zugewiesen werden soll. Diese Frage wird in verschiedenen Programmiersprachen
unterschiedlich beantwortet.
In untypisierten Sprachen wird den Variablen keinen Datentyp zugeordnet. Das heisst, jede Variable
¨
kann Objekte von einem beliebigen Typ reprasentieren.
Die Programmiersprachen Smalltalk und Lisp
¨
sind typische Reprasentanten
dieser Philosophie.
In untypisierten Sprachen kann der Compiler keine sogenannten Typentests durchfuhren.
Zur Kompi¨
¨
lationszeit sind alle Operationen auf allen Variablen moglich.
Es wird also zur Compilationszeit nicht
nachgepruft,
erlaubt sind. Unerlaubte Operationen fuhren
zu Lauf¨ ob gewisse Operationen uberhaupt
¨
¨
zeitfehlern.
In typisierten Sprachen wird allen Variablen ein Datentyp zugeordnet. Entweder mussen
alle Variablen
¨
deklariert werden, wie in den Sprachen Pascal, C, C++ oder Eiffel, oder der Datentyp wird aus der Notation der Variablen klar wie etwa in der Sprache Fortran oder Basic (in Basic sind Variablen, welche mit
dem Zeichen % enden, vom Typ Integer).
In einer typisierten Sprache kann schon der Compiler entscheiden, ob die angegebenen Operationen
typkorrekt sind oder nicht.
Als atomare Typen bezeichnen wir Datentypen, die in einer Sprache schon vordefiniert sind. Die atomaren Typen sind die grundlegenden Bausteine des Typsystems einer Programmiersprache. Aus diesen
¨
atomaren Typen konnen
mit Hilfe von Mengenoperationen (Subtypen, Kartesische Produkte, Listen, ...)
¨
¨
weitere Typen abgeleitet werden. Welche atomaren Typen zur Verfugung
stehen, hangt
von der gewahl¨
ten Programmiersprache ab.
In allen wichtigen Programmiersprachen existieren die atomaren Typen Integer (ganze Zahlen), Float (reelle Zahlen, Fliesskomma), Boolean (logische Werte) und Char (Schriftzeichen). Dabei ist zu bemerken,
dass diese atomaren Typen naturlich
nur eine endliche Teilmenge aus dem Bereich der ganzen, bzw. der
¨
¨
reellen Zahlen darstellen konnen.
1-4
1 Einfuhrung
¨
Beispiel: Der strukturierte Typ Array wird aus zwei gegebenen Datentypen, einem Grundtyp und einem
Indextyp konstruiert. Der Grundtyp ist ein beliebiger atomarer oder abgeleiteter Datentyp. Der Indextyp
ist normalerweise ein Subtyp (oder Intervall) des Typs int .
Auf Arrays ist immer ein Selektor definiert, welcher es erlaubt, ein einzelnes Element des Arrays zu lesen
oder zu schreiben.
Definition: Ein strukturierter Datentyp (eine Klasse) entsteht, wenn wir Elemente von beliebigen
Typen zu einer Einheit zusammenfassen. Ein solcher Typ ist formal gesprochen das kartesische Produkt
von beliebigen Datentypen.
DT = DT1 × DT2 × DT3 × . . . × DTn
¨
Die Datentypen DT1 , . . . , DTn konnen
atomare oder auch strukturierte Typen sein.
¨ ausserdem die Spezifikation der zugehorigen
¨
Dazu gehort
Operationen oder Methoden auf DT .
Beispiel: Wir definieren ein einfaches Interface PushButton als Basis fur
¨ einen Button auf einer Be¨
nutzeroberflache).
1.2 Einige Begriffe: Datenstrukturen
1-5
Abstrakter Datentyp
Der abstrakte Datentyp ist ein wichtiges Konzept in der modernen Informatik: Die Philosophie der objektorientierten Sprachen basiert genau auf dieser Idee. Der abstrakte Datentyp dient dazu, Datentypen
¨
unabhangig
von deren Implementation zu definieren.
Die Idee des abstrakten Datentyps beruht auf zwei wichtigen Prinzipien: dem Geheimnisprinzip und dem
Prinzip der Wiederverwendbarkeit.
Geheimnisprinzip: Dem Benutzer eines Datentyps werden nur die auf diesem Datentyp erlaubten Operationen (mit deren Spezifikation) bekanntgegeben. Die Implementation des Datentyps bleibt fur
¨ den
Benutzer verborgen (abstrakt, Kapselung).
Die Anwendung dieses Prinzips bringt folgende Vorteile:
¨
• Der Anwender kann den Datentyp nur im Sinne der Definition verwenden. Er hat keine Moglichkeit,
Eigenschaften einer speziellen Implementation auszunutzen.
¨
• Die Implementation eines Datentyps kann jederzeit verandert
werden, ohne dass die Benutzer des
Datentyps davon betroffen sind.
• Die Verantwortungen zwischen dem Anwender und dem Implementator des Datentyps sind durch
die Interface-Definitionen klar geregelt. Die Suche nach Fehlern wird dadurch erheblich vereinfacht.
Wiederverwendbarkeit: Ein Datentyp (Modul) soll in verschiedenen Applikationen wiederverwendbar
¨
¨ werden mussen.
sein, wenn ahnliche
Probleme gelost
¨
Die Idee hinter diesem Prinzip ist klar. Es geht darum, die Entwicklungszeit von Systemen zu reduzieren.
Das Ziel ist, Softwaresysteme gleich wie Hardwaresysteme zu bauen, das heisst, die einzelnen Komponenten eines Systems werden eingekauft, eventuell parametrisiert und zum Gesamtsystem verbunden.
1-6
1 Einfuhrung
¨
Ein abstrakter Datentyp definiert einen Datentyp nur mit Hilfe des Wertebereichs und der Menge der
Operationen auf diesem Bereich. Jede Operation ist definiert durch ihre Spezifikation, also die Input- und
Output-Parameter und die Vor- und Nachbedingungen.
¨
Die Datenstruktur ist dann eine Instanz eines (abstrakten) Datentyps. Sie beinhaltet also die Reprasentation der Daten und die Implementation von Prozeduren fur
¨ alle definierten Operatoren.
Wir sprechen hierbei auch von der logischen, bzw. der physikalischen Form von Datenelementen. Die
Definition des abstrakten Datentyps ist die logische, deren Implementation die physikalische Form des
Datenelements.
Der abstrakte Datentyp spezifiziert einen Typ nicht mit Hilfe einer Implementation, sondern nur als eine
Liste von Dienstleistungen, die der Datentyp dem Anwender zur Verfugung
stellt. Die Dienstleistungen
¨
nennt man auch Operationen, Methoden oder Funktionen.
Ein abstrakter Datentyp kann viele verschiedene Implementationen oder Darstellungen haben. Der abstrakte Datentyp gibt darum nicht an, wie die verschiedenen Operationen implementiert oder die Daten
¨
reprasentiert
sind. Diese Details bleiben vor dem Benutzer verborgen.
Beispiel: Der abstrakte Datentyp Stack wird durch die Menge der angebotenen Dienste definiert: Einfugen
eines Elements (push ), entfernen eines Elements (pop ), lesen des obersten Elements (peek ) und
¨
prufen
auf leer (empty ).
¨
Eine solche Beschreibung berucksichtigt
also nur, was ein Stack dem Anwender zu bieten hat.
¨
Bei den verschiedenen Methoden muss stehen, was die Methoden tun oder bewirken (Nachbedingung)
¨
und was fur
Vorbedingungen) an die Verwendung der Methoden
¨ Voraussetzungen (Einschrankungen,
gestellt sind.1
¨
In Java konnte
ein Interface fur
¨ einen Stack wie folgt aussehen:
1 Optimalerweise steht noch dabei, welchen Aufwand die Methode hat.
1.2 Einige Begriffe: Datenstrukturen
1-7
public interface Stack<E> {
/**
* Pushes an item onto the top of this stack.
* @param item
the item to be pushed onto this stack.
* @return the item argument.
*/
E push(E item);
/**
* Removes the object at the top of this stack and returns that
* object as the value of this function.
* @return
The object at the top of this stack (the last
*
item of the Vector object).
* @exception EmptyStackException if this stack is empty.
*/
E pop();
/**
* Looks at the object at the top of this stack without removing
* it from the stack.
* @return
the object at the top of this stack (the last
*
item of the Vector object).
* @exception EmptyStackException if this stack is empty.
*/
E peek();
/**
* Tests if this stack is empty.
* @return true if and only if this stack contains no items;
*/
boolean empty();
}
Bei den Methoden push und empty gibt es keine Vorbedingungen. Die Methoden pop und peek werfen
eine Runtime-Exception, wenn der Stack leer ist.
1-8
1 Einfuhrung
¨
¨
¨
Die Spezifikation eines Datentyps muss vollstandig,
prazise
und eindeutig sein. Weiter wollen wir keine
Beschreibung, die auf der konkreten Implementation des Datentyps basiert, obwohl diese die geforderten
¨
Kriterien erfullen
wurde.
Eine Beschreibung, die auf der Implementation basiert, fuhrt
zu einer Uberspe¨
¨
¨
zifikation des Datentyps.
¨
Konkret konnen
wir den Datentyp Stack zum Beispiel als Arraystruktur (mit einem Zeiger auf das aktuelle
oberste Element head des Stacks) implementieren. Flexibler ist allerdings die Implementation mit Hilfe
einer Listenstruktur..
1.3 Einige Begriffe: Algorithmen
1-9
1.3 Einige Begriffe: Algorithmen
Ein Algorithmus2 beschreibt das Vorgehen oder eine Methode, mit der eine Aufgabe oder ein Problem
¨ werden kann, bzw. mit der eine Funktion berechnet werden kann. Ein Algorithmus besteht aus
gelost
¨
einer Folge von einfachen (Rechen-)Schritten (Anweisungen), welche zur Losung
der gestellten Aufgabe
fuhren.
Der Algorithmusgedanke ist keine Besonderheit der Informatik. In fast allen Naturwissenschaften
¨
¨
aber auch im Alltag werden Arbeitsvorgange
mit Hilfe von Algorithmen beschrieben.
Jeder Algorithmus muss die folgenden Eigenschaften erfullen:
¨
1. Er muss aus einer Reihe von konkret ausfuhrbaren
¨
Schritten bestehen.
2. Er muss in einem endlichen Text beschreibbar sein.
¨
3. Er darf nur endlich viele Schritte benotigen
(Termination).
¨
4. Er darf zu jedem Zeitpunkt nur endlich viel Speicherplatz benotigen.
5. Er muss bei der gleichen Eingabe immer das selbe Ergebnis liefern.
¨
6. Nach der Ausfuhrung
eines Schrittes ist eindeutig festgelegt, welcher Schritt als nachstes
auszufuh¨
¨
ren ist.
7. Der vom Algorithmus berechnete Ausgabewert muss richtig sein (Korrektheit).
Bemerkung: Die Forderung nach Eindeutigkeit wird etwa in parallelen oder probabilistischen Algorith¨
men zum Teil fallengelassen. Nach dem Abschluss eines einzelnen Schrittes ist der nachste
Schritt nicht
¨
¨
eindeutig bestimmt, sondern es existiert eine endliche Menge von (moglichen) nachsten Schritten. Die
¨
Auswahl des nachsten
Schrittes aus der gegebenen Menge ist nichtdeterministisch.
Der Anspruch, dass alle Algorithmen terminieren mussen,
bedeutet, dass nicht alle von uns benutzten
¨
Programme Algorithmen sind. Editoren, Shells oder das Betriebssystem sind alles Programme, die nicht
(von selber) terminieren.
¨
Wir konnen
aber jedes dieser Programme als Sammlung von verschiedenen Algorithmen betrachten,
welche in verschiedenen Situationen zur Anwendung kommen.
¨ 825 vor Christus ein
ˆ
2 Das Wort Algorithmus stammt vom Persischen Autor Abu Ja’far Mohammed ibn Mus
ı, welcher ungefahr
ˆ aˆ al-Khowarizmˆ
Buch uber
arithmetische Regeln schrieb.
¨
1-10
1 Einfuhrung
¨
Algorithmen werden der Einfachheit halber oft in einer Pseudocode Sprache formuliert. Damit erspart
man sich alle technischen Probleme, welche die konkrete Umsetzung in eine Programmiersprache mit¨
bringen konnte.
¨
Beispiel: Grosster
gemeinsamer Teiler von m und n: Die kleinere der beiden Zahlen wird so lange von
¨
der grosseren
subtrahiert, bis beide Werte gleich sind. Dies ist dann der GgT von m und n.
Initialisiere m und n
Wiederhole solange m und n nicht gleich sind
Ja
Ist m > n ?
Verringere m um n
Verringere n um m
Gib m aus
Siehe auch [4]: Programmieren in Java, Kapitel 3.
Beispiele von Algorithmen in Java
int proc( int n )
{
return n/2;
}
bool isPrim( int n )
{
return false;
}
//
Nein
return true if n is a prime
1.3 Einige Begriffe: Algorithmen
¨
Das nachste
Beispiel stammt von L. Collatz (1937):
long stepNum( long n )
{
// return number of steps
long m = 0;
while( n > 1 )
{
if( n%2 == 0 ){ n = n/2; }
else { n = 3*n + 1; }
m++;
}
return m;
}
1-11
1-12
1 Einfuhrung
¨
1.4 Algorithmen Schema: Iteration
Unter einem Algorithmen-Schema verstehen wir ein Verfahrens-Muster oder eine allgemeine Methode,
¨ werden kann. Nicht jede Methode ist fur
mit welcher ein Problem gelost
¨ jedes Problem gleich gut geeignet. Umso wichtiger ist es also, die verschiedenen Algorithmen-Schemata zu kennen.
¨
¨
Ein Problem wird durch Iteration gelost,
falls der zugehorige
Algorithmus einen Loop (while- oder forSchleife) benutzt. Iteration ist zum Beispiel dann sinnvoll, wenn die Daten in einem Array (oder einer
3
Liste) abgelegt sind und wir mit jedem Element des Array die gleichen Schritte durchfuhren
mussen
.
¨
¨
Beispiel: Das Addieren zweier Vektoren kann wie folgt implementiert werden:
public DVector sum(DVector v1) throws VectorException {
if (v1.size != size)
throw new VectorException("Incompatible vector length");
DVector res = new DVector(size);
for (int i = 0; i < size; i++)
res.value[i] = v1.value[i] + value[i];
return res;
}
1.5 Algorithmen Schema: Greedy (die gierige Methode)
¨
¨
Greedy-Verfahren werden vor allem dann erfolgreich eingesetzt, wenn von n moglichen
Losungen
eines
¨
Problems die bezuglich
einer Bewertungsfunktion f optimale Losung
gesucht wird (Optimierungsproble¨
me).
Die Greedy-Methode arbeitet in Schritten, ohne mehr als einen Schritt voraus- oder zuruckzublicken.
Bei
¨
¨
jedem Schritt wird aus einer Menge von moglichen
Wegen derjenige ausgesucht, der den Bedingungen
des Problems genugt
¨ und lokal optimal ist.
3 Solche Algorithmen lassen sich oft auch sehr einfach parallelisieren.
1.5 Algorithmen Schema: Greedy (die gierige Methode)
1-13
Wir wollen die Arbeitsweise dieser Methode an einem anschaulichen Beispiel illustrieren. Wir nehmen
¨
an, dass jemand sich irgendwo auf einem Berg befindet und so schnell wie moglich
zum Gipfel kommen
¨
mochte.
Eine einfache Greedy-Strategie fur
¨ dieses Problem ist die folgende: Bewege dich immer entlang
¨
¨
der grossten
Steigung nach oben bis dies nicht mehr moglich
ist, das heisst, bis in allen Richtungen die
Wege nur noch nach unten fuhren.
¨
Dieser Ansatz ist in der Abbildung 1.1 dargestellt. Es ist ein typischer Greedy-Ansatz. Man schaut nicht
¨ jeweils die lokal optimale Strategie.
zuruck
¨ und wahlt
Abbildung 1.1: Hill climbing
Maximum
Lokales Maximum
Abbildung 1.2: Erreichen eines lokalen Maximums mit Greedy
In der Abbildung 1.2 sehen wir aber, dass diese Strategie nicht unbedingt zum (optimalen) Ziel fuhrt.
Hat
¨
der Berg mehrere Nebengipfel, so bleiben wir vielleicht auf einem solchen Nebengipfel stehen.
¨
¨
Bei Problemen dieser Art liefert oft nur ein exponentieller Algorithmus eine global beste Losung,
wahrend
4
¨
ein heuristischer Ansatz mit Greedy nicht immer die beste Losung
liefert, dies aber in polynomialer Zeit.
¨
Ahnliche
Probleme sind das Finden von kurzesten
Wegen, oder besten (Spiel-)Strategien, Verpackungs¨
¨
probleme (moglichst
viele verschieden grosse Kisten in einen Lastwagen packen) oder Scheduling von
verschieden langen Prozessen auf Mehrprozessor-Rechnern.
4 Eine Heuristik ist eine Richtlinie, ein generelles Prinzip oder eine Daumenregel, welche als Entscheidungshilfe benutzt werden kann.
1-14
1 Einfuhrung
¨
Ein weiteres Problem dieser Art ist das Suchen eines minimalen Pfades in einem allgemeinen Graphen.
¨
¨
Um eine optimale Losung
zu finden, mussten
wir im wesentlichen samtliche
Pfade abgehen und deren
¨
¨ das Problem viel schneller, indem er jeweils lokal
Gewichte aufschreiben. Ein Greedy-Algorithmus lost
¨
den kurzesten
(leichtesten) Pfad wahlt.
Allerdings findet man mit dieser Methode nicht unbedingt den
¨
insgesamt kurzesten
Pfad.
¨
Es existieren aber auch Probleme, bei denen der Greedy-Ansatz zum optimalen Ergebnis fuhrt.
Ein
¨
¨ das folgende Problem: Finde ein minimales (maximales) Gerust
Greedy-Algorithmus lost
¨ in einem ge¨ man jeweils die Kante, die das kleinste (grosste)
¨
wichteten Graphen. Dabei wahlt
Gewicht hat und keinen
¨
Zyklus verursacht. Der Algorithmus ist fertig, sobald ein zusammenhangender
Teilgraph entstanden ist.
9
9
3
3
7
5
6
6
5
5
x
7
5
4
4
6
8
7
6
8
7
3
5
1
8
8
7
8
8
4
3
5
1
4
y
3
7
9
5
x
1.6 Algorithmen Schema: Rekursion
1-15
1.6 Algorithmen Schema: Rekursion
Rekursion ist ein fundamentales Konzept der Informatik. Eine Prozedur heisst rekursiv, wenn sie sich
direkt oder indirekt selber aufruft. Dabei mussen
wir darauf achten, dass eine Abbruchbedingung existiert,
¨
damit die Prozedur in jedem Fall terminiert.
¨
Beispiele: Die rekursive Implementation der Fakultatsfunktion:
long factorial( int n )
{
if( n <= 1 )
return 1;
return n*factorial(--n);
}
Der rekursive Aufruf kann auch indirekt erfolgen:
int proc( int a, int b )
{
if( b-a < 5 )
return sub( b );
return a * proc(a-1, b/2)
}
int sub( int c )
{
if( c%2 == 0 )
return c*c;
return proc(c-2,c+1);
}
Bei einer rekursiven Prozedur sind die folgenden Punkte besonders zu beachten:
• Die Rekursion darf nicht unendlich sein. Es muss also in der Prozedur ein Instruktionszweig existie¨ Diesen Teil der Prozedur nennt man den Rekursionsren, der keinen Aufruf der Prozedur enthalt.
anfang. Bei indirekter Rekursion (Prozedur A ruft Prozedur B auf und B ruft wieder A auf) ist jeweils
besondere Vorsicht geboten.
• Es muss sichergestellt sein, dass die Anzahl der hintereinander ausgefuhrten
rekursiven Aufrufe
¨
(also die Rekursionstiefe) vernunftig
bleibt, da sonst zu viel Speicher verwendet wird. Beim rekursiven
¨
¨ sein.
Sortieren von n Elementen sollten zum Beispiel nur O(log(n)) rekursive Aufrufe notig
¨
• Rekursion soll dann angewandt werden, wenn die Formulierung der Losung
dadurch klarer und
¨
¨
kurzer
wird. Auch darf der Aufwand der rekursiven Losung
in der Ordnung nicht grosser
werden
¨
1-16
1 Einfuhrung
¨
¨
als der Aufwand der iterativen Losung.
Insbesondere kann die Rekursion leicht eliminiert werden,
¨ und dieser Aufruf die letzte Instruktion der
wenn die Prozedur nur einen rekursiven Aufruf enthalt
Prozedur ist (tail recursion, diese wird von einem optimierenden Compiler normalerweise automatisch eliminiert.)
Beispiel Die Fibonacci Funktion ist wie folgt definiert:
fibonacci(0)
= 1
fibonacci(1)
= 1
fibonacci(n + 2)
= fibonacci(n + 1) + fibonacci(n)
Diese Definition kann direkt in dieser Form als Rekursion implementiert werden:
Diese Implementierung fuhrt
zu einem exponentiellen Aufwand5 . Auf jeder Stufe sind zwei rekursive Auf¨
¨
¨
rufe notig,
welche jeweils unabhangig
voneinander die gleichen Funktionswerte berechnen. Eine bessere
¨
¨
Implementation (ohne Rekursion) benotigt
nur linearen Aufwand (vgl. Ubung).
1.6.1 Rekursionselimination
¨
Wie bereits vorher erwahnt,
soll Rekursion nur dann verwendet werden, wenn dadurch die Programme
¨ nicht grosser
¨
¨
einfacher lesbar werden und die Komplexitat
als die der iterativen Losung
ist.
¨
¨
Ist ein Problem durch eine (unnotig
aufwandige)
Rekursion formuliert, stellt sich die Frage, ob und wie
¨
sich die Rekursion allenfalls eliminieren lasst.
Prinzipiell kann dies durch folgendes Vorgehen versucht
werden:
¨
¨
5 Die Prozedur benotigt
zum Berechnen von fib(n) in der Grossenordnung
von 2·fib(n) rekursive Aufrufe.
1.6 Algorithmen Schema: Rekursion
1-17
Umdrehen der Berechnung (von unten nach oben).
Abspeichern der Zwischenresultate in einen Array, eine Liste oder einen Stack.
Beispiel: Gegeben ist die folgende rekursive Funktion, die wir in eine nichtrekursive Prozedur umschreiben wollen:
long rekFunction(int x, int y)
{
if( x <= 0 || y <= 0 )
return 0;
return x + y + rekFunction(x-1, y);
}
Etwas komplizierter wird die Rekursionselimination, wenn die Funktion, wie im folgenden Beispiel, von
¨
zwei Parametern abhangt:
long Pascal(int x, int y)
{
if( x <= 0 || y <= 0 )
return 1;
return Pascal(x-1, y) + Pascal(x, y-1);
}
1-18
1 Einfuhrung
¨
1.6.2 Divide and Conquer
¨
Die Divide and Conquer Methode (kurz: DAC) zerlegt das zu losende
Problem in kleinere Teilprobleme
¨
(divide) bis die Losung
der einzelnen Teilprobleme (conquer) einfach ist. Anschliessend werden die
¨
¨
Teillosungen
zur Gesamtlosung
vereinigt (merge)6 .
¨ werden,
Da das Problem in immer kleinere Teilprobleme zerlegt wird, welche alle auf die gleiche Art gelost
¨
ergibt sich normalerweise ein Losungsansatz
mit Rekursion.
Ein DAC-Algorithmus hat also folgende allgemeine Form:
void DAC( problem P ) {
¨
if( Losung
von P sehr einfach ) {
¨
return Losung(P)
// conquer
}
else {
divide( P, Teil1 , . . . ,Teiln );
return combine( DAC(Teil1 ),. . .,DAC(Teiln ) );
}
}
¨
DAC-Algorithmen konnen
grob in die beiden folgenden Kategorien unterteilt werden.
¨
• Das Aufteilen in Teilprobleme (divide) ist einfach, dafur
¨ ist das Zusammensetzen der Teillosungen
(merge) schwierig.
¨
• Das Aufteilen in Teilprobleme (divide) ist schwierig, dafur
¨ ist das Zusammensetzen der Teillosungen
(merge) einfach.
¨
Wenn sowohl das Aufteilen in Teilprobleme als auch das Zusammensetzen der Teillosungen
schwierig
ist, ist Divide and Conquer vermutlich nicht der richtige Ansatz.
¨
6 Das Divide and Conquer Schema eignet sich vor allem auch zum parallelen oder verteilten Losen
von Problemen.
1.6 Algorithmen Schema: Rekursion
1-19
Bekannte Beispiele fur
¨ Divide and Conquer sind die Sortieralgorithmen Quicksort und Mergesort.
¨ einem Pivotelement in verschiedene
Quicksort : (Hard Split Easy Join) Die Elemente werden gemass
Mengen aufgeteilt. Das Einsammeln ist dann trivial.
Mergesort : (Easy Split Hard Join) Die Elemente werden in beliebige (gleichgrosse) Mengen aufgeteilt.
Beim Einsammeln der verschiedenen (sortierten) Mengen muss nachsortiert werden.
void Sort( Menge P ) {
if( P besteht aus wenigen Elementen ) // zum Beispiel aus weniger als 10
{
verwende einfachen (linearen) Sortieralgorithmus und gib sortierte Menge zuruck
¨
}
else {
divide( P, Teil1 , . . . ,Teiln ); // Zerteile P in n Teile
// Fuge
die sortierten Mengen zusammen (trivial oder durch Nachsortieren).
¨
return merge( Sort(Teil1 ),. . .,Sort(Teiln ) );
}
}
1-20
1 Einfuhrung
¨
¨
1.7 Ubung
1
1. Nichtdeterministischer Primzahltest Das folgende Verfahren testet, ob ein Kandidat P eine Prim¨
¨
zahl ist: Wahlen
Sie eine genugend
grosse Menge beliebiger (zufalliger)
Zahlen zi und versuchen
¨
Sie nacheinander, P durch zi zu teilen. Falls keine der Zahlen zi ein Teiler ist, geben Sie true zuruck,
¨
andernfalls false.
Formulieren Sie fur
¨ das Verfahren einen Algorithmus in Pseudocode (Initialisierung, sequenzelle Anweisungen, if, while, ...)
2. Rekursionselimination: Gegeben ist die folgende Implementation der Fibonacci-Funktion:
public long fibonacci( int n ) {
if( n < 2 )
return 1;
return fibonacci(n-1) + fibonacci(n-2);
}
Finden Sie eine effizientere Implementierung ohne Rekursion fur
¨ die Berechnung der Fibonacci-Zahlen.
3. Rekursionselimination:
Eliminieren Sie aus den der folgenden Prozedur die Rekursion:
public long procRek(int n) {
if(n<=3)
return 2;
else
return 2*procRek(n-1) + procRek(n-2)/2 - procRek(n-3);
}
¨
4. Rekursion: Zahlen
der Knoten eines Baumes
Implementieren Sie eine Methode countNodes(), welche mit Hilfe einer Rekursion die Anzahl Knoten
eines Baumes berechnet.
Die Anzahl Knoten eines Baumes sind rekursiv wie folgt definiert: Wenn ein Baum nur aus einem
Blatt (leaf) besteht, dann gilt countNodes(leaf) = 1.
Sonst gilt countNodes(node) = 1 + sum(countNodes(c): c the children of node)
Rahmenprogramme finden Sie unter www.sws.bfh.ch/
∼amrhein/AlgoData/uebung1
2
¨ von Algorithmen
Komplexitat
¨
2.1 Komplexitatstheorie
¨
Nicht alle (mathematischen) Probleme (Funktionen) sind algorithmisch losbar
(berechenbar). Ausser¨
dem sind unter den berechenbaren Funktionen viele, deren Berechnung sehr aufwandig
und deshalb
undurchfuhrbar
ist.
¨
In diesem Abschnitt wollen wir nun die prinzipiell berechenbaren Probleme weiter unterteilen: in solche,
¨
die mit vernunftigem
Aufwand losbar
sind und die restlichen.
¨
Alle Funktionen
Berechenbare Funktionen
Durchführbare Algorithmen
Abbildung 2.1: Durchfuhrbare
Algorithmen
¨
¨
¨
Fur
Probleme ist es wichtig zu wissen, wieviele Betriebsmittel (Ressourcen) fur
¨ losbare
¨ ihre Losung
¨
erforderlich sind. Nur solche Algorithmen, die eine vertretbare Menge an Betriebsmitteln benotigen, sind
¨
tatsachlich
von praktischem Interesse.
¨ von Algorithmen
2 Komplexitat
2-2
¨
Die Komplexitatstheorie
stellt die Frage nach dem Gebrauch von Betriebsmitteln und versucht diese zu
beantworten. Normalerweise werden fur
¨ einen Algorithmus die Betriebsmittel Zeit- und Speicherbedarf
¨
untersucht. Mit Zeitbedarf meint man die Anzahl benotigter
Rechenschritte1 .
¨
2.2 Komplexitatsanalyse
¨
¨
Mit Hilfe der Komplexitatsanalyse
konnen
wir die Effizienz verschiedener Algorithmen vergleichen, bzw.
¨
versuchen zu entscheiden, ob ein Algorithmus das Problem im Allgemeinen innert nutzlicher
Frist lost.
¨
¨
¨
Eine Moglichkeit,
die Effizienz verschiedener Algorithmen zu vergleichen ware,
alle Algorithmen zu im¨
plementieren und die benotigte
Zeit und den Platzverbrauch zu messen. Allerdings ist dieses Verfahren
¨
¨ viel programmiert werden. Wir konnen
¨
¨
hochst
ineffektiv. Es muss unnotig
auch nicht einschatzen,
ob nicht
ein Algorithmus schlechter programmiert wurde als die anderen oder ob die Testbeispiele eventuell einen
2
Algorithmus begunstigen
.
¨
¨
¨
Auch mit Hilfe einer Komplexitatsanalyse
konnen
wir nicht wirklich entscheiden, ob ein Programm schnell
laufen wird. Vielleicht kann ein optimierender Compiler den einen Code besser unterstutzen
als den an¨
¨
¨
deren. Vielleicht sind gewisse Speicherzugriffe ubers
Netz notig,
die den Code langsam machen. Mogli¨
cherweise ist der Algorithmus auch einfach schlecht implementiert.
¨
Dennoch kann eine Komplexitatsanalyse
einen Hinweis geben, ob ein Algorithmus uberhaupt
prinzipi¨
¨
¨
¨
ell fur
der Anzahl notiger
Rechenschritte konnen
wir
¨ unser Problem in Frage kommt. Durch das Zahlen
zumindest verschiedene Algorithmen einigermassen fair vergleichen. Ein Rechenschritt besteht dabei
aus einer einfachen Operation, einer Zuweisung oder einem Vergleich (was normalerweise in einer Programmzeile steht).
Algorithmen nehmen Eingabedaten entgegen und fuhren
mit diesen eine Verarbeitung durch. Die Anzahl
¨
¨
¨
¨
Rechenschritte hangt
normalerweise von der Lange
(Grosse)
der Eingabedaten ab.
¨ gelost
¨ werden. Fur
• Ein Problem kann durch verschiedene Algorithmen mit verschiedener Komplexitat
¨
¨ werden mussen,
Probleme, welche sehr oft gelost
ist es von grossem Interesse, einen Algorithmus
¨
¨
zu finden, welcher moglichst
wenig Betriebsmittel erfordert.
¨ eines Algorithmus ist naturlich
¨
1 Die Komplexitat
unabhangig
von der Geschwindigkeit des verwendeten Computers.
¨
¨
2 Wir mussten
fairerweise alle moglichen
Eingaben testen, was naturlich
nicht machbar ist.
¨
¨
¨
2.2 Komplexitatsanalyse
2-3
¨ eines Algorithmus hangt
¨
¨
¨
• Die Komplexitat
von der Grosse
der Eingabedaten ab. Je grosser
die Di¨
mension n der Matrizen, desto langer
wird die Ausfuhrung
des Algorithmus dauern. Im Allgemeinen
¨
¨
¨ eines Algorithmus als Funktion der Lange
¨
konnen
wir die Komplexitat
der Eingabedaten angeben.
¨
Als Vereinfachung betrachten wir normalerweise nicht die (exakte) Lange
der Eingabe (zum Beispiel in
¨
Anzahl Bytes), sondern grossere,
fur
Einheiten. Man spricht dann von der naturli¨ das Problem naturliche
¨
¨
¨
¨
¨ eines Algorithmus
chen Lange
des Problems. Will man nur eine Grossenordnung
fur
¨ die Komplexitat
¨ man auch nicht alle Operationen, sondern nur diejenigen, welche fur
¨
angeben, so zahlt
des
¨ die Losung
Problems am wichtigsten (zeitintensivsten) sind. In der folgenden Tabelle sind Probleme mit ihrer naturli¨
¨
chen Lange
und ihren wichtigsten Operationen angegeben.
Problem
naturliche
Einheit
¨
Operationen
Algorithmen auf ganzen Zahlen
(z.B. Primzahlalgorithmen )
Suchalgorithmen
Sortieralgorithmen
Algorithmen auf reellen Zahlen
Matrix Algorithmen
Anzahl Ziffern
Operationen in
Anzahl Elemente
Anzahl Elemente
¨
Lange
der Eingabe
Dimension der Matrix
Vergleiche
Vergleiche, Vertauschungen
Operationen in IR
Operationen in IR
¨ der folgenden Prozeduren, indem wir die Anzahl Aufrufe von
Beispiel: Wir berechnen die Komplexitat
¨
¨
do something() (abhangig
vom Input n ) zahlen.
int proc1( int n )
{
int res = 0;
for( i = 0; i < n; i++ )
res = do_something(i);
return res;
}
int proc2( int n )
{
int res = 0;
for( i = 0; i < n; i++ )
for( j = 0; j < n; j++ )
res = do_something(i, j);
return res;
}
¨
¨
Wir verandern
die Prozedur etwas und berechnen wiederum die Komplexitat.
¨ von Algorithmen
2 Komplexitat
2-4
int proc3( int n )
{
int res = 0;
for( i = 0; i <= n; i++ )
for( j = 0; j <= i; j++ )
res = do_something(i, j);
return res;
}
¨
Wir zahlen
auch hier, wie oft do something()
aufgerufen wird.
2.2.1 Best-Case, Average-Case, Worst-Case Analyse
¨
Je nach Input kann die Anzahl benotigter
Rechenschritte sehr stark schwanken. Dies geschieht beispiels¨
weise dann, wenn die Prozedur Fallunterscheidungen (if/else) enthalt.
int proc3( int n )
{
int res = 1;
if( n % 2 == 0 )
return res;
for( int i=0; i<n; i++ )
res = do_something(res, i);
return res;
}
¨
2.3 Asymptotische Komplexitat
2-5
¨
¨
Bei Suchalgorithmen zahlen
wir die Anzahl notiger
Vergleiche.
public int indexOf( Object elem ) {
// lineare Suche, elem != null
for( int i=0; i < size; i++ ) {
if( elem.equals(elementData[i]) )
return i;
}
return -1;
}
n = size
int procRek( int n )
{
int res = do_something(n);
if( n <= 1 ) return res;
if( n % 2 == 0 )
return procRek(n/2);
return procRek(n+1);
}
¨
2.3 Asymptotische Komplexitat
¨ eines
Eine Vereinfachung ergibt sich, wenn man nur das asymptotische Verhalten der Komplexitat
¨
Algorithmus betrachtet. Das asymptotische Verhalten eines Polynoms entspricht dessem grossten
Term.
Konstante Faktoren werden dabei ignoriert.
Beispiel: In der Funktion
f (n) = 2n2 − 10n + 20
¨ fur
fallt
dem Ausdruck 2n2 immer weniger ins Gewicht.
¨ wachsendes n der Ausdruck 10n + 20 gegenuber
¨
Der dominierende Ausdruck ist in diesem Fall 2n2 .
¨ von Algorithmen
2 Komplexitat
2-6
10000
200
8000
150
6000
100
4000
50
0
2000
2
4
6
8
10
12
0
14
20
40
n
60
80
100
n
Das asymptotische Verhalten von f ist also n2 . Man schreibt auch f (n) ∈ O(n2 ) um das Wachstumsverhalten einer Funktion zu klassifizieren.
2
n
2n
1600
2
10n log(n)
1400
20 n
1200
1000
800
10 n
600
400
log(n)
200
10
20
30
40
50
Wir sagen, eine Funktion f hat exponentielles Wachstumsverhalten, wenn der dominierende Term von
f (n) von der Form kcn ist, f hat polynomiales Wachstum, falls er von der Form knc ist (c fest!), lineares
Wachstum, falls er von der Form kn ist und logarithmisches Wachstum, falls der dominierende Term von
der Form k log(n) ist.
¨
¨ nur das proportionale
Wie schon vorher erwahnt,
interessiert uns bei der asymptotischen Komplexitat
Verhalten. Die O-Notation gibt uns ein Mittel, dies mathematisch auszudrucken:
¨
¨
2.3 Asymptotische Komplexitat
2-7
Definition: [O-Notation] Eine Funktion f (n) ist aus O(g(n)), falls es Konstanten c und N gibt, so dass
fur
¨ alle m > N die Beziehung f (m) < cg(m) gilt.
Die Notation sagt genau das aus, was wir vorher schon etwas salopp formuliert hatten: Eine Funktion
¨ zu O(g(n)), falls sie (bis auf eine Konstante) nicht schneller wachst
¨
f (n) gehort
als g(n).
Man sagt auch, f hat das gleiche asymptotische Verhalten wie g.
¨
So gehoren
zum Beispiel die Funktionen 300n2 + 2n − 1, 10n + 12 und 5n3/2 + n
¨
Hingegen gehoren
die Funktionen 2n oder n3 nicht zu O(n2 ).
alle zu O(n2 ).
¨ nichts uber
Umgekehrt sagt das Wissen, dass eine Funktion f zu O(g) gehort,
die Konstanten c und
¨
¨
N aus. Diese konnen
sehr gross sein, was gleichbedeutend damit ist, dass ein Algorithmus mit dieser
¨ eventuell erst fur
(asymptotischen) Komplexitat
¨ sehr grosse Eingabewerte sinnvoll einsetzbar ist 3 .
Nachfolgend sind einige wichtige Regeln (ohne Beweis) angegeben:
• Die Ordnung des Logarithmus ist kleiner als die Ordnung einer linearen Funktion.
log(n) ∈ O(n) n ̸∈ O(log(n))
¨
• Die Ordnung eines Polynoms ist gleich der Ordnung des Terms mit der hochsten
Potenz.
ak nk + ak−1 nk−1 + . . . + a1 n + a0 ∈ O(nk )
• Fur
¨ zwei Funktionen f und g gilt:
O( f + g) = max{O( f ), O(g)}
O( f ∗ g) = O( f ) · O(g)
¨
• Die Ordnung der Exponentialfunktion ist grosser
als die Ordnung eines beliebigen Polynoms. Fur
¨ alle
c > 1 und k gilt:
cn ̸∈ O(nk )
3 Der FFT-Algorithmus fur
¨ Langzahlarithmetik ist zum Beispiel erst fur
¨ Zahlen, die mehrere hundert Stellen lang sind, interessant.
¨ von Algorithmen
2 Komplexitat
2-8
¨ der folgenden Prozeduren.
Beispiel: Wir berechnen die asymptotische Komplexitat
int proc4( int n )
{
int res = 0, m = n*n;
for( i = m; i > 1; i=i/2 )
res = do_something(res, i);
return res;
}
¨
Wir zahlen
wieder, wie oft do something()
aufgerufen wird:
¨
¨ im folgenden Beispiel. Der EinfachEine andere Methode benotigen
wir zum Berechnen der Komplexitat
heit halber nehmen wir an, n sei eine Zweierpotenz (n = 2k ).
int procRec( int n )
{
int res = 0;
if(n <= 1)
return res;
for( int i = 0; i < n; i++ )
res = do_something(res, i);
return procRec(n/2);
}
¨
Wir zahlen
wiederum, wie oft do something()
aufgerufen wird.
¨
2.4 Ubung
2
2-9
¨
2.4 Ubung
2
¨ von einfachen Prozeduren
1. Komplexiat
¨
¨ der Prozeduren 1 bis 4. Wie oft wird do something() aufgerufen? UberBerechnen Sie die Komplexitat
¨
¨
prufen
Sie Ihre Losungen,
indem Sie die Prozeduren in Java implementieren und einen Zahler
einbauen.
¨
void procedure1 ( int n )
{
for(int i=0; i<=n; i++)
do something(i,n);
for(int j=n; j>=0; j--)
do something(j,n);
}
void procedure2 ( int n )
{
for(int i=0; i<n; i++)
for(int j=0; j<2*i; j++)
do something(i,j,n);
}
void procedure3 ( int n )
{
for(int i=0; i<n; i++)
{
int j = 0;
while( j < 2*n )
{
j++;
do something(i,j,n);
}
}
}
void procedure4 ( int n )
{
int j=n;
while( j > 0 )
{
j = j/2;
do something(i,j,n);
}
}
¨ von Algorithmen
2 Komplexitat
2-10
¨ rekursiver Prozeduren
2. Komplexitat
¨ der folgenden rekursiven Prozeduren. Wie oft wird do something() ausBerechnen Sie die Komplexitat
¨
gefuhrt?
Wahlen
Sie fur
¨
¨ n eine Zweierpotenz: n = 2k .
void procRec1( int n )
{
if( n<=1 )
return;
int procRec2( int n, int res )
{
res = do_something(res, n);
if( n <= 1 )
return res;
res = procRec2(n/2, res);
res = procRec2(n/2, res);
return res;
do_something(n)
procRec1(n/2);
}
}
¨ verschiedener Java Methoden
3. Komplexitat
¨ der MeBestimmen Sie von den Java Klassen ArrayList und LinkedList die asymptotische Komplexitat
thoden
-
public
public
public
public
public
public
public
boolean contains(Object o)
E get(int index)
E set(int index, E element)
boolean add(E o)
void add(int index, E element)
E remove int(index)
boolean remove(Object o)
¨
Sie mussen
dazu die Algorithmen nicht im Detail verstehen. Es genugt,
¨
¨ die Iterationen (auch der benotig¨
¨
ten Hilfsfunktionen) zu zahlen
(wir werden diese Algorithmen in einem spateren
Kapitel noch genauer
betrachten).
3
Datentypen: Listen, Stacks und Queues
¨
Listen, Stacks und Queues konnen
entweder arraybasiert oder zeigerbasiert implementiert werden. Die
Implementierung mit Hilfe von Arrays hat den Vorteil, dass ein wahlfreier Zugriff besteht. Der Nachteil
¨
hingegen ist, dass wir schon zu Beginn wissen mussen,
wie viele Elemente die Liste maximal enthalt.
¨
¨
¨
¨
Viele Kopieraktionen sind notig,
wenn der gewahlte
Bereich zu klein gewahlt
wurde, oder wenn in der
¨
Mitte einer Liste ein Element eingefugt
werden soll.
¨ oder geloscht
Eine flexiblere Implementation bietet die Realisation von Listen mit Hilfe von Zeigerstrukturen.
3.1 Array Listen
In einer Array Liste werden die einzelnen Elemente (bzw. die Referenzen auf die Elemente) in einen Array
(vom generischen Typ E) abgelegt.
initialCapacity
E[ ] elementData
....
size
Der Vorteil von Array Listen ist der direkte Zugriff auf das n-te Element. Der Nachteil ist allerdings, dass
¨
bei jedem Einfugen
oder Loschen
von Elementen der Array (in sich) umkopiert werden muss. Ausserdem
¨
3-2
3
Datentypen: Listen, Stacks und Queues
¨
muss der Array in einen neuen, grosseren
Array umkopiert werden, sobald die initiale Anzahl Elemente
uberschritten
wird.
¨
Die ArrayList benutzt also einen Array von (Zeigern auf) Elementen E als Datenspeicher:
public class ArrayList<E> extends AbstractList<E> {
private Object[] elementData;
private int size; // The number of elements.
/** Constructs an empty list with the specified initial capacity. */
public ArrayList(int initialCapacity) { ... }
/** Returns true if this list contains no elements.
public boolean isEmpty() { ... }
*/
/** Returns the index of the first occurrence of the specified element. */
public int indexOf(Object elem) { ... }
/** Returns the element at the specified position in this list. */
public E get(int index) { ... }
/**
Inserts the element at the specified position in this list.
Shifts any subsequent elements to the right. */
public void add(int index, E element) { ... }
/**
Removes the element at the specified position in this list.
Shifts any subsequent elements to the left. */
public E remove(int index) { ... }
/** Increases the capacity of this ArrayList instance. */
public void ensureCapacity(int minCapacity) { ... }
...
}
3.1 Array Listen
3-3
¨
Im Konstruktor wird der elementData Array mit Lange
initialCapacity initialisiert:
public ArrayList(int initialCapacity) {
if (initialCapacity < 0) throw new IllegalArgumentException( ... );
elementData = new Object[initialCapacity];
}
Der Zugriff auf ein Element an einer gegebenen Stelle ist direkt und damit sehr schnell.
public E get(int index) {
if (index >= size || index < 0) throw new IndexOutOfBoundsException( ... );
return (E) elementData[index];
}
¨
Das Einfugen
von neuen Elementen in den Array hingegen ist aufwandig,
da der hintere Teil des Array
¨
umkopiert werden muss.
arrayCopy
....
add
public void add(int index, E element) {
if (index > size || index < 0) throw new IndexOutOfBoundsException(...)
ensureCapacityInternal(size + 1);
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
3-4
3
Datentypen: Listen, Stacks und Queues
¨
¨
Das Gleiche gilt fur
von Elementen aus einer ArrayList. Alle Elemente hinter dem geloschten
¨ das Loschen
Element mussen
umkopiert werden.
¨
public E remove(int index) {
if (index >= size || index < 0) throw new IndexOutOfBoundsException( ... );
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData,
index, numMoved);
elementData[--size] = null; // Let gc do its work
return oldValue;
}
Sobald der aktuell angelegte Array voll ist, muss ein neuer Datenspeicher angelegt und der gesamte
Array umkopiert werden.
public void ensureCapacity(int minCapacity) {
if (minCapacity - elementData.length > 0) // -> grow
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// copy all elements to new (larger) memory area
elementData = Arrays.copyOf(elementData, newCapacity);
}
}
3.2 Doppelt verkettete Listen
3-5
3.2 Doppelt verkettete Listen
In einer doppelt verketteten Liste besteht jedes Listenelement aus einem Datenfeld (bzw. einer Referenz
auf ein Datenfeld) (element) und zwei Zeigern (next und prev).
Als Listenelemente dient die Klasse Node.
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
Die Klasse Node ist eine innere Klasse von List und wird einzig zum Verpacken der Datenelemente
bentutzt.
3-6
3
Datentypen: Listen, Stacks und Queues
Eine (doppelt) verkettete Liste entsteht dann durch Zusammenfugen
einzelner Node Elemente. Beson¨
dere Node Elemente bezeichnen dabei den Listenanfang und das Ende.
Die Definition einer Liste sieht dann zum Beispiel wie folgt aus:
public class
transient
transient
transient
LinkedList<E> {
Node<E> first;
Node<E> last;
int size = 0;
/**
* Returns true if this list contains no elements.
*/
boolean isEmpty(){ ... };
/**
* Returns the element at the specified position in this list.
* Throws IndexOutOfBoundsException if the index is out of range.
*/
E get(int index){ ... };
/**
* Inserts the element at the specified position in this list.
* Throws IndexOutOfBoundsException if the index is out of range.
*/
void add(int index, E element){ ... };
/**
* Removes the element at position index in this list.
* Returns the element previously at the specified position.
* Throws IndexOutOfBoundsException if the index is out of range.
3.2 Doppelt verkettete Listen
*/
E remove(int index){ ... };
/**
* Returns the index of the first occurrence of the specified
* element, or -1 if this list does not contain this element.
*/
int indexOf(Object o){ ... };
. . .
}
¨
Wir betrachten hier je eine Implementation fur
¨
und fur
eines Elementes.
¨ das Einfugen
¨ das Loschen
Suchen einer bestimmten Stelle
Node<E> node(int index) {
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
3-7
3-8
Einfugen
¨
an einer bestimmten Stelle
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
}
3
Datentypen: Listen, Stacks und Queues
3.2 Doppelt verkettete Listen
void linkBefore(E e, Node<E> succ) {
final Node<E> pred = succ.prev;
// assert succ != null;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
}
void addFirst(E e) {
// oder linkFirst
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
}
public void add(E e) {
// add at the end
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
}
Am effizientesten ist also das nicht-sortierte Einfugen,
das heisst am Ende oder am Anfang.
¨
3-9
3-10
3
Datentypen: Listen, Stacks und Queues
¨
Loschen
¨
Beim Loschen
von Elementen muss gepruft
¨ werden, ob ev. first und/oder last korrigiert werden mussen.
¨
public E remove(int index) {
if(index >= 0 && index < size)
return unlink(node(index));
else
throw new IndexOutOfBoundsException( ... );
}
E unlink(Node<E> x) {
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) {
first = next;
} else {
prev.next = next;
}
if (next == null) {
last = prev;
} else {
next.prev = prev;
}
x.item = null;
size--;
return element;
}
x.prev = null;
x.next = null;
3.3 Stacks und Queues
3-11
3.3 Stacks und Queues
Ein Interface fur
¨ einen Stack hatten wir im Abschnitt 1.2 bereits gesehen. Stacks sind einfache Listen¨
strukturen, bei denen bloss am Kopf Elemente eingefugt,
gelesen, bzw. geloscht
werden durfen.
¨
¨
Wir betrachten hier die Implementation eines Stacks mit Hilfe von Zeigerstrukturen.
public class Stack<E> {
private Node<E> first;
private int size = 0;
public E push(E item) {
first = new Node<E>(item, first);
size++;
return item;
}
public E pop() {
if (size==0) throw new EmptyStackException();
Node<E> e = first;
E result = e.element;
first = e.next;
e.element = null;
e.next = null;
size--;
return result;
}
public E peek() {
if (size==0) throw new EmptyStackException();
return first.element;
3-12
3
Datentypen: Listen, Stacks und Queues
}
public boolean empty() {
return size == 0;
}
private static class Node<E> {
E element;
Node<E> next;
Node(E element, Node<E> next) {
this.element = element;
this.next = next;
}
}
}
¨
¨
In einer Queue konnen
Elemente nur am Ende angefugt
Ele¨ werden. Nur am Kopf der Queue konnen
¨
mente gelesen, bzw. geloscht
werden.
3.4 Iteratoren
3-13
3.4 Iteratoren
Auf Listenstrukturen hat man ublicherweise
eine Hilfsklasse, welche zum Durchlaufen der Liste dient. Die
¨
zwei wichtigsten Methoden von Iterator Klassen sind hasNext zum Prufen,
ob das Ende der Liste erreicht
¨
¨
ist, sowie die Methode next, welche den Inhalt des nachsten
Elements zuruckgibt.
¨
public interface Iterator<E> {
/**
* Returns true if the iteration has more elements.
*/
boolean hasNext();
/**
* Returns the next element in the iteration.
* @exception NoSuchElementException iteration has no more elements.
*/
E next();
...
}
3-14
3
Datentypen: Listen, Stacks und Queues
¨
3.5 Ubung
3
Fur
¨ die Implementationsaufgabe finden Sie Rahmenprogramme unter
www.sws.bfh.ch/∼amrhein/AlgoData/
1. List Iterator
Entwerfen Sie (ausgehend vom Rahmenprogramm) eine innere Klasse ListIterator, welche als Iterator fur
¨ die LinkedList verwendet werden kann.
Implementieren Sie dazu in der LinkedList Klasse eine innere Klasse ListIterator mit einem Konstruktor ListIterator(int index), welcher ein ListIterator Objekt erzeugt, welches an die Position index zeigt.
Implementieren Sie ausserdem die Methoden E next(), boolean hasNext(), boolean hasPrevious()
und E previous().
2. Queue
¨ dem gegebenen Interface (vgl. Rahmenprogramm).
Implementieren Sie eine Klasse Queue gemass
-
¨ LinkedList, aber ohne die Methoden der
Implementieren Sie die Queue zuerst als Liste (gemass
LinkedList zu benutzen).
-
¨ ArrayList, aber ohne die Methoden
Als zweites implemtieren Sie die Queue als Array (gemass
der ArrayList zu benutzen). In der Array-basierten Queue durfen
Sie annehmen, dass die Queue
¨
¨
nicht mehr als MAX viele Elemente enthalten muss. Uberlegen
Sie sich eine Implementierung,
¨
welche nicht nach jedem Einfugen
oder Loschen
den ganzen Array umkopiert.
¨
3. Das Collection Interface
Zeichnen Sie die Klassenhierarchie der (wichtigsten) Collection Klassen.
Zeichnen Sie die Hierarchie der Interfaces List, Queue, Set und SortedSet, sowie der Klassen ArrayList, HashSet, LinkedHashSet, LinkedList, PriorityQueue, Stack, TreeSet, Vector
4
¨
Datentypen: Baume,
Heaps
¨
Alle bisher betrachteten Strukturen waren linear in dem Sinn, dass jedes Element hochstens
einen Nach¨
folger hat. In einem Baum kann jedes Element keinen, einen oder beliebig viele Nachfolger haben. Baume
sind wichtig als Strukturen in der Informatik, da sie auch oft im Alltag auftauchen: zum Darstellen von
¨
Abhangigkeiten
oder Strukturen, als Organigramme von Firmen, als Familienstammbaum, aber auch
zum Beschleunigen der Suche.
Definition: Ein Graph ist definiert als ein Paar B = (E, K) bestehend aus je einer endlichen Menge E
von Ecken (Knoten, Punkten) und einer Menge von Kanten. Eine Kante wird dargestellt als Zweiermenge
von Ecken {x, y}, den Endpunkten der Kante.
¨
¨
Ein Baum ist ein Graph mit der zusatzliche
Einschrankung,
dass es zwischen zwei Ecken nur eine (direkte oder indirekte) Verbindung gibt1 .
¨
¨
Wir befassen uns hier zuerst vor allem mit einer besonderen Art von Baumen:
den Binarbaumen.
Ein
¨ falls jeder Knoten hochstens
¨
Baum heisst binar,
zwei Nachfolger hat.
¨
1 Ein Baum ist ein zusammenhangender
Graph ohne Zyklen.
4-2
.
¨
4 Datentypen: Baume,
Heaps
.
.
. . . .
..
. ..
¨
Definition: Ein binarer
Baum besteht aus einer Wurzel (Root) und (endlich vielen) weiteren Knoten und
verbindenden Kanten dazwischen. Jeder Knoten hat entweder keine, ein oder zwei Nachfolgerknoten.
¨
Ein Weg in einem Baum ist eine Liste von disjunkten, direkt verbunden Kanten. Ein binarer
Baum ist
¨
¨
¨
vollstandig
(von der Hohe
n), falls alle inneren Knoten zwei Nachfolger haben und die Blatter
maximal
¨
Weglange
n bis zur Wurzel haben.
¨
Jedem Knoten ist eine Ebene (level) im Baum zugeordnet. Die Ebene eines Knotens ist die Lange
des
¨
Pfades von diesem Knoten bis zur Wurzel. Die Hohe
(height) eines Baums ist die maximale Ebene, auf
der sich Knoten befinden.
¨
Ein binarer
Baum besteht also aus Knoten mit einem (Zeiger auf ein) Datenelement data , einem linken
Nachfolgerknoten left und einem rechten Nachfolgerknoten right .
left
public class BinaryTreeNode<T> {
protected T data;
protected BinaryTreeNode<T> leftChild;
protected BinaryTreeNode<T> rightChild;
right
4-3
public BinaryTreeNode(T item){ data=item; }
// tree traversals
public BinaryTreeNode<T> inOrderFind(T item) { . . . }
public BinaryTreeNode<T> postOrderFind(T item) { . . . }
public BinaryTreeNode<T> preOrderFind(T item) { . . .}
// getter and setter methods
. . .
public class BinaryTree<T> {
protected BinaryTreeNode<T> rootTreeNode;
public BinaryTree(BinaryTreeNode<T> root) {
this.rootTreeNode = root;
}
// tree traversals
public BinaryTreeNode<T> inOrderFind(T item) {
return rootTreeNode.inOrderFind(item);
}
public BinaryTreeNode<T> preOrderFind(T item) { ... }
public BinaryTreeNode<T> postOrderFind(T item) { ... }
public BinaryTreeNode<T> postOrderFindStack(T item) { ... }
//getter and setter methods
. . .
4-4
¨
4 Datentypen: Baume,
Heaps
¨
4.1 Baumdurchlaufe
¨
¨
Baume
konnen
auf verschiedene Arten durchlaufen werden. Die bekanntesten Verfahren sind Tiefensuche (depth-first-search, DFS) und Breitensuche (breadth-first-search, BFS). Tiefensuche kann unter¨
¨
schieden werden in die drei Typen praorder,
postorder und inorder, abhangig
von der Reihenfolge der
rekursiven Aufrufe.
4.1.1 Tiefensuche
¨
Praorder
• Betrachte zuerst den Knoten (die Wurzel des Teilbaums),
• durchsuche dann den linken Teilbaum,
• durchsuche zuletzt den rechten Teilbaum.
Inorder
• Durchsuche zuerst den linken Teilbaum,
• betrachte dann den Knoten,
• durchsuche zuletzt den rechten Teilbaum.
Postorder
• Durchsuche zuerst den linken Teilbaum,
• durchsuche dann den rechten Teilbaum,
• betrachte zuletzt den Knoten.
¨
4.1 Baumdurchlaufe
.
. .
..
.
.
.
. . . .
..
. ..
.
4-5
.
. .
. ..
.
.
.
. . . .
..
. ..
¨
Wir betrachten als Beispiel fur
¨ die Tiefensuche den Praorder-Durchlauf.
public BinaryTreeNode<T> preOrderFind(T item) {
if (data.equals(item))
return this;
if (leftChild != null) {
BinaryTreeNode<T> result = leftChild.preOrderFind(item);
if (result != null)
return result;
}
if (rightChild != null) {
BinaryTreeNode<T> result = rightChild.preOrderFind(item);
if (result != null)
return result;
}
return null;
4-6
¨
4 Datentypen: Baume,
Heaps
}
4.1.2 Tiefensuche mit Hilfe eines Stacks
¨
¨
Mit Hilfe eines Stacks konnen
wir die rekursiven Aufrufe in der praorder
Tiefensuche vermeiden. Auf dem
¨
Stack werden die spater
zu behandelnden Baumknoten zwischengespeichert.
public BinaryTreeNode<T> preOrderFindStack(T item) {
Stack<BinaryTreeNode<T>> stack = new Stack<BinaryTreeNode<T>>();
stack.push(this.rootTreeNode);
while (!stack.isEmpty()) {
BinaryTreeNode<T> tmp = stack.pop();
if (tmp.getData().equals(item))
return tmp;
if (tmp.getRightChild() != null)
stack.push(tmp.getRightChild());
if (tmp.getLeftChild() != null)
stack.push(tmp.getLeftChild());
}
return null;
}
¨
4.1 Baumdurchlaufe
4-7
4.1.3 Breitensuche mit Hilfe einer Queue
Bei der Breitensuche besucht man jeweils nacheinander die Knoten der gleichen Ebene:
• Starte bei der Wurzel (Ebene 0).
¨
¨
• Bis die Hohe
des Baumes erreicht ist, setze den Level um eines hoher
und gehe von links nach
rechts durch alle Knoten dieser Ebene.
.
.
.
. . . .
..
. ..
Bei diesem Verfahren geht man nicht zuerst in die Tiefe, sondern betrachtet von der Wurzel aus zuerst
¨
alle Elemente in der naheren
Umgebung. Um mittels Breitensuche (levelorder) durch einen Baum zu
wandern, mussen
wir uns alle Baumknoten einer Ebene merken. Diese Knoten speichern wir in einer
¨
¨
¨
Queue ab, so dass wir spater
darauf zuruckgreifen
konnen.
¨
public BinaryTreeNode<T> levelOrderFind(T item) {
QueueImpl<BinaryTreeNode<T>> queue = new QueueImpl<BinaryTreeNode<T>>();
queue.add(rootTreeNode);
while (!queue.isEmpty()) {
BinaryTreeNode<T> tmp = queue.poll();
if (tmp.getData().equals(item))
return tmp;
if (tmp.getLeftChild() != null)
queue.add(tmp.getLeftChild());
if (tmp.getRightChild() != null)
queue.add(tmp.getRightChild());
}
return null;
}
¨
4 Datentypen: Baume,
Heaps
4-8
¨ Suchbaume
¨
4.2 Binare
¨
¨
Ein binarer
Suchbaum ist ein Baum, welcher folgende zusatzliche
Eigenschaft hat:
Alle Werte des linken Nachfolger-Baumes eines Knotens K sind kleiner, alle Werte des rechten
¨
Nachfolger-Baumes von K sind grosser
als der Wert von K selber.
¨
¨
Der grosse Vorteil von binaren
Suchbaumen
ist, dass wir sowohl beim Einfugen
als auch beim Suchen
¨
von Elementen immer bloss einen der zwei Nachfolger untersuchen mussen.
Falls der gesuchte Wert
¨
kleiner ist als der Wert des Knotens, suchen wir im linken Teilbaum, anderenfalls im rechten Teilbaum
weiter.
¨
Beispiel: Die folgenden zwei Baume
entstehen durch Einfugen
der Zahlen 37, 43, 53, 11, 23, 5, 17, 67,
¨
47 und 41 in einen leeren Baum. Einmal werden die Zahlen von vorne nach hinten eingefugt,
¨ das zweite
Mal von hinten nach vorne.
¨ Suchbaume
¨
4.2 Binare
public class BinarySearchTreeNode <T extends Comparable<T>> {
public void add(T item) {
int compare = data.compareTo(item);
if (compare > 0) {
// (data > item)?
if (leftChild == null)
leftChild = new BinarySearchTreeNode<T>(item);
else
leftChild.add(item);
// left recursion
} else {
// (item >= data)
if (rightChild == null)
rightChild = new BinarySearchTreeNode<T>(item);
else
rightChild.add(item);
// right recursion
}
}
public BinarySearchTreeNode<T> find(T item) {
int compare = data.compareTo(item);
if (compare == 0)
return this;
if (compare > 0 && leftChild != null) // data > item
return leftChild.find(item);
if (compare < 0 && rightChild != null) // data < item
return rightChild.find(item);
return null;
}
. . .
}
4-9
¨
4 Datentypen: Baume,
Heaps
4-10
¨
4.3 B-Baume
¨
¨
Ein B-Baum ist ein stets vollstandig
balancierter und sortierter Baum. Ein Baum ist vollstandig
balanciert,
¨
wenn alle Aste gleich lang sind. In einem B-Baum darf die Anzahl Kindknoten variieren. Ein 3-4-5 BBaum ist zum Beispiel ein Baum, in welchem jeder Knoten maximal 4 Datenelemente speichern und
¨
jeder Knoten (ausser der Wurzel und den Blattern)
minimal 3 und maximal 5 Nachfolger haben darf (der
¨
Wurzelknoten hat 0-4 Nachfolger, Blatter
haben keine Nachfolger).
¨
¨
Durch die flexiblere Anzahl Kindknoten ist das Rebalancing weniger haufig
notig.
Ein Knoten eines B-Baumes speichert:
•
•
•
•
eine variable Anzahl s von aufsteigend sortierten Daten-Elementen k1 , . . . , ks
eine Markierung isLeaf, die angibt, ob es sich bei dem Knoten um ein Blatt handelt.
s + 1 Referenzen auf Kindknoten, falls der Knoten kein Blatt ist.
¨
Jeder Kindknoten ist immer mindestens zur Halfte
gefullt.
¨
Die letzte Bedingung lautet formal: es gibt eine Schranke m, so dass m <= s <= 2m gilt. Das heisst,
¨
jeder Kindknoten hat mindestens m, aber hochstens
2m Daten-Elemente.
Die Werte von k1 , . . . , ks dienen dabei als Splitter. Die Daten-Elemente der Kindknoten ganz links mussen
¨
¨
kleiner sein als k1 , diejenigen ganz rechts grosser
als ks . Dazwischen mussen
die Daten-Elemente des
¨
¨
i-ten Kindes grosser
als ki und kleiner als ki+1 sein.
Das folgende Bild zeigt einen B-Baum mit m gleich 2. Jeder innere Knoten hat also mindestens 2 und
maximal 5 Nachfolger.
¨
4.3 B-Baume
4-11
¨
Operationen in B-Baumen
Suchen
¨
Die Suche nach einem Datenelement e lauft
in folgenden Schritten ab: Beginne bei der Wurzel als aktuellen Suchknoten k.
¨
• Suche in k von links her die Position p des ersten Daten-Elementes x, welches grosser
oder gleich e
ist.
•
•
•
•
Falls alle Daten-Elemente von k kleiner sind als e, fuhre
die Suche im Kindknoten ganz rechts weiter.
¨
Falls x gleich e ist, ist die Suche zu Ende.
Anderfalls wird die Suche beim p-ten Kindelement von k weitergefuhrt.
¨
Falls k ein Blatt ist, kann die Suche abgebrochen werden (fail).
Einfugen
¨
Beim Einfugen
muss jeweils beachtet werden, dass nicht mehr als 2m Daten-Elemente in einem Knoten
¨
¨
untergebracht werden konnen.
¨
Zunachst
wird das Blatt gesucht, in welches das neue Element eingefugt
Dabei kann
¨ werden musste.
¨
gleich wie beim Suchen vorgegegangen werden, ausser dass wir immer bis zur Blatt-Tiefe weitersuchen
(sogar, wenn wir den Wert unterwegs gefunden haben). Falls es in dem gesuchten Blatt einen freien
Platz hat, wird der Wert dort eingefugt.
¨
Einfugen
des Werts 31 in den folgenden Baum:
¨
4-12
¨
4 Datentypen: Baume,
Heaps
Der Wert 31 sollte in das Blatt (30,34,40,44) eingefugt
¨ werden. Dieses ist aber bereits voll, muss also
¨
aufgeteilt werden. Dies fuhrt
dazu, dass der Wert in der Mitte (34) in den VorgangerKnoten verschoben
¨
wird. Da das alte Blatt ganz rechts vom Knoten (20,28) liegt, wird der Wert 34 rechts angefugt
¨ (neuer,
¨
¨ dieser Knoten neu 3 Werte und 4 Nachfolger.
grosster
Wert dieses Knotens). Damit erhalt
Dieser Prozess muss eventuell mehrmals (in Richtung Wurzel) wiederholt werden, falls durch das Hoch¨
¨
schieben des Elements jeweils der Vorganger-Knoten
ebenfalls uberl
auft.
¨
¨
4.3 B-Baume
4-13
¨
Loschen
von Elementen
¨
Beim Loschen
eines Elementes muss umgekehrt beachtet werden, dass jeder Knoten nicht weniger als
m Datenelemente enthalten muss.
¨
Falls das geloschte
Element in einem Blatt liegt, welches mehr als m Datenelemente hat, kann das
¨
¨
Element einfach geloscht
werden. Andernfalls konnen
entweder Elemente vom benachbarte Blatt ver¨
schoben oder (falls zu wenig Elemente vorhanden sind) zwei Blatter
verschmolzen werden.
¨
Verschiebung Aus dem linken B-Baum soll das Element 18 geloscht
werden. Dies wurde
dazu fuhren,
¨
¨
dass das linke Blatt zu wenig Datenelemente hat. Darum wird aus dem rechten Nachbarn das kleinste
¨
Element nach oben, und das Splitter-Element des Vorgangers
in das linke Blatt verschoben.
¨
¨
Analog konnte
(falls vorhanden) aus einem linken Nachbarn das grosste
Element verschoben werden.
¨
Falls ein Element eines inneren Knotens (z.B. das Element 34) geloscht
wird, muss entweder von den
¨
linken Nachfolgern das grosste,
oder von den rechten Nachfolgern das kleinste Element nach oben verschoben werden, damit weiterhin genugend
Elemente (als Splitter) vorhanden sind, und die Ordnung
¨
bewahrt wird.
4-14
¨
4 Datentypen: Baume,
Heaps
¨
Verschmelzung Aus dem linken B-Baum soll das Element 60 geloscht
werden. Dies wurde
dazu fuhren,
¨
¨
dass das mittlere Blatt zu wenig Datenelemente hat. Weder der rechte noch der linke Nachbar hat
¨
genugend
Elemente, um eine Verschiebung durch zu fuhren
- es mussen
zwei Blatter
verschmolzen
¨
¨
¨
werden.
¨ vom mittleren Blatt das Element 55, sowie von der Wurzel das Element 50. Die
Das linke Blatt erhalt
Wurzel muss ebenfalls ein Element abgeben, da nach der Verschmelzung bloss noch 2 Nachfolge-Knoten
¨
existieren. Das rechte Blatt bleibt unverandert.
¨
Mit Hilfe der Verschiebung- und Verschmelzungs-Operation konnen
wir nun beliebige Elemente aus ei¨
nem B-Baum loschen.
Beispiel
¨
Aus dem folgenden Baum loschen
wir zuerst das Element 75, danach das Element 85:
4.4 Priority Queues
4-15
4.4 Priority Queues
¨
In vielen Applikationen will man die verschiedenen Elemente in einer bestimmten Reihenfolge (Prioritat)
¨
¨
abarbeiten. Allerdings will man das (aufwandige!)
Sortieren dieser Elemente nach moglichkeit
vermeiden.
¨
Eine der bekanntesten Anwendungen in diesem Umfeld sind Scheduling-Algorithmen mit Prioritaten.
Alle
¨ ihrer Prioritat
¨ in einer Priority Queue gesammelt, so dass immer das Element
Prozesse werden gemass
¨
¨ verfugbar
mit hochster
Prioritat
ist. Priority Queues haben aber noch weit mehr Anwendungen, zum
¨
Beispiel bei Filekomprimierungs- oder bei Graph-Algorithmen.
¨
Eine elegante Moglichkeit
der Implementierung einer Priority Queue ist mit Hilfe eines Heaps.
4.4.1 Heaps
¨
¨
Ein Heap ist ein (fast) vollstandiger
Baum, in welchem nur in der untersten Ebene von rechts her Blatter
fehlen durfen.
¨
65
56
52
37
25
48
31
18
45
6
3
15
¨
4 Datentypen: Baume,
Heaps
4-16
¨
¨
Definition: [Heap] Ein Heap ist ein vollstandiger
binarer
Baum, dem nur in der untersten Ebene ganz
¨
rechts Blatter
fehlen durfen
mit folgenden Zusatzeigenschaften.
¨
¨ und eventuell noch weitere Daten.
1. Jeder Knoten im Baum besitzt eine Prioritat
¨ eines Knotens ist immer grosser
¨
¨ der Nachkommen.
2. Die Prioritat
als (oder gleich wie) die Prioritat
Diese Bedingung heisst Heapbedingung.
¨
¨
Aus der Definition kann sofort abgelesen werden, dass die Wurzel des Baumes die hochste
Prioritat
¨
¨
¨
besitzt. Weil der Heap im wesentlichen ein vollstandiger
binarer
Baum ist, lasst
er sich einfach als Array2
implementieren. Wir numerieren die Knoten des Baumes von oben nach unten und von links nach rechts.
Die so erhaltene Nummerierung ergibt fur
¨ jeden Knoten seinen Index im Array.
¨
Die dargestellten Werte im Baum sind naturlich
bloss die Prioritaten
der Knoten. Die eigentlichen Daten
¨
lassen wir der Einfachheit halber weg.
public class Heap<T extends Comparable<T>> {
private List<T> heap;
public Heap() { heap = new ArrayList<T>(); }
public T removeMax() { . . . }
public void insert(T data) { . . . }
private
private
private
private
boolean isLeaf(int position) { . . . }
int parent(int position) { . . . }
int leftChild(int position) { . . . }
int rightChild(int position){ . . . }
2 Dies hat den Nachteil, dass die maximale Anzahl Elemente (size ) beim Erzeugen des Heaps bekannt sein muss.
4.4 Priority Queues
4-17
65
56
52
37
25
48
31
18
15
45
6
3
...
Werden die Knoten auf diese Weise in den Array abgelegt, so gelten fur
¨ alle i, 0 ≤ i < length die
folgenden Regeln:
• Der linke Nachfolger des Knotens i befindet sich im Array-Element
Ferner gilt: heap[i]
heap[
]
• Der rechte Nachfolger des Knotens i befindet sich im Array Element
Ferner gilt: heap[i]
heap[
]
• Der direkte Vorfahre eines Knotens i befindet sich im Array-Element
Ferner gilt: heap[i]
heap[
]
Wir sind jetzt in der Lage, die beiden wichtigen Operationen insert und removeMax zu formulieren.
¨
4 Datentypen: Baume,
Heaps
4-18
¨
insert Da ein Element hinzugefugt
wir zuerst length um eins. Das neue Element
¨ werden muss, erhohen
¨
¨
wird dann an der Stelle length-1 eingefugt.
Der Array reprasentiert
immer noch einen vollstandigen
¨
¨
¨
binaren
Baum mit nur rechts unten fehlenden Blattern.
Das neue Element verletzt aber eventuell die
Heapbedingung. Um wieder einen Heap zu erhalten, vertauschen wir das neue Element solange mit
¨
seinen direkten Vorgangern,
bis die Heapbedingung wieder erfullt
¨ ist.
¨ Baum vollstandig
¨
Diese Methode verfolgt einen direkten Weg von einem Blatt zur Wurzel. Da der binare
¨
¨
¨
ist, hat ein solcher Weg hochstens die Lange der Hohe des Baumes. Mit anderen Worten, wir brauchen
¨
hochstens
log2 (n) Vertauschoperationen, um ein Element im Heap einzufugen.
¨
65
52
56
37
25
48
31
18
45
6
3
15
55
public void insert(T data) {
heap.add(data);
int crt = heap.size() - 1;
while ((crt != 0)
// heap[crt] > heap[parent(crt)]
&& (heap.get(crt).compareTo(heap.get(parent(crt))) > 0)) {
Collections.swap(heap, crt, parent(crt));
crt = parent(crt);
}
}
}
4.4 Priority Queues
4-19
¨
¨ befindet sich im Element heap[0] und wird vom
removeMax Das Element mit der hochsten
Prioritat
Heap entfernt. heap[0] wird nun mit heap[length-1]
uberschrieben
und length um eins verringert.
¨
¨
¨
Damit erhalten wir wieder einen fast vollstandigen
binaren
Baum. Das neue Element heap[0] verletzt
nun vermutlich die Heapbedingung.
¨
seiner beiden Nachfolger und fahren so fort, bis die
Wir vertauschen also heap[0] mit dem grosseren
Heapbedingung wieder erfullt
¨ ist.
65
public T removeMax() {
if (heap.isEmpty()) return null;
Collections.swap(heap, 0, heap.size() - 1);
T element = heap.remove(heap.size() - 1);
if (heap.size() > 1)
siftDown(0);
return element;
}
4-20
¨
4 Datentypen: Baume,
Heaps
private void siftDown(int position) {
while (!isLeaf(position)) {
int j = leftChild(position);
if ((j < heap.size() - 1)
// heap[j] < heap[j+1]
&& (heap.get(j).compareTo(heap.get(j + 1)) < 0)) {
j++;
}
// heap[position] >= heap[j]
if (heap.get(position).compareTo(heap.get(j)) >= 0) {
return;
}
Collections.swap(heap, position, j);
position = j;
}
}
¨
4.5 Ubung
4
4-21
¨
4.5 Ubung
4
¨ Suchbaume
¨
Binare
¨ Suchbaume,
¨
Bauen Sie aus der folgenden Zahlenreihe zwei binare
indem Sie die Zahlen einmal von
links nach rechts und einmal von rechts nach links lesen.
39, 40, 50, 10, 25, 5, 19, 55, 35, 38, 12, 16, 45
Heaps
¨
Loschen
Sie aus dem folgenden Heap zuerst drei Elemente, fugen
Sie danach ein neues Element
¨
¨ 42 in den Heap ein.
mit Prioritat
52
43
32
35
17
20
22
12
15
6
8
18
5
3
BTree
¨
Fugen
Sie im folgenden BTree zuerst das Element 42 ein, loschen
Sie dann die Elemente 28 und 45.
¨
4-22
5
Suchen
5.1 Grundlagen
¨
Suchen ist eine der haufigsten
Operationen, die mit dem Computer ausgefuhrt
werden. Normalerweise
¨
geht es darum, in einer Menge von Daten die richtigen Informationen zu finden. Wir kennen zum Beispiel
¨
einen Namen und suchen die zugehorige
Mitgliedernummer. Oder wir geben (mit Hilfe einer EC-Karte)
¨
eine Kontonummer ein und das System sucht das dazugehorige
Konto. Oder wir kennen eine Telefon¨
nummer und suchen den dazugehorigen Abonnenten, usw.
Wenn wir im folgenden jeweils Listen von Zahlen durchsuchen, so tun wir das bloss der Einfachheit
¨
halber. Die gleichen Algorithmen konnen
naturlich
fur
¨
¨ beliebige Objekte angewandt werden. Ein Objekt kann zum Beispiel eine Klasse Adresse mit den Member-Variablen name, vorname, strasse,
wohnort, telefonNummer, kundenNummer
sein. Dann verwenden wir eine der Member-Variablen
als Suchschlussel,
also zum Beispiel Adresse.name .
¨
¨
Da Suchalgorithmen so haufig
verwendet werden, lohnt es sich, diese effizient zu implementieren. An¨
derseits spielt naturlich
die Lange
der zu durchsuchenden Datenmenge eine entscheidende Rolle: Je
¨
¨
grosser
die Datenmenge, desto wichtiger die Effizienz der Suche.
Ausserdem spielt die benutzte Datenstruktur eine entscheidende Rolle. Wir werden hier jeweils annehmen, dass wir auf alle Elemente der Datenfolge schnellen wahlfreien Zugriff haben (wie z. Bsp. in einer
ArrayList). Falls dies nicht der Fall ist, sind gewisse Suchalgorithmen sehr viel weniger effizient.
5-2
5 Suchen
Falls kein wahlfreier Zugriff existiert, kann dies mit Hilfe eines Pointer-Arrays simuliert werden, in welchem die Adressen der Daten-Objekte gespeichert sind. Die richtige Wahl der benutzten Datenstruktur
ist entscheidend, ob ein Algorithmus effizient implementiert werden kann oder nicht.
5.2 Lineare Suche
Wie der Name schon sagt, gehen wir bei der linearen Suche linear durch die Suchstruktur und testen
jedes Element, bis wir das gesuchte finden oder ans Ende gelangen.
/**
* Searches for the first occurence of the given argument.
* @param
elem an object.
* @return the index of the first occurrence of the argument in
*
this list; returns -1 if the object is not found.
*/
public int indexOf(Object elem) {
if (elem == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (elem.equals(elementData[i]))
return i;
}
return -1;
}
¨
Die for -Schleife bricht spatestens
dann ab, wenn das letzte Element der Liste gepruft
¨ ist.
¨ der linearen Suche
Komplexitat
¨
Um die Effizienz der linearan Suche zu bestimmen, bestimmen wir die Anzahl der notigen
Vergleiche in
¨
¨
Abangigkeit
von der Lange
n der Folge.
¨ Suche
5.3 Binare
5-3
¨ Suche
5.3 Binare
¨
¨
¨
¨
Eine Folge, auf die sehr haufig
zugegriffen (und nicht so haufig
verandert)
wird, sollte wenn moglich
¨
sortiert gehalten werden1 . Dies lasst
sich leicht realisieren, indem die neuen Elemente jeweils an der
richtigen Stelle einsortiert werden2 .
Falls die Daten so dargestellt sind, kann das Suchen auf sehr viel schnellere Art und Weise realisiert
¨ Suche. Bei der binaren
¨
werden, zum Beispiel durch binare
Suche wird die Folge in zwei Teile
Elem[0]
|
· · · Elem[p-1]
{z
}
Elem[p+1]
|
· · · Elem[len]
{z
}
geteilt und das Element Elem[p] mit dem zu suchenden Element a verglichen. Falls Elem[p] kleiner als
a ist, suchen wir in der rechten Teilfolge weiter, andernfalls in der linken.
r = size
l=0
a
p = (r+l)/2
¨
Die ersten drei Schritte der binaren
Suche
Da die Folge sortiert ist, ist dieses Vorgehen korrekt.
1 Dies setzt naturlich
voraus, dass sich die Datenelemente sortieren lassen, also eine Ordnungsrelation < auf den Datenschlusseln
existiert.
¨
¨
In Java bedeutet dies, die Elemente mussen
das Comparable Interface erfullen,
d.h. eine compareTo() Methode haben.
¨
¨
¨
¨
2 Im Abschnitt uber
Baume
sind wir bereits der speziell dafur
Baumes begegnet
¨
¨ konzipierten Datenstruktur des binaren
5-4
5 Suchen
¨
Wenn wir die Folge jeweils nicht in der Mitte teilen, sondern p = l oder p = r wahlen,
erhalten wir die
¨
lineare Suche als Spezialfall der binaren
Suche.
/**
* return index where item is found, or -1
*/
public int binarySearch( Comparable<T>[ ] a, T x )
{
int l = 0; int p;
int r = a.length - 1;
while( l <= r )
{
p = ( l + r ) / 2;
if( a[p].compareTo( x ) < 0 )
//
l = p + 1;
else if( a[p].compareTo( x ) > 0 )
r = p - 1;
//
else
return p;
}
return -1
}
¨ der binaren
¨
Komplexitat
Suche
a[p] < x
a[p] > x
5.4 Hashing
5-5
5.4 Hashing
¨
Eine Hash-Tabelle ist eine Ubersetzungstabelle,
mit der man rasch auf jedes gesuchte Element einer
¨ einer zeigerbasierten Liste bietet. Hashtabellen
Liste zugreifen kann, welche aber trotzdem die Flexibilitat
werden zum Beispiel auch bei Compilern benutzt, um die Liste der Variablen (und ev. deren Typen) zu
verwalten.
¨
Ein einfaches Beispiel einer Hash-Tabelle ist ein Array. In einem Array konnen
wir auf jedes Element
direkt zugreifen. Einen Array als Hash-Tabelle zu benutzen ist dann gunstig,
wenn wir genugend
Platz
¨
¨
¨
¨
haben, um einen Array der Lange
Anzahl moglicher
Schlussel
anzulegen.
¨
¨
Beispiel: Falls alle Mitglieder eines Vereins unterschiedliche Initialen haben, konnen
wir dies als
Schlussel
fur
¨
¨ die Hashtabelle benutzen.
Berta Amman
Doris Bucher
Chris Carter
Friedrich Dunner
¨
BA
DB
CC
FD
7→
7
→
7
→
7
→
(2,1)
(4,2)
(3,3)
(6,4)
¨
¨
Mit einem Array der Lange
26×26 konnen
wir auf jedes Mitglied direkt zugreifen.
Hash−Tabelle
(H,R)
1
Menge aller Schlüssel
(D,H)
(U,M)
(C,F)
...
(H,A)
(B,A)
(C,C)
(W,S)
2
3
4
...
Daten(BA)
Daten(DB)
Daten(CC)
...
Benötigte Schlüssel
(D,B)
(F,D)
1
2
3
4
5
6
Daten(FD)
Der Nachteil hierbei ist, dass wir bei dieser Methode offensichtlich viel Speicherplatz verschwenden. Aus¨
serdem konnen
wir nicht sicher sein, dass nicht eines Tages ein neues Mitglied mit bereits existierenden
¨
Initialen in unseren Verein eintreten will. Fur
zu
¨ beide Probleme versuchen wir im folgenden Losungen
finden.
5-6
5 Suchen
5.4.1 Hash-Funktionen
Eine Hash-Funktion ist eine Methode, mit welcher wir mit Hilfe von einfachen arithmetischen Operationen
¨
die Speicherstelle eines Elementes aus seinem Schlussel
berechnen konnen.
Optimalerweise sollte eine
¨
Hash-Funktion jedem Element einer Menge einen anderen Funktionswert zuordnen (vermeiden von Kol¨
lisionen). Dies ist leider in der Regel nicht moglich.
Allerdings gibt es Hash-Funktionen, welche diesen
Anspruch besser, und solche, welcher ihn weniger gut erfullen.
¨
Definition: Eine Hashfunktion sollte mindestens die folgenden Eigenschaften erfullen.
¨
¨
• Der Hashwert eines Objekts muss wahrend
der Ausfuhrung
der Applikation gleich bleiben.
¨
¨
Der Hashwert darf aber bei einer nachsten
Ausfuhrung
der Applikation anders sein.
¨
¨ der equals() Methode, muss der Hashwert der beiden Objekte
• Falls zwei Objekte gleich sind gemass
gleich sein.
¨
• Zwei verschiedene Objekte konnen
den gleichen Hashwert haben.
Allerdings wird die Performance von Applikationen verbessert, wenn unterschiedliche Objekte unterschiedliche Hashwerte haben.
Die folgende Hash-Funktion summiert die ASCII-Werte der Buchstaben eines Strings. Fur
¨ das Einfugen
¨
¨
in die Hashtabelle muss dieser Wert dann modulo der Lange
der Hashtabelle genommen werden.
long Elem_hash(Object key) {
String keyString = key.toString();
int sum = 0;
for (int i = 0; i < keyString.length(); i++)
sum = sum + keyString.charAt(i);
return sum;
}
¨
Wie wir am folgenden Beispiel sehen, funktioniert diese Methode leider nicht allzu gut. Alle Worter,
die
aus den gleichen Buchstaben (in anderer Reihenfolge) bestehen, haben den gleichen Funktionswert.
¨
Aber auch sonst verteilt diese Methode verschiedene Worter
offensichtlich nicht optimal (erzeugt viele
Kollisionen).
5.4 Hashing
5-7
Anna
Jochen
Otto
Gabi
Tina
Kurt
Elem_hash()
Tina
Otto
Jochen
Anna
Kurt
0
1
2
3
4
Gabi
5
6
7
8
9
10
Eine oft benutzte, gut streuende Hash-Funktion fur
¨ Strings ist die ELF hash -Methode.
long ELFhash(String key) {
long h = 0;
for (int i = 0; i < key.length(); i++) {
h = (h << 4) + (int) key.charAt(i);
long g = h & 0xF0000000L; // AND
if (g != 0)
h = h ˆ g >>> 24; // XOR, Shift right
h = h & ˜g;
}
return h;
}
Anna
Jochen
Otto
Gabi
Tina
Kurt
ELF_hash()
Kurt
0
Otto
1
2
Gabi Anna
3
4
5
Tina
6
Jochen
7
8
9
10
5-8
5 Suchen
Naturlich
kann auch die ELF hash -Methode nicht alle Kollisionen vermeiden. Die ELF hash -Methode
¨
¨
¨ zum Beispiel fur
mit Tabellenlange
11 erhalt
¨ “Otto” und “Martin” den gleichen Schlussel.
¨
Die Frage ist darum: wie behandelt man Kollisionen?
5.4.2 Double Hashing
Bei Double Hashing verwenden wir zwei verschiedene Hashfunktionen Hash1 und Hash2 3 . Hash1 dient
dazu, die Hashadresse eines Schlussels
in der Tabelle zu suchen. Hash2 dient dazu, bei einer Kollision
¨
¨
in der Tabelle den nachsten
freien Platz zu suchen.
Hash 1 (k)
0
Hash 2(k)
leeres Feld
besetztes Feld
2
neuer Eintrag
3
4
5
6
7
8
9
10
11
Einfugen
¨
eines Objekts mit Schlussels
¨
k: Zuerst wird die Hashadresse
Hash1 (k) mod N
berechnet. Ist dieser Tabellenplatz noch leer, dann wird das Objekt dort eingetragen. Ist der Tabellenplatz schon besetzt, so wird nacheinander bei den Adressen
(Hash1 (k) + Hash2 (k)) mod N,
(Hash1 (k) + 2 · Hash2 (k)) mod N,
...
¨
¨
3 Im einfachsten Fall wahlen
wir Hash2 (k) = p fur
N der Hashtabelle nicht teilt. Dann
¨ p gleich 1 oder fur
¨ eine Primzahl p, welche die Lange
erhalten wir den sog. Linear Probing Algorithmus. Im Allgemeinen kann Hash2 (k) eine beliebige Funktion sein, welche Werte relativ prim zu
N liefert.
5.4 Hashing
5-9
¨
gesucht, bis ein freier Platz gefunden wird (N = Lange
der Tabelle). An der ersten freien Stelle wird
das Objekt eingetragen.
¨
Damit bei der Suche nach einem freien Platz alle Elemente der Tabelle durchsucht werden konnen,
muss Hash2 (k) fur
¨ alle k relativ prim zu N sein (d.h. Hash2 (k) und N haben keine gemeinsamen
Primfaktoren). Sobald die Hashtabelle den maximalen Fullstand
ubersteigt
(z.B. 60%), muss die
¨
¨
¨
Hashtabelle vergrossert
und ein Rehashing vorgenommen werden (alle Elemente neu zuteilen).
Suchen des Objekts mit Schlussels
¨
k:
Die Hashadresse
Hash1 (k) mod N
wird berechnet. Ist das gesuchte Element mit Schlussel
k an dieser Adresse gespeichert, ist die
¨
Suche erfolgreich. Falls nicht, wird der Wert Hash2 (k) berechnet und das Element in den Tabellen¨
platzen
(Hash1 (k) + Hash2 (k)) mod N,
(Hash1 (k) + 2 · Hash2 (k)) mod N,
...
gesucht. Die Suche wird durch eine der drei folgenden Bedingungen abgebrochen:
• Das Element wird gefunden. Die Suche ist erfolgreich abgeschlossen.
• Ein leerer Tabellenplatz wird gefunden,
• oder wir geraten bei der Suche in einen Zyklus (hypothetischer Fall).
¨
In den beiden letzten Fallen
ist das gesuchte Element nicht in der Tabelle.
Hash1 (k)
Hash2 (k)
leeres Feld
besetztes Feld
gelöschtes Feld
5-10
5 Suchen
¨
¨
Loschen
eines Schlussels:
¨
Das Loschen
von Elementen aus einer Tabelle mit Double Hashing ist etwas heikel. Damit ein in der Tabelle eingetragener Schlussel
in jedem Fall wieder gefunden wird,
¨
¨
durfen
wir die Elemente aus der Tabelle nicht einfach loschen,
da wir nicht wissen, ob sie eventuell
¨
als Zwischenschritt beim Einfugen
von anderen Elementen benutzt wurden.
¨
Jeder Tabelleneintrag muss darum ein Flag besitzen, welches angibt, ob ein Eintrag leer, benutzt
¨
oder geloscht
ist. Die oben beschriebene Suche darf dann nur bei einem leeren Element abgebro¨
¨
chen werden. Beim Loschen
eines Schlussels
aus der Tabelle muss der Tabellenplatz mit geloscht
¨
markiert werden.
Als zweite Hashfunktion genugt
¨ oft eine sehr einfache Funktion, wie zum Beispiel Hash2 (k) = k mod 8 +
¨
1. Um sicherzustellen, dass diese Funktionswerte teilerfremd zur Lange
der Hashtabelle sind, kann man
¨
¨
zum Beispiel als Tabellenlange
eine Primzahl wahlen.
5.4 Hashing
5-11
5.4.3 Bucket Hashing
¨
Eine andere Moglichkeit,
Kollisionen zu behandeln, ist das Aufteilen des Hash-Arrays in verschiedene
¨
¨
buckets. Eine Hashtabelle der Lange
H wird dabei aufgeteilt in H/B Teile (buckets), von der Grosse
B. Es wird nur eine Hashfunktion benutzt, Elemente mit gleichem Hashwert (modulo Hashsize) werden
¨
¨
im selben Bucket abgelegt. Die Hashfunktion sollte die Datenelemente moglichst
gleichmassig
uber
die
¨
verschiedenen Buckets verteilen.
Hashtable
Bucket Hashing,
¨
Buckets der Lange
4
Overflow
0
leer
1
besetzt
2
gelöscht
3
4
5
6
7
8
...
Einfugen:
¨
Die Hashfunktion ordnet das Element dem entsprechenden Bucket zu. Falls der erste Platz
im Bucket bereits besetzt ist, wird das Element im ersten freien Platz des Bucket abgelegt.
¨
Falls ein Bucket voll besetzt ist, kommt der Eintrag in einen Uberlauf
(overflow bucket) von genugen¨
¨
¨
der Lange
am Ende der Tabelle. Alle Buckets teilen sich den selben Uberlauf-Speicher.
¨
¨
Naturlich
soll der Uberlauf-Speicher
moglichst
gar nie verwendet werden. Sobald die Hashtabelle
¨
einen gewissen Fullgrad
erreicht hat, muss ein Rehashing erfolgen, so dass die Zugriffe schnell
¨
bleiben (die Buckets nicht uberlaufen).
¨
Suchen: Um ein Element zu suchen, muss zuerst mittels der Hashfunktion der Bucket gesucht werden,
in welchem das Element liegen sollte. Falls das Element nicht gefunden wurde und im Bucket noch
¨
¨
freie Platze
sind, kann die Suche abgebrochen werden. Falls der Bucket aber keine freien Platze
mehr
hat, muss der Overflow durchsucht werden bis das Element gefunden wurde, oder alle Elemente des
Overflow uberpr
uft
¨
¨ sind.
¨
¨
Loschen:
Auch beim Bucket Hashing mussen
wir beim Loschen
vorsichtig sein. Falls der Bucket noch
¨
¨
¨
freie Platze hat, konnen wir den Tabellen-Platz einfach freigeben. Falls nicht, muss der Platz als
¨
“geloscht”
markiert werden, damit beim Suchen der Elemente auch der Overflow durchsucht wird.
5-12
5 Suchen
¨
¨
Eine Variante des Bucket Hashing ist die folgende: Wir wahlen
wiederum eine Bucket-Grosse
B. Wir
teilen die Hashtabelle aber nicht explizit in Buckets auf, sondern bilden jeweils einen virtuellen Bucket
rund um den Hashwert. Dies hat den Vorteil, dass jeder Tabellenplatz als Ausgangsposition fur
¨ das
¨
Einfugen
benutzt werden kann, was die Anzahl Kollisionen bei gleicher Tabellen-Grosse
vermindert.
¨
Bucket Hashing Variante,
¨
Buckets der Lange
5
Hashtable
Overflow
leer
besetzt
gelöscht
P
neuer Eintrag
P+1
P+2
Einfugen:
¨
Die Hashfunktion berechnet den Platz P in der Hashtabelle. Falls dieser Platz bereits besetzt
ist, werden die Elemente rund um P in der Reihenfolge P + 1, P + 2, . . ., P + B − 2, P + B − 1
durchsucht, bis ein freier Platz gefunden wurde. Falls kein freier Platz in dieser Umgebung gefunden
¨
wird, kommt das Element in den Uberlauf-Speicher.
Suchen: Um ein Element zu suchen, muss zuerst mittels der Hashfunktion der Platz P in der Hashtabelle
bestimmt werden. Falls das Element an der Stelle P nicht gefunden wird, werden die Elemente rund
um P in der selben Reihenfolge wie oben durchsucht.
Falls wir das Element finden, oder auf einen leeren Platz stossen, kann die Suche abgebrochen
werden. Andernfalls muss der Overflow durchsucht werden bis das Element gefunden wurde, oder
der ganze Overflow durchsucht ist.
¨
¨
Loschen:
Das geloschte
Feld muss auch in dieser Variante markiert werden, damit wir beim Suchen
keinen Fehler machen.
5.4 Hashing
5-13
5.4.4 Separate Chaining
Die flexibelste Art, um Kollisionen zu beheben, ist mit Hilfe von Separate Chaining. Bei dieser Methode
hat in jedes Element der Hashtabelle einen next-Zeiger auf eine verkettete Liste.
Einfugen
¨
des Schlussels
¨
k: Zuerst wird die Hashadresse Hash(k) berechnet. Dann wird der neue
Schlussel
am Anfang der verketteten Liste eingefugt.
¨
¨
Suchen des Schlussels
¨
k: Die Hashadresse Hash(k) wird berechnet. Dann wird k mit den Schlusseln
¨
in der entsprechenden Liste verglichen, bis k entweder gefunden wird oder das Ende der Liste erreicht ist.
¨
Loschen
des Schlussels
¨
k: Das Element wird einfach aus der Liste in Hash(k) entfernt.
Hashing mit Separate Chaining
5-14
5 Suchen
¨
5.5 Ubung
5
Linear Probing
Fugen
Sie mit den Hashfunkionen Hash1 (k) = k und Hash2 (k) = 1 die Liste der Zahlen
¨
2, 3, 14, 12, 13, 26, 28, 15
¨
in eine leere Hashtabelle der Lange
11 ein. Wieviele Vergleiche braucht man, um festzustellen, dass
die Zahl 46 nicht in der Hashtabelle ist?
Double Hashing
Fugen
Sie mit den Hashfunkionen Hash1 (k) = k und Hash2 (k) = k mod 8 + 1 die Liste der Zahlen
¨
2, 3, 14, 12, 13, 26, 28, 15
¨
in eine leere Hashtabelle der Lange
11 ein. Wieviele Vergleiche braucht man, um festzustellen, dass
die Zahl 46 nicht in der Hashtabelle vorkommt?
Bucket Hashing
Fugen
Sie mit der Hashfunkion Hash(k) = k die Zahlen 4, 3, 14, 12, 13, 26, 28, 15, 2, 20
¨
¨
¨
leere Hashtabelle der Lange
8 ein mit Bucket Grosse
3 ein.
in eine
Overflow:
Java Hashtabelle
Sie finden unter ∼amrhein/AlgoData/uebung5 eine vereinfachte Version der Klasse Hashtable der
java.util Library. Finden Sie heraus, welche der verschiedenen im Skript vorgestellten Varianten
in der Java Library benutzt werden.
6
Sortieren
¨
¨
Sortierprogramme werden vorallem fur
von Daten benotigt,
wenn die Daten zum
¨ die die Prasentation
¨
¨
Beispiel sortiert nach Zeit, Grosse,
letzten Anderungen,
Wert, ... dargestellt werden sollen.
Wenn die Mengen nicht allzu gross sind (weniger als 500 Elemente), genugt
¨ oft ein einfach zu implemen¨ von O(n2 ), wobei
tierender, langsamer Suchalgorithmus. Diese haben normalerweise eine Komplexitat
der Aufwand bei fast sortierten Mengen geringer sein kann (Bubble Sort). Zum Sortieren von grossen
Datenmengen lohnt es sich allerdings, einen O(n log2 (n)) Algorithmus zu implementieren.
Noch mehr als bei Suchalgorithmen spielen bei Sortieralgorithmen die Datenstrukturen eine entscheidende Rolle. Wir nehmen an, dass die zu sortierende Menge entweder eine Arraystruktur (ein BasisTyp-Array wie float[n] oder eine ArrayList ) oder eine Listenstruktur (wie zum Beispiel LinkedList )
¨
ist. Listen erlauben zwar keinen wahlfreien Zugriff, dafur
Listenelemente durch Umketten (also
¨ konnen
ohne Umkopieren) von einer unsortierten Folge F in eine sortierte Folge S uberf
uhrt
werden. Arrays
¨
¨
¨
erlauben wahlfreien Zugriff. Dafur
und Loschen
(Umsortieren) von Elementen viele
¨ sind beim Einfugen
¨
¨
Kopier-Schritte notig.
Speziell ist zu beachten, dass viele Sortier-Algorithmen auf Array-Strukturen zwar sehr schnell aber nicht
stabil sind.
¨ der Vergleichsfunktion
Definition: Ein Sortier-Algorithmus heisst stabil, falls Elemente, welche gemass
gleich sind, ihre Originalreihenfolge behalten.
6-2
6
Sortieren
6.1 Selection Sort
¨
Beim Sortieren durch Auswahlen
teilen wir die zu sortierende Menge F (scheinbar) in eine unsortierte
Teilmenge U und eine sortierte Menge S. Aus U wird jeweils das kleinste Element gesucht und mit dem
letzten Element von S vertauscht. Wegen dieser Vertausch-Aktionen ist dieser Algorithmus eher geeignet
fur
aber dazu, dass der Algorithmus nicht stabil ist.
¨ Arraystrukturen. Die Vertauschungen fuhren
¨
public void selectionSort(int l, int r) {
int min_pos;
for( int i=l; i<r; i++) {
min_pos = findMin(i);
swap(i, min_pos);
}
}
private int findMin(int n) { // find position with minimal Element
int min = n;
for( int i = n+1; i<array.size(); i++ )
if( array.get(i).compareTo(array.get(min)) < 0 )
min = i;
return min;
}
Die Array-Prozedur find min(i) sucht jeweils das kleinste Element aus dem Rest-Array. find min
betrachtet also nur die Elemente mit Positionen j ≥ i im Array (der unsortieren Teilmenge U ). Das neue
kleinste Element min (an der Position min pos ) wird mit dem Element an der Position i vertauscht (dem
letzten der Teilmenge S).
6.1 Selection Sort
6-3
Beispiel Wir sortieren die Folge F = (21, 5, 12, 1, 27, 3)
21
5 12
1
27
3
Dass der Algorithmus nicht stabil ist, sehen wir auch am folgenden Beispiel. Die Folge Beat Suter, Claudia
Meier, Daniel Suter, Emil Bucher, Fritz Abegg ist bereits sortiert nach Vornamen. Sie soll nun mit Hilfe
¨ den Nachnamen sortiert werden.
von Selection Sort gemass
BeatSuter ClaudiaMeier DanielSuter EmilBucher FritzAbegg
6-4
6
Sortieren
6.2 Insertion Sort
Beim Sortieren durch Einfugen
nimmt man jeweils das erste Element aus der unsortierten Folge F und
¨
fugt
¨ es an der richtigen Stelle in die sortierte Folge S ein. Dieser Algorithmus ist nicht geeignet fur
¨ arraybasierte Folgen, da in jedem Schritt einige Elemente im Array nach hinten verschoben werden mussten.
¨
Wir betrachten nochmals die Folge vom Beispiel vorher:
21
5 12
1
27
3
¨ der Ordnung) gleichen Elemente
Falls das Element beim Ein-Sortieren jeweils am Ende aller (gemass
eingefugt
¨ wird, ist dieser Algorithmus stabil.
public void insertSorted(MSEntry<T> o) {
MSEntry<T> e = header;
// find place for o
while (e.next != null && o.element.compareTo(e.next.element) > 0)
e = e.next;
// while(o.element < e.next.element)
o.next = e.next;
// insert o between e and e.next
e.next = o;
if (e == tail)
tail = o;
size++;
}
6.3 Divide-and-Conquer Sortieren
6-5
public MSList<E> insertSort(MSList<E> list) {
MSList<E> newList = new MSList<E>();
newList.addFirst(list.removeFirst());
while (list.size() > 0)
newList.insertSorted(list.removeFirst());
return newList;
}
6.3 Divide-and-Conquer Sortieren
Das abstrakte Divide-and-Conquer Prinzip (vgl. Kap. 1.6.2) lautet wie folgt:
1. Teile das Problem (divide)
¨ die Teilprobleme (conquer )
2. Lose
¨
3. Kombiniere die Teillosungen
(join)
¨
Beim Sortieren gibt es zwei Auspragungen:
Hard split / Easy join: Dabei wird die gesamte Arbeit beim Teilen des Problems verrichtet und die
Kombination ist trivial, das heisst, F wird so in Teilfolgen F1 und F2 partitioniert, dass zum Schluss
¨
die sortierten Teilfolgen einfach aneinandergereiht werden konnen:
S = S1 S2 . Dieses Prinzip fuhrt
¨
zum Quicksort-Algorithmus.
Easy split / Hard join: Dabei ist die Aufteilung in Teilfolgen F = F1 F2 trivial und die Hauptarbeit liegt
beim Zusammensetzen der sortierten Teilfolgen S1 und S2 zu S. Dieses Prinzip fuhrt
zum Mergesort¨
Algorithmus.
6-6
6
Sortieren
6.4 Quicksort
Einer der schnellsten und am meisten benutzten Sortieralgorithmen auf Arrays ist der Quicksort-Algo¨
rithmus (C.A.R. Hoare, 1960). Seine Hauptvorteile sind, dass er nur wenig zusatzlichen
Speicherplatz
¨
braucht, und dass er im Durchschnitt nur O(n log2 (n)) Rechenschritte benotigt.
¨ 1 . Dann wird der zu sortierende Bereich F
Beim Quicksort wird zuerst ein Pivot-Element q ausgewahlt
so in zwei Teilbereiche Fklein und Fgross partitioniert, dass in Fklein alle Elemente kleiner als q und in Fgross alle
¨
Elemente grosser
gleich q liegen.
Danach wird rekursiv Fklein und Fgross sortiert. Am Ende werden die je sortierten Folgen wieder zusammengefugt.
¨
¨
Die Prozedur partition sucht jeweils von links ein Element g, welches grosser
und von rechts ein Element k, welches kleiner als der Pivot ist. Diese zwei Elemente g und k werden dann vertauscht. Dies wird
so lange fortgesetzt, bis sich die Suche von links und von rechts zusammen trifft. Zuruckgegeben
wird
¨
der Index der Schnittstelle. Anschliessend an partition wird der Pivot an der Schnittstelle eingesetzt
(vertauscht mit dem dortigen Element).
Um zu sehen, was beim Quicksort-Algorithmus passiert, betrachten wir das folgende Tracing:
¨ werden, optimalerweise ist q aber der Median aller zu sortierenden Werte. Da die Berechnung des Medians viel zu
1 q kann beliebig gewahlt
¨
¨
¨ man als Pivot oft einfach das erste Element. Eine bessere Wahl ist das Element an der Stelle length/2 im Array als
aufwandig
ware,
wahlt
Pivot; dies fuhrt
bei beinahe sortierten Folgen zu einem optimalen Algorithmenverlauf.
¨
6.4 Quicksort
54
93
6-7
83
22
7
19
94
48
27
72
39
70
13
28
95
36 100
4
12
6-8
6
Sortieren
private int partition( int l, int r, E pivot )
{
do{
// Move the bounds inward until they meet
while( array.get(++l).compareTo(pivot) < 0 && l < r );
// Move left bound right
while( array.get(--r).compareTo(pivot) > 0 && l < r);
// Move right bound left
if( l < r )
swap( l, r );
// Swap out-of-place values
} while(l < r );
// Stop when they cross
if( array.get(r).compareTo(pivot) < 0 )
return r+1;
return r;
// Return position for pivot
}
¨
Quicksort teilt die zu sortierende Menge so lange auf, bis die Teile eine kritische Lange
(z.B. 4 oder
8) unterschritten haben. Fur
Listen wird der einfachere Selection-Sort Algorithmus benutzt, da
¨ kurzere
¨
dieser fur
¨ kurze Listen einen kleineren Overhead hat.
public void quickSort( int i, int j ) {
int pivotindex = findPivot(i, j);
swap(pivotindex, i);
// stick pivot at i
int k = partition(i, j+1, array.get(i));
// k is the position for the pivot
swap(k, i);
// put pivot in place
if( (k-i) > LIMIT )
// sort left partition
quickSort( i, k-1 );
else
// with selection-sort
selectionSort( i, k-1 );
//
for short lists
if( (j-k) > LIMIT )
quickSort( k+1, j );
// sort right partition
else
selectionSort( k+1, j );
}
6.5 Sortieren durch Mischen (Merge Sort)
6-9
¨ des Quicksort-Algorithmus ist im besten Fall O(n log2 (n). Im schlechtesten Fall (worst
Die Komplexitat
¨ O(n2 ).
case), wenn das Pivot-Element gerade ein Rand-Element ist, dann wird die Komplexitat
¨ des Quicksort Algorithmus. Es
Das Finden eines gunstigen
Pivot Elements ist zentral fur
¨
¨ die Komplexitat
¨
¨
gibt verschiedene Verfahren zum Losen
diesese Problems wie, wahle
als Pivot das erste Element des
¨
¨
¨
Arrays, wahle
das Element in der Mitte des Arrays oder wahle
drei zufallige
Elemente aus dem Array
und nimm daraus das mittlere. Eine Garantie fur
¨ eine gute Wahl des Pivots liefert aber keines dieses
Verfahren. Ausserdem ist der Quicksort Algorithmus nicht stabil.
6.5 Sortieren durch Mischen (Merge Sort)
Der Merge-Sort-Algorithmus ist einer der besten fur
¨ Datenmengen, die als Listen dargestellt sind. Die
¨
Rechenzeit ist in (best case und worst case) O(n log2 (n)). Ausserdem wird kein zusatzlicher
Speicher
¨
benotigt und der Algorithmus ist stabil.
Beim Merge-Sort wird die Folge F mit Hilfe einer Methode divideList()
¨
grosse Halften
geteilt.
private MSList<E>[] divideList(MSList<E> list) {
MSList<E> result[] = (MSList<E>[]) new MSList[2];
result[0] = new MSList<E>();
int length = list.size();
for (int i = 0; i < length / 2; i++)
result[0].addFirst(list.removeFirst());
result[1] = list;
return result;
}
¨
in zwei (moglichst)
gleich
6-10
6
Sortieren
Die (im rekursiven Aufruf) sortierten Folgen werden dann in einem linearen Durchgang zur sortierten
Endfolge zusammen gefugt
¨ (gemischt).
private MSList<E> mergeSort(MSList<E> list) {
if (list.size() < LIMIT)
return insertSort(list);
// divide list into two sublists
MSList<E>[] parts = divideList(list);
MSList<E> leftList = parts[0];
MSList<E> rightList = parts[1];
leftList = mergeSort(leftList);
rightList = mergeSort(rightList);
// left recursion
// right recurstion
return merge(leftList, rightList);
}
¨
Das Mischen geschieht dadurch, dass jeweils das kleinere Kopfelement der beiden Listen ausgewahlt,
¨ und als nachstes
¨
herausgelost
Element an die neue Liste angefugt
¨ wird.
4
7
3
3
13
4
8
28
7
12
8
15
6.5 Sortieren durch Mischen (Merge Sort)
6-11
private MSList<E> merge(MSList<E> left, MSList<E> right) {
MSList<E> newList = new MSList<E>();
while (left.size() > 0 && right.size() > 0) {
if (left.getFirst().compareTo(right.getFirst()) < 0)
newList.addLast(left.removeFirst());
else
newList.addLast(right.removeFirst());
}
for (int i = left.size(); i > 0; i--)
newList.addLast(left.removeFirst());
for (int i = right.size(); i > 0; i--)
newList.addLast(right.removeFirst());
return newList;
}
divide
Beispiel: Wie Mergesort genau funktioniert, wollen wir anhand dieses Beispiel nachvollziehen.
merge
sort
3
2
1
6
3
2
1
6
3
2
1
6
3
4
8
2
2
3
1
6
3
4
2
8
2
3
1
6
3
4
2
8
3
4
3
2
1
4
3
2
3
4
2
8
6
2
1
2
8
2
8
3
6-12
6
Sortieren
¨
6.6 Ubung
6
InsertSort, SelectionSort
Erstellen Sie ein Tracing vom InsertSort-, bzw. vom SelectionSort-Algorithmus auf der Eingabe
F = {42, 3, 24, 17, 13, 5, 10}
Insert Sort
42
3
24
17
Selection Sort
13
5
10
42
3
24
17
13
5
10
Mergesort, Quicksort
Erstellen Sie je ein Tracing vom Mergesort-, bzw. vom Quicksort-Algorithmus (einmal mit dem PivotElement an der Stelle 1, dann an der Stelle (r+l)/2 , r der rechte, l der Linke Rand des Bereichs)
auf der Eingabe
F = {42, 3, 24, 33, 13, 5, 7, 25, 28, 14, 46, 16, 49, 15}
HeapSort
¨
Uberlegen
Sie sich ein Verfahren welches eine gegebene Menge mit Hilfe eines Heaps sortiert.
Welchen Aufwand hat dieses Verfahren im besten / im schlechtesten Fall?
Selbststudium: BucketSort, RadixSort
Lesen Sie die Unterlagen zum Selbststudium uber
die zwei weiteren Suchalgorithmen: Bucket Sort
¨
und Radix Sort.
Sortieren Sie die obige Menge F mit Hilfe von RadixSort mit 5 Buckets.
¨
6.6 Ubung
6
6-13
Quick Sort
42
3
24
33
13
5
7
25
28
14
46
16
49
15
42
3
24
33
13
5
7
25
28
14
46
16
49
15
6-14
7
Pattern Matching
¨
Pattern Matching ist eine Technik, mit welcher ein String aus Text oder Binardaten
nach einer Zeichenfolge durchsucht wird. Die gesuchten Zeichenfolgen werden dabei in Form eines Suchmusters (Pattern)
angegeben.
Solche Algorithmen werden in der Textverarbeitung (Suchen nach einem Zeichenstring in einer Datei) aber
auch von Suchmaschinen auf dem Web verwendet. Das
Hauptproblem beim Pattern-Matching ist: Wie kann entschieden werden, ob ein Text ein gegebenes Muster
erfullt.
¨
¨ Ausdrucke
7.1 Beschreiben von Pattern, Regulare
¨
¨
¨ Ausdrucke)
Zunachst
brauchen wir eine Sprache, mit welcher wir die Pattern (hier regulare
beschreiben
¨
¨
¨
konnen
(um zu sagen, welche Art von Wortern
oder Informationen wir suchen).
Sei E ein Alphabet, d.h. eine endliche Menge von Zeichen. Ein Wort uber
E ist eine endliche Folge von
¨
Zeichen aus E :
w = e1 e2 . . . en ,
ei ∈ E
Das leere Wort, das aus keinem Zeichen besteht, bezeichnen wir mit λ.
¨
Mit E ∗ bezeichnen wir die Menge aller Worter
uber
dem Alphabet E .
¨
7-2
7 Pattern Matching
Beispiel: Fur
¨ E = {A, B} ist E ∗ =
Die Pattern bauen wir mit Hilfe der folgenden drei Regeln zusammen:
¨
Definition: Ein (einfacher) regularer
Ausdruck ist ein Wort (String), welches mit Hilfe der folgenden drei
Operationen zusammengebaut wird:
¨
¨
Konkatenation setzt zwei Worter
zusammen. So wird aus den Wortern
’AB’ und ’BC’ das neue Wort
’ABBC’.
¨
¨
Auswahl erlaubt uns, zwischen einem der Worter
auszuwahlen.
Das heisst AB|B ist entweder das Wort
’AB’ oder das Wort ’B’. Wir nennen solche Terme auch Or-Ausdrucke.
¨
¨
Iteration repetiert das gegebene Wort beliebig oft (auch 0 mal). A(AB)∗ entspricht also den Wortern
’A’,
’AAB’, ’AABAB’, · · ·.
¨
Zu beachten ist in diesem Zusammenhang die Bindungsstarke
der drei Operationen: Die Iteration (∗ )
¨
¨
bindet starker
als die Konkatenation. Am schwachsten
bindet der Oder-Strich (|).
Beispiele
¨
Der Ausdruck (A|BC)∗ AB erzeugt die Worter:
¨
Der Ausdruck AB∗ C|A(BC)∗ erzeugt die Worter:
¨
¨
Wir beschranken
uns hier auf diese wenigen Moglichkeiten
zum Erzeugen von Pattern, obwohl es naturlich
noch viele weitere, sehr elegante Operationen gibt: Zum Beispiel mit dem Zeichen ’.’ fur
¨
¨ einen
¨
beliebigen Buchstaben konnten
lange Or-Ausdrucke
viel kurzer
dargestellt werden. AB(A|B| · · · |Z)∗ G
¨
¨
¨
entspricht dann AB( . )∗ G. Allerdings konnen
wir damit keine neuen Wortmengen definieren. Darum
begenugen
wir uns vorerst mit den obigen Operationen.
¨
¨
Um zu entscheiden, ob ein Wort einen regularen
Ausdruck erfullt,
¨ setzen wir endliche Automaten ein.
7.2 Endliche Automaten
7-3
7.2 Endliche Automaten
¨
¨
Endlichen Automaten begegnen wir im taglichen
Leben in Form von Getrankeautomaten,
Billetautomaten, Bancomaten ... . Allen ist gemeinsam, dass sie ein einfaches endliches Eingabealphabet und ein
¨
einfaches endliches Ausgabealphabet haben und jeweils eine endliche Menge von Zustanden
annehmen
¨
konnen.
Beispiel Ein Bancomat funktioniert wie folgt: Nachdem die EC-Karte eingeschoben wurde, muss der
Benutzer die Geheimzahl (Pincode) eingeben. Falls der Pincode korrekt war, bekommt der Benutzer eine
¨
Auswahl prasentiert
(Geld abheben, Kontostand abfragen, abbrechen). Je nach Verhalten des Benutzers
gibt der Bancomat den gewunschten
Geldbetrag aus und/oder gibt die EC-Karte wieder zuruck.
¨
¨
Geldbetrag
Geld ausgeben
Auswahl Abbruch
Karte ausgeben
Auswahl
Geld
5
korrekter
Pincode
Auswahl
Kontostand
3
Karte
1
einschieben
ok
2
4
falscher Pincode
6
Error
Karte ausgeben
¨
Definition: Ein endlicher (deterministischer) Automat besteht aus einer endlichen Menge von Zustan¨
den, einem Anfangs- (oder Start-) Zustand und einem oder mehreren Endzustanden
(oder akzeptieren¨
den Zustanden).
• Eingabe: Ein Automat wird von aussen bedient, d.h. er wird mit Eingabedaten versorgt. Es gibt also
eine endliche Menge E von Eingabezeichen, die der Automat lesen kann und die eine gewisse Aktion
¨
auslosen.
Die Menge E heisst Eingabealphabet.
• Zustand: Ein deterministischer Automat befindet sich stets in einem bestimmten Zustand. Die endli¨
¨
che Menge Z der moglichen
Zustande
heisst die Zustandsmenge.
7-4
7 Pattern Matching
• Zustandsubergang:
¨
Die Verarbeitung eines einzelnen Eingabezeichens kann durch eine Nachfolgefunktion, ein Zustandsdiagramm oder durch eine Zustandstafel beschrieben werden. Unter der
Einwirkung der Eingabe kann er von einem Zustand in einen andern ubergehen.
¨
• Ausgabe: Im Laufe seiner Arbeit kann der Automat eine Ausgabe produzieren, d.h. er kann Ausgabedaten ausgeben. Die endliche Menge A der produzierten Ausgabezeichen heisst Ausgabealphabet.
Beispiel: Fur
¨ den Bancomat setzen wir
Eingabe:
E = {EC-Karte, Pincode (korrekt/falsch), Auswahl (Geld, Kontostand ...), Geldbetrag, Ok }
¨
Zustande:
Z = {1 (Startzustand), 2 (warten auf Pincode), 3 (warten auf Auswahl), 4 (Kontostand
anzeigen), 5 (warten auf Betrag) }
Ausgabe:
A = {EC-Karte, Kontostand, Geld}.
und definieren die Funktionsweise durch die folgende Zustandstafel:
Zustand
Eingabe
1
2
3
4
5
6 (Error)
Karte (E)
korrekter (K)
Pincode
falscher
Pincode (F)
Auswahl (G)
Geld
Auswahl
Kontostand (S)
Auswahl
Abbruch (A)
Geldbetrag (B)
Ok (O)
¨
¨
Mit Hilfe von endlichen Automaten konnen
wir entscheiden, ob ein gegebenes Wort einem regularen
Ausdruck entspricht, also ob ein gefundenes Wort in unser Schema (das vorgegebene Pattern) passt.
7.2 Endliche Automaten
7-5
¨
Beispiel: Worter,
welche vom obigen Automaten (Bancomaten) akzeptiert werden, sind:
¨
¨
Worter,
welche nicht zum obigen Automaten gehoren
(nicht akzeptiert werden) sind:
Ein endlicher Automat heisst deterministisch, falls jede Eingabe des Eingabealphabetes in jedem Zustand erlaubt ist und zu einem eindeutigen Nachfolgezustand fuhrt.
Ein nichtdeterministischer endlicher
¨
¨
Automat kann fur
haben.
¨ jeden Zustand und jede Eingabe null, einen oder mehrere Nachfolgezustande
Der Automat des vorigen Beispiels ist ein deterministischer endlicher Automat, da alle Eingaben nur
¨
in einen eindeutigen Nachfolgezustand fuhren.
Nichtdeterministische Automaten konnen
aber immer in
¨
¨
deterministische Automaten ubergef
uhrt
werden, indem neue mehrdeutige Zustande
eingefuhrt
werden.
¨
¨
¨
Beispiele Das folgende ist ein deterministischer, endlicher Automat: in jedem Zustand fuhrt
jede Eingabe
¨
zu einem eindeutigen Nachfolgezustand:
A
A
A
1
4
0
B
B
A
C
2
A
B
C
C
B
3
Zustand
B
C
C
Eingabe
A
B
C
0
1
2
3
4
7-6
7 Pattern Matching
Das folgende ist ein nichtdeterministischer, endlicher Automat: Manche Eingaben fuhren
in gewissen
¨
¨
Zustanden
zu keinem oder zu mehr als einem Nachfolgezustand:
A
A
1
C
C
Zustand
4
0
A
Eingabe
A
B
2
1
2
3
4
A
B
B
0
C
A
B
3
C
C
¨
¨
Ein weiteres Konstrukt in nichtdeterministischen Automaten sind sogenannte leere Uberg
ange,
das
¨
¨
¨
¨
¨
¨
heisst Uberg
ange
ohne gelesenes Zeichen. Solche Uberg
ange
heissen auch epsilon-Uberg
ange
und
werden mit ε bezeichnet.
A
A
1
C
C
Zustand
4
0
Eingabe
B
C
B
A
A
ε
ε
2
C
B
3
B
C
0
1
2
3
4
¨
7.3 Automaten zu regularen
Ausdrucken
¨
7-7
¨
7.3 Automaten zu regularen
Ausdrucken
¨
¨
¨
¨
Wir suchen nun einen zu einem regularen
Ausdruck aquivalenten
Automaten. Ausgehend vom regularen
¨
Ausdruck konnen
wir mit den folgenden Regeln den entsprechenden nichtdeterministischen endlichen
Automaten herleiten.
Durch das Symbol
bezeichnet.
wird der Startzustand, durch
der akzeptierende Zustand des Automaten
Konkatenation: E1 E2
E1 :
1
2
E2 :
3
4
Beispiel:
B
A
B
C
A
A
.
7-8
7 Pattern Matching
Auswahl: E1 | E2
E1 :
1
2
E2 :
3
4
.
Beispiel:
B
A
B
C
A
A
Iteration: E∗
E:
1
2
Beispiel:
A
B
C
.
¨
7.3 Automaten zu regularen
Ausdrucken
¨
7-9
¨
Im allgemeinen kann man sehr viel kleinere Automaten konstruieren, welche den gleichen regularen
Ausdruck beschreiben. Es gibt auch einen Algorithmus, welcher aus einem nichtdeterministischen Auto¨
¨
maten einen deterministischen Automaten (ohne leere Uberg
ange)
erzeugt. Diesen Algorithmus wollen
wir hier aber nicht behandeln.
Beispiel 1: Ein endlicher Automat fur
¨ den Ausdruck (AB|C)∗ (A|B)
¨
Beispiel 2: Ein Automat fur
Ausdruck (AB|BC)∗ (C|BC)
¨ den regularen
7-10
7 Pattern Matching
¨
7.4 Ubung
7
¨
1. Finden Sie jeweils einen endlichen Automaten und/oder einen regularen
Ausdruck, welcher die fol¨
gende Menge von Wortern
uber
dem Alphabet {A, B,C} beschreibt:
¨
¨
- Alle Worter,
welche mit A anfangen und mit C enden.
-
¨
Alle Worter,
welche eine gerade Anzahl A enthalten und mit C enden.
-
¨
Alle Worter,
deren Anzahl Buchstaben durch 3 teilbar sind.
-
¨
Alle Worter,
welche eine gerade Anzahl B und eine gerade Anzahl C enthalten.
¨
2. Erzeugen Sie je einen nichtdeterministischen Automaten fur
Ausdrucke:
¨ die regularen
¨
- (A*BC)*|BB
-
((AB|B)(BA|CB))*
- (BB|CAB*|AB)*
Sie mussen
dabei die angegebenen Regeln zur Erzeugung des Automaten nicht strikt befolgen – Sie
¨
¨
¨
konnen
auch versuchen, einen Automaten mit weniger Zustanden
zu finden.
3. Erzeugen Sie eine Zustandsubergangs-Tabelle
fur
¨
¨ den folgenden Automaten.
ε
ε
0
C
B
ε
1
A
A
2
B
4
B
3
A
¨
7.4 Ubung
7
7-11
¨
4. Lesen Sie die Worter
AACBC, ABACA und ACACB mit Hilfe der von Ihnen erzeugten Zustandsuber¨
gangstabelle, indem Sie Schritt fur
¨ Schritt den aktuellen Zustand notieren.
5. Holen Sie sich das Java Programm unter ∼amrhein/AlgoData/uebung7 und beantworten Sie die
folgenden Fragen:
¨
- Erklaren
Sie die Methoden find , group , start , end , split und replaceAll des java.regex
Package.
-
¨
¨
Erganzen
Sie das gegebene Programm: Geben Sie vom Input String alle Worter
aus, welche
weniger als 5 Buchstaben haben.
7-12
7 Pattern Matching
¨
Die wichtigsten regularen
Ausdrucke
¨
Bedeutung
\
.
x
ˆx
[x]
()
|
{x}
{x,}
{x,y}
?
*
+
ˆ
$
Escape, um Instanzen von Zeichen zu finden, welche als Metazeichen benutzt
werden (wie Punkt, Klammer, ... )
Ein beliebiges Zeichen (ausser newline)
Eine Instanz von x
Jedes Zeichen ausser x
Alle Zeichen in diesem Bereich (z. B. [abuv] die Buchstaben a, b, u oder v, [a-z]
alle Kleinbuchstaben)
runde Klammern dienen fur
¨ die Gruppierung
der OR Operator (Auswahl) (a|A)
Der Ausdruck muss genau x mal vorkommen
Der Ausdruck muss mindestens x mal vorkommen
¨
Der Ausdruck kommt mindestens x mal und hochstens
y mal vor
Abkurzung
fur
¨
¨ {0, 1}
Abkurzung
fur
¨
¨ {0, }
Abkurzung
fur
¨
¨ {1, }
Start einer neuen Zeile
Ende der Zeile
Beispiele
[a-zA-Z]*
Beliebig viele Zeichen aus Buchstaben (z. B. ugHrB).
[A-Z0-9]{8}
Acht Zeichen aus A bis Z und 0 bis 9, (z. B. RX6Z45UB).
[A-Z]([a-z])+
Ein Grossbuchstabe gefolgt von mindestens einem Kleinbuchstaben (z.Bsp Stu).
([0-9]-){2}[0-9]}
Drei Zahlen, durch Striche getrennt (z. B. 2-1-8).
[A-G]{2,} Mindestens zwei Grossbuchstaben aus A bis G (z. B. BGA).
[bRxv]{3} Drei Buchstaben aus b, R, x und v (z. B. xxv).
8
Top Down Parser
¨
¨
Hohere
Programmiersprachen wie Java oder C++ konnen
von einem Prozessor nicht direkt verarbeitet
¨
werden. Die in diesen Sprachen geschriebenen Programme mussen
zuerst in eine fur
¨
¨ den gewahlten
Prozessor geeignete Maschinensprache ubersetzt
werden. Programme, die diese Aufgabe ubernehmen,
¨
¨
¨
nennt man Compiler. Ein Compiler hat im Prinzip zwei Aufgaben zu losen:
1. Erkennen der legalen Programme der gegebenen Sprache. Das heisst, der Compiler muss testen,
ob die Syntax des Programms korrekt ist oder nicht. Diese Operation nennt man parsing und das
¨ einen Parser.
Programm, das diese Aufgabe lost,
2. Generieren von Code fur
¨ die Zielmaschine.
Auch wenn wir keinen Compiler schreiben wollen, so kommt es doch oft vor, dass wir komplizierte Benutzereingaben wie zum Beispiel
-
Arithmetische Ausdrucke:
2(a − 3) + b − 21
¨
-
Polynome: a + 3x2 − 4x + 16
-
Boole’sche Ausdrucke
a ⊙ (b ⊙ c) ⊕ b
¨
-
eine Befehlssprache
-
ein Datenubermittlungsprotokoll
¨
-
...
erkennen und verarbeiten mussen.
¨
8-2
8
Top Down Parser
8.1 Kontextfreie Grammatik
Mit Hilfe einer Grammatik beschreiben wir den Aufbau oder die Struktur (-Regeln) einer Sprache. Kontextfreie Grammatiken1 dienen als Notation zur Spezifikation einer Sprachsyntax.
Beispiel: Ein einfacher deutscher Satz kann zum Beispiel eine der folgenden Strukturen annehmen:
S ’ist’ A
S ’ist’ A ’und ’ A
S ’ist’ A ’oder ’ A
wobei S normalerweise die Form
Artikel Nomen
¨ ’gross’, ’schnell’ oder ’lang’.
hat und A ersetzt werden kann durch ein Adjektiv wie ’schon’,
Eine kontextfreie Grammatik (bzw. ein Syntaxdiagramm) fur
¨ dieses Konstrukt sieht dann etwa wie folgt
aus:
Grammatik
(EBNF: Extended Backus-Naur Form)
Satz
S
Artikel
Artikel
Nomen
Nomen
::=
::=
::=
::=
...
::=
::=
S ’ist’ A
A
A
Adjektiv
Adjektiv
::=
::=
::=
::=
::=
...
Satz
S
S
Artikel
A
ist
Artikel Nomen
’der’
Nomen
’ein’
’Baum’
Artikel
der
ein
’Hund’
...
A
Syntax-Diagramm
A
Adjektiv
Adjektiv
Adjektiv ’und’ A
und
Adjektiv ’oder’ A
oder
¨
’schon’
’gross’
Adjektiv
A
...
¨ Chomsky-Hierarchie vier Typen von Grammatiken: Typ 3: lineare Grammatik (entpricht endlichem Automat), Typ 2: kontext1 Es gibt gemass
freie Grammatik (nur Nichtterminale auf der linken Seite), Typ 1: kontextsensitive Grammatik (nichtverkurzend),
Typ 0: allgemeine Grammatik
¨
¨
(ohne Einschrankung).
8.1 Kontextfreie Grammatik
8-3
Eine solche Ersetzungs-Regel heisst eine Produktion.
Ein Satz, welcher dieser Grammatik entspricht, ist:
Ein Satz, welcher nicht dieser Grammatik entspricht, ist:
¨
Eine kontextfreie Grammatik beschreibt eine Sprache (Menge von Wortern
oder Strings).
¨
Definition: Zu einer kontextfreien Grammatik gehoren
vier Komponenten.
1. Eine Menge von Terminalen, d.h. von Symbolen, die am Ende einer Herleitung stehen (hier fettgedruckte Zeichenketten wie ’ist’, ’und’ oder ’oder’).
2. Eine Menge von Nichtterminalen, d.h. von Namen oder Symbolen, die weiter ersetzt werden (hier
kursiv gedruckte Zeichenketten).
3. Eine Menge von Produktionen (l ::= r). Jede Produktion besteht aus einem Nichtterminal, das die linke Seite der Produktion bildet, einem Pfeil und einer Folge von Terminalen und/oder Nichtterminalen,
die die rechte Seite der Produktion darstellen.
4. Ein ausgezeichnetes Nichtterminal dient als Startsymbol. Das Startsymbol ist immer das Nichtterminal auf der linken Seite der ersten Produktion.
Als vereinfachte Schreibweise fassen wir alle rechten Seiten der Produktionen zusammen, welche das
gleiche Nichtterminal als linke Seite haben, wobei die einzelnen Alternativen durch ‘|’ (zu lesen als “oder”)
getrennt werden.
Ziffer
Ziffer
..
.
::= ’0’
::= ’1’
Ziffer ::= ’9’
kann also auch als
Ziffer ::= ’0’ | ’1’ | ’2’ | ’3’ | ’4’ | ’5’ | ’6’ | ’7’ | ’8’ | ’9’
geschrieben werden.
8-4
8
Top Down Parser
Definition: Die Herleitung eines Wortes aus einer Grammatik geschieht wie folgt: Wir beginnen mit dem
Startsymbol und ersetzen dann jeweils in dem hergeleiteten Wort ein Nichtterminal durch die rechte Seite
einer Produktion. Dies wird so lange wiederholt, bis im Ausdruck keine Nichtterminale mehr vorkommen.
¨
Alle Worter,
die aus dem Startsymbol herleitbar sind, bilden zusammen die von der Grammatik definierte
Sprache.
Beispiel:
Die Grammatik G1 besteht aus den Produktionen:
G1 :
S ::= ′ A′ | ′ A′ S | b
b ::= ′ B′ | ′ B′ b
¨
G1 erzeugt die folgende Menge von Wortern:
G2 besteht aus den Produktionen:
G2 :
S ::= ′ A′ | ′ B′ | ′ A′ b | ′ B′ a
a ::= ′ A′ | ′ A′ b
b ::= ′ B′ | ′ B′ a
¨
G2 erzeugt die Worter:
8.1 Kontextfreie Grammatik
8-5
Beispiel Die Menge der arithmetischen Ausdrucke
wird durch die folgende Grammatik erzeugt:
¨
expression
term
factor
number
digit
::= term { ′ + ′ term | ′ − ′ term }
::= factor { ′ ∗ ′ factor }
::=
′ ′
( expression ′ )′ | number
::= digit { digit }
::=
′ ′
0 | ′ 1′ | ′ 2′ | ′ 3′ | ′ 4′ | ′ 5′ | ′ 6′ | ′ 7′ | ′ 8′ | ′ 9′
Geschweifte Klammern bedeuten in der EBNF-Schreibweise null oder beliebig viele Wiederholungen.
Eine Expression ist also ein Term oder eine Summe von Termen. Ein Term ist ein Faktor oder ein Produkt
von Faktoren. Ein Faktor ist ein Klammer-Ausdruck oder eine Zahl. Eine Zahl besteht aus einer oder
mehreren Ziffern.
+
expression
term
*
term
factor
−
Um zu uberpr
ufen,
ob ein Ausdruck ein korrekter arithmetischer Ausdruck ist, beschreiben wir den Her¨
¨
leitungsprozess mit Hilfe eines Herleitungsbaumes (Parsetree):
Der Parsetree von 12 ∗ 4 − 3 ∗ (2 + 14) + 21
8-6
8
Top Down Parser
Beispiel: Suchmaschinen erlauben ublicherweise
die komplexe Suche nach Mustern wie
¨
⊕ (schule
software
⊙ schweiz)
Dafur
uber
Zei¨ braucht man eine Sprache, mit welcher der Benutzer diese (boole’schen) Ausdrucke
¨
¨
chenfolgen eingeben kann. Die Menge der boole’schen Ausdrucke
kann zum Beispiel wie folgt erzeugt
¨
werden:
bexpr
::= bterm [ ′ ⊕ ′ bexpr ]
bterm
::= bfac [ ′ ⊙ ′ bterm ]
bfac
::= [ ′ − ′ ] ′ (′ bexpr ′ )′ | [ ′ − ′ ] string
string
::= letter { letter }
letter
::=
′ ′
a | ′ b′ | . . . | ′ z′
Eckige Klammern bezeichnet in der EBNF Schreibweise ein optionales Vorkommen (null oder einmal).
.. bexpr
....
bterm .............
....
...
....
....
.....
...
.
.
.
.
....
......
+g .
................
bexpr
Wir zeichnen den Parsetree des boole’schen Ausdrucks
( a ⊙ b ) ⊙
ac ⊕ abc
8.2 Top-Down Parser
8-7
8.2 Top-Down Parser
¨
Aus einer solchen Grammatik lasst
sich nun relativ leicht ein (rekursiver) Top-Down Parser herleiten: Auf¨
passen mussen
wir dabei nur, dass wir keine nichtterminierenden Zyklen einbauen. Vermeiden konnen
¨
¨ ein oder zwei Zeichen vorauslesen. Dies kann bei Klammerausdrucken
wir das, indem wir falls notig
oder
¨
¨ sein, bzw. immer dann, wenn es mehrere Moglichkeiten
¨
Operationszeichen notig
gibt.
8.2.1 Parser fur
¨ arithmetische Ausdrucke
¨
Zum Implementieren des Parsers fur
schreiben wir eine Klasse Arithmetic¨ arithmetische Ausdrucke
¨
ExpressionParser . Darin definieren wir die Member-Variablen parseString fur
¨ den zu parsenden
¨
String, position fur
des zu parsenden Strings.
¨ die aktuelle Lese-Position und length die Lange
public class ArithmeticExpressionParser {
private String parseString;
private int position;
private int length;
public void parse(String aExpr) throws ParseException { . . . }
// one method per grammar line
. . .
}
Die Methode parse() ruft die Startfunktion expression()
String gelesen wurde.
auf und testet am Schluss, ob der ganze
public void parse(String aExpr) throws ParseException {
position = 0;
parseString = aExpr;
length = parseString.length();
expression();
if (position < length) throw new ParseException(position, "parse");
}
8-8
8
Top Down Parser
¨
expression()
fangt
(laut Grammatik) immer mit einem Term an, also rufen wir zuerst die Prozedur
term() auf. Falls ein ’+ ’ oder ein ’- ’ im Ausdruck folgt, haben wir weitere Terme und es ist ein Loop
¨
notig.
private void expression() throws ParseException {
term();
while(position < length ) {
if( parseString.charAt(position) == ’+’
|| parseString.charAt(position) == ’-’) {
position++;
term();
}
else
return;
}
}
term()
¨
fangt
(laut Grammatik) mit einem Faktor an. Falls darauf ein ’* ’ folgt, ist ein rekursiver Aufruf
¨
notig.
private void term() throws ParseException {
factor();
while (position < length)
if( parseString.charAt(position) == ’*’) {
position++;
factor();
}
else
return;
}
¨
¨
In factor() ist nun eine Abfrage notig,
um sicherzustellen, dass jede geoffnete
Klammer wieder geschlossen wurde. Falls keine Klammer gelesen wurde, muss an dieser Stelle eine oder mehrere Ziffern
stehen.
8.2 Top-Down Parser
8-9
private void factor() throws ParseException {
try {
if (parseString.charAt(position) == ’(’) {
position++;
expression();
if (parseString.charAt(position) == ’)’)
position++;
else
throw new ParseException(position, "factor");
} else
number();
}
catch (StringIndexOutOfBoundsException e) {
throw new ParseException(position, "factor");
}
}
¨
number() muss mindestens eine Ziffer lesen konnen,
andernfalls ist an dieser Stelle im Ausdruck ein
Fehler.
private void number() throws ParseException {
int n = position;
while (position < length && isDigit(parseString.charAt(position)))
position++;
if (n == position)
throw new ParseException(position, "number: digit expected");
}
8-10
8
Top Down Parser
8.2.2 Parser fur
¨ boole’sche Ausdrucke
¨
¨
Als nachstes
bauen wir einen Parser fur
¨ die von der Grammatik von Seite 8-6 erzeugten boole’schen
Ausdrucke:
¨
bexpr
::= bterm [ ′ ⊕ ′ bexpr ]
bterm
::= bfac [ ′ ⊙ ′ bterm ]
bfac
::= [ ′ − ′ ] ′ (′ bexpr ′ )′ | [ ′ − ′ ] string
string
::= letter { letter }
letter
::=
′ ′
a | ′ b′ | . . . | ′ z ′
Da wir auf der normalen Tastatur die Zeichen
ein + fur
¨ ′ ⊕ ′ und ein ∗ fur
¨ ′ ⊙′ .
′
⊙ ′ und
′
⊕ ′ nicht haben, schreiben wir im Programm
¨
Die Methode parse() konnen
wir (fast) aus dem letzten Abschnitt kopieren.
8.2 Top-Down Parser
public void parse(String aExpr) throws ParseException {
position = 0;
parseString = aExpr;
length = parseString.length();
booleanExpression();
if (position < length)
throw new ParseException(position, "parse");
}
Ein boole’scher Ausdruck ist entweder ein einfacher Term oder ein OR-Ausdruck (bterm + bexpr)2 .
private void booleanExpression( ) throws ParseException {
2 vgl. ∼ amrhein/AlgoData/Parser
8-11
8-12
8
Top Down Parser
Ein bterm ist ein AND-Term, also ein bfac oder ein bfac multipliziert mit einem bterm.
private void booleanTerm( ) throws ParseException {
Ein booleanFactor ist ein String, ein negierter String, ein boole’scher Ausdruck oder ein negierter boole’scher Ausdruck.
private void booleanFactor(
) throws ParseException {
8.2 Top-Down Parser
booleanName liest so lange als Buchstaben im Ausdruck erscheinen.
void booleanName() throws ParseException {
int n = position;
while (position < length && isAlpha(parseString.charAt(position)))
position++;
if (n == position)
throw new ParseException(position, "booleanVariable: letter expected");
}
8-13
8-14
8
Top Down Parser
¨
8.3 Ubung
8
Syntax-Diagramm Gegeben ist das folgende Syntaxdiagramm:
S
T
T
(
+
S
-
S
F
*
T
)
/
F
F
a
b
c
1. Schreiben Sie es in eine Grammatik um.
2. Welche der folgenden Terme sind durch diese Grammatik erzeugt worden?
(a) a*(b-c)
(c) a+(a*b)+c
(e) (a+b)/(a-b)
(b) a/(b*c)
(d) a+b+(c*b)
(f) ((a*b)/(b*c))
Parser Gegeben sei die folgende Grammatik:
r ::=
s ::=
t ::=
′ ′ ′
L +′ s | s
N ′ | ′ N ′ ′ (′ t ′ )′
′ ′ ′ ′
M + r | r
′
1. Welche der folgenden Ausdrucke
sind von dieser Grammatik erzeugt worden?
¨
(a) L + N
(d) L + N (N + M)
(b) N (M + N)
(e) N (L + N (M)))
(c) L + N (L + N)
(f) N (N (L + M))
2. Schreiben Sie einen Parser fur
¨ diese Grammatik.
Grammatiken
1. Geben Sie eine Grammatik fur
dem Alphabet { A,B } an, welche
¨ die Menge aller Strings uber
¨
¨
hochstens
zwei gleiche Buchstaben in Folge haben.
2. Erweitern Sie die Grammatik fur
so, dass auch Exponentiation (∧ ) und
¨ arithmetische Ausdrucke
¨
Division (/) als Operationen erlaubt sind.
9
Kryptologie
Mit der zunehmenden Vernetzung, insbesondere seit das Internet immer mehr Verbreitung findet, sind
Methoden zum Verschlusseln
von Daten immer wichtiger geworden. Kryptologie fand ihren Anfang vor al¨
¨
lem in militarischen
Anwendungen. Seit der Erfindung des elektronischen Geldes findet die Kryptologie1
aber immer mehr Anwendungen im kommerziellen Bereich. Die wichtigsten Stichworte sind hier: Ge¨ Integriat
¨
¨ (Falschungssicherheit).
heimhaltung, Authentifizierung(Nachweisen der eigenen Identitat),
Um zu wissen, wie sicher eine Verschlusselungsmethode
ist, mussen
wir aber auch die andere Seite
¨
¨
¨
kennen. Wahrend
sich die Kryptographie (Lehre des Verschlusselns)
mit den verschiedenen Verschlusse¨
¨
¨
lungs Methoden beschaftigt,
lehrt die Kryptoanalyse, wie man Codes knackt. Nur wenn wir die Methoden
¨
der Code-Knacker kennen, konnen
wir beurteilen, ob eine Verschlusselungsmethode
fur
¨
¨ unser Ansinnen
brauchbar (d.h. genugend
sicher) ist.
¨
Kryptologie = Kryptographie + Kryptoanalyse
In der Regel gilt, je kritischer die Daten sind, desto sicherer muss die Verschlusselung
sein, und desto
¨
¨
¨
aufwandiger
ist das Verschlusselungsverfahren.
Je schwieriger namlich
ein Code zu knacken ist, desto
¨
¨
teurer ist eine Attacke fur
Attacke versuchen,
¨ den Kryptoanalytiker. Er wird also nur dann eine aufwandige
wenn er sich einen entsprechenden Gewinn erhoffen kann. Prinzipiell gilt:
• es gibt keine einfachen Verfahren, die trotzdem einigermassen sicher sind.
• (fast) jeder Code ist knackbar, falls genugend
Zeit und genugend
verschlusselter
Text vorhanden ist.
¨
¨
¨
1 Weitere Informationen zu Kryptographie findet man zum Beispiel unter home.nordwest.net/hgm/krypto
.
9-2
9 Kryptologie
9.1 Grundlagen
¨
Ein klassisches Kryptosystem besteht aus einem Sender, einem Empfanger
und einer Datenleitung, an
¨
welcher ein Horcher2 zuhort.
Horcher
Klartext
Sender
unsichere
Datenleitung
Schlüssel
Empfänger
Klartext
Schlüssel
sichere Übertragung
Der Sender verschlusselt
eine Meldung (den Klartext) und sendet diesen uber
die unsichere Datenlei¨
¨
¨
tung dem Empfanger.
Das Verschlusseln
geschiet entweder Zeichenweise (Stromchiffre) oder der Text
¨
¨
¨
¨
wird erst in Blocke
aufgeteilt und dann werden die Blocke
verschlusselt
(Blockchiffre). Der Emfpanger
¨
entschlusselt
dann die Meldung wieder mit der Umkehrfunktion. Der verwendete Schlussel
muss vorher
¨
¨
auf sicherem Weg (zum Beispiel per Kurier) ubermittelt
werden.
¨
¨
¨
Diese Situation ist heute Normalfall nicht (mehr) gewahrleistet.
So mochte
der Kunde im WWW nicht vorher per Post mit jedem Anbieter geheime Schlussel
austauschen. Trotzdem will er sicher sein, dass kein
¨
¨
Horcher das Bankpasswort, die Bestell/Transaktionsdaten oder die Kreditkartennummer erfahrt.
Ausser¨
dem ist das Verwalten von vielen Schlusseln
sehr aufwandig
(und unsicher).
¨
¨
¨
Das Ziel ist also, ein moglichst
effizientes und doch sicheres System zu haben, welches mit moglichst
wenig Verwaltungsaufwand auskommt.
¨
2 Als Sender/Empfanger
mussen
wir davon ausgehen, dass der Horcher weiss, welches Verschlusselungsverfahren
angewandt wurde.
¨
¨
9.2 Einfache Verschlusselungmethoden
¨
9-3
9.2 Einfache Verschlusselungmethoden
¨
¨
Eine der einfachsten und altesten
Methoden zur Verschlusselung
von Texten wird Kaiser Caesar zuge¨
schrieben. Die Methode heisst darum auch die Caesar Chiffre. Dabei wird jeder Buchstabe des Textes
durch den um k Buchstaben verschobenen Buchstaben ersetzt (Stromchiffre).
Beispiel
Klartext:
A
B
C
D
E
F
G
H
I
Verschlusselt:
¨
D
E
F
G
H
I
J
K
L
···
···
W
X
Z
Y
Z
A
B
C
Der Klartext geheimer Text wird damit zu
Klartext:
G
E
H
Verschlusselt:
¨
J
H
K
E
I
M
E
R
T
E
X
T
Der Schlussel
ist k = 3, da alle Buchstaben um drei verschoben werden.
¨
¨
¨
Dieser Code lasst
sich sehr leicht knacken, auch wenn wir den Schlussel
nicht kennen. Nach hochstens
¨
27 Versuchen haben wir den Code entziffert.
Verschlusselt:
¨
X
Y
W
J
S
L
E
L
J
M
J
N
R
Klartext:
Eine etwas verbesserte Methode ist, ein Schlusselwort
als Additionstabelle zu benutzen (Blockchiffre).
¨
¨
` Chiffre. Dabei andert
Diese Verschlusselungsart
ist bekannt als Vigenere
sich die Anzahl zu verschie¨
benden Buchstaben jeweils in einem Zyklus, welcher gleich lang wie das Schlusselwort
ist.
¨
Beispiel Wir benutzen das Wort geheim als Schlussel.
Die Verschlusselung
geschieht dann nach fol¨
¨
gendem Schema:
Klartext:
D
I
E
S
E
R
Schlussel
¨
G
E
H
E
I
M
Verschlusselt:
¨
G
T
E
X
T
E
H
E
I
I
M
S
T
···
9-4
9 Kryptologie
¨
¨
Eine weitere Moglichkeit
besteht darin, alle Buchstaben zufallig
zu permutieren. Dies fuhrt
zu einer Per¨
mutationschiffre. Der Schlussel
ist dann die auf den Buchstaben benutzte Permutationsfunktion (bzw.
¨
die Umkehrung davon).
Klartext:
A
B
C
D
E
F
G
H
I
J
K
Verschlusselt:
¨
S
H
X
A
K
D
G
R
.
.
.
L
···
¨
Eine leicht verbesserte Version von Permutationschiffren benutzt Permutationen von Blocken,
zum Bei¨
spiel von Zweierblocken:
Klartext:
AA
AB
AC
AD
AE
AF
AG
AH
AI
AJ
Verschlusselt:
¨
RS
HI
WX
CD
JK
RE
HG
UV
.
.
···
Damit mussten
im Prinzip 27! (bzw. 272 !) Variationen getestet werden, um den Text zu entziffern. Leider
¨
ist die Kryptoanalyse auch fur
einfach, sofern ein normaler (deut¨ diese zwei Verschlusselungsmethoden
¨
¨
¨
scher) Text ubermittelt
wird. Um solche Texte zu knacken, arbeitet man mit Haufigkeitsanalysen.
So lasst
¨
sich zum Beispiel die Verschlusselung
des Buchstabens E schnell erraten, da dies mit grossem Abstand
¨
¨
der haufigste
Buchstabe ist.
E
-
N
R
I
S
T
A
D
H
U
L
15.36
15.15
8.84
6.86
6.36
5.39
4.73
4.58
4.39
4.36
3.48
2.93
...
¨
Am zweithaufigsten
ist das Leerzeichen, dann der Buchstabe N usw.. Da Sprache im allgemeinen stark
redundant ist, kann man oft mit Hilfe von ein paar wenigen erkannten Buchstaben bereits den ganzen
Text entziffern.
¨
¨
Auch fur
kurzer Lange)
funktioniert die gleiche Attacke. Fur
¨ Blockpermutationen (mit Blocken
¨ diese
¨
¨
¨
braucht man eine Haufigkeitsanalyse
der Zweier- (Dreier-)Blocke
einer Sprache. Der haufigste
Zweierblock in der deutschen Sprache ist die Silbe en. Der Text muss allerdings genugend
lang sein, d.h.
¨
¨
¨
genugend
viele Blocke
aufweisen, um eine aussagekraftige
Statistik zu erhalten.
¨
¨
¨
` Blockchiffren angewendet werden (sepaSolche Haufigkeitsanalysen
konnen
genau gleich auf Vigenere
¨
rat auf jeden Buchstaben des Schlusselwortes),
falls die Texte viel langer
sind als das Schlusselwort.
¨
¨
9.3 Vernamchiffre, One Time Pad
9-5
9.3 Vernamchiffre, One Time Pad
` Chiffre das Schlusselwort
¨
Falls in der Viginere
aus einer zufalligen
Buchstabenfolge besteht, die ebenso
¨
lang ist wie der verschlusselte
Text, und falls jeder Schlussel
nur einmal verwendet wird, ist das Ver¨
¨
schlusselungs-Verfahren
absolut sicher. Man nennt dieses Verfahren die Vernam-Chiffre oder das One
¨
Time Pad.
¨
Die Vernam-Chiffre ist allerdings sehr umstandlich,
da fur
Zeichen zuvor ein Zei¨ jedes zu ubermittelnde
¨
chen uber
einen sicheren Weg transportiert werden muss. Dennoch wird sie benutzt, wenn absolute,
¨
¨ ist.
beweisbare Sicherheit notig
¨
Statt einer zufalligen
Buchstabenfolge (welche auf einem sicheren Weg ubermittelt
werden muss), wird
¨
¨
als Schlussel
haufig
eine Zufalls-Zahlenreihe benutzt. Diese wird mit Hilfe einer geheimen, vorher aus¨
¨
gemachten Zufallsfunktion generiert. Solange der Horcher diese Funktion nicht durch Sabotage erfahrt,
ist dieses Verfahren sehr effizient und ebenfalls sicher. Oft werden sogar mehrere Zufalls-Funktionen
kombiniert oder abwechlungsweise benutzt.
Beispiel: Eine Funktion, welche eine gute “Zufallsfolge” herstellt, ist zum Beispiel die Funktion f (n) =
⌊100(sin(n) + 1)⌋. Die erzeugte Zahlenreihe ist:
n
:
1
2
3
4
5
6
7
8
9
10
11
12
...
f (n)
:
184
190
114
24
4
72
165
198
141
45
0
46
...
f (n) mod 27 :
22
1
6
24
4
18
3
9
6
18
0
19
...
Mit Hilfe von solchen Funktionen werden sogennante Verschlusselungs/Entschl
usselungs-Maschinen
ge¨
¨
¨
¨
baut, zum Beispiel fur
von grossen Datenmengen notig
¨ Telefone, die typischerweise die Ubertragung
¨ erzeugen jeweils die gleiche Zufallsfolge zum (binaren)
¨
machen. Beide Gerate
Ver- bzw. Entschlusseln
¨
der geheimen Texte. Die im Telefon eingebauten Schlusselerzeuger
sind dann im Prinzip nichts anderes
¨
als gute und effiziente Zufallszahlen-Generatoren.
9-6
9 Kryptologie
9.4 Moderne symmetrische Verfahren
Die meisten der heute eingesetzten symmetrischen Verfahren sind Blockchiffren. Dabei wird der Text in
¨
¨
¨
¨
Blocke
einer gewissen Lange
(haufig
8 oder 16 Zeichen, also 64 oder 128 Bits) zerlegt. Auf diese Blocke
wird dann eine Kombination von verschiedenen einfachen Verschlusselungsverfahren
(z.B. modulare Ad¨
¨
dition, Substitution, Linear-Transformation, Vertauschen von Teilblocken,
...) angewandt.
Das folgende Bild zeigt zum Beispiel die Anordnung fur
¨ DES.
Normalerweise wird ein geheimer, vorher vereinbarter Schlussel
verwendet. Das Entschlusseln
geschieht
¨
¨
indem alle Operationen in umgekehrter Reihenfolge (invers) angewandt werden.
Beispiele von Blockhiffren sind: DES (Data Encryption Standard) oder DEA (Data Encryption Algorithm)
¨
, benutzt einen Schlussel
der Lange
56. Triple-DES: Dreimaliges Anwenden von DES mit zwei oder
¨
drei verschiedenen Schlusseln.
RC4 Rivest Cipher, 1987 von Ronald L. Rivest, eine Stromchiffre IDEA:
¨
¨
arbeitet ahnlich
wie DES, CAST, ... SSL (Secure Socket Layer) verwendet RC4, DES oder Triple-DES.
S-HTTP (Secure HTTP) verwendet DES, Triple-DES oder IDEA. PGP (Pretty Good Privacy) benutzt
verschiedene der Verfahren IDEA, Triple-DES, RSA, ...
9.5 Asymmetrische Verfahren: Public Key Kryptosysteme
9-7
9.5 Asymmetrische Verfahren: Public Key Kryptosysteme
Bei kommerziellen Applikationen wie zum Beispiel Telebanking, beim Benutzen von elektronischem Geld
¨
oder beim Versenden von (geheimer) Email ist es zu aufwandig,
mit jedem Kunden/Partner vorher geheime Schlussel
auszutauschen. Um genugend
Sicherheit zu bieten, mussten
lange Schlussel
verwendet
¨
¨
¨
¨
¨
¨
werden, welche haufig
gewechselt werden. (Die mit den Banken vereinbarten Schlussel/Passw
orter
die¨
nen beim Telebanking in der Regel in erster Linie zur Authentifikation/Identifikation des Kunden.)
Es gibt aber Verfahren, welche ohne die Verteilung von geheimen Schlusseln
auskommen, und die darum
¨
Public Key Kryptosysteme (PKK) genannt werden3 . Wie der Name sagt, benutzen PKKs nicht geheime,
¨
sondern offentliche
Schlussel
zum Verschlusseln
der Texte.
¨
¨
Verschlüsselung
öffentlicher
Schlüssel des Empfängers
Entschlüsselung
Übermittlung
geheimer
Schlüssel des Empfängers
In PKKs werden fur
Funktionen benutzt, welche leicht zu berechnen, aber ohne
¨ die Verschlusselung
¨
¨
¨
¨
zusatzliches
Wissen nicht invertierbar sind. Diese Einwegfunktionen konnen
dann offentlich
bekannt
gegeben werden. Da die Funktionen schwierig zu invertieren sind, ist das Entschlusseln
nicht einfach
¨
¨
moglich.
Es gilt dann also:
¨
• Jeder kann mit dem offentlichen
Schlussel
Meldungen codieren.
¨
• Nur wer den geheimen Schlussel
kennt, kann die Meldung decodieren.
¨
Definition: Eine bijektive Funktion f : X → Y heisst eine Einwegfunktion falls gilt:
• Die Funktion f ist leicht (mit wenig Rechenaufwand) zu berechnen.
3 Da fur
zum Ver- bzw. Entschlusseln
verwendet werden, spricht man auch von asymmetrischen
¨ diese Verfahren zwei verschiedene Schlussel
¨
¨
Verfahren.
9-8
9 Kryptologie
¨
• Die Umkehrfunktion f −1 ist ohne zusatzliche
(geheime) Informationen sehr schwierig (mit grossem
Aufwand) zu berechnen.
Ein einfaches Modell fur
¨ eine Einwegfunktion ist ein Telefonbuch, mit welchem sehr schnell zu jedem
¨
Namen mit Adresse die Telefonnummer gefunden werden kann. Hingegen ist es sehr aufwandig,
mit
¨
Hilfe eines Telefonbuchs zu einer Telefonnummer den zugehorigen
Namen zu finden. Es musste
das
¨
ganze Buch durchsucht werden.
¨
Das Finden von sicheren Einwegfunktionen ist nicht einfach. Wenn wir den Schlussel
kennen, konnen
wir
¨
in allen bisherigen Verfahren sehr leicht die Umkehrfunktion berechnen. Das Suchen von guten, schnellen
und beweisbar sicheren Einwegfunktionen ist ein zentrales Forschungsgebiet der Kryptologie. Heute sind
aber schon einige praktisch verwendbare (nicht beweisbar sichere) Einwegfunktionen bekannt.
Die Idee bei einem Public Key Kryptosystem ist, dass jeder Teilnehmer fur
¨ sich ein Paar von Schlusseln
¨
¨
generiert: einen offentlichen
Schlussel
zum Verschlusseln
der Meldungen, und einen privaten, gehei¨
¨
¨
men Schlussel
zum Entschlusseln.
Der geheime Schlussel
darf aus dem offentlichen
Schlussel
nur mit
¨
¨
¨
¨
¨
riesigem Aufwand oder gar nicht berechnet werden konnen.
Der erste Schlussel
generiert dann eine Einwegfunktion, welche nur mit Kenntnis des zweiten Schlus¨
¨
sels (oder nur mit sehr grossem Aufwand) invertiert werden kann.
¨
Um einem Teilnehmer eine Meldung zu verschicken, verschlusseln
wir die Meldung mit dessen offentli¨
chem Schlussel.
Nur der Adressat, der den geheimen Schlussel
kennt, kann die Einwegfunktion invertie¨
¨
ren, also die verschlusselte
Meldung wieder entschlusseln.
¨
¨
Definition: Fur
die folgenden Bedingungen erfullt
¨ ein PKK mussen
¨
¨ sein:
1. Es gibt genugend
viele Paare (V, E) von Verschlusselungsund Entschlusselungsfunktionen
(bzw.
¨
¨
¨
¨
von offentlichen
und geheimen Schlusseln
(v,e)).
¨
2. Fur
¨ jede Meldung M gilt E(V (M)) = M .
3. V ist eine Einwegfunktion.
4. V und E sind leicht zu berechnen, wenn man den Schlussel
v, bzw. e kennt.
¨
9.5 Asymmetrische Verfahren: Public Key Kryptosysteme
9-9
¨
Das erste PKK ist der Diffie-Hellmann Algorithmus von 1976. Auf einer ahnlichen
Idee basiert der um
1978 von R. Rivest, A. Shamir und L. Adleman gefundene RSA Algorithmus. Die darauf basierenden
Verfahren werden deshalb RSA-Kryptosysteme genannt.
9.5.1 Das RSA Verfahren
Das RSA-Verfahren ist heute das am meisten benutzte PKK. RSA bildet die Grundlage fur
¨ SSL (Secure
Socket Layer), welche vor allem fur
¨ WWW gebraucht werden, fur
¨ SET (Secure Electronic Transactions),
welche im Zusammenhang mit elektronischem Geld wichtig sind, fur
¨ S/Mime, also sichere Email und
vieles mehr (z.B. S-HTTP, SSH, ...).
Die Sicherheit des RSA-Verfahren basiert auf dem Problem, eine grosse Zahl in ihre Primfaktoren zu
zerlegen und aus dem Problem des diskreten Logarithmus. Das Berechnen von M v modm ist relativ
einfach. Fur
¨ das Berechnen der v-ten Wurzel modulo m ist bisher kein schneller Algorithmus bekannt.
Die beiden Schlussel
werden so erzeugt:
¨
¨
• Wahle
zwei verschiedene grosse Primzahlen p und q und berechne deren Produkt: m = p ∗ q. Setze
n = (p − 1) · (q − 1).
¨
• Wahle
einen beliebigen Wert e, der kleiner ist als m und teilerfremd zu n. Zu diesem wird dasjenige
v berechnet, fur
¨ das gilt: e · v = 1 + l · n (Euklid’scher Algorithmus).
˜ = M˜ e mod m.
Es gilt dann fur
V (M) = M v mod m fur
E(M)
¨ das Verschlusseln:
¨
¨ das Entschlusseln:
¨
v
V(M) = M mod m
öffentlicher
Schlüssel des Empfängers
Übermittlung
e
E(M) = M mod m
geheimer
Schlüssel des Empfängers
¨
Es gilt namlich
nach dem Satz von Fermat
E(V (M)) = (V (M))e mod m = M ve mod m = M (1+ln) modm = M
9-10
9 Kryptologie
9.5.2 Authentifikation mit Hilfe von RSA
¨
¨
Mit Hilfe eines RSA-Kryptosystems konnen
wir auch feststellen, ob der Absender einer Meldung tatsachlich derjenige ist, der er zu sein vorgibt. Durch umgekehrtes Anwenden des RSA-Verfahrens kann der
¨
Empfanger
nachprufen,
ob die Meldung vom richtigen Sender stammt.
¨
Wir wissen bereits, dass E(V (M)) = M ve mod m = M gilt. Die Potenzoperation ist aber kommutativ,
¨
so dass auch M ev mod m = M gilt. Wir konnen
also die Operationen Verschlusseln/Entschl
usseln
auch
¨
¨
umdrehen.
Verschlüsselung
Übermittlung
Entschlüsselung
öffentlicher
Schlüssel des Senders
geheimer, privater
Schlüssel des Senders
¨
Nur wenn beim Entschlusseln
eines Textes mit dem offentlichen
Schlussel
des Absenders Klartext ent¨
¨
¨
steht, stammt die Meldung von diesem Absender. Da nur der Absender den zu seinem offentlichen
Schlussel
passenden geheimen Schlussel
kennt, kann nur dieser eine solche Meldung verfassen.
¨
¨
¨
9.5.3 Integritatspr
ufung:
¨
Fingerabdruck, Message Digest
¨
Ein zentrales Problem vor allem von grossen Anbietern (Banken, Online-Verkaufern,
...) ist, den Kunden
¨
zu garantieren, dass eine (unverschlusselte)
Webseite tatsachlich
die richtige Seite ist (und nicht eine
¨
¨
¨ werden.
gefalschte).
Dieses Problem kann mit Hilfe einer Hashfunktion und eines PKKs gelost
Übermittlung
Hash
Funktion
1
0
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
=?
Hash
Funktion
Verschlüsselung
geheimer, privater
Schlüssel des Senders
Entschlüsselung
öffentlicher
Schlüssel des Senders
9.5 Asymmetrische Verfahren: Public Key Kryptosysteme
9-11
¨
Falls beim Entschlusseln
des Hashcodes mit dem offentlichen
Schlussel
des Absenders der gleiche Wert
¨
¨
¨
herauskmmt, sind wir sicher, dass unterwegs niemand die Meldung verandert
hat.
¨
Allerdings funktioniert dies nur, wenn der uns bekannte offentliche
Schlussel
korrekt ist, uns also kein
¨
¨
falscher Schlussel
vorgetauscht
wird. Dies garantieren spezielle Firmen und Institutionen, sogenannte
¨
Trustcenter wie TC TrustCenter, VeriSign oder Thawte.
9.5.4 Kombinierte (Hybride) Verfahren
Eine kombinierte Methode verbindet die Sicherheit von RSA mit der Schnelligkeit von symmetrischen
Verschlusselungsmethoden,
wie zum Beispiel DES.
¨
DES
DES Schlüssel
0110
000000000
111111111
111111111
000000000
111111111
000000000
111111111
000000000
111111111
000000000
Übermittlung
Digital
Envelope
Verschlüsselung
öffentlicher Schlüssel
des Empfängers
Ein Digital Envelope wird erzeugt, indem der Text durch ein schnelles, weniger sicheres Verfahren ver¨
schlusselt
wird (zum Beispiel mit DES), der DES-Schlussel
selber wird mit dem offentlichen
RSA-Schlus¨
¨
¨
¨
sel des Empfangers
verschlusselt.
¨
¨
Auf diese Weise konnen
die Vorteile beider Systeme kombiniert werden. Es mussen
keine geheimen
¨
Schlussel
auf einem (langsamen) sicheren Weg vorher vereinbart werden. Ausserdem kann fur
¨
¨ jede
¨
Ubermittlung ein neuer DES-Schlussel
verwendet werden. Durch einmaliges Verwenden jedes DES¨
Schlussels
wird die Sicherheit des DES-Verfahrens erheblich verbessert.
¨
¨
Nur der Empfanger
kann den DES-Schlussel
lesen, da er dazu seinen privaten RSA-Schlussel
braucht.
¨
¨
Danach kann er mit Hilfe des DES-Schlussels
den Text entziffern.
¨
9-12
9 Kryptologie
¨
9.6 Ubung
9
Fragen / Aufgaben zur Kryptologie
¨ uhrung
¨
Sie finden die Losungen
zu den Fragen entweder im Skript oder unter dem Link Einf
in die Kryp¨
¨
¨ der Ubungsseite.
tologieauf
1. Welches sind heute die zentralen Einsatzgebiete der Kryptologie?
2. Was bedeutet Kryptografie?
3. Was bedeutet Kryptoanalyse?
4. Was ist Steganografie?
¨
¨
5. Wie heisst der Uberbegriff
fur
Zeichenweise ablauft?
¨ die Verfahren, bei welcher die Verschlusselung
¨
¨
6. Gewisse Verfahren teilen den Text zuerst in gleich grosse Blocke
(zum Beispiel 64 Bit) auf: Welches
¨
ist der Uberbegriff
fur
¨ diese Verfahren?
7. Skizzieren Sie ein symmetrisches Kryptosystem.
¨
8. Verschlusseln
Sie mit der Casar
Chiffre und dem Schlussel
B (k=1) Ihren Namen.
¨
¨
` Chiffre und dem Schlussel
9. Verschlusseln
Sie mit der Viginere
BBC Ihren Namen.
¨
¨
10. Welches sind die Vor- und Nachteile des One Time Pad (Vernam Chiffre)?
11. Was waren die Hauptgrunde
dafur,
¨
¨ dass die Enigma im zweiten Weltkrieg geknackt werden konnte?
¨
(Punkte 3, 6 und 7 der Aufzahlung
unter http://www.nwn.de/hgm/krypto/ → Enigma)
12. Welche symmetrischen Kryptoverfahren werden heute (noch) verwendet?
13. Skizzieren Sie ein asymmetrisches Kryptosystem.
14. Welches ist der Hauptunterschied zwischen symmetrischen und asymmtetrischen Verfahren?
15. Wer hat das erste PKK erfunden?
16. Worauf basiert die Sicherheit von RSA?
¨ man mit einem PKK das Authentizitatsproblem?
¨
17. Wie lost
¨ man mit einem PKK das Integritatsproblem?
¨
18. Wie lost
19. Was ist der Vorteil von hybriden Kryptoverfahren?
Literaturverzeichnis
[AHU74] Aho, Hopcroft, and Ullman. The Design and Analysis of Computer Algorithms. Addison Wesley,
Reading, Massachusetts, 1974. ISBN 0-201-00029-6.
[AU95]
A.V. Aho and J.D. Ullman. Foundations Of Computer Science C Edition. Computer Science
Press An Imprint of W.H. Freeman and Company, New York, 1995. ISBN 0-7167-8284-7.
[Bud94] Timothy A. Budd. Classic Data Structures in C++. Addison-Wesley, Reading, MA, 1994.
[Knu73a] D.E. Knuth. The Art of Computer Programing, volume 3 Sorting and Searching. Addison Wesley,
Reading, MA, 1973. ISBN 0-201-03803-X.
[Knu73b] D.E. Knuth. The Art of Computer Programing, volume 1 Fundamental Algorithms. Addison
Wesley, Reading, MA, 1973. ISBN 0-201-03809-9.
[Knu81] D.E. Knuth. The Art of Computer Programing, volume 2 Seminumerical algorithms. Addison
Wesley, Reading, MA, 1981. ISBN 0-201-03822-6.
[Sed92] Robert Sedgewick. Algorithmen in C++. Addison Wesley, Bonn, 1992. ISBN 3-89319-462-2.
[Sed03] Robert Sedgewick. Algorithmen in Java. Grundlagen, Datenstrukturen, Sortieren, Suchen..
Pearson Studium, 2003. ISBN 3-82737-072-8.
[Sha97] Clifford A. Shaffer. A Practical Introduction to Data Structures and Algorithm Analysis. Prentice
Hall, London, 1997. ISBN 0-131-90752-2, C++ Version.
[Sha98] Clifford A. Shaffer. A Practical Introduction to Data Structures and Algorithm Analysis: Java
Edition. Prentice Hall, London, 1998. ISBN 0-136-60911-2.
[Wir86]
N. Wirth. Algorithmen und Datenstrukturen mit Modula-2. Teubner, Stuttgart, 1986. ISBN
0-13-629031-0.
[SaSa04] Gunter Saake, Kay-Uwe Sattler Algorithmen und Datenstrukturen, Eine Einfuhrung
mit Java.
¨
dpunkt, 2004. ISBN 3-89864-255-0.
[Schied05] Reinhard Schiedermeier Programmieren mit Java, Eine methodische Einfuhrung.
Pearson
¨
Studium, 2005 ISBN 3-8273-7116-3.
W-2
Index
abstrakter Datentyp, 1-5, 1-6
Algorithmus, 1-9
asymptotisches Verhalten, 2-5, 2-7
¨ 2-1
Komplexitat,
O-Notation, 2-7
Allgemeine Strukturen, 1-4
Array
Grundtyp, 1-4
Indextyp, 1-4
Selektor, 1-4
Atomare Typen, 1-3
Auswahl, 7-2
Automat, 7-3
¨
ε-Ubergang,
7-6
Ausgabe, 7-4
deterministischer, 7-5
Eingabe, 7-3
Eingabealphabet, 7-3
endlicher, 7-2
¨
leerer Ubergang,
7-6
nichtdeterministischer, 7-5
Zustand, 7-3
Zustandsdiagramm, 7-4
Zustandstafel, 7-4
B-Baum, 4-10
¨
Baume,
4-1
BinNode, 4-2
¨
Baumdurchlaufe,
4-4
Breitensuche, 4-7
Inorder, 4-4
Levelorder, 4-7
Postorder, 4-4
¨
Praorder,
4-4
Tiefensuche, 4-4, 4-6
¨
Binarbaum,
4-1, 4-2
¨ Suchbaume,
¨
Binare
4-8
Caesar Chiffre, 9-3
Compiler, 8-1
Daten, 1-2
Bezeichung, 1-2
Semantik, 1-2
Syntax, 1-2
Wertemenge, 1-2
Datenstruktur, 1-6
Datentyp, 1-2
Konstanten, 1-2
Methoden, 1-2
Operatoren, 1-2
Wertebereich, 1-2
Divide and Conquer, 1-18
EBNF, 8-2
Einwegfunktion, 9-8
Extended Backus-Naur Form, 8-2
Grammatik, 8-2
Herleitung, 8-3
kontextfreie, 8-2
Nichtterminalsymbol, 8-3
Produktion, 8-3
Terminalsymbol, 8-3
Hashing, 5-5
Bucket Hashing, 5-11
Double Hashing, 5-8
Kollision, 5-6
Linear Probing, 5-8
Separate Chaining, 5-13
Heap, 4-15
Heapbedingung, 4-16
Iteration, 1-12, 7-2
Klassen, 1-4
¨ 2-1
Komplexitat,
Best-Case, 2-4
Worst-Case, 2-4
Konkatenation, 7-2
Kryptoanalyse, 9-1
Kryptologie, 9-1
Caesar Chiffre, 9-3
Einwegfunktion, 9-8
Permutationschiffre, 9-4
Public Key Kryptosystem, 9-7, 9-8
RSA-Kryptosystem, 9-9
Vernam-Chiffre, 9-5
` Chiffre, 9-3
Vigenere
Kryptosystem, 9-2
Liste, 3-1
Array Liste, 3-1
doppelt verkettet, 3-5
Node, 3-5
O-Notation, 2-6
Parser, 8-1
Pattern, 7-1
Alphabet, 7-1
Wort, 7-1
Pattern Matching, 7-1
Permutationschiffre, 9-4
Priority Queue, 4-15
Priority Queues, 4-15
Pseudocode, 1-10
Public Key Kryptosystem, 9-7, 9-8
Queue, 3-1, 3-11
¨
Regularer
Ausdruck, 7-2
Rekursion, 1-15
RSA-Kryptosystem, 9-9
Sortieren
Insertion-Sort, 6-4
Merge-Sort, 6-9
Quick-Sort, 6-6
Selection-Sort, 6-2
stabiler Algorithmus, 6-1
Spezifikation, 1-8
Sprache, 8-3
Herleitung, 8-3
Stack, 3-1, 3-11
Suchen, 5-1
¨ Suche, 5-3
Binare
Lineare Suche, 5-2
Top Down Parser, 8-1
Trustcenter, 9-11
Vernam-Chiffre, 9-5
Verschlusselung,
9-1
¨
` Chiffre, 9-3
Vigenere

Download PDF (496KB) - Springer

Blatt 10

Anlagenbericht Helbra - SAXLUND International GmbH

Anlagenbericht - SAXLUND International GmbH

Seminar - Mathematisches Institut der Universität Heidelberg

Aktueller Menüplan

Übungsblatt 1

Turnierkalender drucken

Blatt 06 - Fakultät für Mathematik

2015 - khrt.org

Algorithmen und Datenstrukturen SS 2015

Universal-Investment Factsheet

Einleitung p. 1 Was ist Computeralgebra? p. 1 Literatur p. 3

CRPM Veranstaltungen 2015

Pfarrblatt

Produktkatalog Product Catalog Instruments and