
Algorithmen und Datenstrukturen
Description
Alles über E-Books | Antworten auf Fragen rund um E-Books, Kopierschutz und Dateiformate finden Sie in unserem Info- & Hilfebereich.
Dieses moderne Lehrbuch zum Thema Algorithmen und Datenstrukturen führt auf systematische Art und Weise in die Kunst der Programmierung ein und liefert sowohl das dazu erforderliche Wissen als auch das Handwerkszeug. Es behandelt in drei Teilen nicht nur das Entwerfen, die Gestaltung und die Analyse von Algorithmen und Datenstrukturen, sondern vermittelt auch das Verständnis für ausgewählte Algorithmen zur Lösung von Standardaufgaben sowie die Konzepte und Methoden für das Design der Architektur von größeren Programmsystemen. Ausgehend von einer fundierten Darstellung der Grundlagen wird anhand von vielen Beispielen und illustriert durch eine Fülle von Abbildungen gezeigt, wie man von einer Aufgabenstellung zu ihrer algorithmischen Lösung gelangt. Die Motivation, die Erläuterung und die Anwendung der wichtigsten Paradigmen zur Gestaltung der Architektur von größeren Programmsystemen runden den behandelten Stoff ab. Der durchgängig verwendete, leicht erlern- und gut lesbare Pseudocode gestattet es, den Blick auf das Wesentliche zu richten, und erlaubt eine einfache Übertragung der behandelten Algorithmen in eine konkrete Programmiersprache. Das Buch richtet sich an Studierende der Informatik, Wirtschaftsinformatik und Software Engineering, aber auch an Studierende anderer Studienrichtungen, für die eine Grundausbildung in Algorithmen und Programmierung vorgesehen ist, wie z.B. die Bioinformatik.
Über die Autoren
Gustav Pomberger ist Vorstand des Instituts für Wirtschaftsinformatik - Software Engineering an der Johannes Kepler Universität in Linz.
Heinz Dobler ist Leiter des Masterstudiengangs Software Engineering der Fachhochschule Oberösterreich in Hagenberg. Beide beschäftigen sich seit vielen Jahren sowohl in der Forschung als auch in der Lehre mit der systematischen Entwicklung von Algorithmen, Datenstrukturen und Architekturen großer Softwaresysteme.
Über den Inhalt
TEIL I: Algorithmen und Datenstrukturen Einführung, Grundbegriffe und elementare Konzepte Struktur und systematischer Entwurf von Algorithmen Grundkonzepte zur Modellierung von Datenobjekten Rekursive Algorithmen und Laufzeitkomplexität von Algorithmen
TEIL II: Elementare Algorithmen für Standardaufgaben (Auswahl) Suchalgorithmen und Sortieralgorithmen Algorithmen zur Erzeugung von Zufallszahlen Exhaustionsalgorithmen und Algorithmen auf Zeichenketten
TEIL III: Elementare Programmierparadigmen Modulorientierte Programmierung Datenorientierte Programmierung Objektorientierte Programmierung
Auf der Companion-Webseite
- Alle Abbildungen aus dem Buch (Für den Dozenten)
- Code für ausgewählte Algorithmen
- Beispielprogramme
- Compiler-Generator Coco-2
More details
Other editions
Additional editions
Persons
Heinz Dobler ist Leiter des Masterstudiengangs Software Engineering der Fachhochschule Oberösterreich in Hagenberg. Beide beschäftigen sich seit vielen Jahren sowohl in der Forschung als auch in der Lehre mit der systematischen Entwicklung von Algorithmen, Datenstrukturen und Architekturen großer Softwaresysteme.
Content
- Algorithmen und Datenstrukturen
- Impressum
- Inhaltsübersicht
- Inhaltsverzeichnis
- Vorwort
- Zum Buch
- Hinweise
- Handhabung des Buchs
- Website
- In eigener Sache
- Einleitung
- Teil I - Algorithmen und Datenstrukturen - Grundlagen
- Kapitel 1 - Grundbegriffe und elementare Konzepte
- 1.1 Beispiele für Algorithmen - Ein erster Blick auf den Arbeitsgegenstand
- 1.2 Algorithmus: Begriff und Eigenschaften
- 1.2.1 Begriff
- 1.2.2 Eigenschaften
- 1.3 Elementare Bestandteile von Algorithmen
- 1.3.1 Datenobjekte und ihre Datentypen
- 1.3.2 Aktionen (auch Anweisungen genannt)
- 1.4 Algorithmen mit ihren Schnittstellen
- 1.4.1 Algorithmen: Deklaration und Aufruf
- 1.4.2 Funktionsalgorithmen
- 1.4.3 Geräteschnittstellen
- 1.4.4 Algorithmen und ihre Schnittstellen - Zusammenfassung
- 1.5 Zur Spezifikationsproblematik von Algorithmen
- 1.6 Darstellungsformen für Algorithmen
- 1.6.1 Grafische Darstellungsformen für Algorithmen
- 1.6.2 Text-basierte Darstellungsformen für Algorithmen
- 1.6.3 Zusammenfassung der Darstellungsformen
- 1.7 Algorithmen und Programme
- 1.7.1 Vom Algorithmus zum Programm
- 1.7.2 Möglichkeiten für die Ausführung eines Programms
- 1.7.3 Unterschiede zwischen Algorithmus und Programm
- Kapitel 2 - Struktur und systematischer Entwurf von Algorithmen
- 2.1 Grundlegende Konstrukte zur Gestaltung der Struktur von Algorithmen
- 2.2 Unbeschränkte Ablaufstruktur und Konsequenzen
- 2.3 Beschränkte Ablaufstrukturen: D-Diagrammkonstrukte
- 2.3.1 Transformation unbeschränkter Ablaufstrukturen in D-Diagramme
- 2.3.2 Transformation nach Knuth
- 2.3.3 Transformation nach Oulsnam
- 2.4 Erweiterte D-Diagrammkonstrukte
- 2.5 Strukturkomplexität von Algorithmen und strukturierte Programmierung
- 2.5.1 Umfangsmetriken
- 2.5.2 Metriken nach Halstead
- 2.5.3 Strukturmetriken nach McCabe
- 2.5.4 Strukturierte Programmierung
- 2.6 Systematischer Entwurf von Algorithmen: Prinzip und Vorgehensmodell
- 2.6.1 Schrittweise Verfeinerung oder Top-down-Entwurf
- 2.6.2 Anwendung des Prinzips der schrittweisen Verfeinerung
- 2.6.3 Ein Vorgehensmodell für den Entwurf von Algorithmen
- Kapitel 3 - Grundkonzepte zur Modellierung von Datenobjekten
- 3.1 Atomare Datenobjekte und -typen
- 3.2 Strukturierte Datenobjekte und -typen
- 3.2.1 Felder
- 3.2.2 Verbunde
- 3.2.3 Gegenüberstellung und Kombination von Feldern und Verbunden
- 3.3 Vernetzte oder dynamische Datenobjekte und -typen
- 3.3.1 Zeiger und Zeigerdatentypen
- 3.3.2 Allokieren und Freigeben von Speicher
- 3.4 Verkettete Listen
- 3.4.1 Von Feldern zu verketteten Listen
- 3.4.2 Einfach-verkettete Listen
- 3.4.3 Doppelt-verkettete Listen
- 3.5 Bäume, Binärbäume und binäre Suchbäume
- 3.5.1 Bäume
- 3.5.2 Binärbäume
- 3.5.3 Binäre Suchbäume
- 3.6 Datenkapselung und abstrakte Datenstrukturen
- 3.6.1 Kellerspeicher (stack) als abstrakte Datenstruktur
- 3.7 Abstrakte Datentypen
- 3.7.1 Warteschlange (queue) als abstrakter Datentyp
- Kapitel 4 - Rekursive Algorithmen
- 4.1 Begriff Rekursion und Standardbeispiele
- 4.1.1 Fakultätsberechnung
- 4.1.2 Bildung der Fibonacci-Zahlen
- 4.1.3 Ackermann-Funktion
- 4.1.4 Primzahlentest
- 4.2 Ausführung und Terminierung rekursiver Algorithmen
- 4.3 Vorgehen beim Entwurf rekursiver Algorithmen
- 4.4 Rekursion und Iteration
- 4.4.1 Verwandtschaft von Rekursion und Iteration
- 4.4.2 Entrekursivierung: Von Rekursion zu Iteration
- 4.4.3 Rekursivierung: Von Iteration zu Rekursion
- 4.5 Rekursive Algorithmen auf rekursiven Datenstrukturen
- 4.5.1 Rekursive Algorithmen auf verketteten Listen
- 4.5.2 Rekursive Algorithmen auf binären (Such-)Bäumen
- Kapitel 5 - Laufzeitkomplexität von Algorithmen
- 5.1 Komplexität von Algorithmen: Begriffe und Abgrenzung
- 5.2 Laufzeitmessung und Programmprofil
- 5.3 Feinanalyse und Laufzeitberechnung
- 5.4 Grobanalyse
- 5.5 Asymptotische Laufzeitkomplexität und O-Notation
- Teil II - Elementare Algorithmen für Standardaufgaben - eine Auswahl
- Kapitel 6 - Suchalgorithmen
- 6.1 Anwendungsgebiete und Anforderungen
- 6.2 Sequenzielle Suche
- 6.2.1 Sequenzielle Suche in Feldern
- 6.2.2 Sequenzielle Suche in verketteten Listen
- 6.2.3 Sequenzielle Suche in Binärbäumen
- 6.2.4 Sequenzielle Suche in beliebigen Behältern mittels Iteratoren
- 6.2.5 Laufzeitkomplexität der sequenziellen Suche
- 6.3 Binäre Suche
- 6.3.1 Binäre Suche in sortierten Feldern
- 6.3.2 Binäre Suche in binären Suchbäumen
- 6.3.3 Laufzeitkomplexität der binären Suche
- 6.4 Hashing-basierte Suche
- 6.4.1 Grundprinzip des Hashing
- 6.4.2 Hash-Funktionen und Kollisionen
- 6.4.3 Kollisionsbehandlung durch Verkettung
- 6.4.4 Kollisionsbehandlung durch offene Adressierung
- Kapitel 7 - Sortieralgorithmen
- 7.1 Anwendungsgebiete und Anforderungen
- 7.2 Auswahlsortieren
- 7.3 Einfügesortieren
- 7.4 Shell-Sortieren
- 7.5 Austauschsortieren (Bubblesort) und Combsort
- 7.6 Quicksort
- 7.7 Heap-Datenstruktur und Heap-Sortieren
- 7.7.1 Heap-Datenstruktur
- 7.7.2 Heap-Sortieren
- 7.8 Weitere Sortierverfahren
- 7.9 Problemkomplexität
- Kapitel 8 - Algorithmen zur Erzeugung von Zufallszahlen
- 8.1 Anwendungsgebiete, Begriffe und Anforderungen
- 8.2 Algorithmen mit Gedächtnis
- 8.3 Methoden zur Erzeugung von Zufallszahlenfolgen
- 8.4 Methoden zur Periodenverlängerung
- 8.5 Abgeleitete Generatoren
- 8.6 Tests zur Prüfung der Güte von Zufallszahlenfolgen
- Kapitel 9 - Exhaustionsalgorithmen
- 9.1 Acht- bzw. n-Damen-Problem
- 9.2 Allgemeine Problemformulierung und grundlegender Lösungsansatz
- 9.3 Varianten von Backtracking-Aufgaben und -Lösungen
- 9.4 Standardproblemstellungen und heuristische Algorithmen
- Kapitel 10 - Algorithmen auf Zeichenketten
- 10.1 Repräsentation von und elementare Operationen auf Zeichenketten
- 10.2 Problem der Mustersuche in Zeichenketten (Pattern Matching)
- 10.3 Elementare Mustersuch-Verfahren
- 10.4 Mustersuch-Verfahren nach Knuth, Morris und Pratt
- 10.5 Mustersuch-Verfahren nach Boyer und Moore
- 10.6 Mustersuch-Verfahren nach Rabin und Karp
- 10.7 Ausblick: Echte Muster, reguläre Ausdrücke und endliche Automaten
- Teil III - Elementare Programmierparadigmen
- Kapitel 11 - Aufgaben- und modulorientierte Programmierung
- 11.1 Entwurf und Eigenschaften aufgabenorientierter Systemarchitekturen
- 11.2 Beispiel zur Vorgehensweise bei aufgabenorientierter Systementwicklung
- 11.3 Modulkonstrukt - Begriff und Eigenschaften
- 11.4 Anwendung des Modulkonstrukts
- Kapitel 12 - Daten- und transformationsorientierte Programmierung
- 12.1 Lösungsansatz für und Aufbau von datenorientierten Systemarchitekturen
- 12.2 Grammatiken zur Beschreibung der syntaktischen Struktur von Datenströmen
- 12.3 Konstruktion der Analysatorkomponenten
- 12.4 Attributierte Grammatiken zur Beschreibung von Transformationsprozessen
- 12.5 Algorithmische Interpretation attributierter Grammatiken
- 12.6 Einsatz von Compiler-Generatoren
- 12.7 Vorgehensweise zur systematischen Entwicklung datenorientierter Programmsysteme
- Kapitel 13 - Objektorientierte Programmierung
- 13.1 Ziel der objektorientierten Programmierung
- 13.2 Objekte und Klassen
- 13.3 Vererbung
- 13.4 Polymorphismus, Klassengarantie und -test
- 13.5 Statische und dynamische Bindung
- 13.6 Abstrakte Klassen, abstrakte Methoden und Klassenbibliotheken
- 13.7 Systematischer Entwurf objektorientierter Systemarchitekturen
- Literaturverzeichnis
- Namensregister
- A
- Ackermann, Wilhelm 199
- Ahrens, Walter 373
- Al Chwarizimi, Muhammed 29
- Applegate, David L. 393
- Archimedes von Syrakrus 394
- Aristoteles 468
- B
- Babington-Smith, Bernard 346
- Bach, Johann Sebastian 188
- Bachmann, Paul 249
- Backus, John 471
- Balzert, Helmut 435
- Baumert, Leonardo D. 378
- Bayer, Rudolf 171
- Beck, Kent 529
- Bentley, John 254, 326
- Bezzel, Max 372
- Binet, Jacques P. M. 198
- Bitner, James R. 373
- Bixby, Robert E. 393
- Böhm, Corrado 95
- Bonaccio, Guglielmo 194
- Booch, Grady 510
- Boole, George 40
- Box, Richard 299, 317
- Boyer, Robert S. 416
- C
- Catalan, Eugène C. 167
- Chomsky, Noam 469
- Cook, Stephen A. 390, 411
- Coulomb, Charles 38
- Cunningham, Ward 529
- D
- Dahl, Ole-Johan 108
- Dijkstra, Edsger W. 88, 93, 94, 101, 108, 119
- Dobosiewicz, Wlodzimier 317
- E
- Escher, Maurits Cornelis 188
- Euler, Leonhard 194, 359
- F
- Floyd, Robert W. 334
- Friend, Edward H. 306
- G
- Gamma, Erich 531
- Gauß, Carl Friedrich 55, 361
- Gödl, Kurt 188
- Golomb, Solomon W. 378
- Grenander, Ulf 254
- Gu, Jun 378
- Guibas, Leonidas J. 171
- H
- Halstead, Maurice H. 103
- Hibbard, Thomas N. 313
- Hilbert, David 199
- Hoare, Charles Antony Richard 108, 299, 321, 342
- Hofstadter, Douglas R. 188
- Hollerith, Hermann 298
- I
- Ichbiah, Jean 448
- J
- Jacobsen, Grady 510
- Jacopini, Giuseppe 95
- K
- Kadane, Jay 256
- Karp, Richard M. 421
- Kendall, Maurice G. 346
- Kepler, Johannes 21, 198
- Kernighan, Brian W. 395
- Knuth, Donald E. 73, 95, 96, 97, 100, 213, 249, 287, 298, 309, 313, 347, 354, 356, 357, 363, 411, 487
- Kosters, Walter 372
- L
- Lacey, Stephen 299, 317
- Landau, Edmund 249
- Landis, Yevgeniy M. 171
- Lehmer, Derrick H. 347, 353, 365, 380
- Leibniz, Gottfried W. 359
- Leonardo von Pisa 194
- Lin, Shen 395
- Liskov, Barbara H. 514
- M
- MacLaren, Malcom D. 356
- Mandelbrot, Benoit 191
- Marsaglia, George 356
- Mauchly, John W. 309
- McCabe, Thomas J. 105, 119
- Moore, Gordon 257
- Moore, J. Strother 416
- Morris, James H. 411
- Morris, Robert 291
- Moscato, Pablo 393
- Mössenböck, Hanspeter 495
- N
- Nassi, Ike 72
- Nauck, Franz 372
- Naur, Peter 471
- O
- Oulsnam, Gordon 95, 98, 99
- P
- Papernov, Abram A. 313, 315
- Parnas, David L. 172, 448
- Péter, Rózsa 199
- Polya, George 373
- Pratt, Vaughan R. 411
- R
- Rabin, Michael O. 421
- Rechenberg, Peter 495
- Reinelt, Gerhard 393
- Reingold, Edward M. 373
- Rumbaugh, Grady 510
- S
- Schickard, Wilhelm 21
- Sedgewick, Robert 32, 171, 313, 315, 323, 324, 354, 355, 363, 387, 408
- Shamos, Michael 256
- Shell, Donald L. 298, 310, 315, 317, 342
- Shneiderman, Ben 72
- Singleton, Richard C. 327
- Sorber, Gordon 339
- Sosic, Rok 378
- Stasevich, Grigory V. 313, 315
- Steinhaus, Hugo D. 307, 309
- Stirling, James 194
- Stone, Harold S. 378
- Stone, Janice M. 378
- Stroustrup, Bjarne 504
- T
- Tausworthe, Robert C. 355
- Theodorus von Kyrene 190
- Turing, Alan M. 382
- V
- Von Neumann, John 298, 352
- W
- Wegener, Ingo 336
- Williams, John W. J. 334
- Wing, Jeannette M. 514
- Wirth, Niklaus 88, 108, 109, 119, 163, 373, 436, 448, 471
- Register
- Register
- Copyright
System requirements
File format: PDF
Copy protection: Watermark-DRM (Digital Rights Management)
System requirements:
- Computer (Windows; MacOS X; Linux): Use the free software Adobe Reader, Adobe Digital Editions, or any other PDF viewer of your choice (see eBook Help).
- Tablet/Smartphone (Android; iOS): Install the free app Adobe Digital Editions or another reading app for eBooks, e.g., PocketBook (see eBook Help).
- E-reader: Bookeen, Kobo, Pocketbook, Sony, Tolino and many more (only limited: Kindle).
The file format PDF always displays a book page identically on any hardware. This makes PDF suitable for complex layouts such as those used in textbooks and reference books (images, tables, columns, footnotes). Unfortunately, on the small screens of e-readers or smartphones, PDFs are rather annoying, requiring too much scrolling.
This eBook uses Watermark-DRM, a „soft” copy protection. This means that there are no technical restrictions to prevent illegal distribution. However, there is a personalised watermark embedded in the eBook that can be used to identify the purchaser of the eBook in the event of misuse and to provide evidence for legal purposes.
For more information, see our eBook Help page.