Sir Charles Antony Richard Hoare ist (inzwi­schen eme­ri­tier­ter) Professor of Computing in Oxford und arbei­tet bei Microsoft Research Cambridge. Informatik-StudentInnen ken­nen ihn als den Erfinder des Quicksort-Algorithmus und Turing Award Preisträger — die­sen “Nobelpreis der Informatik” erhielt der Brite im Jahr 1980. An der TU Wien hält Hoare einen Vortrag mit anschlie­ßen­der Diskussion.

Ort: TU Wien, Neues Elektrotechnisches Institutsgebäude, Hörsaal EI 9, Gußhausstraße 25, EG

Der Vortrag beginnt pünkt­lich um 17 Uhr, im Fokus steht das Thema Fine-Grain Concurrency:

I have always been frigh­te­ned by con­cur­rent pro­grams which share a com­mon memory, with fine-grained inter­lea­ving of access to it. But with multi-core com­pu­ters, that is the way of the future. Fortunately, the recent deve­lop­ment of sepa­ra­tion logic gives an ele­gant way of expres­sing ownership of sto­rage loca­ti­ons and the trans­fer of ownership.

I will intro­duce a seman­tics based on Petri nets, using sepa­ra­tion logic to anno­tate their arcs and to prove absence of race con­di­ti­ons as well as asser­tio­nal correctness.

Weitere Infos zur Veranstaltung
Tony Hoare: Biographie

Was hat’s auf sich mit Quicksort?

Die Problemstellung, Daten anhand bestimm­ter Parameter zu sor­tie­ren, tritt bei der Programmierung sehr häu­fig auf. Quicksearch nutzt einen rekur­si­ven Algorithmus, der mit einer kur­zen inne­ren Schleife äußerst per­for­mante und spei­cher­scho­nende Sortierverfahren erlaubt. Er bedient sich dabei des soge­nann­ten “Teile und herr­sche” bzw. “divide et impera” Prinzips — dabei geht es um die Zerlegung eines kom­ple­xen Problems in viele kleine Einzelprobleme. Quicksort etwa gene­riert viele kleine Ergebnislisten, aus denen das Gesamtergebnis dann zusam­men­ge­setzt wird. Näheres weiß die Wikipedia:

Zunächst wird die zu sor­tie­rende Liste in zwei Teillisten umsor­tiert. Dazu wählt Quicksort ein soge­nann­tes Pivotelement aus der Liste aus, das die Grenze zwi­schen den bei­den Teillisten fest­legt. Alle Elemente die klei­ner als das Pivotelement sind, kom­men in die linke, untere Teilliste und alle die grö­ßer sind, in die rechte, obere Teilliste. Die Längen der Teillisten wer­den also nicht schon vor­her fest­ge­legt, son­dern erge­ben sich aus der Wahl des Pivotelements. Die Positionen der Elemente, die gleich dem Pivotelement sind, hän­gen vom ver­wen­de­ten Teilungsalgorithmus ab. Sie kön­nen sich belie­big auf die Teillisten verteilen.

Keine ähnli­chen Beiträge.