English English

Termine

Art
Termin / Ort
Veranstalter
S2
Blockseminar
22.-23. Juli,BI-T (Bonn)
Vöcking, Ochel, Olbrich

 


Themen

Das Seminar beschäftigt sich mit unterschiedlichsten Problem und deren algorithmischer Lösung (siehe Vorträge).

Alle Teilnehmenden bereiten zu je einem der Themen einen maximal 45-minütigen Vortrag (plus Diskussion) sowie eine Ausarbeitung vor. Da sich das Seminar an Studierende des Grundstudiums richtet, sind die im Grundstudium erworbenen Kenntnisse für die Bearbeitung der Themen ausreichend. Es gibt keine weiteren Voraussetzungen.

Termine und Meilensteine

  • 19.05.2008: 10:00 Themenvergabe, Seminarraum 4017
  • 10.06.2008: 15:30 Kurzvorträge
  • bis zum 13.07.2008: Abgabe und Besprechung der Folien (bis zum heisst nicht am!)
  • 22.- 23. Juli: Seminar
  • bis zum 15.08.2008: Abgabe und Besprechung der Ausarbeitung

Vorträge

    Session 1 (22.07., vormittags)

    • Matrixmultiplikation (Lukas Niessen)
    • Quantenalgorithmen (Malte Kampschulte)
    • Chords' Problem (Martin Blume)

    Session 2 (22.07., nachmittags)

    • Minimizing Congestion in General Networks (Friedrich Gretz)
    • Primzahltests (Astrid Sturm)

    Session 3 (23.07., vormittags)

    • Sublineare Algorithmen (Silvio de Carolis)
    • Maximal Matchings via Gaussian Elimination (Simon Lessenich)
    • SAT-Algorithmen (Martin Lang)

Literatur (Auswahl)

  • Schönhage, Strassen: Schnelle Multiplikation grosser Zahlen, Computing 7, 1971, Springer Verlag, S. 281-292

  • Fürer: Faster integer multiplication, Proc. of the 39th STOC, 2007

  • von zur Gathen, Gerhard: Modern Computer Algebra, Cambridge University Press, 2003

  • Mucha, Sankowski: Maximum matchings in planar graphs via gaussian elimination, Proc. of the 12th ESA, 2004

  • Daurat, Gerard, Nivat: The chords' problem, TCS 282:319-336, 2002

  • Czumaj, Sohler: Estimating the weight of metric minimum spanning trees in sublinear-time, Proc. of the 36th STOC, 2004

  • Schöning: A probabilistic algorithm for k-SAT based on limited local search and restart, Algorithmica 32(4): 615-623, 2002

  • Gruska: Quantum Computing, McGraw-Hill, 1999

  • Nielsen, Chuang: Quantum Computation and Quantum Information, Cambridge University Press, 2000

  • Grover: A fast quantum mechanical algorithm for database search, Proc. of the 28th STOC, 1996


Kontakt

Marcel Ochel: ochel(at) cs.rwth-aachen.de, Lars Olbrich: lars (at) cs.rwth-aachen.de