Algorithmen und Datenstrukturen [Lecture notes] by Sven O. Krumke

By Sven O. Krumke

Show description

Read Online or Download Algorithmen und Datenstrukturen [Lecture notes] PDF

Similar structured design books

Advanced ANSI SQL Data Modeling and Structure Processing (Artech House Computer Science Library)

This quantity is a device for using the ANSI/ISO SQL outer sign up for operation, and a advisor to utilizing this operation to accomplish basic or advanced info modelling. It offers a glance on the outer subscribe to operation, its robust syntax, and contours and features that may be constructed in line with the operation's information modelling potential.

Algorithmic Aspects in Information and Management: 10th International Conference, AAIM 2014, Vancouver, BC, Canada, July 8-11, 2014, Proceedings (Lecture Notes in Computer Science)

This quantity constitutes the complaints of the overseas convention on Algorithmic elements in info and administration, AAIM 2014, held in Vancouver, BC, Canada, in July 2014. The 30 revised complete papers offered including 2 invited talks have been conscientiously reviewed and chosen from forty five submissions.

Transactions on Large-Scale Data- and Knowledge-Centered Systems XVII: Selected Papers from DaWaK 2013 (Lecture Notes in Computer Science)

The LNCS magazine Transactions on Large-Scale info- and Knowledge-Centered platforms makes a speciality of facts administration, wisdom discovery and data processing, that are middle and scorching issues in machine technology. because the Nineteen Nineties, the web has turn into the most motive force in the back of program improvement in all domain names.

Theory of Cryptography: 12th International Conference, TCC 2015, Warsaw, Poland, March 23-25, 2015, Proceedings, Part I (Lecture Notes in Computer Science)

The two-volume set LNCS 9014 and LNCS 9015 constitutes the refereed court cases of the twelfth foreign convention on concept of Cryptography, TCC 2015, held in Warsaw, Poland in March 2015. The fifty two revised complete papers awarded have been conscientiously reviewed andselected from 137 submissions. The papers are equipped in topicalsections on foundations, symmetric key, multiparty computation,concurrent and resettable safeguard, non-malleable codes and tampering, privateness amplification, encryption an key alternate, pseudorandom services and purposes, proofs and verifiable computation, differential privateness, useful encryption, obfuscation.

Extra resources for Algorithmen und Datenstrukturen [Lecture notes]

Example text

Innerhalb von L EFTIST-L AZY   M INIMUM sind hier (im Gegensatz zur Implementierung mit Binomial-  Heaps) die beiden Endpunkte u und v in verschiedenen Mengen. 12 T ← T ∪ {(u, v)} 13 Vi ← F IND -S ET(v) { Finde die Menge Vi mit v ∈ Vi . } 14 Vj ← F IND -S ET(v) { analog für v. } 15 Entferne die zu Vi und Vj gehörenden Heaps Qi und Qj aus L. 16 U NION (Vi , Vj ) { Ersetze Vi und Vj durch Vi ∪ Vj . A. Qi , ist bereits aus L entfernt. Er ist      derjenige Heap, den wir zu Anfang der Iteration der while-Schleife als        erstes Element von L entfernt haben.

K/2 die Anzahl der Elemente im iten dieser Heaps. k/2 Dann ist n = i=1 ni . Wir wissen, daß ein L EFTIST-M ELD , das zu einem Heap mit ni Elementen führt, in O(log ni ) Zeit ausgeführt werden kann. Daher ist die Gesamtzeit für die k/2 Aufrufe von L EFTIST-M ELD:  O k/2 i=1  max{1, log ni } . 6) von der Größenordnung O(k max{1, log nk }) ist. Wir haben somit gezeigt, daß der erste Lauf durch die Liste O(k max{1, log nk }) Zeit benötigt und die Anzahl der Heaps in der Liste für den nächsten Durchlauf auf k/2 mindestens halbiert.

Füge x hinten an die Wurzelliste von H an. if x = x1 oder x = x2 then Entferne x = xi aus der entsprechenden Wurzelliste und setze xi ← right[xi ]. Beim Entfernen ist xi das vorderste Element der Liste von Hi , so daß das Entfernen in konstanter Zeit möglich ist. end if carrybit_tree ← NULL end if { 2. Fall: Genau zwei Bäume mit Grad k sind vorhanden. } if genau zwei Bäume haben Grad k then Seien dies y und z. if key[z] < key[y] then carrybit_tree ← B INOM -L INK (H, y, z) else carrybit_tree ← B INOM -L INK (H, z, y) end if Entferne analog zu oben bei Bedarf die Bäume aus den Wurzellisten von H 1 und H2 .

Download PDF sample

Rated 4.53 of 5 – based on 15 votes