nach oben

2012 | Buch

Kapitel lesen Erstes Kapitel lesen

Entwurf und Analyse von Algorithmen

verfasst von: Markus Nebel

Verlag: Vieweg+Teubner Verlag

Buchreihe : XSB Informatik

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

Kenntnisse über effiziente Algorithmen und Datenstrukturen sind eine der zentralen Voraussetzungen für die Entwicklung leistungsfähiger Programme. Daher ist es wichtig, für grundlegende Probleme der Informatik gute algorithmische Lösungen zu kennen und zu verstehen, wie diese zu Lösungen komplexerer Aufgaben kombiniert werden können. Entsprechend behandelt dieses Buch eine Vielzahl bekannter Datenstrukturen und Algorithmen. Doch nicht für alle Probleme, denen wir in der Praxis begegnen, gelingt eine Lösung nur aus bereits bekannten Bausteinener. Für die Lösung solcher Probleme werden Herangehensweisen - Entwurfsmethoden genannt - vorgestellt.

Inhaltsverzeichnis

Frontmatter

1. Einleitung

Zusammenfassung

Ein Computer bedarf der Programmierung, um sinnvoll eingesetzt werden zu können. Möchte man ihn zur Lösung bestimmter Probleme verwenden, wie etwa das Sortieren von Daten oder die Multiplikation von Matrizen, so muss die Programmierung eine Vorschrift beschreiben, die festlegt, in welcher Reihenfolge der Computer welche Aktionen durchzuführen hat, damit letztlich die gesuchte Lösung erzeugt wird. Dabei ist es unsinnig, die Vorschrift für eine einzige Eingabe maßzuschneidern. Ziel muss es sein, alle für das jeweilige Problem sinnvolle Eingaben nach derselben Vorschrift abzuarbeiten.

Markus Nebel

2. Elementare Datenstrukturen

Zusammenfassung

Wie wir im vorherigen Kapitel gesehen haben, unterscheiden wir zwischen einem Abstrakten Datentyp und seiner Implementierung. In diesem Kapitel werden wir einige fundamentale Abstrakte Datentypen kennenlernen und verschiedeneMöglichkeiten der Implementierung beleuchten. Ziel dabei ist, die Vor- und Nachteile der jeweiligen Implementierung zu erkennen. Einige der hier behandelten Typen werden wir später als Teil der Lösung von speziellen Problemen wiederfinden.

Markus Nebel

3. Das Wörterbuchproblem

Zusammenfassung

In diesem Kapitel befassen wir uns mit der Suche nach bereits gespeicherten Daten. Hierfür nehmen wir an, dass jeder Datensatz (jedes Element der Menge gespeicherter Daten) durch einen sog. Schlüssel eindeutig identifiziert wird. In der Anwendung kann dies z. B. die Matrikelnummer sein, die einen Studenten unter allen anderen eindeutig identifiziert. Der Datensatz kann noch weitere Informationen wie den Namen oder die Adresse des Studenten speichern.

Markus Nebel

4. Graph-Algorithmen

Zusammenfassung

Ein Graph-Algorithmus ist ein Algorithmus, der auf einem Graphen operiert. Da Graphen für die Modellierung der unterschiedlichsten Dinge und Zusammenhänge eingesetzt werden, ist auch die Anzahl unterschiedlicher Graph-Algorithmen immens. Viele Anwendungen jedoch haben bestimmte Kernprobleme wie z. B. die Bestimmung kürzester Wege oder die Berechnung eines minimal spannenden Baumes gemeinsam. Solchen Kernproblemenwollen wir uns in diesem Kapitel zuwenden.

Markus Nebel

5. Sortieren

Zusammenfassung

In diesemKapitelwollen wir uns einemanderen Standardproblemder Informatik zuwenden, dem Sortieren. Dabei geht es darum, eine Menge von Daten, deren Elemente in der Regel eindeutig über einen Schlüssel identifiziert werden, in die bzgl. des Schlüssels aufsteigend sortierte Anordnung zu bringen.Wie auch bei denWörterbüchern abstrahieren wir von den sonstigen Daten eines Datensatzes und betrachten nur die Schlüsselwerte. Der Datentyp der Schlüssel spielt dabei keine wesentliche Rolle.

Markus Nebel

6. String-Algorithmen

Zusammenfassung

Die Modellierung von Objekten als Wörter (Strings) ist in der Informatik allgegenwärtig; durch das wachsende Interesse an der Bioinformatik hat sie in jüngerer Zeit verstärkt Aufmerksamkeit erhalten. Wir studieren deshalb in diesem Kapitel grundlegende Algorithmen und Datenstrukturen zur Verarbeitung von Wörtern. Dazu zählen Verfahren zur exakten Suche von Wörtern in Wörtern genauso wie Methoden zur Bestimmung von Wiederholungen in einem Wort.

Markus Nebel

7. Entwurfsmethoden für Algorithmen

Zusammenfassung

Über die Zeit haben Informatiker eine Reihe von Methoden entdeckt, deren Anwendung bei der Suche nach einem neuen Algorithmus oft zu einem effizienten Verfahren führt. In diesem Kapitel wollen wir uns solchen Methoden zuwenden.

Markus Nebel

8. Komplexitätstheorie

Zusammenfassung

Bisher haben wir uns ausschließlich mit Problemen beschäftigt, für die eine algorithmische Lösung existierte, die mit einer in der Eingabegröße polynomiellen Laufzeit auskommt. Doch was ist, wenn wir eine solche Lösung nicht finden?Wie sollen wir diesen Umstand unserem Auftraggeber erklären?Wenn wir ihm beweisen könnten, dass nicht nur wir keinen solchen Algorithmus finden, sondern dass für das betrachtete Problem kein Algorithmus mit polynomieller Laufzeit existiert, kann er wohl kaum mit uns unzufrieden sein. Er sollte dann vielmehr sein Problem neu formulieren (vielleicht ist er ja nur an Spezialfällen interessiert, für die effiziente Lösungen existieren) oder sich mit approximativen Lösungen zufriedengeben (hierzu kommen wir im nächsten Kapitel).

Markus Nebel

9. Entwurfsmethoden für schwere Optimierungsprobleme

Zusammenfassung

ImvorherigenAbschnitt habenwir Entscheidungsprobleme in Probleme formaler Sprachen transformiert, indem wir L als die Sprache all jener codierten Instanzen des Problems definierten, für die das Entscheidungsproblemdas Ergebnis JA liefert.

Markus Nebel

10. Anhang

Markus Nebel

Backmatter

Titel: Entwurf und Analyse von Algorithmen
verfasst von: Markus Nebel
Verlag: Vieweg+Teubner Verlag
Electronic ISBN: 978-3-8348-2339-7
Print ISBN: 978-3-8348-1949-9
DOI: https://doi.org/10.1007/978-3-8348-2339-7

Springer Professional

Über dieses Buch

Inhaltsverzeichnis

Frontmatter

1. Einleitung

2. Elementare Datenstrukturen

3. Das Wörterbuchproblem

4. Graph-Algorithmen

5. Sortieren

6. String-Algorithmen

7. Entwurfsmethoden für Algorithmen

8. Komplexitätstheorie

9. Entwurfsmethoden für schwere Optimierungsprobleme

10. Anhang

Backmatter

Premium Partner