Kapitel 6-7

Ein Algorithmus ist eine detaillierte und explizite Vorschrift zur schrittweisen Lösung eines Problems, die präzise formuliert, in endlicher Form dargestellt und effektiv ausführbar ist.

• Elementare Operation: Die Basiselemente eines Algorithmus, die ausgeführt werden, ohne näher aufgeschlüsselt zu werden.

• Sequentielle Ausführung: Das Hintereinanderausführen von Schritten.

• Bedingte Ausführung: Schritt, der nur ausgeführt wird, falls bestimmte Bedingung erfüllt ist.

• Schleife: Wiederholte Ausführung einer Tätigkeit, bis vorgegebene Bedingung nicht mehr erfüllt ist

• Liste wird Element für Element durchsucht, bis gesuchtes gefunden wird.

• Suchaufwand wächst mit Anzahl der Elemente linear an

• funktioniert nur mit sortierten Listen

• Liste wird in der Hälfte geteilt und mit gesuchtem Element verglichen

• in passenderen Hälfte wird solange weiter geteilt und gesucht, bis das verglichene Element dem gesuchtem Element gleich ist

kommen beim Sortieren von Folgen zum Einsatz, die auf externen Datenmedien wie Festplatte oder Magnetband ab- gelegt sind. Speziell in Datenbanksystemen, die Giga- oder Terabytes verwalten, werden externe Verfahren eingesetzt.

kommen beim Sortieren von Folgen zum Einsatz, die als Ganzes in den Hauptspeicher passen.

Der Insertion Sort gehört in der Informatik zu den stabilen Sortieralgorithmen und kann als Sortieren durch Einfügen beschrieben werden.

Algorithmus

Funktionsweise

1. Liste in zwei Hälften zerlegen. Solange weiter unterteilen, bis nur noch ein Element in einer Menge vorhanden ist.

2. Teillisten wieder schrittweise zu Listen zusammenfügen, beim zusammenfügen sortieren

Funktionsweise:

• Pivotelement auswählen, in zwei Teillisten trennen.

• Alle Elemente < Pivotelement, kommen in die linke Teilliste; alle Elemente > Pivotelement, in die rechte Teilliste.

• Nach der Aufteilung sind die Elemente der linken Liste kleiner oder gleich den Elementen der rechten Liste.

• Um Teillisten zu sortieren, wird quickSort auf Teillisten angewandt

InsertionSort: langsamer Algorithmus, nur für kleine Listen o. zum einsortieren in sortierte Listen

MergeSort: schneller Algortihmus (sowohl in Best-, Worst- und Average-Case), stabil, braucht viel Zwischenspeicher bei großen Datenmengen

QuickSort: schneller Algorithmus, nicht stabil,

Prinzip:

• häufig vorkommende Zeichen bekommen einen kurzen Code

• wenig vorkommende Zeichen bekommen einen langen Code

Encodieren:

• relative Häufigkeiten der vorkommenden Zeichen berechnen

• Huffmann-Codebaum erzeugen

• Codes aus Baum ableiten

Prinzip:

wiederkehrende Textmuster kompakt speichern, indem an der Position des zweiten Auftretens einer Zeichenfolge, auf die erste Zei- chenfolge verwiesen wird.

Encodierung & Decodierung TBD:

• Jedes Zeichen bekommt einen Blattknoten, Blattknoten nach Häufigkeit sortieren

• Zeichen mit geringster relativer Häufigkeit mit Verbindungsknoten verbinden, linke Kante mit 0 markieren, rechte Kante mit 1

• Verbindungsknoten hat die Summe der Häufigkeit seiner Blätter

• verbleibende Knoten immer nach geringster relativer Häufigkeit verbinden, bis man einen Ursprungsknoten hat

Prinzip:

• Längere Zeichenketten werden durch kürzere Kodierung ersetzt

• bei häufigem Auftreten von längeren Zeichenketten ergibt sich eine große Datenreduktion

Encodierung:

• Eingabe wird von links abgearbeitet

• Zeichen wird mit nachfolgendem Zeichen solange Code zugeordnet, bis Zeichenfolge erneut vorkommt

• Zeichenkette wird um nachfolgendes Zeichen ergänzt und neuer Code zugeordnet