MSE Master of Science in Engineering

The Swiss engineering master's degree

Jedes Modul umfasst 3 ECTS. Sie wählen insgesamt 10 Module/30 ECTS in den folgenden Modulkategorien:

  • ​​​​12-15 ECTS in Technisch-wissenschaftlichen Modulen (TSM)
    TSM-Module vermitteln Ihnen profilspezifische Fachkompetenz und ergänzen die dezentralen Vertiefungsmodule.
  • 9-12 ECTS in Erweiterten theoretischen Grundlagen (FTP)
    FTP-Module behandeln theoretische Grundlagen wie die höhere Mathematik, Physik, Informationstheorie, Chemie usw. Sie erweitern Ihre abstrakte, wissenschaftliche Tiefe und tragen dazu bei, den für die Innovation wichtigen Bogen zwischen Abstraktion und Anwendung spannen zu können.
  • 6-9 ECTS in Kontextmodulen (CM)
    CM-Module vermitteln Ihnen Zusatzkompetenzen aus Bereichen wie Technologiemanagement, Betriebswirtschaft, Kommunikation, Projektmanagement, Patentrecht, Vertragsrecht usw.

In der Modulbeschreibung (siehe: Herunterladen der vollständigen Modulbeschreibung) finden Sie die kompletten Sprachangaben je Modul, unterteilt in die folgenden Kategorien:

  • Unterricht
  • Dokumentation
  • Prüfung
Approximation Algorithms (FTP_ApprAlg)

An algorithm is typically called efficient if its worst-case running time is polynomial in the size of the input. This course will focus on a huge and practically relevant family of problems, namely NP-hard ones, for which (most likely) no efficient algorithm exists. This family includes fundamental problems in computational biology, network design, systems, computer vision, data mining, online markets, etc.

The first goal of this course it to learn how to identify NP-hard problems.

For a given NP-hard optimization problem it might still be possible to compute efficiently a feasible solution whose cost is (in the worst-case) within a small multiplicative factor (approximation factor) from the optimum: this is the aim of approximation algorithms. The second goal of this course is to learn how to design accurate approximation algorithms, and how to (theoretically) bound their approximation factor.

Eintrittskompetenzen

Basics of theoretical analysis of algorithms.

Lernziele

The main goal of this course is to learn how to identify NP-hard problems, and how to design and (theoretically) analyze approximation algorithms for fundamental NP-hard optimization problems.

Modulinhalt

A. Complexity Classes: polynomial Reductions; NP-completeness and NP-hardness.

B. NP-hard problems: SAT and Max-SAT; Vertex/Set Cover; Steiner Tree and generalizations; TSP; Max Cut; Knapsack and Bin Packing; k-Center and clustering; Scheduling; Facility Location; Item Pricing; etc.

C. Approximation Algorithms:

  1. Basic notions: approximation factor; hardness of approximation.
  2. Basic techniques: greedy; local search; randomization; dynamic programming.

LP-based techniques: randomized rounding; primal-dual; iterative rounding.

Lehr- und Lernmethoden

Interactive lectures both for theory and exercises.

Bibliografie

- V. V. Vazirani. Approximation Algorithms. Springer.

- D. P. Williamson, D. B. Shmoys. The Design of Approximation Algorithms. Cambridge University Press.

Vollständige Modulbeschreibung herunterladen

Zurück