UE Mathématiques pour l'informatique / Mathematics for informatics

Le but de l'enseignement de MATHÉMATIQUES DISCRÈTES  est l'approfondissement de plusieurs notions fondamentales de mathématiques, accompagné d'un aperçu de leur utilisation en informatique. Ce cours est conçu comme une introduction aux études de INFO : on y étudie un petit nombre de concepts-clés (notions d'algorithme, de langage, de codage,...) qui sous-tendent l'étude des outils informatiques vue dans d'autres cours.

- Les ensembles et leurs partitions sont illustrés par des exemples portant sur les mots et les langages.  
- Les fonctions et leurs images réciproques fournissent un point de vue unifié sur les problèmes de codage : encodage binaire, compression, cryptographie, codes correcteurs.
- Les relations d'équivalence et la notion de passage au quotient permettent d'appréhender des questions fondamentales de sémantique des langages de programmation.

1. Ensembles et partitions. Mots et langages. 
2. Fonctions et images réciproques. Quelques problèmes de codage.
3. Relations d'équivalence et passage au quotient. Notions de sémantique.

The aim of the Discrete Mathematics course is to explore several fundamental notions from mathematics and see how they apply to computer science. This course is devised as an introduction to the contents of the INFO curriculum: we study a small set of key concepts (the notions of algorithm, language, coding...) codage,...) that underly many of the tools specific to computer science and studied in other courses.

- Sets and their partitions are illustrated with examples about words and languages.
- Functions and their inverse images yield a unified point of view over coding problems: binary encoding, compression, cryptography, error correction.
- Equivalence relations and quotients give a general framework for studying the issues of semantics in programming languages.

1. Sets and partitions. Words and langages.
2. Functions and inverse images. Some coding theory.
3. Equivalence relations and quotients. Some semantic issues.

Voir la page complète

L'enseignement "AUTOMATES et GRAMMAIRES" comporte 4 volets :

- La présentation de résultats fondamentaux de l'informatique : une technique de preuve de correction de programmes, différents modèles de calculs (séquentiel, parallèle, non-déterministe), la réalisation en un temps fini d'opérations sur des données infinies (les langages représentés sous forme d'automates), la récursivité

- L'illustration des ces notions dans le cas des automates et des grammaires

- Un exemple concret d'utilisation récente des automates : vérification de drivers, protocoles médicaux, personnage autonome dans les jeux vidéo, ...

- Un exemple concret d'utilisation des grammaires attribuées

- La présentation d'un résultat surprenant : les automates d'arbres, l'ordinateur quantique, les limites de l'informatique, ...

1. Preuve de correction partielle de programmes par la technique de Floyd-Hoare-Dijkstra : comment être sûr que un programme fait bien ce qu'on attend. Autrement dit, monterez-vous dans l'avion dont vous avez programmé le pilote automatique ?

2. Automates (à  nombres d'états finis/à  pile, déterministes/non-déterministes) : quel est le modèle de calcul d'un processeur ? y'a t'il des langages (des modèles) plus puissants que d'autres ?

3. Représentations équivalentes (des grammaires régulières aux équations d'Arden aux expressions régulières et finalement jusqu'aux automates à  états finis) : comment passent-on d'une description lisible à  une version utilisable par un processeur ?

4. Application et implantation des automates : les automates sont utilisés pour programmer (des analyseurs lexicaux, des micro-contrôleurs, des interfaces, des protocoles, des jeux,...), pour piloter (des chaines de production, des systèmes cyber-physiques,...) et pour vérifier (des drivers, des politiques de sécurité ...) en fait on en trouve un peu partout.

5. Grammaires attribuées et génératives : les grammaires sont le quotidien des informaticiens qui ne cessent de traduire un langage ou des données d'un format vers un autre.

6. Application : implantation en ANTLR ou JavaCC d'un interpréteur d'expressions booléennes

The course "AUTOMATES and GRAMMARIES" has 4 components:

  1. The presentation of fundamental results of computer science: a technique of correctness proof of programs, different computation models  (sequential, parallel, non-deterministic), the computation in finite time of operations on infinite data (the languages represented as automata), recursion

  2. The illustration of these notions in the case of automata and grammars

  3. A concrete example of recent use of automata: verification of drivers, medical protocols, autonomous character in video games, ...

4. A concrete example of the use of attributed grammars

5. The presentation of a surprising result: tree automatons, the quantum computer, the limits of computing, ...



TARGETED SKILLS:

- know how to prove that a program is correct
- know how to program using an automaton
- know how to write a simple analyzer / translator

1. Proof of partial program correctness by the Floyd-Hoare-Dijkstra technique: how to be sure that a program is doing what is expected. In other words, will you get on the plane which runs an autopilot you programmed?

2. Automata (with finite state / stack numbers, deterministic / non-deterministic): what is the computation model of a processor? are there languages ?more powerful than others?

3. Equivalent representations (from Regular Grammars to Arden's Equations then to Regular Expressions and finally to Finite State Automata): how do we go from a readable description to a version usable by a processor?

4. Application and implementation of Automata (ie. Programmable Logic Controller): PLC are used to program (lexical analyzers, micro-controllers, interfaces, protocols, games, ...), to control (production chains, physical, ...) and to check (drivers, security policies ...) in fact we find them everywhere.

5. Attributed and Generative Grammars: Grammars are the everyday tool of developpers who translate language or data from one format to another.

6. Application: implementation in ANTLR or JavaCC of an interpreter of Boolean expressions

Voir la page complète