Bibliographic Metadata

Title
Analyse und Varianten von In situ-Permutationsalgorithmen / Silvio Dorrighi
AuthorDorrighi, Silvio
CensorPanholzer, Alois
Published2009
DescriptionIII, 100 Bl. : graph. Darst.
Institutional NoteWien, Techn. Univ., Dipl.-Arb., 2009
LanguageGerman
Document typeThesis (Diplom)
Keywords (DE)In situ-Permutation / In place-Permutation / Zyklenführeralgorithmen / Zyklenführersuche
Keywords (EN)In situ-permutation / In place-permutation / cycle leader algorithms / cycle leader search
URNurn:nbn:at:at-ubtuw:1-28631 Persistent Identifier (URN)
Restriction-Information
 The work is publicly available
Files
Analyse und Varianten von In situ-Permutationsalgorithmen [1.36 mb]
Links
Reference
Classification
Abstract (German)

Diese Arbeit beschäftigt sich mit der Laufzeitanalyse von In situ-Permutationsalgorithmen, deren Ziel es ist, ein Datenfeld anhand einer Permutation mit sublinearen Hilfsspeicher umzuspeichern. Dabei wird stets die Zyklenstruktur einer Permutation ausgenützt um ein spezielles Element in jedem Zyklus, den Zyklenführer, auszuzeichnen und dort mit einer Umspeicherroutine den gesamten Zyklus im Speicher zu rotieren. Daher bezeichnet die Zyklenführersuche den Kern der Algorithmen.

Abstract (English)

This thesis deals with the frequency analysis of In situ-permutationalgorithms, which restore an array of data without using more than linear additional space. The cycle structure of the permutation is used to determine a specific element within every cycle, called cycle leader, and start there with rotating the corresponding data along the cycle. So the main goal is to look effectively for the cycle leaders.