AK der Algorithmik 5 VU 2.0

LVA-Kennzahl:

186.137 (SS)

Allgemeines:

Diese Vorlesung mit Übung beschäftigt sich mit ausgewählten Algorithmen. Die Auswahl erfolgte nach Aktualität, Relevanz, aber auch Ästhetik. Geplant sind u.a. folgende Themen:

• Heiratssatz
  Wir stellen uns ein Dorf vor, in dem es genauso viele Männer wie Frauen gibt und in dem jeder Mann eine Frau und jede Frau einen Mann heiraten will. Jeder Mann und jede Frau haben eine Rangliste, wen sie am liebsten, zweitliebsten usw. heiraten möchten. Das Ziel ist es nun, alle Männer und Frauen so zu verheiraten, dass es zu keinen Scheidungen kommt, nur weil sich zwei Leute lieber haben als ihre jeweiligen Ehepartner.
• Algorithmen in der Bio-Informatik
  In der Genforschung werden Computer zum Lösen vielfältiger Probleme eingesetzt. Beispiele sind der Vergleich von Gensequenzen, das Berechnen von phylogenetischen Bäumen zur Verwandtschaftsanalyse von Lebewesen u.s.w.
• Planar Point Location
  Stellen Sie sich vor, Sie befinden sich in einer fremden Stadt und wollen wissen, wo sich das nächste Beisel befindet. Deshalb nehmen Sie Ihr modernes, mit Global Positioning System ausgestattetes UMTS-Handy aus der Tasche und tippen die entsprechende Frage ein. Welche Algorithmen kann nun Ihr Provider verwenden, um möglichst schnell Ihre Frage zu beantworten, wenn er Ihre Position und die Position aller Beisel kennt?
• Fibonacci-Heaps
  Fibonacci-Heaps sind eine weniger strikte Variante von Binomial-Heaps und erlauben deswegen eine bessere theoretische Analyse. Insbesondere wenn die Anzahl der Löschoperationen im Datentyp Prioritätswarteschlange gering ist, sind sie (zumindest theoretisch) von Vorteil. Gezeigt wird das mit amortisierter Analyse, einem mächtigen Werkzeug zum Abschätzen der Laufzeit einer Folge von Operationen.
• Softwarevisualisierung
  Unter Softwarevisualisierung (SV) versteht man die graphische Repräsentation von abstrakten Algorithmen sowie von konkreten Programmen. Derartige Repräsentationen können sowohl von statischer Natur sein, wie etwa Diagramme, als auch dynamisch in Form von Animationen realisiert werden. Sie finden Anwendung zur Fehlersuche bei der Programmentwicklung und werden sehr häufig in webbasierten Lehr- und Lernsystemen eingesetzt. Die Vorlesung geht auf verschiedene Aspekte, Techniken und Werkzeuge der SV ein und verdeutlicht diese anhand von Beispielsystemen. Gestreift werden auch Themen aus der sogenannten Visuellen Programmierung.

Die Lehrveranstaltung wird in drei Blöcken zu je zwei bis vier Vorlesungseinheiten abgehalten, denen jeweils eine Übungseinheit folgt. Bei den Übungsterminen gilt strikte Anwesenheitspflicht.

Vorbesprechung:

Donnerstag, 4. März 2004, 13:00 Uhr, im Seminarraum 186 (Favoritenstr. 9-11, 5. Stock).

Ablauf des Übungsteils:

Die Anmeldung erfolgt durch die Eintragung zu Übungsgruppen in der Vorlesung am 30. März 2004.

Jede Übungsgruppe muss zu allen drei Übungsterminen jeweils gemeinsam ein Beispiel ausarbeiten und vortragen. Die Zuordnung der Gruppen zu den Beispielen erfolgt nach dem Zufallsprinzip. Der aktuelle Stand der Zuordnung ist in der Folge dargestellt.

Gruppe	1.Übungstermin (20.4.2004) [Übungsblatt 1]	2.Übungstermin (25.5.2004) [Übungsblatt 2]	3.Übungstermin (22.6.2004) [Übungsblatt 3]
Gruppe A	Aufgabe 3 [PDF]	Aufgabe 1	Aufgabe 4
Gruppe B	Aufgabe 5 [PDF]	Aufgabe 2	Aufgabe 1
Gruppe C	Aufgabe 4 [PDF]	Aufgabe 4	Aufgabe 5
Gruppe D	Aufgabe 2 [PDF]	Aufgabe 3	Aufgabe 2
Gruppe E	Aufgabe 1 [PDF]	Aufgabe 5	Aufgabe 3

Termine:

Die Lehrveranstaltung wird von 9. März bis 22. Juni 2004 jeweils am Dienstag von 13:00 bis 14:30 (pünktlich) Uhr im Seminarraum 186 (Favoritenstr. 9-11, 5.Stock) abgehalten.

Davon sind Übungstermine (mit Anwesenheitspflicht):
Dienstag, 20. April 2004 [Übungsblatt 1 als PDF-Datei]
Dienstag, 25. Mai 2004 [Übungsblatt 2 als PDF-Datei] und [JSAMBA Dokumentation]
Dienstag, 22. Juni 2004 [Übungsblatt 3 als PDF-Datei]

Die mündlichen Abschlussprüfungen finden in der Zeit von 23. bis 25. Juni 2004 nach individueller Vereinbarung statt.

Beurteilung:

Um ein positives Zeugnis zu erhalten, müssen Sie aktiv an den Übungsterminen teilnehmen und die mündliche Abschlussprüfung bestehen. Zu diesem Prüfungstermin ist eine Anmeldung erforderlich. Die Anmeldeliste liegt in der letzten Übungsstunde am 22. Juni 2004 zur Eintragung auf.

Stoff der Prüfung ist der gesamte während der Lehrveranstaltung (Vorlesungs- und Übungsteil) durchgenommene Lehrinhalt; die gestellten Aufgaben umfassen sowohl theoretische Fragen als auch praktische Beispiele.

Unterlagen:

Unterlagen zu den einzelnen Themen werden im Laufe der Lehrveranstaltung zur Verfügung gestellt.

Hinweis: Artikel vom Portal der Association for Computing Machinery (ACM) können im Rahmen einer campusweiten Lizenz von allen Anschlüssen im TUNET (auch über externe Zugänge) abgerufen und z.B. als PDF-Dateien heruntergeladen werden. Wo sowohl Digital Object Identifier (DOI) als auch ein Link auf das ACM Portal angegeben sind, führen beide im Normalfall auf die gleiche Seite der ACM Digital Library. Auch für SpringerLink gibt es eine campusweite Lizenz, Downloads sind ebenfalls möglich.

• Heiratssatz
  • Andrew W. Goldberg, Combinatorial optimization lecture notes [PostScript]
    http://hyde.eng.tau.ac.il/CO02/Goldberg-combinatorial-optimization-lecture-notes.ps
    (relevant sind die Seiten 8 bis 11 oben)
  • Harry Mairson, The Stable Marriage Problem
    http://www1.cs.columbia.edu/~evs/intro/stable/writeup.html
• Primzahlenberechnung
  • Java-Programme aus der Vorlesung: [1] [2] [3] [4] [5] [6] [7]
  • Einige "klassische" (und schon relativ alte) Algorithmen:
    • T. C. Wood, Algorithm 35: Sieve
      Communications of the ACM, Vol.4, No.3, p.151, ACM Press, March 1961
      [DOI] [ACM Portal]
    • M. Shimrat, Algorithm 223: Prime twins
      Communications of the ACM, Vol.7, No.4, p.243, ACM Press, April 1964
      [DOI] [ACM Portal]
    • Patrick C. Fischer, Generation of Primes by a One-Dimensional Real-Time Iterative Array
      Journal of the ACM, Vol.12, No.3, pp.388-394, ACM Press, July 1965
      [DOI] [ACM Portal]
    • B. A. Chartres, Algorithm 310: Prime number generator 1
      Communications of the ACM, Vol.10, No.9, p.569, ACM Press, September 1967
      [DOI] [ACM Portal]
    • Richard C. Singleton, Algorithm 356: a prime number generator using the treesort principle [A1]
      Communications of the ACM, Vol.12, No.10, p.563, ACM Press, October 1969
      [DOI] [ACM Portal]
    • Richard C. Singleton, Algorithm 357: an efficient prime number generator [A1]
      Communications of the ACM, Vol.12, No.10, pp.563-564, ACM Press, October 1969
      [DOI] [ACM Portal]
  • Fortgeschrittene Verfahren:
    • Harry G. Mairson, Some new upper bounds on the generation of prime numbers
      Communications of the ACM, Vol.20, No.9, pp.664-669, ACM Press, September 1977
      [DOI] [ACM Portal]
    • David Gries and Jayadev Misra, A linear sieve algorithm for finding prime numbers
      Communications of the ACM, Vol.21, No.12, pp.999-1003, ACM Press, December 1978
      [DOI] [ACM Portal]
    • Paul Pritchard, A sublinear additive sieve for finding prime numbers
      Communications of the ACM, Vol.24, No.1, pp.18-23, ACM Press, January 1981
      [DOI] [ACM Portal]
    • Paul Pritchard, Some negative results concerning prime number generators
      Communications of the ACM, Vol.27, No.1, pp.53-57, ACM Press, January 1984
      [DOI] [ACM Portal]
    • Paul Pritchard, Improved incremental prime number sieves
      Proceedings of the First International Symposium on Algorithmic Number Theory, pp.280-288, Ithaca, NY, USA, May 6-9, 1994
      [Citeseer] (Links defekt, Artikel nur noch unter "Cached" verfügbar!)
  • Zusätzliche Unterlagen für Interessierte (kein Prüfungsstoff!):
    • Jeffrey Shallit, The prime factorization of 1
      ACM SIGAPL APL Quote Quad, Vol.6, No.4, pp.36-37, ACM Press, Winter 1976
      [DOI] [ACM Portal]
    • Eric Bach, How to generate random integers with known factorization
      Proceedings of the fifteenth annual ACM symposium on Theory of computing, pp.184-188, ACM Press, 1983
      [ACM Portal]
    • Xuedong Luo, A practical sieve algorithm for finding prime numbers
      Communications of the ACM, Vol.32, No.3, pp.344-346, ACM Press, March 1989
      [DOI] [ACM Portal]
    • J. H. Davenport, Primality testing revisited
      Papers from the international symposium on Symbolic and algebraic computation, pp.123-129, Berkeley, CA, USA, 1992
      [DOI] [ACM Portal]
    • Jonathan P. Sorenson, Trading Time for Space in Prime Number Sieves
      Proceedings of the Third International Symposium on Algorithmic Number Theory, pp.179-195, Portland, OR, USA, June 21-25, 1998; Springer LNCS 1423, 1998.
      [SpringerLink]
• Ausgewählte Kapitel der Bioinformatik
  • Kommentierte Folien (PDF): [Teil 1] [Teil 2]
• Softwarevisualisierung
  • Vorlesungsfolien (PDF): [Teil 1] [Teil 2]
  • A. Kerren and J. T. Stasko. Algorithm Animation - Chapter Introduction.
    In Software Visualization, volume 2269 of LNCS State-of-the-Art Survey, pages 1-15. Springer, 2002.
    [PDF]
  • Stephan Diehl (Hrsg.), Software Visualization.
    volume 2269 of LNCS State-of-the-Art Survey, 2002.
    [SpringerLink]
  • Stefan Schiffer, Visuelle Programmierung - Grundlagen und Einsatzmöglichkeiten
    [Buch in HTML-Format]
• Planar Point Location
  • Vorlesungsfolien (PDF1, PDF2)
  • Beweise (PDF)
• Fibonacci-Heaps und Minimale Schnitte
  • Vorlesungsfolien Fibonacci-Heaps I, Beweise der Lemmata
  • Vorlesungsfolien Fibonacci-Heaps II, Minimale Schnitte

Verantwortliche:

Univ.Ass. Dr. Martin Schönhacker (Organisation)
Univ.Ass. Dr. Gabriele Koller
Univ.Ass. Dr. Andreas Kerren
Univ.Ass. Dr. Gunnar Klau
Univ.Ass. Dr. René Weiskircher

---

Lehrveranstaltungen des aktuellen Semesters | Algorithms and Data Structures Group | Inst. of Computer Graphics and Algorithms | TU Wien

---

Wenn Sie Anregungen haben, kontaktieren Sie bitte webmaster @ads.tuwien.ac.at.
Last modification: 2004-06-15, 14:57