MSE Master of Science in Engineering

The Swiss engineering master's degree


Chaque module vaut 3 ECTS. Vous sélectionnez 10 modules/30 ECTS parmi les catégories suivantes:

  • 12-15 crédits ECTS en Modules technico-scientifiques (TSM)
    Les modules TSM vous transmettent une compétence technique spécifique à votre orientation et complètent les modules de spécialisation décentralisés.
  • 9-12 crédits ECTS en Bases théoriques élargies (FTP)
    Les modules FTP traitent de bases théoriques telles que les mathématiques élevées, la physique, la théorie de l’information, la chimie, etc., vous permettant d’étendre votre profondeur scientifique abstraite et de contribuer à créer le lien important entre l’abstraction et l’application dans le domaine de l’innovation.
  • 6-9 crédits ECTS en Modules contextuels (CM)
    Les modules CM vous transmettent des compétences supplémentaires dans des domaines tels que la gestion des technologies, la gestion d’entreprise, la communication, la gestion de projets, le droit des brevets et des contrats, etc.

Le descriptif de module (download pdf) contient le détail des langues pour chaque module selon les catégories suivantes:

  • leçons
  • documentation
  • examen 
Informatique théorique (FTP_TheoComp)

Le but de ce module est d’approfondir certains aspects théoriques de base de l’informatique. Les étudiants de maîtrise apprendront que ...

  • les langages formels et les automates sont des concepts essentiels pour décrire différents types de problèmes et de calculs;
  • La calculabilité/décidabilité est essentielle pour expliquer que, pour de nombreux problèmes, il semble exister une solution intuitive, bien qu'ils ne puissent pas être résolus par des algorithmes;
  • La complexité concerne le temps nécessaire pour résoudre un problème,  il existe de nombreux problèmes très important dans la pratique qui ne peuvent pas être résolus en un temps ou un espace raisonnable.

Compétences préalables

Bonnes connaissances de la programmation, des algorithmes et des mathématiques discrètes.

Objectifs d'apprentissage

  • Les étudiants comprennent que les trois formalismes mathématiques différents (automates finis, grammaires régulières, expressions régulières) sont équivalents et définissent l'ensemble des langages réguliers. Les automates à états finis et les expressions régulières sont largement utilisés et seront expliqués à l'aide d'exemples tirés d'analyse lexicale, de la modélisation de systèmes simples à base d'états, de protocoles de télécommunication et de vérification de programmes.
  • Les étudiants réalisent que les langages de programmation  ne peuvent pas être complètement décrits à l'aide de langages réguliers. Les grammaires hors contexte, quant à elles, conviennent au développement de tous les langages de programmation modernes. L'analyse syntaxique est étroitement liée aux langages hors-contexte. À l'aide de générateurs d'analyseurs syntaxiques, les élèves saisissent ce qu'est l'analyse syntaxique descendante et ascendante.
  • Les étudiants réalisent que de nombreux problèmes sont indécidables, c'est-à-dire qu'il n'y a pas d'algorithmes pour les résoudre, ou plutôt que tout n'est pas prévisible. De tels problèmes intuitivement difficiles à comprendre se produisent, par exemple. dans les systèmes d'exploitation (problème d'interblocage), les langages de programmation orientés objet (décision de la relation de sous-typage) ou de vérification de programmes.
  • Les étudiants comprennent que les problèmes décidables sont classés en fonction des ressources nécessaires pour les résoudre (temps ou espace) et connaissent les principales classes de complexité (P, NP, EXP, PSPACE), leurs différences et leurs interrelations (hiérarchie, par exemple).
  • Les étudiants comprennent le concept de non-déterminisme qui joue un rôle essentiel dans l’étude de la complexité. La classe de complexité NP (temps polynomial non déterministe) comprend une sous-classe de problèmes très importants dans la pratique qui ne peuvent pas être résolus en temps raisonnable. La cryptologie, la vision par ordinateur, divers problèmes d'optimisation et de nombreux autres domaines sont concernés par ces problèmes. Les étudiants peuvent démontrer que de tels problèmes sont effectivement insolubles en temps raisonnable et connaissent certains des moyens de contourner cette limitation au moyen de techniques d'approximation. De nombreux problèmes connus, dits NP-complets, sont présentés et étudiés.

Catégorie de module

Le module est divisé en trois parites:

  1. Langages et automates (environ 36 %)
    1. Alphabets, mots, langages formels, grammaires
    2. Automates à états finis, langages réguliers,  grammaires/expressions régulières, non déterminisme
    3. Automates à pile, langages/grammaires hors-contexte
    4. Machine de Turing
  2. Calulabitité/décidabilité (environ 21 %)
    1. Divers modèles de calculabilité, thèse de Church-Turing
    2. Réduction d'un problème à un autre
    3. Problèmes décidables/indécidables
    4. Fonctions calculables/non calculables
  3. Complexité (environ 43 %)
    1. Types de complexité (temps, espace)
    2. Classes de complexité, classes de complexité en temps polynomial, NP, Réduction en temps polynomial, NP-complétude
    3. Méthode d'approximation

Méthodes d'enseignement et d'apprentissage

  • Enseignement frontal
  • Présentation et discussion de sujets théoriques
  • Discussion sur des exemples pratiques pour combler le fossé entre la théorie et la pratique
  • Exercices et auto-apprentissage de sujets choisis

Bibliographie

Introduction to the Theory of Computation, Michael Sipser, Cengage Learning, 3rd International Edition, 2013.
Reference: www-math.mit.edu/~sipser/book.html (Homepage de l'auteur du livre)

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.

Télécharger le descriptif complet

Retour