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
Theoretische Informatik (FTP_TheoComp)

Ziel dieses Moduls ist die Vertiefung einiger grundlegenden theoretischen Aspekte der Informatik. Die Master-Studierenden werden lernen, dass…

  • formale Sprachen und Automaten wesentliche Konzepte sind, um verschiedene Problematypen und Berechnungen zu beschreiben;
  • Berechenbarkeit/Entscheidbarkeit zentral sind, um erklären zu können, dass es für viele Probleme eine intuitive Lösung zu geben scheint, obwohl sie nicht mittels Algorithmen gelöst werden können;
  • Komplexität sich mit dem zur Lösung eines Problems benötigten Aufwand an Platz oder Zeit befasst, und es zudem viele sehr praktische Probleme gibt, die mit einem vernünftigen Aufwand an Zeit oder Platz nicht gelöst werden können.

Eintrittskompetenzen

Gute Kenntnisse der Programmierung, Algorithmen und diskreten Mathematik.

Lernziele

  • Die Studierenden verstehen, dass drei unterschiedliche mathematische Formalismen (endliche Automaten, reguläre Grammatiken, reguläre Ausdrücke) gleichwertig sind und die Gruppe der regulären Sprachen definieren. Endliche Automaten und reguläre Ausdrücke sind weit verbreitet und werden anhand von Beispielen aus der lexikalischen Analyse, der Modellierung einfacher, zustandsbasierter Systeme sowie anhand von Telekommunikationsprotokollen und der Programm–verifikation erklärt.
  • Die Studierenden erkennen, dass Programmiersprachen mit regulären Sprachen nicht vollständig beschrieben werden können. Kontextfreie Grammatiken hingegen eignen sich, um alle modernen Programmiersprachen zu entwickeln. Parsing ist eng verknüpft mit den kontextfreien Sprachen. Anhand von Parser-Generatoren können die Studierenden Top-Down- und Bottom-Up-Parsing erklären.
  • Die Studierenden wissen, dass viele Probleme unentscheidbar sind, d.h. dass es keine Algorithmen gibt, um sie zu lösen, oder vielmehr, dass nicht alles berechenbar ist. Solche intuitiv schwer zu verstehenden Probleme treten z.B. bei Betriebssystemen (Deadlock-Problem), objektorientierten Programmiersprachen (Subtyp-Entscheid) oder der Programmverifikation auf.
  • Die Studierenden verstehen, dass entscheidbare Probleme gemäss den zur Lösung benötigten Ressourcen (Zeit oder Platz) klassifiziert werden und kennen die wichtigsten Komplexitätsklassen (P, NP, EXP, PSPACE), ihre Unterschiede und wechselseitigen Beziehungen (z.B. Hierarchie).
  • Die Studierenden verstehen das Konzept des Nichtdeterminismus, welches bei der Untersuchung von Komplexität eine wesentliche Rolle spielt. Die Komplexitätsklasse NP (nichtdeterministisch polynomiale Zeit) beinhaltet eine Unter-Klasse von sehr praktischen Problemen, die nicht in angemessener Zeit gelöst werden können. Kryptologie, maschinelles Sehen, verschiedene Optimierungsprobleme und viele andere Gebiete sind von solch Problemen betroffen. Die Studierenden können aufzeigen, dass solche Probleme, und kennen einige der Möglichkeiten, um diese Unlösbarkeit mittels Annäherungsverfahren zu umgehen. Viele als NP-vollständig bekannte Probleme werden vorgestellt und untersucht.

Modulkategorie

Das Modul gliedert sich in drei Teile:

  1. Sprachen und Automaten (ca. 36 %)
    1. Alphabete, Wörter, formale Sprachen, Grammatiken
    2. Endliche Automaten, reguläre Sprachen/Grammatiken, reguläre Ausdrücke, Nichtdeterminismus
    3. Kellerautomaten, kontextfreie Sprachen/Grammatiken
    4. Turingmaschinen
  2. Berechenbarkeit/Entscheidbarkeit (ca. 21 %)
    1. Verschiedene Berechnungsmodelle, Church-Turing-These
    2. Reduktion eines Problems auf ein anderes
    3. Entscheidbare/unentscheidbare Probleme
    4. Berechenbare/nicht berechenbare Funktionen
  3. Komplexität (ca. 43 %)
    1. Komplexitätsarten (Zeit, Platz)
    2. Komplexitätsklassen, Polynomialzeit-Komplexität, NP, Reduzierbarkeit der Polynomialzeit, NP-Vollständigkeit
    3. Annäherungsverfahren

Lehr- und Lernmethoden

  • Frontalunterricht
  • Präsentation und Diskussion theoretischer Fragestellungen
  • Diskussion praktischer Beispiele, um die Lücke zwischen Theorie und Praxis zu schliessen
  • Übungen und Selbststudium ausgewählter Themen

Bibliografie

Introduction to the Theory of Computation, Michael Sipser, Cengage Learning, 3rd International Edition, 2013.
Referenz: www-math.mit.edu/~sipser/book.html (Homepage des Autors zum Buch)

Computers Ltd.: What They Really Can't Do, David Harel, Oxford University Press, 2000.

Introduction to automata theory, languages, and computation, J.E. Hopcroft and J.D. Ullman, Addison-Wesley Publishing Company, Reading, MA, 1979.

Vollständige Modulbeschreibung herunterladen

Zurück