Seiteninterne Suche

Lehre

Algorithmische Schönheiten – Algorithms Unplugged

Dozent:

Rolf Wanka

ECTS:

5

Zielgruppe:

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

Vorbesprechung:

Interessierte Studierende sind eingeladen, am Dienstag, d. 4. April 2017, um 10:00 Uhr in den Raum 02.112-128 im Felix-Klein-Gebäude zur Vorbesprechung und Vergabe der Themen zu kommen.

Umfang:

Kompakt zum Ende der vorlesungsfreien Zeit
Termin: 4. August (9 Uhr bis ca. 16 Uhr)
Raum: 02.112-128

Vortragslänge: 45 Minuten (möglichst genau!)
Ausarbeitung: 5 Seiten, Abgabe bis zum 25. August


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:

Wenn Sie mögen, können Sie den LaTeX-Rumpf der FAU nutzen. 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

  1. Parallele Sortiernetzwerke: Bitonic Sort, Leitungselimination, Columnsort (Corona)
    • 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
  2. Manchmal sind als NP-vollständig vermutete Probleme doch in P
  3. Mild-exponentielle exakte Algorithmen für das Vertex-Cover- und das Independent-Set-Problem
    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
    • U. Schöning.
      A probabilistic algorithm for k-SAT based on limited local search and restart.
      Algorithmica 32 (2002) 615-623.
      Paper beim Autor
    • 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. Kantenfärbungen mit höchstens einer Farbe zu viel: Der Satz von Vizing (Neureiter)
  6. Lastverteilung in parallelen Computernetzen: Online vs. Offline (Anwendung von Flußalgorithmen) (Mierzwinsky)
    • F. Meyer auf der Heide, B. Oesterdiekhoff, R. Wanka.
      Strongly Adaptive Token Distribution.
      Algorithmica 15 (1996) 413-427
      doi:10.1007/BF01955042
  7. 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
  8. Ameisen berechnen Minimale Spannbäme
    • 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
  9. Schwärme berechnen Rundreisen – manchmal mehr schlecht als recht (Schreiner)
    • 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
  10. 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
  11. 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
  12. 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.
  13. 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)
  14. Approximationsalgorithmus für das 2D Bin-Packing-Problem (Trümpelmann)
    • 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
  15. 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
  16. Maximaler Fluss und parametrisierte kürzeste Pfade in planaren Graphen (Sammler)
    • 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
  17. Approximationsalgorithmus für das Bandbreitenproblem auf dichten Graphen