Hilfe Warenkorb Konto Anmelden
 
 
   Schnellsuche   
     zur Expertensuche                      
Algorithmen und Datenstrukturen - Eine Einführung mit Java
  Großes Bild
 
Algorithmen und Datenstrukturen - Eine Einführung mit Java
von: Gunter Saake, Kai-Uwe Sattler
dpunkt, 2011
ISBN: 9783864910227
552 Seiten, Download: 3638 KB
 
Format: EPUB, PDF
geeignet für: geeignet für alle DRM-fähigen eReader Apple iPad, Android Tablet PC's Apple iPod touch, iPhone und Android Smartphones Online-Lesen PC, MAC, Laptop

Typ: B (paralleler Zugriff)

 

 
eBook anfordern
Inhaltsverzeichnis

  Vorwort 5  
  Inhaltsverzeichnis 11  
  I Grundlegende Konzepte 19  
     1 Vorbemerkungen und Überblick 21  
        1.1 Informatik, Algorithmen und Datenstrukturen 21  
        1.2 Historischer Überblick: Algorithmen 23  
        1.3 Historie von Programmiersprachen und Java 24  
        1.4 Grundkonzepte der Programmierung in Java 27  
     2 Algorithmische Grundkonzepte 33  
        2.1 Intuitiver Algorithmusbegriff 33  
           2.1.1 Beispiele für Algorithmen 33  
           2.1.2 Bausteine für Algorithmen 37  
           2.1.3 Pseudocode-Notation für Algorithmen 39  
           2.1.4 Struktogramme 44  
           2.1.5 Rekursion 44  
        2.2 Sprachen und Grammatiken 47  
           2.2.1 Begriffsbildung 48  
           2.2.2 Reguläre Ausdrücke 49  
           2.2.3 Backus-Naur-Form (BNF) 50  
        2.3 Elementare Datentypen 52  
           2.3.1 Datentypen als Algebren 52  
           2.3.2 Signaturen von Datentypen 53  
           2.3.3 Der Datentyp bool 54  
           2.3.4 Der Datentyp integer 55  
           2.3.5 Felder und Zeichenketten 56  
        2.4 Terme 58  
           2.4.1 Bildung von Termen 58  
           2.4.2 Algorithmus zur Termauswertung 60  
        2.5 Datentypen in Java 61  
           2.5.1 Primitive Datentypen 61  
           2.5.2 Referenzdatentypen 64  
           2.5.3 Operatoren 67  
     3 Algorithmenparadigmen 71  
        3.1 Überblick über Algorithmenparadigmen 71  
        3.2 Applikative Algorithmen 72  
           3.2.1 Terme mit Unbestimmten 72  
           3.2.2 Funktionsdefinitionen 73  
           3.2.3 Auswertung von Funktionen 73  
           3.2.4 Erweiterung der Funktionsdefinition 75  
           3.2.5 Applikative Algorithmen 76  
           3.2.6 Beispiele für applikative Algorithmen 77  
        3.3 Imperative Algorithmen 85  
           3.3.1 Grundlagen imperativer Algorithmen 85  
           3.3.2 Komplexe Anweisungen 88  
           3.3.3 Beispiele für imperative Algorithmen 91  
        3.4 Das logische Paradigma 97  
           3.4.1 Logik der Fakten und Regeln 97  
           3.4.2 Deduktive Algorithmen 99  
        3.5 Weitere Paradigmen 103  
           3.5.1 Genetische Algorithmen 104  
           3.5.2 Neuronale Netze 107  
        3.6 Umsetzung in Java 110  
           3.6.1 Ausdrücke und Anweisungen 111  
           3.6.2 Methoden 118  
           3.6.3 Applikative Algorithmen und Rekursion 124  
     4 Literaturhinweise zum Teil I 131  
  II Algorithmen 133  
     5 Ausgewählte Algorithmen 135  
        5.1 Suchen in sortierten Folgen 135  
           5.1.1 Sequenzielle Suche 136  
           5.1.2 Binäre Suche 138  
        5.2 Sortieren 142  
           5.2.1 Sortieren: Grundbegriffe 142  
           5.2.2 Sortieren durch Einfügen 143  
           5.2.3 Sortieren durch Selektion 145  
           5.2.4 Sortieren durch Vertauschen: BubbleSort 147  
           5.2.5 Sortieren durch Mischen: MergeSort 149  
           5.2.6 QuickSort 153  
           5.2.7 Sortierverfahren im Vergleich 157  
     6 Formale Algorithmenmodelle 161  
        6.1 Registermaschinen 161  
        6.2 Abstrakte Maschinen 170  
        6.3 Markov-Algorithmen 174  
        6.4 Church'sche These 180  
        6.5 Interpreter für formale Algorithmenmodelle in Java 182  
           6.5.1 Java: Markov-Interpreter 182  
           6.5.2 Registermaschine in Java 184  
     7 Eigenschaften von Algorithmen 191  
        7.1 Berechenbarkeit und Entscheidbarkeit 191  
           7.1.1 Existenz nichtberechenbarer Funktionen 192  
           7.1.2 Konkrete nichtberechenbare Funktionen 194  
           7.1.3 Das Halteproblem 196  
           7.1.4 Nichtentscheidbare Probleme 198  
           7.1.5 Post'sches Korrespondenzproblem 199  
        7.2 Korrektheit von Algorithmen 201  
           7.2.1 Relative Korrektheit 201  
           7.2.2 Korrektheit von imperativen Algorithmen 202  
           7.2.3 Korrektheitsbeweise für Anweisungstypen 205  
           7.2.4 Korrektheit imperativer Algorithmen an Beispielen 207  
           7.2.5 Korrektheit applikativer Algorithmen 212  
        7.3 Komplexität 214  
           7.3.1 Motivierendes Beispiel 214  
           7.3.2 Asymptotische Analyse 215  
           7.3.3 Komplexitätsklassen 219  
           7.3.4 Analyse von Algorithmen 222  
     8 Entwurf von Algorithmen 225  
        8.1 Entwurfsprinzipien 225  
           8.1.1 Schrittweise Verfeinerung 225  
           8.1.2 Einsatz von Algorithmenmustern 228  
           8.1.3 Problemreduzierung durch Rekursion 228  
        8.2 Algorithmenmuster: Greedy 229  
           8.2.1 Greedy-Algorithmen am Beispiel 229  
           8.2.2 Greedy: Optimales Kommunikationsnetz 231  
           8.2.3 Verfeinerung der Suche nach billigster Kante 232  
        8.3 Rekursion: Divide-and-conquer 234  
           8.3.1 Das Prinzip „Teile und herrsche“ 235  
           8.3.2 Beispiel: Spielpläne für Turniere 236  
        8.4 Rekursion: Backtracking 238  
           8.4.1 Prinzip des Backtracking 239  
           8.4.2 Beispiel: Das Acht-Damen-Problem 241  
        8.5 Dynamische Programmierung 243  
           8.5.1 Das Rucksackproblem 244  
           8.5.2 Rekursive Lösung des Rucksackproblems 245  
           8.5.3 Prinzip der dynamischen Programmierung 246  
     9 Verteilte Berechnungen 249  
        9.1 Kommunizierende Prozesse 249  
        9.2 Modell der Petri-Netze 250  
           9.2.1 Definition von Petri-Netzen 250  
           9.2.2 Formalisierung von Petri-Netzen 254  
           9.2.3 Das Beispiel der fünf Philosophen 256  
        9.3 Programmieren nebenläufiger Abläufe 258  
           9.3.1 Koordinierte Prozesse 259  
           9.3.2 Programmieren mit Semaphoren 260  
           9.3.3 Philosophenproblem mit Semaphoren 262  
           9.3.4 Verklemmungsfreie Philosophen 264  
        9.4 Beispielrealisierung in Java 266  
     10 Literaturhinweise zum Teil II 273  
  III Datenstrukturen 275  
     11 Abstrakte Datentypen 277  
        11.1 Signaturen und Algebren 278  
        11.2 Algebraische Spezifikation 280  
           11.2.1 Spezifikationen und Modelle 281  
           11.2.2 Termalgebra und Quotiententermalgebra 282  
           11.2.3 Probleme mit initialer Semantik 285  
        11.3 Beispiele für abstrakte Datentypen 286  
           11.3.1 Der Kellerspeicher (Stack) 287  
           11.3.2 Beispiel für Kellernutzung 289  
           11.3.3 Die Warteschlange (Queue) 293  
        11.4 Entwurf von Datentypen 294  
     12 Klassen, Schnittstellen und Objekte in Java 297  
        12.1 Grundzüge der Objektorientierung 297  
        12.2 Klassen und Objekte in Java 300  
        12.3 Vererbung 305  
        12.4 Abstrakte Klassen und Schnittstellen 312  
        12.5 Ausnahmen 315  
        12.6 Umsetzung abstrakter Datentypen 317  
     13 Grundlegende Datenstrukturen 323  
        13.1 Stack und Queue als Datentypen 323  
           13.1.1 Implementierung des Stacks 327  
           13.1.2 Implementierung der Queue 328  
           13.1.3 Bewertung der Implementierungen 330  
        13.2 Verkettete Listen 331  
        13.3 Doppelt verkettete Listen 338  
        13.4 Das Iterator-Konzept 343  
        13.5 Java Collection Framework 346  
        13.6 J2SE 5.0 und Generics 350  
     14 Bäume 353  
        14.1 Bäume: Begriffe und Konzepte 353  
        14.2 Binärer Baum: Datentyp und Basisalgorithmen 356  
           14.2.1 Der Datentyp „Binärer Baum“ 356  
           14.2.2 Algorithmen zur Traversierung 361  
        14.3 Suchbäume 366  
           14.3.1 Suchen in Suchbäumen 367  
           14.3.2 Einfügen und Löschen 370  
           14.3.3 Komplexität der Operationen 375  
        14.4 Ausgeglichene Bäume 376  
           14.4.1 Rot-Schwarz-Bäume 377  
           14.4.2 AVL-Bäume 386  
           14.4.3 B-Bäume 394  
        14.5 Digitale Bäume 407  
           14.5.1 Tries 408  
           14.5.2 Patricia-Bäume 414  
        14.6 Praktische Nutzung von Bäumen 415  
           14.6.1 Sortieren mit Bäumen: HeapSort 415  
           14.6.2 Sets mit binären Suchbäumen 421  
     15 Hashverfahren 427  
        15.1 Grundprinzip des Hashens 427  
        15.2 Grundlagen und Verfahren 428  
           15.2.1 Hashfunktionen 428  
           15.2.2 Behandlung von Kollisionen 430  
           15.2.3 Aufwand beim Hashen 434  
           15.2.4 Hashen in Java 436  
        15.3 Dynamische Hashverfahren 440  
           15.3.1 Grundideen für dynamische Hashverfahren 441  
           15.3.2 Erweiterbares Hashen 444  
           15.3.3 Umsetzung des erweiterbaren Hashens 446  
     16 Graphen 451  
        16.1 Arten von Graphen 451  
           16.1.1 Ungerichtete Graphen 452  
           16.1.2 Gerichtete Graphen 453  
           16.1.3 Gewichtete Graphen 454  
        16.2 Realisierung von Graphen 455  
           16.2.1 Knoten- und Kantenlisten 455  
           16.2.2 Adjazenzmatrix 456  
           16.2.3 Graphen als dynamische Datenstrukturen 456  
           16.2.4 Transformationen zwischen Darstellungen 457  
           16.2.5 Vergleich der Komplexität 458  
           16.2.6 Eine Java-Klasse für Graphen 458  
        16.3 Ausgewählte Graphenalgorithmen 461  
           16.3.1 Breitendurchlauf 461  
           16.3.2 Tiefendurchlauf 465  
           16.3.3 Zyklenfreiheit und topologisches Sortieren 469  
        16.4 Algorithmen auf gewichteten Graphen 472  
           16.4.1 Kürzeste Wege 473  
           16.4.2 Dijkstras Algorithmus 474  
           16.4.3 A*-Algorithmus 477  
           16.4.4 Kürzeste Wege mit negativen Kantengewichten 484  
           16.4.5 Maximaler Durchfluss 487  
           16.4.6 Der Ford-Fulkerson-Algorithmus 489  
        16.5 Weitere Fragestellungen für Graphen 493  
     17 Suchen in Texten 497  
        17.1 Probleme der Worterkennung 497  
        17.2 Knuth-Morris-Pratt 499  
        17.3 Boyer-Moore 503  
        17.4 Pattern Matching 509  
           17.4.1 Reguläre Ausdrücke 509  
           17.4.2 Endliche Automaten 510  
           17.4.3 Java-Klassen für reguläre Ausdrücke 516  
           17.4.4 Ähnlichkeit von Zeichenketten: Die Levenshtein-Distanz 517  
     18 Literaturhinweise zum Teil III 521  
  A Quelltext der Klasse IOUtils 523  
  Abbildungsverzeichnis 527  
  Tabellenverzeichnis 533  
  Algorithmenverzeichnis 535  
  Beispielverzeichnis 537  
  Programmverzeichnis 539  
  Literaturverzeichnis 541  
  Index 545  


nach oben


  Mehr zum Inhalt
Kapitelübersicht
Kurzinformation
Inhaltsverzeichnis
Leseprobe
Blick ins Buch
Fragen zu eBooks?

  Navigation
Belletristik / Romane
Computer
Geschichte
Kultur
Medizin / Gesundheit
Philosophie / Religion
Politik
Psychologie / Pädagogik
Ratgeber
Recht
Reise / Hobbys
Sexualität / Erotik
Technik / Wissen
Wirtschaft

© 2008-2019 ciando GmbH | Impressum | Kontakt | F.A.Q. | Datenschutz