Algorithmische Schönheiten – Algorithms Unplugged

Das Seminar Algorithmische Schönheiten findet dieses Semester, Sommersemester 2023, nicht statt.

Dozent:

Rolf Wanka

Betreuer:

Bernd Bassimir
Matthias Kergaßner

ECTS:

5

Zielgruppe:

Bachelor- und Master-Studierende der Informatik,
Interessierte anderer Studiengänge

Vorbesprechung:

Die Vorbesprechung zum Seminar findet am Mi., den 27.04.2022 um 16:15 Uhr im H10 statt.


Eine kurze Zusammenfassung der Themen und der Organisation des Seminars finden Sie in folgendem Video.

Anmeldung:

Die Anmeldung wird via StudOn durchgeführt (Link zur Anmeldung) um Überbuchung zu vermeiden. Die Anmeldung ist ab dem 21.02.2022 möglich und Plätze werden nach dem FCFS Prinzip vergeben.
Die Teilnehmerzahl ist auf maximal 24 beschränkt.
Sollten mehr als 12 Anmeldungen vorliegen, so werden Themen zu zweit bearbeitet.

Umfang:

Die Vorträge finden kompakt in der vorlesungsfreien Zeit statt.

Vortragslänge:

  • Vortrag als Einzelperson: 30 Minuten
  • Vortrag zu Zweit: 2 x 20 Minuten

Vortragslänge möglichst genau einhalten!

Ausarbeitung je Vortrag: 5 Seiten

Folientemplates:

Wenn Sie mögen, können Sie die LaTeX-Beamer-Klasse der FAU nutzen. Sie finden ein entsprechendes tar-file hier.

Nutzen Sie PowerPoint, so haben wir hier eine entsprechende Vorlage.

Ausarbeitungstemplates:

Nutzen Sie bitte den LaTeX-Rumpf der FAU. Sie finden ein entsprechendes zip-file hier.

Themen:

Viele Algorithmen lösen nicht „einfach nur“ das Problem, für das sie ausgedacht worden sind, sie sind oft auch ästhetisch sehr ansprechend. Sie benutzen anschauliche Ideen auf überraschend schlaue Art und Weise, oder sie verwenden Ideen aus einem Bereich bewundernswert clever in einem anderen Einsatzbereich wieder.

Ziel dieses Seminares ist es, einige dieser Algorithmen kennenzulernen. Die Teilnehmerinnen und Teilnehmer bekommen Texte, lesen diese und suchen zusätzlich einige der Hintergrundaufsätze und stellen „ihre“ Algorithmen in einem Vortrag und einer schriftlichen Ausarbeitung vor.

 

Themenliste

  • Parallele Sortiernetzwerke: Bitonic Sort, Leitungselimination, Columnsort
    • R. Wanka.
      Paralleles Sortieren – Parallel geht schnell.
      in: Taschenbuch der Algorithmen; Springer; pp. 31-41, 2008.
      doi:10.1007/978-3-540-76394-9_4
    • M. Mühlenthaler, R. Wanka.
      Improving Bitonic Sorting by Wire Elimination.
      in: Proc. 23rd PARS-Workshop on Parallel Systems and Architectures of the 23rd Int. Conf. on Architecture of Computing Systems (ARCS); pp. 15-22, 2010.
      Zum Paper
    • T. Leighton.
      Tight Bounds on the Complexity of Parallel Sorting.
      IEEE Transactions on Computers C-34 (1985) 344-354.
      doi:10.1109/TC.1985.5009385 bzw. pdf

  • Measure and Conquer Analyse mild-exponentieller exakter Algorithmen für das Vertex-Cover- und das Independent-Set-Problem
    Warum es sich lohnt, alte Algorithmen neu zu analysieren
  • k-SAT in o(2n) Schritten: Die Algorithmen von Schöning und Moser/Scheder
    • U. Schöning.
      A probabilistic algorithm for k-SAT based on limited local search and restart.
      Algorithmica 32 (2002) 615-623.
      doi:10.1007/s00453-001-0094-7 bzw. pdf.
    • R. A. Moser, D. Scheder.
      A Full Derandomization of Schöning’s k-SAT Algorithm.
      in: Proc. 43rd Symposium on Theory of Computing (STOC), pp. 245-251, 2011.
      doi:10.1145/1993636.1993670
  • Lastverteilung in parallelen Computernetzen: Online vs. Offline (Anwendung von Flußalgorithmen)
    • F. Meyer auf der Heide, B. Oesterdiekhoff, R. Wanka.
      Strongly Adaptive Token Distribution.
      Algorithmica 15 (1996) 413-427
      doi:10.1007/BF01955042
  • Zählen von Rucksackfüllungen
    • M. Dyer.
      Approximate counting by dynamic programming.
      in: Proc. 35th ACM Symp. on Theory of Computing (STOC), pp. 693-699, 2003.
      10.1145/780542.780643
    • P. Gopalan, A. Klivans, R. Meka, D. Stefankovic, S. Vempala, E. Vigoda.
      An FPTAS for #Knapsack and Related Counting Problems.
      in: Proc. 52nd IEEE Symp. on Foundations of Computer Science (FOCS), pp. 817-826, 2011
      doi:10.1109/FOCS.2011.32
  • Ameisen berechnen Minimale Spannbäume
    • F. Neumann, C. Witt.
      Ant Colony Optimization and the Minimum Spanning Tree Problem.
      in: Proc. Learning and Intelligent Optimization (LION), pp. 152-166, 2008.
      doi:10.1007/978-3-540-92695-5_12
  • Schwärme berechnen Rundreisen – manchmal mehr schlecht als recht
    • M. Hoffmann, M. Mühlenthaler, S. Helwig, R. Wanka.
      Discrete Particle Swarm Optimization for TSP: Theoretical Results and Experimental Evaluations.
      in: Proc. International Conference on Adaptive and Intelligent Systems (ICAIS), pp. 416-427, 2011.
      doi:10.1007/978-3-642-23857-4_40

    Zusätzliche Information:

  • Parametrisierte Komplexität beim Vertex-Cover-Problem: ein Algorithmus der Laufzeit O(kn + 1.325kk2)
    • R. Balasubramanian, M. R. Fellows, V. Raman.
      An improved fixed-parameter algorithm for vertex cover.
      Information Processing Letters 65 (1998) 163-168.
      doi:10.1016/S0020-0190(97)00213-5
  • Expander-Graphen im Einsatz: Das Multibutterfly-Netzwerk.
    • F. T. Leighton, B. Maggs.
      Fast algorithms for routing around faults in multibutterflies and randomly-wired splitter networks.
      IEEE Transactions on Computers 41 (1992) 578-587.
      doi:10.1109/12.142684
  • Hamilton-Wege auf schönen Graphen
    • R. Feldmann, P. Mysliwietz.
      The shuffle exchange network has a Hamiltonian path.
      Theory of Computing Systems 29 (1996) 471-485.
      doi:10.1007/BF01184811
    • The Cube-Connected Cycles Network has a Hamiltonian Cycle.
      Theorem 3.14 auf S. 466ff in
      F. T. Leighton, Introduction to Parallel Algorithms, Morgan Kaufman, 1992.
  • Partikel wollen raus: Das Anfangsverhalten von Partikelschwärmen in beschränkten Suchräumen.
    • S. Helwig, R. Wanka.
      Theoretical Analysis of Initial Particle Swarm Behavior.
      in: Proc. 10th International Conference on Parallel Problem Solving from Nature (PPSN); pp. 889-898, 2008.
      doi:10.1007/978-3-540-87700-4_88
    • zum Hintergrund: Sabine Helwig.
      Particle Swarms for Constrained Optimization.
      Doktorarbeit, Universität Erlangen-Nürnberg, 2010.
      (Zum Volltext)
  • Approximationsalgorithmus für das 2D Bin-Packing-Problem
    • Andrea Lodi, Silvano Martello, Daniele Vigo.
      Approximation algorithms for the oriented two-dimensional bin packing problem.
      in: European Journal of Operational Research 112 (1999) 158-166.
      doi:10.1016/S0377-2217(97)00388-3

    Zusätzliche Information:

    • Silvano Martello, Daniele Vigo.
      Exact Solution of the Two-Dimensional Finite Bin Packing Problem.
      in: Management Science Volume 44, Issue 3 (1998) 285-432.
      doi:10.1287/mnsc.44.3.388 bzw. pdf
    • J. O. Berkey and P. Y. Wang.
      Two-Dimensional Finite Bin-Packing Algorithms.
      in: The Journal of the Operational Research Society, Volume 38, Issue 5 (1987) 423-429.
      doi:10.1057/jors.1987.70 bzw. pdf
  • Ameisen-Algorithmus für das Knotenüberdeckungsproblem mit geringstem Gewicht
    • Shyong Jian Shyu, Peng-Yeng Yin, Bertrand M.T. Lin.
      An Ant Colony Optimization Algorithm for the Minimum Weight Vertex Cover Problem.
      in: Annals of Operations Research 131, 283–304, 2004.
      doi:10.1023/B:ANOR.0000039523.95673.33
  • Maximaler Fluss und parametrisierte kürzeste Pfade in planaren Graphen
    • Jeff Erickson.
      Maximum Flows and Parametric Shortest Paths in Planar Graphs.
      in: Proceeding SODA ’10 Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete algorithms, Pages 794-804.
      http://dl.acm.org/citation.cfm?id=1873601.1873666
  • Approximationsalgorithmus für das Bandbreitenproblem auf dichten Graphen
  • Ameisenalgorithmus für das Prüfungsplanungsproblem