Navigation

Algorithmische Schönheiten – Algorithms Unplugged

Dozent:

Rolf Wanka

Betreuer:

Alexander Raß
Bernd Bassimir

ECTS:

5

Zielgruppe:

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

Vorbesprechung:

Die Vorbesprechung zum Seminar hat bereits stattgefunden.

Umfang:

Kompakt zum Ende der vorlesungsfreien Zeit.
Termin: 4.10.+5.10. jeweils ab 9:30 Uhr im Raum 01.255-128

Vortragslänge: 30 Minuten (möglichst genau!)
Ausarbeitung: 5 Seiten, Abgabetermin am 26.10. als pdf per Mail


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 tar-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 (noch nicht endgültig)

  1. Parallele Sortiernetzwerke: Bitonic Sort, Leitungselimination, Columnsort (Darko B.) (Vortrag/Ausarbeitung)
    • 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
  2. Manchmal sind als NP-vollständig vermutete Probleme doch in P (Jonas F.) (Vortrag/Ausarbeitung)
  3. Mild-exponentielle exakte Algorithmen für das Vertex-Cover- und das Independent-Set-Problem (Matthias K.) (Vortrag/Ausarbeitung)
    Warum es sich lohnt, alte Algorithmen neu zu analysieren
    • Kapitel 6 aus:
      F. V. Fomin, D. Kratsch. Exact Exponential Algorithms. Springer, 2010.
      doi:10.1007/978-3-642-16533-7
      leider hat die FAU dieses Buch nicht abonniert, aber das
      pdf zum Herunterladen ist HIER.
  4. k-SAT in o(2n) Schritten: Die Algorithmen von Schöning und Moser/Scheder (Keyao W.) (Vortrag/Ausarbeitung)
    • 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 oder HIER.
    • 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
  5. Lastverteilung in parallelen Computernetzen: Online vs. Offline (Anwendung von Flußalgorithmen) (Jeanette W.) (Vortrag/Ausarbeitung)
    • F. Meyer auf der Heide, B. Oesterdiekhoff, R. Wanka.
      Strongly Adaptive Token Distribution.
      Algorithmica 15 (1996) 413-427
      doi:10.1007/BF01955042
  6. Zählen von Rucksackfüllungen (nicht vergeben)
    • 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
  7. Ameisen berechnen Minimale Spannbäume (Julian P.) (Vortrag/Ausarbeitung)
    • 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
  8. Schwärme berechnen Rundreisen – manchmal mehr schlecht als recht (Aaron S.) (Vortrag/Ausarbeitung)
    • 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:

  9. Parametrisierte Komplexität beim Vertex-Cover-Problem: ein Algorithmus der Laufzeit O(kn + 1.325kk2) (Thilo K.) (Vortrag/Ausarbeitung)
    • 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
  10. Expander-Graphen im Einsatz: Das Multibutterfly-Netzwerk. (Maximilian L.) (Vortrag/Ausarbeitung)
    • 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
  11. Hamilton-Wege auf schönen Graphen (Thomas R.) (Vortrag/Ausarbeitung)
    • 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.
  12. Partikel wollen raus: Das Anfangsverhalten von Partikelschwärmen in beschränkten Suchräumen. (Alexander F.) (Vortrag/Ausarbeitung)
    • 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)
  13. Approximationsalgorithmus für das 2D Bin-Packing-Problem (Lukas S.) (Vortrag/Ausarbeitung)
    • 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
  14. Ameisen-Algorithmus für das Knotenüberdeckungsproblem mit geringstem Gewicht (Moritz F.) (Vortrag/Ausarbeitung)
    • 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
  15. Maximaler Fluss und parametrisierte kürzeste Pfade in planaren Graphen (Kevin H.) (Vortrag/Ausarbeitung)
    • 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
  16. Approximationsalgorithmus für das Bandbreitenproblem auf dichten Graphen (Moritz K.) (Vortrag/Ausarbeitung)
  17. Eine Anwendung von 2SAT (Marius F.) (Vortrag/Ausarbeitung)
    Problemstellung und Lösungsanleitung (ab 45m:54s)
  18. Ameisenalgorithmus für das Prüfungsplanungsproblem (Elena T.) (Vortrag/Ausarbeitung)