|
Folien
Übungen
Bilder
 Zurück
|
Multimedia-Ergänzungen zum Buch: Algorithmen und Datenstrukturen, Kapitel 9: Ausgewählte Themen
|
|
|
Textsuche
In zahlreichen Anwendungen von Computern spielen Texte eine dominierende
Rolle. Man denke etwa an Texteditoren, Literaturdatenbanken,
Bibliothekssysteme und Systeme zur Symbolmanipulation. Der
Begriff Text wird hier meistens in
einem sehr allgemeinen Sinne benutzt. Texte sind nicht weiter
strukturierte Folgen beliebiger Länge von Zeichen aus einem
endlichen Alphabet. Das Alphabet kann Buchstaben, Ziffern und zahlreiche
Sonderzeichen enthalten.
Der diesen Anwendungen zugrundeliegende Datentyp ist der Typ string. Wir lassen offen,
wie dieser Datentyp programmtechnisch realisiert wird.
Unabhängig
von der programmtechnischen Realisierung soll jeder Zeichenkette eine nichtnegative,
ganzzahlige Länge zugeordnet werden können und der Zugriff auf das i-te Zeichen einer
Zeichenkette möglich sein. Algorithmen zur Verarbeitung
von Zeichenketten (string processing) umfassen ein weites
Spektrum. Dazu gehören das Suchen in Texten und allgemeiner das Erkennen bestimmter
Muster (pattern matching), das Verschlüsseln und Komprimieren von
Texten, das Analysieren (parsing) und Übersetzen von Texten und
viele andere Algorithmen.
Wir wollen in diesem Abschnitt nur das Suchen in Texten behandeln und einige
klassische Algorithmen zur Lösung dieses Problems angeben.
Parallele Algorithmen
Wir sind bisher stets davon ausgegangen, dass die Instruktionen von Programmen
durch einen einzigen Prozessor sequentiell nacheinander ausgeführt
werden. Als Modell eines solchen, nach dem Von-Neumann-Prinzip
aufgebauten Rechners haben wir die Random-Access-Maschine
(RAM) eingeführt. Eine Beschleunigung von Algorithmen für Rechner dieses
Typs kann nur dadurch erfolgen, daß man die Arbeitsgeschwindigkeiten der
einzelnen Systemkomponenten (Prozessor, Speicher,
Datenübertragungswege) erhöht. Hier ist man inzwischen fast an der
Grenze des physikalisch Möglichen angelangt. Eine weitere Steigerung der
Rechengeschwindigkeit ist jedoch erreichbar, wenn man die
Von-Neumann-Architektur verläßt und sogenannte Parallelrechner mit vielen
Prozessoren benutzt, die es erlauben, mehrere Verarbeitungsschritte gleichzeitigauszuführen.
Parallelität bedeutet aus algorithmischer Sicht, dass man Probleme daraufhin
untersucht, ob sich mehrere zur Lösung erforderliche Teilaufgaben unabhängig
voneinander und damit parallel erledigen lassen. Solche Verfahren können
dann unter Umständen auf geeigneten Parallelrechnern implementiert
werden.
Inzwischen wurde eine größe Zahl verschiedener Parallelrechner vorgeschlagen
und teilweise auch realisiert. Analog zur RAM hat man auch idealisierte
Modelle von Parallelrechnern vorgeschlagen und studiert. Das wichtigste
Modell ist die
Parallel-Random-Access-Maschine (PRAM). Sie besteht aus p
Prozessoren, die sämtlich auf einen gemeinsamen Speicher
zugreifen können. Außer diesem gemeinsamen Speicher verfügt jeder
Prozessor noch über einen privaten Arbeitsspeicher. Die p
Prozessoren sind synchronisiert, d.h. sie führen Rechenschritte gleichzeitig,
taktweise durch.
|
|
Bei Fragen zu
dem Inhalt des Buches senden Sie bitte eine Email an ad-buch@informatik.uni-freiburg.de.
|
|