Entwurf und Analyse von Algorithmen

Medientyp: E-Book

Titel: Entwurf und Analyse von Algorithmen

Enthält: Vorwort; Inhaltsverzeichnis; 1 Einleitung; 1.1 Ziele und Überblick; 1.2 Algorithmentheorie - eine kurze Einführung; 1.3 Grundlagen der Analyse von Algorithmen; 1.3.1 Erzeugendenfunktionen; 1.3.2 Asymptotische Notationen; 1.3.3 Amortisierte Kosten; 1.3.4 Rekursion; 1.4 Abstrakte Datentypen; 1.4.1 Einleitung; 1.4.2 Felder (Arrays); 1.5 Quellenangaben und Literaturhinweise; 1.6 Aufgaben; 2 Elementare Datenstrukturen; 2.1 Lineare Listen; 2.1.1 Sequentielle Repräsentation Linearer Listen; 2.1.2 Verkettete Repräsentation Linearer Listen; 2.1.3 Doppelt verkettete Lineare Listen
3.7 Aufgaben4 Graph-Algorithmen; 4.1 Kürzeste Wege; 4.2 Minimale Spannbäume; 4.3 Quellenangaben und Literaturhinweise; 4.4 Aufgaben; 5 Sortieren; 5.1 Primitive Sortier-Algorithmen; 5.1.1 Bubble-Sort; 5.1.2 Insertion-Sort; 5.1.3 Selection-Sort; 5.1.4 Laufzeitbetrachtung; 5.1.5 Optimale Anzahl an Vergleichen; 5.2 Quicksort; 5.3 Heapsort; 5.4 Mergesort; 5.4.1 2-Wege-Mergesort; 5.4.2 Direkter 2-Wege-Mergesort; 5.4.3 Externes Sortieren; 5.5 Distribution Counting, Radix-Exchange und Radixsort; 5.6 Sortiernetzwerke; 5.7 Quellenangaben und Literaturhinweise; 5.8 Aufgaben; 6 String-Algorithmen
6.1 String-Matching6.1.1 String-Matching mit endlichen Automaten; 6.1.2 Der Knuth-Morris-Pratt-Algorithmus; 6.1.3 Vergleich der mittleren Laufzeit von KMP und dem naiven Algorithmus; 6.1.4 Der Boyer-Moore-Algorithmus; 6.1.5 Weitere Verfahren; 6.2 Suffix-Bäume; 6.2.1 Ukkonen-Algorithmus; 6.2.2 Anwendungen; 6.3 Quellenangaben und Literaturhinweise; 6.4 Aufgaben; 7 Entwurfsmethoden für Algorithmen; 7.1 Divide and Conquer; 7.1.1 Multiplikation zweier n-Bit-Zahlen; 7.1.2 Multiplikation zweier Matrizen; 7.2 Dynamisches Programmieren; 7.3 Greedy-Algorithmen; 7.3.1 Huffman-Codes
7.3.2 Das Binpacking-Problem7.3.3 Matroide; 7.4 Lineares Programmieren; 7.5 Transformationen; 7.5.1 Die diskrete Fourier-Transformation und ihre Inverse; 7.5.2 Die schnelle Fourier-Transformation; 7.5.3 Die schnelle Fourier-Transformation mit Bit-Operationen; 7.5.4 Produkte von Polynomen; 7.5.5 Der Schönhage-Strassen-Algorithmus; 7.6 Quellenangaben und Literaturhinweise; 7.7 Aufgaben; 8 Komplexitätstheorie; 8.1 NP-Vollständigkeit; 8.2 Wichtige NP-vollständige Probleme; 8.3 Quellenangaben und Literaturhinweise; 8.4 Aufgaben; 9 Entwurfsmethoden für schwere Optimierungsprobleme
9.1 Backtracking und Branch&Bound
2.1.4 Anwendungsbeispiel2.2 Stacks und Queues; 2.2.1 Stacks; 2.2.2 Queues; 2.2.3 Anwendungsbeispiel; 2.3 Mengen; 2.4 Graphen und Bäume; 2.4.1 Datenstrukturen für Graphen; 2.4.2 Datenstrukturen für Bäume; 2.4.3 Traversieren von Bäumen und Graphen; 2.5 Partitionen; 2.6 Quellenangaben und Literaturhinweise; 2.7 Aufgaben; 3 Das Wörterbuchproblem; 3.1 Binäre Suchbäume; 3.2 Balancierte Bäume; 3.2.1 Höhenbalancierte Bäume; 3.2.2 Splay-Trees; 3.2.3 B-Bäume; 3.3 Digitale Suchbäume und Tries; 3.4 Hashing; 3.5 Datenstrukturen für das Information Retrieval; 3.6 Quellenangaben und Literaturhinweise

Beteiligte: Nebel, Markus [Verfasser:in]

Erschienen: Wiesbaden: Vieweg+Teubner Verlag, 2012

Umfang: Online-Ressource (VIII, 392S. 149 Abb, digital)

Sprache: Deutsch

DOI: 10.1007/978-3-8348-2339-7

ISBN: 9783834823397

Identifikator:

RVK-Notation: ST 134 : Algorithmen-, Komplexitätstheorie

Schlagwörter: Algorithmentheorie > Datenstruktur
Algorithmentheorie > Datenstruktur

Entstehung:

Anmerkungen: Description based upon print version of record

Beschreibung: Elementare Datenstrukturen -- Das Wörterbuchproblem -- Graph-Algorithmen -- Sortieren -- String-Algorithmen -- Entwurfsmethoden für Algorithmen -- Komplexitätstheorie -- Entwurfsmethoden für schwere Optimierungsprobleme.

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. Der Inhalt Elementare Datenstrukturen - Das Wörterbuchproblem - Graph-Algorithmen - Sortieren - String-Algorithmen - Entwurfsmethoden für Algorithmen - Komplexitätstheorie - Entwurfsmethoden für schwere Optimierungsprobleme Die Zielgruppe Studierende der Informatik im Bachelor Studiengang an Fachhochschulen und Universitäten Der Autor Prof. Dr. Markus Nebel lehrt und forscht an der TU Kaiserslautern. Die Reihe "Studienbücher Informatik" wird herausgegeben von Prof. Dr. Walter Hower.

Nur in Feld suchen:

Zuletzt gesuchte Begriffe: