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
Theoretical Computer Science (FTP_TheoComp)
The aim of this module is to deepen some basic theoretical aspects of computer science. The master students will learn that ...
- formal languages and automata are essential concepts to describe different types of problems and computations;
- Computability/decidability are central to explain that for many problems seem to have an intuitive solution, although they can not be solved by algorithms;
- Complexity deals with the amount of time required to solve a problem, and there are many very practical problems that can not be solved in reasonable time or space.
Compétences préalables
Good knowledge of programming, algorithms and discrete mathematics.
Objectifs d'apprentissage
- The students understand that three different mathematical formalisms (finite state automata, regular grammars, regular expressions) are equivalent and define the set of regular languages. Finite state automata and regular expressions are widely used and will be explained using examples from lexical analysis, modeling of simple state-based systems, telecommunications protocols and program verification.
- The students realize that programming languages with regular languages can not be fully described. Context-free grammars, on the other hand, are suitable for developing all modern programming languages. Parsing is closely linked to the context-free languages. Using parser generators, students can explain top-down and bottom-up parsing.
- The students know that many problems are undecidable, i.e. that there are no algorithms to solve them, or rather that not everything is predictable. Such intuitively difficult to understand problems occur e.g. in the case of operating systems (deadlock problem), object-oriented programming languages (subtype decision) or program verification.
- The students understand that decidable problems are classified according to the resources needed to solve them (time or space) and know the major complexity classes (P, NP, EXP, PSPACE), their differences, and interrelationships (e.g., hierarchy).
- The students understand the concept of nondeterminism, which plays an essential role in the study of complexity. The complexity class NP (nondeterministic polynomial time) includes a subclass of very practical problems that are not solvable in reasonable time. Cryptology, machine vision, various optimization problems and many other areas are affected by such problems. Students can demonstrate that such problems are indeed unsolvable in reasonable time, and know some ways to circumvent this limitation through approximation techniques. Many problems known as NP-complete are presented and investigated.
Catégorie de module
Méthodes d'enseignement et d'apprentissage
- Frontal teaching
- Presentation and discussion of theoretical topics
- Discussion of practical examples to reduce the gap between theory and practice
- Exercises and self-study of selected topics
Bibliographie
Introduction to the Theory of Computation, Michael Sipser, Cengage Learning, 3rd International Edition, 2013.
Reference: www-math.mit.edu/~sipser/book.html (Homepage of author of the book)
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