Outils théoriques pour l’informatique

Description

Objectifs

A la fin de ce module, l'étudiant devra avoir compris et pourra expliquer (principaux concepts) :

- Complexité des algorithmes et des problèmes
- Expressions régulières
- Programmation linéaire
- Théorie de l¿information avec ses applications en compression de données, codes correcteurs et cryptographie

L'étudiant sera capable :

- D'évaluer la complexité asymptotique d'un algorithme, de reconnaître et d'expliquer certaines techniques algorithmiques (diviser pour régner, programmation dynamique, algorithmes gloutons), et d'identifier la classe de complexité d'un problème
- De reconnaître un problème résoluble grâce aux expressions régulières, de choisir l'outil approprié, et d'appliquer la solution rapidement.
- D'utiliser les bases de la théorie de l¿information dans le cadre de la compression de données, des codes correcteurs et de la cryptographie
- De modéliser des problèmes sous forme de programmes linéaires et de les résoudre via l'algorithme du simplexe

Pré-requis

Mathématiques de base (algèbre linéaire, probabilités, arithmétique modulaire)

Algorithmique, représentation de l'information, structures de données, Shell Unix

Évaluation

L’évaluation des acquis d’apprentissage est réalisée en continu tout le long du semestre. En fonction des enseignements, elle peut prendre différentes formes : examen écrit, oral, compte-rendu, rapport écrit, évaluation par les pairs…