Technische Universität Braunschweig
  • Study & Teaching
    • Beginning your Studies
      • Prospective Students
      • Degree Programmes
      • Application
      • Fit4TU
    • During your Studies
      • Freshmen-Hub
      • Term Dates
      • Information for Freshman
      • Practical Information
      • Additional Qualifications
      • Financing and Costs
      • Special Circumstances
      • Campus life
    • At the End of your Studies
      • Discontinuation and Credentials Certification
      • After graduation
      • Alumni
    • For Teaching Staff
      • Strategy, Offers and Information
      • Learning Management System Stud.IP
      • Team Teaching and Media Education
    • Contact
      • Student Advice Centre
      • Academic Advice Service
      • Admissions Office
  • Research
    • Research Profile
      • Core Research Areas
      • Clusters of Excellence
      • Research Projects
      • Research Centres
    • Early Stage Researchers
      • Promotion of early career scientists
      • PhD-Students
      • Postdocs
      • Junior research group leaders
      • Junior Professorship and Tenure-Track
      • Habilitation
      • Service Offers for Scientists
    • Research Data & Transparency
      • Transparency in Research
      • Research Data
      • Open Access Strategy
      • Digital Research Announcement
    • Research Funding
      • Research funding
    • Contact
      • Research Services
      • Academy for Graduates
  • International
    • International Students
      • Why Braunschweig?
      • Degree seeking students
      • Exchange Studies
      • Doctorate (PhD)
      • Refugee Students
      • Welcome Programme
      • TU Braunschweig Summer School
    • Scientists
      • Mobile Researchers at the TU Braunschweig
      • Research Services and European Office
    • Language and intercultural competence training
      • Learning German
      • Intercultural Communication
    • International Profile
      • Internationalisation
      • International Cooperation
    • International House
      • Information for first semester students
      • Contact
      • News and Events
      • Advisory Services
      • Location
      • About us
  • TU Braunschweig
    • Our Profile
      • Aims & Values
      • Regulations and Guidelines
      • Alliances & Partners
      • Facts & Figures
      • Our History
    • Career
      • Working at TU Braunschweig
      • Vacancies
    • Economy & Business
      • Knowledge and Technology Transfer
      • Entrepreneurship
    • General Public
      • Access to the University Library
    • Media Services
      • Communications and Press Service
      • Communications and Press Service
      • Film and photo permits
      • Advices for scientists
      • Topics and stories
    • Contact
      • General Contact
      • Getting here
  • Organisation
    • Presidency & Administration
      • Presidency
      • Designated Offices
      • Administration
      • Committees
    • Faculties
      • Carl-Friedrich-Gauß-Fakultät
      • Faculty of Life Sciences
      • Architecture, Civil Engineering and Environmental Sciences
      • Faculty of Mechanical Engineering
      • Fakultät für Elektrotechnik, Informationstechnik, Physik
      • Faculty of Humanities and Studies in Education
    • Institutes
      • Institutes from A to Z
    • Facilities
      • University Library
      • Gauß-IT-Zentrum
      • International House
      • Sports Centre
      • Facilities from A to Z
    • Equal Opportunity Office
      • Equal Opportunity Office
      • Family
      • Diversity for Students
  • Search
  • Quicklinks
    • People Search
    • Webmail
    • Campus map
    • CloudStorage
    • Messenger
    • Cafeteria
    • Courses
    • Stud.IP
    • Library Catalogue
    • IT Self-Service
    • Information Portal (employees)
    • Link Collection
    • DE
    • EN
    • IBR Twitter
    • IBR YouTube
    • Facebook
    • Twitter
    • Instagram
    • YouTube
    • LinkedIn
Menu
  • Technische Universität Braunschweig
  • Organisation
  • Faculties
  • Carl-Friedrich-Gauß-Fakultät
  • Institutes
  • Institute of Operating Systems and Computer Networks
Logo IBR
IBR Login
  • Institute of Operating Systems and Computer Networks
    • News
    • About us
      • Whole Team
      • Directions
      • Floor Plan
      • Projects
      • Publications
      • Software
      • News Archive
    • Connected and Mobile Systems
      • Team
      • Courses
      • Theses
      • Projects
      • Publications
      • Software
      • Datasets
    • Distributed Systems
      • Team
      • Courses
      • Theses
      • Projects
      • Publications
      • Software
    • Algorithms
      • Team
      • Courses
      • Theses
      • Projects
      • Publications
    • Microprocessor Lab
    • Education
      • Summer 2023
      • Winter 2022/2023
      • Summer 2022
      • Theses
    • Services
      • Library
      • Mailinglists
      • Webmail
      • Knowledge Base
      • Wiki
      • Account Management
    • Spin-Offs
      • Docoloc
      • AIPARK
      • Confidential Technologies
    • Research Cooperations
      • IST.hub

Algorithm Engineering

Semester
Summer 2022
Summer 2016Summer 2013Summer 2011Summer 2009
Module #INF-ALG-17
Event # INF-ALG-009 , INF-ALG-010
ProgrammesBusiness Information Systems Master, Computer Science Master, Computer and Communication Systems Engineering Master
IBR GroupALG (Prof. Fekete)
TypeLecture & Exercise
Lecturers
Photo
Dr. Phillip Keldenich
Wissenschaftlicher Mitarbeiter
keldenich[[at]]ibr.cs.tu-bs.de
+49 531 3913112
Room 318
Photo
Dr. Dominik Krupke
Wissenschaftlicher Mitarbeiter
krupke[[at]]ibr.cs.tu-bs.de
+49 531 3913116
Room 332
Credits5
Hours2+2
Time & Place

Lecture: Tuesday 11:30-13:00, SN19.3
Exercise: Monday 15:00-16:30, SN19.2
Wir gehen aktuell von Präsenzlehre aus.

Start

First lecture: 25.04.2022 (im Übungsslot)
First exercise class: 26.04.2022 (im Vorlesungsslot)

Prerequisites

Kenntnis von Algorithmen und Datenstrukturen sowie Programmierkenntnisse. Kenntnisse von C++ und Python sind grundsätzlich nützlich, müssen aber nicht unbedingt mitgebracht werden. Die Vorlesung kann ausdrücklich auch von fortgeschrittenen Bachelorstudenten besucht werden. Die Prüfung kann in diesem Fall sowohl als reguläre Bachelor-Prüfung (nach §4.11 der aktuellen BPO) als auch als vorgezogene Master-Prüfung abgelegt werden.

Certificates Während des Semesters werden Hausaufgabenblätter ausgegeben, die von den Teilnehmern bearbeitet werden müssen. Am Ende des Semesters gibt es eine mündliche Prüfung.

Anmeldung und Kommunikation

Wir verwenden auch für diesen Kurs eine Mailingliste. Über diese Liste versenden wir Material und Ankündigungen, beispielsweise wenn kurzfristig eine Veranstaltung ausfallen sollte. Wir bitten daher alle Teilnehmer und Interessenten, sich möglichst auf dieser Liste anzumelden.

Inhalt

Beim Algorithm Engineering geht es grob vereinfacht gesagt darum, Algorithmen aus der Theorie möglichst effizient und robust in die Praxis umzusetzen. Dabei kann es auch vorkommen, dass man Algorithmen entwirft oder modifiziert, damit sie sich besser in die Praxis umsetzen lassen. In diesem Kurs werdet Ihr folgendes lernen.

Allgemeine Patterns und Guidelines zum Entwickeln und Tunen von Algorithmen:

  • Nützliche Design Patterns und API-Design,
  • Reproduzierbarkeit und strukturierte Ausführung von Experimenten (z.B. mit slurm),
  • Profiling,
  • Datenanalyse mit Pandas, Seaborn und Jupyter Notebooks,
  • Nativen C++-Code in Python nutzen.

Effizienten Code in C++ schreiben und Performance-Pitfalls moderner Hardware vermeiden:

  • Effiziente Datenstrukturen,
  • Caching,
  • Branch Predicition, Data Dependencies und Pipelining.

NP-Schwere kombinatorische Probleme in vielen Fällen mit wenig (Python-)Code effizient lösen:

  • SAT-Solver,
  • Constraint Programming (ortools),
  • Mixed Integer Programming (Gurobi),
  • (Meta-)Heuristiken.

Es gibt inhaltliche Überlappungen mit dem Kurs Mathematische Methoden der Algorithmik und dem Algorithmik-Teamprojekt. Für diesen Kurs solltet Ihr euch grundsätzlich zutrauen, Codebeispielen in C++ und Python zu folgen, sowie ein Interesse am Entwickeln von Algorithmen und auch am Programmieren haben. Der Schwerpunkt der Vorlesung liegt auf dem dritten Teil zu NP-schweren Problemen.

Lernziele

Einführung

In dieser Vorlesung wird ein Überblick über das restliche Semester gegeben. Erst soll gelernt werden, dass aufgrund moderner CPU-Architekturen eine gute Implementierung einen großen Unterschied machen kann und Konstanten nicht zu vernachlässigen sind. Dann soll gelernt werden, dass dank SAT, LP/MIP und CP viele NP-schwere Probleme mittlerweile gut optimiert werden können. Ein Beispiel hier ist das TSP.

CPU Architektur

Moderne CPU-Architekturen sind sehr komplex geworden und weichen mittlerweile stark vom theoretischen Modell ab. Unterschiedliche Operationen, z.B. Addition vs. Division, können nicht nur unterschiedlich lange brauchen sondern selbst die gleichen Operationen können in unterschiedlichen Kontexten unterschiedliche performant sein da sie nicht strikt sequentiell ausgeführt werden (ILP, Branch Prediction, etc.). In dieser Vorlesung sollen die Studierenden lernen, warum Programme trotz gleicher Instruktionszahl (und minimalen Cache-Misses) stark abweichende Laufzeiten haben können und wie sie dies beeinflussen können.

Memory Hierarchy

Da schneller Speicher teuer und aufwendig ist, wird das Prinzip der Lokalität genutzt und auf unterschiedliche Speicherlevel bzw. Caches gesetzt. In dieser Vorlesung sollen die Studierenden lernen, wie der Speicher funktioniert und wie sie diesen am effizientesten Nutzen. Zusätzlich werden die wichtigsten Datenstrukturen betrachtet.

Parallelisierung

Aufgrund stagnierender CPU-Frequenzen wird immer mehr auf Parallelisierung gesetzt. Parallelisierung ist aber nicht einfach und mit einigen Problem und Overheads (insb. bei der Synchronisierung) verbunden. In dieser Vorlesung soll gelernt werden, wie Parallelisierung sinnvoll implementiert weren kann und was es dabei unbedingt zu vermeiden gilt.

Linear Programming

Linear Programming ist ein mächtiges Werkzeug in vielen Kontexten: Einige Optimierungsprobleme lassen sich direkt als LP ausdrücken. Andere Optimierungsprobleme haben eine hilfreiche Linear Relaxation. Lineare Programme können sowohl in der Theorie als auch in der Praxis effizient gelöst werden. Insbesondere lassen sich LPs iterativ lösen. In dieser Vorlesung sollen die Studierenden die Grundlagen des Linear Programmings (Grundlegende Formulierung, Algorithmen, Dualität, Cutting Planes,…) und deren Nutzen lernen. Zusätzlich soll der Gurobi-Log verstanden werden.

Mixed Integer Programming

Mixed Integer Programming ist eine Technik, mit der sich viele wichtige aber NP-schwere Optimierungsprobleme optimal oder zumindest gut lösen lassen. Die Technik nutzt die Lineare Relaxierung aus um mittels Branch and Bound und Cutting Planes zur optimalen Lösung zu gelangen. In dieser Vorlesung sollen die Studierenden die umfangreichen mathematischen Modellierungsmethoden (und deren Probleme) kennen lernen, um so effiziente Modelle für diverse Probleme erstellen zu können.

Traveling Salesman Problem

Am Beispiel vom TSP soll die Funktionsweise von Mixed Integer Programming Solvern tiefer verstanden werden. Ein Großteil der Techniken die Mixed Integer Programming Solver ausmachen, wurde vorher am Traveling Salesman Problem erprobt. Dies macht es zu einem exzellenten Beispiel um Branch and Bound (schon vorher behandelt) und insbesondere Cutting Planes (die hier recht anschaulich sind) tiefer zu verstehen. Hierbei gehen wir auch ein wenig auf die theoretischen Hintergründe ein.

SAT

Moderne SAT-Solver können regelmäßig Probleme mit hunderttausenden Variablen und millionen von Klauseln für reale Anwendungen lösen. In dieser Vorlesung gehen wir auf die hierfür genutzten Techniken ein, insbesondere dem Lernen von Konfliktklauseln. Im Anschluss sollten die Studierenden genug Kenntnisse haben, um einen mäßig effizienten SAT-Solver selber implementieren zu können.

Constraint Programming

Constraint Programming erlaubt es komplexe kombinatorische Probleme zu modellieren, leider waren die Solver aber lange Zeit lang nicht sehr konkurrenzfähig (insb. im Vergleich zu MIPs). Dies scheint sich jetzt insbesondere durch CP-SAT geändert zu haben. CP-SAT nutzt als Grundtechnik einen SAT-Solver mit Lazy Clause Generation, integriert aber u.A. auch den Simplex-Algorithmus. In dieser Vorlesung sollen die Studierenden die Grundideen von CP-SAT sowie dessen Anwendungsmöglichkeiten (insb. im Vergleich zu MIPs) erlernen.

Heuristiken

Nicht immer sind MIP/SAT/CP-Solver selber in der Lage, vernünftige Lösungen zu generieren. In diesen Fällen ist die Nutzung von Heuristiken sinnvoll. Diese können dann genutzt werden um selbständig Lösungen zu finden, oder etwa den MIP-Solver zu unterstützen. In der LNS kann der MIP/CP-Solver selbst auch genutzt werden, um mit wenig Aufwand, gute Heuristiken zu bauen. Zusätzlich werden sich noch weitere Ansätze wie Reinforcement Learning sowie Heuristiken angesehen. Im Anschluss sollten die Studierenden in der Lage sein, für die meisten (kombinatorischen) Probleme eine einfache, aber brauchbare Heuristik zu bauen.


last changed 2022-07-25, 17:41 by Dr. Phillip Keldenich

For All Visitors

Vacancies of TU Braunschweig
Career Service' Job Exchange 
Merchandising

For Students

Term Dates
Courses
Degree Programmes
Information for Freshman
TUCard

Internal Tools

Glossary (GER-EN)
Change your Personal Data

Contact

Technische Universität Braunschweig
Universitätsplatz 2
38106 Braunschweig

P. O. Box: 38092 Braunschweig
GERMANY

Phone: +49 (0) 531 391-0

Getting here

© Technische Universität Braunschweig
ImprintPrivacyAccessibility