Algorithmen - Eine Einführung

 
 
de Gruyter Oldenbourg (Verlag)
  • 4. Auflage
  • |
  • erschienen am 11. Januar 2017
  • |
  • XX, 1319 Seiten
 
E-Book | PDF mit Wasserzeichen-DRM | Systemvoraussetzungen
E-Book | PDF ohne DRM | Systemvoraussetzungen
978-3-11-052201-3 (ISBN)
 
Der "Cormen" bietet eine umfassende und vielseitige Einführung in das moderne Studium von Algorithmen. Es stellt viele Algorithmen Schritt für Schritt vor, behandelt sie detailliert und macht deren Entwurf und deren Analyse allen Leserschichten zugänglich. Sorgfältige Erklärungen zur notwendigen Mathematik helfen, die Analyse der Algorithmen zu verstehen. Den Autoren ist es dabei geglückt, Erklärungen elementar zu halten, ohne auf Tiefe oder mathematische Exaktheit zu verzichten. Jedes der weitgehend eigenständig gestalteten Kapitel stellt einen Algorithmus, eine Entwurfstechnik, ein Anwendungsgebiet oder ein verwandtes Thema vor. Algorithmen werden beschrieben und in Pseudocode entworfen, der für jeden lesbar sein sollte, der schon selbst ein wenig programmiert hat. Zahlreiche Abbildungen verdeutlichen, wie die Algorithmen arbeiten. Ebenfalls angesprochen werden Belange der Implementierung und andere technische Fragen, wobei, da Effizienz als Entwurfskriterium betont wird, die Ausführungen eine sorgfältige Analyse der Laufzeiten der Programme mit ein schließen. Über 1000 Übungen und Problemstellungen und ein umfangreiches Quellen- und Literaturverzeichnis komplettieren das Lehrbuch, dass durch das ganze Studium, aber auch noch danach als mathematisches Nachschlagewerk oder als technisches Handbuch nützlich ist. Für die dritte Auflage wurde das gesamte Buch aktualisiert. Die Änderungen sind vielfältig und umfassen insbesondere neue Kapitel, überarbeiteten Pseudocode, didaktische Verbesserungen und einen lebhafteren Schreibstil. So wurden etwa - neue Kapitel zu van-Emde-Boas-Bäume und mehrfädigen (engl.: multithreaded) Algorithmen aufgenommen, - das Kapitel zu Rekursionsgleichungen überarbeitet, sodass es nunmehr die Teile-und-Beherrsche-Methode besser abdeckt, - die Betrachtungen zu dynamischer Programmierung und Greedy-Algorithmen überarbeitet; Memoisation und der Begriff des Teilproblem-Graphen als eine Möglichkeit, die Laufzeit eines auf dynamischer Programmierung beruhender Algorithmus zu verstehen, werden eingeführt. - 100 neue Übungsaufgaben und 28 neue Problemstellungen ergänzt. Umfangreiches Dozentenmaterial (auf englisch) ist über die Website des US-Verlags verfügbar.
4., durchges. und korr. Aufl.., 4th rev. ed.
  • Deutsch
  • Berlin/Boston
  • |
  • Deutschland
  • Für höhere Schule und Studium
  • |
  • US School Grade: From College Freshman to College Senior
  • 8,77 MB
978-3-11-052201-3 (9783110522013)
3110522012 (3110522012)
http://www.degruyter.com/isbn/9783110522013
weitere Ausgaben werden ermittelt
  • Intro
  • Inhaltsverzeichnis
  • Vorwort
  • I Grundlagen
  • 1 Die Rolle von Algorithmen in der elektronischen Datenverarbeitung
  • 1.1 Algorithmen
  • 1.2 Algorithmen als Technologie
  • 2 Ein einführendes Beispiel
  • 2.1 Sortieren durch Einfügen
  • 2.2 Analyse von Algorithmen
  • 2.3 Entwurf von Algorithmen
  • 3 Wachstum von Funktionen
  • 3.1 Asymptotische Notation
  • 3.2 Standardnotationen und Standardfunktionen
  • 4 Teile-und-Beherrsche
  • 4.1 Das Max-Teilfeld-Problem
  • 4.2 Strassens Algorithmus zur Matrizenmultiplikation
  • 4.3 Die Substitutionsmethode zum Lösen von Rekursionsgleichungen
  • 4.4 Die Rekursionsbaum-Methode zum Lösen von Rekursionsgleichungen
  • 4.5 Die Mastermethode zum Lösen von Rekursionsgleichungen
  • 4.6* Beweis des Mastertheorems
  • 5 Probabilistische Analyse und randomisierte Algorithmen
  • 5.1 Das Bewerberproblem
  • 5.2 Indikatorfunktionen
  • 5.3 Randomisierte Algorithmen
  • 5.4 * Probabilistische Analyse und mehr zur Verwendung der Indikatorfunktion
  • II Sortieren und Ranggrößen
  • 6 Heapsort
  • 6.1 Heaps
  • 6.2 Die Heap-Eigenschaft aufrechterhalten
  • 6.3 Einen Heap bauen
  • 6.4 Der Heapsort-Algorithmus
  • 6.5 Prioritätswarteschlangen
  • 7 Quicksort
  • 7.1 Beschreibung von Quicksort
  • 7.2 Die Performanz von Quicksort
  • 7.3 Eine randomisierte Version von Quicksort
  • 7.4 Analyse von Quicksort
  • 8 Sortieren in linearer Zeit
  • 8.1 Untere Schranken für das Sortieren
  • 8.2 Countingsort
  • 8.3 Radixsort
  • 8.4 Bucketsort
  • 9 Mediane und Ranggrößen
  • 9.1 Minimum und Maximum
  • 9.2 Auswahl in linearer erwarteter Zeit
  • 9.3 Auswahl in linearer Zeit im schlechtesten Fall
  • III Datenstrukturen
  • 10 Elementare Datenstrukturen
  • 10.1 Stapel und Warteschlangen
  • 10.2 Verkettete Listen
  • 10.3 Implementierung von Zeigern und Objekten
  • 10.4 Darstellung von gerichteten Bäumen
  • 11 Hashtabellen
  • 11.1 Adresstabellen mit direktem Zugriff
  • 11.2 Hashtabellen
  • 11.3 Hashfunktionen
  • 11.4 Offene Adressierung
  • 11.5* Perfektes Hashing
  • 12 Binäre Suchbäume
  • 12.1 Was ist ein binärer Suchbaum?
  • 12.2 Abfragen in einem binären Suchbaum
  • 12.3 Einfügen und Löschen
  • 12.4* Zufällig erzeugte binäre Suchbäume
  • 13 Rot-Schwarz-Bäume
  • 13.1 Eigenschaften von Rot-Schwarz-Bäumen
  • 13.2 Rotationen
  • 13.3 Einfügen eines Knotens
  • 13.4 Löschen eines Knotens
  • 14 Erweitern von Datenstrukturen
  • 14.1 Dynamische Ranggröße
  • 14.2 Wie man eine Datenstruktur erweitert
  • 14.3 Intervallbäume
  • IV Fortgeschrittene Entwurfs- und Analysetechniken
  • 15 Dynamische Programmierung
  • 15.1 Schneiden von Eisenstangen
  • 15.2 Matrizen-Kettenmultiplikation
  • 15.3 Elemente dynamischer Programmierung
  • 15.4 Längste gemeinsame Teilsequenz
  • 15.5 Optimale binäre Suchbäume
  • 16 Greedy-Algorithmen
  • 16.1 Ein Aktivitäten-Auswahl-Problem
  • 16.2 Elemente der Greedy-Strategie
  • 16.3 Huffman-Codierungen
  • 16.4* Matroiden und Greedy-Methoden
  • 16.5* Ein Task-Scheduling-Problem als Matroid
  • 17 Amortisierte Analyse
  • 17.1 Aggregat-Analyse
  • 17.2 Account-Methode
  • 17.3 Die Potentialmethode
  • 17.4 Dynamische Tabellen
  • V Höhere Datenstrukturen
  • 18 B-Bäume
  • 18.1 Die Definition von B-Bäumen
  • 18.2 Grundoperationen auf B-Bäumen
  • 18.3 Löschen eines Schlüssels aus einem B-Baum
  • 19 Fibonacci-Heaps
  • 19.1 Die Struktur von Fibonacci-Heaps
  • 19.2 Operationen der fusionierbaren Heaps
  • 19.3 Verringern eines Schlüssels und Entfernen eines Knotens
  • 19.4 Beschränkung des maximalen Grades
  • 20 van-Emde-Boas-Bäume
  • 20.1 Vorbereitende Ansätze
  • 20.2 Eine rekursive Datenstruktur
  • 20.3 Die van-Emde-Boas-Bäume
  • 21 Datenstrukturen disjunkter Mengen
  • 21.1 Operationen auf disjunkten Mengen
  • 21.2 Darstellung disjunkter Mengen mithilfe verketteter Listen
  • 21.3 Wälder disjunkter Mengen
  • 21.4* Analyse der Vereinigung nach dem Rang mit Pfadverkürzung
  • VI Graphenalgorithmen
  • 22 Elementare Graphenalgorithmen
  • 22.1 Darstellungen von Graphen
  • 22.2 Breitensuche
  • 22.3 Tiefensuche
  • 22.4 Topologisches Sortieren
  • 22.5 Starke Zusammenhangskomponenten
  • 23 Minimale Spannbäume
  • 23.1 Aufbau eines minimalen Spannbaums
  • 23.2 Die Algorithmen von Kruskal und Prim
  • 24 Kürzeste Pfade von einem Startknoten aus
  • 24.1 Der Bellman-Ford-Algorithmus
  • 24.2 Kürzeste Pfade von einem Startknoten aus in DAGs
  • 24.3 Dijkstras Algorithmus
  • 24.4 Differenzbedingungen und kürzeste Pfade
  • 24.5 Beweise der Eigenschaften kürzester Pfade
  • 25 Kürzeste Pfade für alle Knotenpaare
  • 25.1 Kürzeste Pfade und Matrizenmultiplikation
  • 25.2 Der Floyd-Warshall-Algorithmus
  • 25.3 Johnsons Algorithmus für dünn besetzte Graphen
  • 26 Maximaler Fluss
  • 26.1 Flussnetzwerke
  • 26.2 Die Ford-Fulkerson-Methode
  • 26.3 Maximales bipartites Matching
  • 26.4* Push/Relabel-Algorithmen
  • 26.5* Der Relabel-to-Front-Algorithmus
  • VII Ausgewählte Themen
  • 27 Mehrfädige Algorithmen
  • 27.1 Grundlagen von dynamischem Multithreading
  • 27.2 Mehrfädige Matrizenmultiplikation
  • 27.3 Mehrfädiges Sortieren durch Mischen
  • 28 Operationen auf Matrizen
  • 28.1 Lösen linearer Gleichungssysteme
  • 28.2 Matrixinversion
  • 28.3 Symmetrische positiv definite Matrizen, Summe der quadratischen Fehler
  • 29 Lineare Programmierung
  • 29.1 Standard- und Schlupfform
  • 29.2 Darstellung von Problemen als lineare Programme
  • 29.3 Der Simplexalgorithmus
  • 29.4 Dualität
  • 29.5 Die initiale zulässige Basislösung
  • 30 Polynome und die FFT
  • 30.1 Darstellung von Polynomen
  • 30.2 Die DFT und FFT
  • 30.3 Effiziente Implementierung der FFT
  • 31 Zahlentheoretische Algorithmen
  • 31.1 Elementare zahlentheoretische Begriffe
  • 31.2 Größter gemeinsamer Teiler
  • 31.3 Modulare Arithmetik
  • 31.4 Lösen modularer linearer Gleichungen
  • 31.5 Der chinesische Restsatz
  • 31.6 Potenzen eines Elements
  • 31.7 Das RSA-Kryptosystem
  • 31.8* Primzahltests
  • 31.9* Primfaktorzerlegung
  • 32 String-Matching
  • 32.1 Der naive String-Matching-Algorithmus
  • 32.2 Der Rabin-Karp-Algorithmus
  • 32.3 String-Matching mit endlichen Automaten
  • 32.4* Der Knuth-Morris-Pratt-Algorithmus
  • 33 Algorithmische Geometrie
  • 33.1 Eigenschaften von Strecken
  • 33.2 Bestimmung von Schnittpunkten in einer Menge von Strecken
  • 33.3 Bestimmen der konvexen Hülle
  • 33.4 Berechnung des dichtesten Punktepaares
  • 34 NP-Vollständigkeit
  • 34.1 Polynomielle Zeit
  • 34.2 Verifikation in polynomieller Zeit
  • 34.3 NP-Vollständigkeit und Reduktion
  • 34.4 NP-Vollständigkeitsbeweise
  • 34.5 NP-vollständige Probleme
  • 35 Approximationsalgorithmen
  • 35.1 Das Knotenüberdeckungsproblem
  • 35.2 Das Problem des Handelsreisenden
  • 35.3 Das Mengenüberdeckungsproblem
  • 35.4 Randomisierung und lineare Programmierung
  • 35.5 Das Teilsummenproblem
  • VIII Anhang
  • A Summen
  • A.1 Summenformeln und Eigenschaften
  • A.2 Abschätzungen für Summen
  • B Mengen usw
  • B.1 Mengen
  • B.2 Relationen
  • B.3 Funktionen
  • B.4 Graphen
  • B.5 Bäume
  • C Kombinatorik und Wahrscheinlichkeitstheorie
  • C.1 Kombinatorik
  • C.2 Wahrscheinlichkeiten
  • C.3 Diskrete Zufallsvariablen
  • C.4 Die geometrische Verteilung und die Binomialverteilung
  • C.5* Die Ränder der Binomialverteilung
  • D Matrizen
  • D.1 Matrizen und Matrizenoperationen
  • D.2 Elementare Matrizeneigenschaften
  • Literaturverzeichnis
  • Index

Dateiformat: PDF
Kopierschutz: Wasserzeichen-DRM (Digital Rights Management)

Systemvoraussetzungen:

Computer (Windows; MacOS X; Linux): Verwenden Sie zum Lesen die kostenlose Software Adobe Reader, Adobe Digital Editions oder einen anderen PDF-Viewer Ihrer Wahl (siehe E-Book Hilfe).

Tablet/Smartphone (Android; iOS): Installieren Sie die kostenlose App Adobe Digital Editions oder eine andere Lese-App für E-Books (siehe E-Book Hilfe).

E-Book-Reader: Bookeen, Kobo, Pocketbook, Sony, Tolino u.v.a.m. (nur bedingt: Kindle)

Das Dateiformat PDF zeigt auf jeder Hardware eine Buchseite stets identisch an. Daher ist eine PDF auch für ein komplexes Layout geeignet, wie es bei Lehr- und Fachbüchern verwendet wird (Bilder, Tabellen, Spalten, Fußnoten). Bei kleinen Displays von E-Readern oder Smartphones sind PDF leider eher nervig, weil zu viel Scrollen notwendig ist. Mit Wasserzeichen-DRM wird hier ein "weicher" Kopierschutz verwendet. Daher ist technisch zwar alles möglich - sogar eine unzulässige Weitergabe. Aber an sichtbaren und unsichtbaren Stellen wird der Käufer des E-Books als Wasserzeichen hinterlegt, sodass im Falle eines Missbrauchs die Spur zurückverfolgt werden kann.

Weitere Informationen finden Sie in unserer E-Book Hilfe.


Dateiformat: PDF
Kopierschutz: ohne DRM (Digital Rights Management)

Systemvoraussetzungen:

Computer (Windows; MacOS X; Linux): Verwenden Sie zum Lesen die kostenlose Software Adobe Reader, Adobe Digital Editions oder einen anderen PDF-Viewer Ihrer Wahl (siehe E-Book Hilfe).

Tablet/Smartphone (Android; iOS): Installieren Sie die kostenlose App Adobe Digital Editions oder eine andere Lese-App für E-Books (siehe E-Book Hilfe).

E-Book-Reader: Bookeen, Kobo, Pocketbook, Sony, Tolino u.v.a.m. (nur bedingt: Kindle)

Das Dateiformat PDF zeigt auf jeder Hardware eine Buchseite stets identisch an. Daher ist eine PDF auch für ein komplexes Layout geeignet, wie es bei Lehr- und Fachbüchern verwendet wird (Bilder, Tabellen, Spalten, Fußnoten). Bei kleinen Displays von E-Readern oder Smartphones sind PDF leider eher nervig, weil zu viel Scrollen notwendig ist. Ein Kopierschutz bzw. Digital Rights Management wird bei diesem E-Book nicht eingesetzt.

Weitere Informationen finden Sie in unserer E-Book Hilfe.


Download (sofort verfügbar)

89,95 €
inkl. 19% MwSt.
Download / Einzel-Lizenz
PDF mit Wasserzeichen-DRM
siehe Systemvoraussetzungen
E-Book bestellen

89,95 €
inkl. 19% MwSt.
Download / Einzel-Lizenz
PDF ohne DRM
siehe Systemvoraussetzungen
E-Book bestellen

Unsere Web-Seiten verwenden Cookies. Mit der Nutzung dieser Web-Seiten erklären Sie sich damit einverstanden. Mehr Informationen finden Sie in unserem Datenschutzhinweis. Ok