15 Fakultätsübergreifend / Sonstige Einrichtung

Permanent URI for this collectionhttps://elib.uni-stuttgart.de/handle/11682/16

Browse

Publication Type: search.filters.UBSTyp.ArbeitspapierSubject: search.filters.subject.004

Search Results

Now showing 1 - 3 of 3
  • Thumbnail Image
    ItemOpen Access
    SEED - das Datenbanksystem für die Software-Entwicklungsumgebung SEEME
    (1984) Glinz, Martin; Ludewig, Jochen
    Im Zusammenhang mit der Konzipierung der Software-Entwicklungsumgebung SEEME stellt sich das Problem einer geeigneten Datenverwaltung, da herkömmliche Datenbanksysteme diese Aufgabe nur unzureichend erfüllen. Um ein Datenmodell für SEEME definieren zu können, stellen wir zunächst die Anforderungen an das Datenbanksystem einer Software-Entwicklungsumgebung zusammen und vergleichen sie mit den Eigenschaften verschiedener, in der Literatur beschriebener Datenbankmodelle. Dabei zeigt sich, dass keines dieser Modelle die Anforderungen in befriedigender Weise erfüllt. Wir definieren daher ein neues, an den Anforderungen einer Software-Entwicklungsumgebung orientiertes Datenbankmodell. Dieses basiert auf einem erweiterten Entity-Relationship-Ansatz und schliesst - im Unterschied zu vielen anderen Modellen - die Operationen auf den Daten ein, was die Betrachtung der Datenbank als abstrakten Datentyp ermöglicht. Die wesentlichen strukturellen Elemente des Modells sind Hierarchien von Objektklassen, welche auf beliebigen Ebenen durch Assoziationen in netzwerkartige Beziehungen gesetzt werden können, sowie die Generalisierung von Klassen und Assoziationen. Ferner führen wir auf der Datenebene den Begriff des Musters ein, der in einem (noch auszuführenden) Variantenkonzept eine zentrale Stellung einnimmt. Für die Datenmanipulation definieren wir mehrere, aufeinander aufbauende Operationsebenen . Die Operationen sind mit ihren Vor- und Nachbedingungen so auf das Datenbankschema abgestimmt, dass sie einerseits die Konsistenz der Datenbank (soweit diese im Schema beschrieben ist) sichern, jedoch andererseits auch die Erfassung von vagen und unvollständigen Informationen zulassen. Durch Definition von Transaktionen (als Teil der Datenbank) können zudem auch höhere, durch die Datenbank garantierte Konsistenzebenen erreicht werden.
  • Thumbnail Image
    ItemOpen Access
    On smoothed analysis of quicksort and hoare's find
    (2009) Fouz, Mahmoud; Kufleitner, Manfred; Manthey, Bodo; Zeini Jahromi, Nima
    We provide a smoothed analysis of Hoare's find algorithm and we revisit the smoothed analysis of quicksort. Hoare's find algorithm - often called quickselect - is an easy-to-implement algorithm for finding the k-th smallest element of a sequence. While the worst-case number of comparisons that Hoare's find needs is quadratic, the average-case number is linear. We analyze what happens between these two extremes by providing a smoothed analysis of the algorithm in terms of two different perturbation models: additive noise and partial permutations. In the first model, an adversary specifies a sequence of n numbers in the interval [0,1], and then each number is perturbed by adding a random number drawn from the interval [0,d]. In this setting, we give a tight bound for the number of comparisons in expectation of Hoare's find algorithm if the adversary may also specify the element that we would like to find. Furthermore, we consider the number of comparisons for finding the median. Again, we give tight bounds for the number of comparison in expectation. In the second model, each element is marked with probability p and then a random permutation is applied to the marked elements. We also provide a tight bound for the expected number of comparisons for this second model. Finally, we provide lower bounds for the smoothed number of comparisons of quicksort and Hoare's find for the median-of-three pivot rule, which usually yields faster algorithms than always selecting the first element: The pivot is the median of the first, middle, and last element of the sequence. We show that median-of-three does not yield a significant improvement over the classic rule: the lower bounds for the classic rule carry over to median-of-three.
  • Thumbnail Image
    ItemOpen Access
    Chasing the busy-beaver : notes and observations on a competition to find the 5-state busy beaver
    (1983) Ludewig, Jochen; Schult, Uwe; Wankmüller, Frank
    This is a report on the results of a competition which was initiated on the occasion of the 6th GI-conference on Theoretical Computer Science, which took place at the University of Dortmund from January 5th to 7th, 1983. It was asked for the best solution of the 5-state Busy-Beaver-Game. At first we make some historical remarks, introduce the formalism, and list some results. Then the two best solutions are described. Next we make some remarks on the behaviour of good beavers and on the strange behaviour of some Turing machines. Zoological names were given to the latter machines. The amusing results are written down in the last chapter. In the appendix you can find a lot of examples.