Solymosi / Grude Grundkurs Algorithmen und Datenstrukturen

Eine Einführung in die praktische Informatik mit Java
2000
ISBN: 978-3-322-93912-8
Verlag: Vieweg & Teubner
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Deutsch, 194 Seiten, eBook

Reihe: Ausbildung und Studium

Der Grundkurs "Algorithmen und Datenstrukturen" stellt die klassischen Informatik-Inhalte bereit wie Sortieralgorithmen, Baumstrukturen, Komplexität, Rekursion und Algorithmenklassen. Das neue an diesem kompakten Lehrbuch ist die klare Ausrichtung an der Praxis, wobei die Realisierung der Algorithmen in Java erfolgt. Das Buch eignet sich für Studenten von Fachhochschulen und Universitäten der Informatik im Haupt- bzw. Nebenfach, ist aber auch für Schüler in Leistungskursen oder IT-Ausbildungsklassen geeignet. Die Themen werden leicht verständlich behandelt und mit in Java formulierten, gut lesbaren Algorithmen dargestellt.

Zielgruppe

Research

Autoren/Hrsg.

Solymosi, Andreas

Grude, Ulrich

Inhaltsverzeichnis

1. Begriffsbildung.- 1.1. Algorithmus.- 1.2. Komplexität.- 1.3. Verbrauch und Komplexität.- 2. Gleichwertige Lösungen.- 2.1. Maximale Teilsumme.- 2.1.1. Summen und Teilsummen.- 2.1.2. Aufgabenstellung.- 2.1.3. Intuitive Lösung.- 2.1.4. Zeitkomplexität der Lösung.- 2.1.5. Zeit für Raum.- 2.1.6. Teile und herrsche.- 2.1.7. Die optimale Lösung.- 2.1.8. Messergebnisse.- 2.1.9. Gleichwertigkeit von Algorithmen.- 2.2. Komplexitätsformel.- 2.3. Datenstrukturen.- 2.3.1. Reihungen.- 2.3.2. Verkettete Listen.- 2.3.3. Gleichwertigkeit von Datenstrukturen.- 3. Rekursion und Wiederholung.- 3.1. Rekursive Algorithmen.- 3.1.1. Fakultät.- 3.1.2. Die Fibonacci-Zahlen.- 3.1.3. Die Ackermann-Funktion.- 3.1.4. Die mathematische Induktion.- 3.1.5. Permutationen.- 3.2. Abarbeitung von Datenstrukturen.- 3.2.1. Iterative Abarbeitung von rekursiven Datenstrukturen.- 3.2.2. Rekursive Abarbeitung von rekursiven Datenstrukturen.- 3.2.3. Rekursive Abarbeitung von Reihungen.- 3.3. Rekursive Kurven.- 3.3.1. Schneeflockenkurve.- 3.3.2. Die Pfeilspitzenkurve.- 3.3.3. Die Hilbert-Kurve.- 3.3.4. Ersetzen der Rekursion durch Wiederholung.- 3.4. Zurückverfolgung.- 3.4.1. Labyrinth.- 3.4.2. Der Weg des Springers.- 3.4.3. Die acht Damen.- 3.5. Spracherkennung.- 3.5.1. Sprachen und Grammatiken.- 3.5.2. Reguläre Ausdrücke.- 3.5.3. Reguläre Grammatiken.- 3.5.4. R-Grammatiken.- 3.5.5. Endliche Automaten.- 3.5.6. Kellerautomaten.- 3.5.7. Endlichkeit und Unendlichkeit.- 4. Suchen.- 4.1. Textsuche.- 4.2. Suchen in Sammlungen.- 4.3. Suchen in einer Reihung.- 4.3.1. Suchen in einer unsortierten Reihung.- 4.3.2. Lineares Suchen in einer sortierten Reihung.- 4.3.3. Binäres Suchen.- 4.4. Hash-Tabellen.- 4.5. Suchen in einer verketteten Liste.- 4.5.1. Lineares Suchen in einer unsortierten Liste.- 4.5.2. Lineares Suchen in einer sortierten Liste.- 4.6. Zeitkomplexitäten beim Suchen.- 5. Sortierverfahren.- 5.1. Die Problemstellung.- 5.1.1. Präzisierung des Problems und Grundbegriffe.- 5.1.2. Zeitbedarf und Zeitkomplexität.- 5.2. Quadratische Sortierverfahren.- 5.2.1. Sortieren durch Vertauschen benachbarter Elemente.- 5.2.2. Sortieren durch Einfügen.- 5.2.3. Sortieren durch Auswählen.- 5.3. Unterquadratische Verfahren.- 5.4. Rekursive Verfahren.- 5.5. Logarithmische Verfahren.- 5.5.1. Halde.- 5.5.2. Die Haldenbedingung.- 5.5.3. Senken.- 5.5.4. Zwei Phasen des Heap Sorts.- 5.5.5. Sortieren auf der Halde.- 5.6. Externe Sortierverfahren.- 5.6.1. Mischen.- 5.6.2. Sortierkanal.- 5.6.3. Mischkanal.- 5.6.4. Fibonacci-Mischen.- 6. Baumstrukturen.- 6.1. Binärbaum.- 6.1.1. Definition.- 6.1.2. Suchen im sortierten Binärbaum.- 6.1.3. Darstellung von Binärbäumen.- 6.2. Sortieren mit Binärbäumen.- 6.2.1. Binärbaum als Halde.- 6.2.2. Senken im Binärbaum.- 6.2.3. Baumsort.- 6.2.4. Durchwandern eines Binärbaums.- 6.3. Operationen für Binärbäume.- 6.3.1. Binärbaum aus Knoten.- 6.3.2. Eintragen in einen sortierten Binärbaum.- 6.3.3. Löschen in Binärbäumen.- 6.4. Ausgeglichene Bäume.- 6.4.1. Eintragen in ausgeglichene Bäume.- 6.4.2. Löschen in ausgeglichenen Bäumen.- 6.5. 2-3-4-Bäume.- 6.5.1. Definition.- 6.5.2. Spalten.- 6.5.3. Einfügen.- 6.6. Rot-Schwarz-Bäume.- 6.7. B-Bäume.- 7. Klassen von Algorithmen.- 7.1. Was ist ein algorithmisches Problem?.- 7.2. Theoretische Lösbarkeit von Problemen.- 7.2.1. Definitionen.- 7.2.2. Beispiele.- 7.2.3. Das Halteproblem.- 7.2.4. Das Kachelproblem.- 7.2.5. Das Paligrammproblem.- 7.2.6. Gleichwertigkeit von Grammatiken.- 7.3. Praktische Lösbarkeit von Problemen.- 7.3.1. Das zweite Kachelproblem.- 7.3.2. Das Rucksackproblem.- 7.3.3. Das Aufteilungsproblem.- 7.3.4. Das Problem des Handelsreisenden.- 7.3.5. Hamiltonsche Wege durch einen Graphen.- 7.3.6. Das Erfüllbarkeitsproblem.- 7.4. Die Klassen P und nP.- 7.5. Ist P=np?.- 7.6. Übersicht über Problemklassen.- Empfehlungen.- Programmverzeichnis.- Abbildungs- und Tabellenverzeichnis.- Sachwortverzeichnis.

Über Autor(innen)

Prof. Dr. Andreas Solymosi ist Hochschullehrer für Informatik an der TFH Berlin, Geschäftsführer einer Softwarefirma und Autor erfolgreicher Lehrbücher, die im Verlag Vieweg erschienen sind.
Prof. Dr. Ulrich Grude ist Diplom-Informatiker, promovierte an der TU Berlin und hat einen Lehrstuhl für Informatik an der Technischen Fachhochschule Berlin.