Department Mathematik
print


Navigationspfad


Inhaltsbereich

Forschungsgruppe TQA - Programm von Veranstaltungen in den vergangenen Semestern (*)

Sommersemester 2017

Seminar: "Kombinatorische Optimierung"

Di 12-14, B 251. Nr. 16066
Ausweichtermin: Di 16-18, B 134.

Inhalt: Im Seminar werden zwei Themengruppen angeboten. Die eine Gruppe besteht aus Themen zum Begriff der Berechenbarkeit und die andere Gruppe besteht aus ausgewählten Themen über geometrische Methoden zur Erzeugung von Optimierungsalgorithmen. Daneben werden eventuell noch Vorträge zur Ablaufplanung (Scheduling) vergeben. Details weiter unten.

Programm

  • 25.04.2017 Vorbesprechung und Planung
  • 02.05.2017 Berechenbarkeit nach Turing und mittels Registriermaschinen (Max Nowosad)
  • 09.05.2107 Rekursive und μ-rekursive Funktionen (Oliver Dörle)
  • 16.05.2017 Berechenbare Funktionen und λ-Kalkül (Leo Hansbauer)
  • 23.05.2017 Neuronale Netze und Berechenbarkeit (Edvard Hakobyan)
  • 30.05.2017 Simplexmethode (Eveline Heck)
  • 13.06.2017 Scheduling: Einmaschinenmodell (Marina Rist)
  • 20.06.2017 Algorithmen zu konvexen Mengen (Nha Nguyen)
  • 27.06.2017 Mehr Konvexität: Konvexe Optimierung (Rebecca Fiebiger)

  • 04.07.2017 Ellipsoid-Methode (Josef Kiesl)
  • 11.07.2017 Anwendungsbeispiel der konvexen Optimierung: Support Vector Machine (Natalia Voronova)
  • 11.07.2017 Das chinesische Postbotenproblem (Ga Ginng Ha)
  • 18.07.2017 Matching (Duc Tung Nguyen)

    Ohne Vortragenden:

  • ... Zelluläre Automaten und Berechenbarkeit (N.N.)

Berechenbarkeit: Es wird in diesem Teil des Seminars herausgearbeitet, dass die sehr unterschiedlichen Begriffsbildungen der Berechenbarkeit, wie sie zu Beginn des letzten Jahrhunderts eingeführt wurden, letztlich alle äquivalent sind. Das wird in dem Vorwort des Buches "Neural Networks" von Rojas als Überblick dargestellt und soll anhand der Bücher von Bridges, Hermes, Cutland, Cooper, Soare, u.a. im Seminar gründlich behandelt werden:
"Berechenbar ist eine vorgegebene Funktion f : N → N (von den natürlichen Zahlen in die natürlichen Zahlen), wenn es einen Algorithmus gibt, mit dem zu jeder Zahl n aus N der Funktionswert f(n) berechnet werden kann."
Diese Aussage gilt es zu präzisieren, um dann die Äquivalenz zur "Berechenbarkeit"

  1. nach Turing,
  2. mit Hilfe von Registermaschinen (URM oder RAM),
  3. um Sinne von Rekursivität,
  4. mit Hilfe des λ-Kalküls,
  5. mit Hilfe von zellulären Automaten,
  6. mit Hilfe von neuronalen Netzen
zu beweisen. Wir könnten auch zu Anwendungen kommen und einen Zusammenhang zur Komplexitätstheorie herstellen.

Geometrische Methoden: Ausgehend von der Simplexmethode werden Probleme zu konvexen Mengen und Lösungsalgorithmen dazu dargestellt, die zum Teil nicht direkt Optimierungen betreffen. Wir werden das Buch von Grötschel, Lovász und Schrijver verwenden und durch das Buch von Boyd und Vandenberghe ergänzen.

Das Seminar ist für Bachelor oder Master geeignet. Masterstudenten müssen einen zweiten Vortrag halten, den zweiten Vortrag möglicherweise zu einem anderen Zeitpunkt (Ausweichtermin).

Jeder Teilnehmer muss eine Basiswissen über Kombinatorische Optimierung haben. Dieses Basiswissen ist gegebenenfalls aus den Lehrbüchern vor Seminarbeginn zu erwerben. Zum Basiswissen gehört das Verständnis über die Grundaufgabe der Kombinatorischen Optimierung und dazu Kenntnis der Linearen Programmierung und der Komplexitätstheorie.

Weitere Geplante Themen (in den kommenden Semestern)

  • Quantenalgorithmen und Komplexität von Quantenalgorithmen
  • Fusionsalgebren als Werkzeug zum Bau eines Quantencomputers

Wintersemester 2016/17

Seminar: "Kombinatorische Optimierung" Di 12-14 in HS B 252.
Ausweichtermin: Di 16 - 18, HS B 040
Inhalt: Im Seminar werden zwei Themengruppen angeboten.
Die eine Gruppe besteht aus ausgewählten Themen zur Optimierung der Produktion und umfasst insbesondere die Ablaufplanung (Scheduling).
Die andere Gruppe hat zum Ziel, einen intelligenten 'Go-Bot' zu bauen.
Details in Themen und Anmeldung.

Schedule

  • 18.10.16 Vorbesprechung und Kurzvortrag durch Rami Daknama.
  • 25.10.16 Einmaschinenmodell (Henning Flechtner)
  • 08.11.16 Parallele Maschinen (Elisabeth Krahmer)
  • 15.11.16 Job Shops (Renée Thommes)
  • 22.11.16 Open Jobs (Patrick Hohmann)
  • 29.11.16 Grundlagen von Machine Learning und die Anwendung im Spiel Go (GoBot-Team)
    1. Regeln von Go und die Schwierigkeit, ein Go-Programm zu schreiben (Tobias Fritz)
    2. Das Perceptron und andere Neuronen (Melanie Michels)
    3. Aufbau eines neuronalen Netzes (Johannes Emmerig)
    4. Wie "lernt" das Netzwerk? (Tomy Kufner)
    5. Stochastic Gradient Descent (Alex Sedlmayr)
    6. Kurzer Überblick über unseren Stand, Ausblick auf Googles AlphaGo (Stefan Sedlmaier)
  • 06.12.16 Schnelle Rundreisen: Das Travelling-Salesman-Problem (Christian Schmid)
  • 13.12.16 12-14 Robust Scheduling (Verena Lorber)
  • 13.12.16 16-18 (B 040) Robust Scheduling zur Operationssaalbelegung (Jasmin Walther)
  • 20.12.16 Lernkurven (Maximilian Mayer)
    • Xmas
  • 10.01.17 12-14 Stochastic Local Search (Jan Gerrit Hölting)
  • 10.01.17 16-18 (B 040) Heuristische Algorithmen zur Ablaufplanung der PVC-Applikation (Murad Muradi)
  • 17.01.17 12-14 Vertriebssteuerung in einem Nachfrageoligopol mit extremem Angebotsüberschuss immaterieller Güter (Oliver Kostinek)
  • 17.01.17 16-18 (B 040) Flugplatznutzung (Melanie Bayerlein)
  • 24.01.17 2. Bericht (GoBot-Team)
    1. Optimierung eines neuralen Netzes (Alex Sedlmayr)
    2. Convolutional Neural Networks, Skizze
  • 31.01.17 Stochastiche Arbeitszeiten (Aaron Wittmann)
  • 07.02.17 12-14 3. Berichte / Resultate (GoBot-Team)
    1. Convolutional Neural Networks / Layer (Stefan Sedlmair)
    2. Trainingsdaten und GoBoard (Melanie Michels)
    3. Tensorflow Network und GitHub (Tobias Fritz)
  • 07.02.17 16-18 (B 040) 4. Berichte / Resultate (GoBot-Team) Themen im zweiten Vortag:
    1. Selbst programmiertes Netz (Johannes Emmerig)
    2. BotBattle (Tomy Kufner)

Sommersemester 2016

Seminar: "Kombinatorische Optimierung"; Di 12-14 in HS B 252.
Ausweichtermin: Di 16 - 18, HS B 251

Schedule

  • 12.04.16: Vorbesprechung
  • 19.04.16:
    1. Online Routing of Virtual Circuits with Applications to Load Balancing / Machine Scheduling (lisa Kraus)
    2. A Priori TSP (Rami Daknama)
    3. Erste Themen festlegen.
  • 26.04.16: Muss leider ausfallen.
  • 03.05.16: Packing Boxes (Lisa Kraus)
  • 10.05.16, 12 Uhr: Einstieg Scheduling (Ian Butler)
  • 10.05.16, 16 Uhr: Airline-Crew-Scheduling (Lisa Hertle)
  • 24.05.16, 12 Uhr: Monte Carlo Methode (Philipp Scheufele)
  • 24.05.16, 16 Uhr: Kürzeste Wege in Graphen (Dennis Pihale)
  • 31.05.16, 12 Uhr: Dynamische Programmierung (Minh Le)
  • 31.05.16, 16 Uhr: Zwei-Personen-Nullsummenspiel (Sabrina Richter)
  • 07.06.16, 12 Uhr: Komplexität von Scheduling-Problemen (Johannes Piller)
  • 07.06.16, 16 Uhr: TSP I (Simon Stadler)
  • 14.06.16, 12 Uhr: Nichtlineare Optimierung (Marie Düsedau)
  • 14.06.16, 16 Uhr: Heuristiken (Oliver Kiss)
  • 21.06.16, 12 Uhr: TSP II (Jakob Knauer)
  • 21.06.16, 16 Uhr: TSP III (Simon Stadler)
  • 28.06.16, 12 Uhr: Portfolio-Optimierung (Annie Wachsmuth)
  • 28.06.16, 16 Uhr: Künstliche Intelligenz I (Anton Sporrer)
  • 05.07.16, 12 Uhr: Künstliche Intelligenz II (Anton Sporrer)
  • 05.07.16, 16 Uhr: Scheduling (Matthias Englbrecht)
  • 12.07.16, 12 Uhr: Local Search (Michael Fuchs)

Wintersemester 2015/16

  • 13.10.15: Vorbereitungstreffen 1
  • 20.10.15: Vorbereitungstreffen 2
  • 27.10.15: Seminar findet nicht statt
  • 03.11.15: Seminar findet nicht statt
  • 10.11.15: Verirrt im Wald - Kurven minimaler Länge in der Ebene (Rami Daknama)
  • 17.11.15: offen für Besprechungen
  • 24.11.15: Quantum Algorithms for Optimization (Thomas Pischke)
  • 01.12.15: offen für Besprechungen
  • 08.12.15: Poker, eine spieltheoretische Analyse (Simon Stadler)
  • 12.01.16: Genetische Algorithmen zur Lösung kombinatorischer Optimierungsprobleme (Lulu Ji)
  • 19.01.16: Carsharing (Rami Daknama)
  • 26.01.16: Muss ausfallen
  • 02.02.16: Portfoliooptimierung mit CAPM (Elena Schumann)
  • ... : Packing Boxes (Lisa Kraus)

Sommersemester 2015

  • 14.04.15: Vorbereitungstreffen
  • 21.04.15: Neuronale Netze im Kontext kombinatorischer Optimierungsprobleme und eine Anwendung im Bereich der intelligenten Lagerhaltung (Rami Daknama)
  • 28.04.15: Kein Vortrag. Präzisierung der Themen in Einzelgesprächen
  • 05.05.15: Kein Vortrag. Präzisierung der Themen in Einzelgesprächen 12:15-13:00
  • 12.05.15: Noch einmal: Besprechung der Themen. 12:15-13:00
  • 19.05.15: Algorithm Runtime Prediction: From Knapsack to Scientific Simulations (Thomas Pischke)
  • 02.06.15: Ant Colony Optimization Algorithms (Lars Maurath)
  • 09.06.15: Lernen von "optimalen" Strategien beim Pokerspiel I (Robert Valta)
  • 16.06.15: Lernen von "optimalen" Strategien beim Pokerspiel II (Robert Valta)
  • 23.06.15: Particle Swarm Optimization (Leonid Kolesnikov)
  • 30.06.15: Keine Vortrag. Besprechung der Themen und Diskussion
  • 07.07.15: Mathematische Modellierung einer konkreten Produktion als Ausgangspunkt einer Optimierung (Daria Akulshyna)

Wintersemester 2014/15

  • 23.09.2014 The bin packing problem (Rami Daknama)
  • 24.02.2015 Runtime Prediction for the Knapsack Problem: Methods and Results (Thomas Pischke)

Sommersemester 2014

Workshop I zum Scheduling: Erarbeitung der Grundlagen und des Standes der Forschung in Kurzvorträgen und Diskussionen.
Workshop II zum maschinellen Lernen: Verfolgung des Video-Kurses "Machine Learning Program" von Ng.

Wintersemester 2013/14

  • 05.11.13: Neue Ansätze zum ganzzahligen Knapsack-Problem I (Lisa Kraus)
  • 26.11.13: TravellingSalesmanProblem - Anwendungspotentiale und Lösungsmethoden (Martin Schottenloher)
  • 03.12.13: Neue Ansätze zum ganzzahligen Knapsack-Problem II (Lisa Kraus)
  • 07.01.14: Neuronale Netze. Ein erster Zugang (Lukas Lentner)
  • 14.01.14: Bewertungsschemata für Heuristiken: Problemstellung, Approximation (Martin Schottenloher)
  • 28.01.14: Bewertungsschemata für Heuristiken: Approximationsschema, stochastsche Analyse, empirische Analyse (Martin Schottenloher)
  • 04.02.14: Ein Approximationsschema (FPTAS) zum Rucksack-Problem (Lisa Kraus)
  • 28.02.14: Adventures in Optimisation - How to solve computationally challenging problems better and faster (Holger H. Hoos)
  • 18.03.14: Aufspannende Bäume in Graphen (Susanne Moll)

Sommersemester 2013

  • 30.04.13: Vorbesprechung
  • 07.05.13: Strategien der kombinatorischen Optimierung (Christian Paleani)
  • 28.05.13: Gegenstand der kombinatorischen Optimierung (Robert Meißner)
  • 18.06.13: Evolutionäre Algorithmen - Genetische Programmierung (Lukas Lentner)
  • 02.07.13: Dynamische Programmierung (Lisa Kraus)
  • 09.07.13: Skyline-Routensuche unter verschieden gewichteten Optimierungskriterien (Sebastian Haug)
  • 16.07.13: Schwarmintelligenz (Christian Paleani)

Wintersemester 2012/13

  • 23.10.12: Auftakt: Problemstellung der Optimierung am konkreten Beispiel - Organisation und Übersicht des Workshops Martin Schottenloher
  • 30.10.12: Komplexität von Algorithmen Michael Klauser
  • 06.11.12: Lineare Programmierung: Konzept und Erste Schritte Christian Paleani
  • 20.11.12: Lineare Programmierung II: Simplexverfahren Christian Paleani
  • 27.11.12: Cutting Stock Problem Simon Lentner
  • 04.12.12: Einführung in die thermodynamische Zustandssummen und die klassische Monte-Carlo-Methode Lukas Lentner
  • 18.12.12: Quantenmechanische Zustandssumme, Operatorstrings und die Quanten-Monte-Carlo am Beispiel des 2-dim. Heisenberg-Modells Lukas Lentner
  • 15.01.13: Quanten Monte Carlo Simulation des unitären Fermigases Olga Goulko
  • 22.01.13: Quanten Monte Carlo Simulation des unitären Fermigases II Olga Goulko

Bis Mitte 2012

  • 29.05.2012: Bicategories for boundary conditions and for surface defects in 3-dimensional TFT. Christoph Schweigert, Universität Hamburg.
  • 02.11.2011:Thermodynamische Algorithmen auf Fusionsalgebren. Simon Lentner, 14 Uhr, B 251.
  • WS 2011/12 Seminar: Topologische Quantenfeldtheorie Martin Schottenloher, Mi 10-12, B 251.
  • 25.08.2011 Projekt SuperCut: Kombinatorische Optimierung zur Prozessoptimierung. Martin Schottenloher, Simon Lentner, 10 Uhr, B 251
  • 04.02.2011Neue Thermodynamische Ansätze zum Cutting Stock Problem. Simon Lentner, 14 Uhr, B 005.
(*) Die Forschungsruppe hat sich erst im Laufe des Jahres 2011 konstituiert.