Datenstrukturen und Algorithmen by Prof. Dr. rer. nat. Ralf Hartmut Güting, Dr. rer. nat.

By Prof. Dr. rer. nat. Ralf Hartmut Güting, Dr. rer. nat. Stefan Dieker (auth.)

Effiziente Algorithmen und Datenstrukturen bilden ein zentrales Thema der Informatik. Wer programmiert, sollte zu den wichtigsten Problembereichen grundlegende L?sungsverfahren kennen. Dieses Buch vermittelt entsprechende Kenntnisse und F?higkeiten. Es setzt Akzente in der klaren Trennung zwischen Datentyp und Datenstruktur als Implementierung eines Datentyps und in der Beschreibung von Algorithmen auf angemessenem Abstraktionsniveau; einen besonderen thematischen Schwerpunkt bilden geometrische Algorithmen. Die jetzt neu bearbeitete Auflage des Buches benutzt Java als Implementierungssprache.

Show description

Read Online or Download Datenstrukturen und Algorithmen PDF

Similar german_4 books

ASIC-Design: Realisierung von VLSI-Systemen mit Mentor V8

In diesem Buch wird der Entwicklungsablauf und die Realisierungstechniken für anwendungsspezifische Schaltkreise am Beispiel einer Speicherschaltung in CMOS-Technologie vorgestellt. Dabei werden alle Entwurfsschritte von der Erstellung des Lastenheftes bis zur Generierung des Testprogramms angesprochen.

Dateien und Datenbanken: Eine anwendungsorientierte Einführung

Schwerpunkte dieses Lehrbuchs sind der Entwurf und die Entwicklung einfacher Datenbankanwendungen. Zunächst wird am Beispiel typischer Datenstrukturen und Algorithmen die Verwaltung unverbundener Dateien behandelt. Anschließend folgt, ausgehend von Beispielen zur Datenbankverwaltung in weitverbreiteten Softwarepaketen, eine Einführung in den Entwurf von Datenbanken.

Historische Sozialforschung: Einführung und Überblick

Aus dem Inhalt: Historische Sozialforschung / Geschichtstheorie / Geschichte und Theorien der Sozialwissenschaften / Quantitative Methoden für die Historie / Neue Quellen- und Datenformen

Extra resources for Datenstrukturen und Algorithmen

Sample text

Man beachte, daß auch der Benutzer dieser Datenstruktur diese Frage anhand der Spezifikation klären kann; er muß sich nicht in den Programmcode vertiefen! 1 beschrieben; if x gefunden then return true eise return/alse end if. algorithm isempty return (top = 0). 1. Man spricht dann auch von einem Datenobjekt anstelle eines Datentyps. 2. Diese Festlegung wird später bei der Implementierung geändert. Wir zeigen dies trotzdem als Beispiel dafür, daß Programmentwicklung nicht immer streng top-down verläuft, sondern daß gelegentlich Entwurfsentscheidungen höherer Ebenen zurückgenommen werden müssen.

Dann gilt: - p =0(p') ~ d =d' - p =o(p') ~ d < d' - p =ro(p') ~d>d' (ii) \;fk > 0, \;fe > 0: lol n = o(n (iii) \;fk > 0: n k = o(2 n ) (iv) 2 n / 2 = o(2 n ) E) 20 KAPITEL 1 EINFÜHRUNG Diese Beziehungen erlauben uns den einfachen Vergleich von Polynomen, logarithmischen und Exponentialfunktionen. 4: Gilt log n = O( Jn)? 14: Die Laufzeit der einfachen Suchverfahren in diesem Abschnitt (contains und contains2) ist O(n) im worst case, aber auch Q(n) und daher auch 8(n). 0 Da die Q-Notation eine untere Schranke für das Wachstum einer Funktion beschreibt, wird sie oft benutzt, um eine untere Schranke für die Laufzeit aller Algorithmen zur Lösung eines Problems anzugeben und damit die Komplexität des Problems zu charakterisieren.

6: Algorithmus contains3 Dieser rekursive Algorithmus wird zu Anfang mit contains 0, n, c) aufgerufen; S wird diesmal als globale Variable aufgefaßt. Wir analysieren das Verhalten im schlimmsten Fall. Wie oben erwähnt, führt ein rekursiver Algorithmus zu Rekursionsgleichungen für die Laufzeit: Sei T(m) die worst-case-Laufzeit von contains, angesetzt auf einen TeilArray mit m Elementen. Es gilt: T(O) =a T(m) =b+T(m/2) Hier sind a und b Konstanten: a beschreibt die Laufzeit (eine obere Schranke für die Anzahl von Elementaroperationen), falls kein rekursiver Aufruf erfolgt; b beschreibt im anderen Fall die Laufzeit bis zum rekursiven Aufruf.

Download PDF sample

Rated 4.42 of 5 – based on 50 votes