L'unité d'enseignement « Récréations mathématico-informatiques » est une UE de niveau (100) initiation relevant de la licence d'informatique. Elle possède un volume de 6 ECTS et s'étend sur 12 semaines. Elle est placée sous la responsabilité de POUZET, marc.

Description

L'objectif de ce cours est de dégager quelques concepts mathématiques simples qui interviennent dans des exemples très concrets. Nous voulons sensibiliser les étudiants à l'intérêt de modéliser et formaliser les problèmes, pour pouvoir les résoudre en introduisant quelques méthodes mathématiques ou informatiques classiques. Ces méthodes sont seulement introduites dans ce cours et sont approfondies tout au long de la Licence et du Master. Ce cours ne nécessite pas de bagage mathématique particulier, autre que celui du lycée: suites récurrentes, opérations de base sur les ensembles, fonctions, etc. Cette unité d'enseignement s'adresse à tout étudiant de première année de licence, mais peut-être plus, à ceux qui éprouvent une certaine appréhension des mathématiques. Elle s'adresse également aux étudiants d'autres disciplines qui souhaitent avoir une introduction à quelques thèmes classiques de l'informatique (e.g. logique, complexité du calcul, automates, décidabilité). L'apprentissage à la rigueur sera faite par une étude complète des concepts les plus simples (e.g. calcul booléen).

Il s'agit, en partant de problèmes très concrets, de montrer des exemples d'utilisation de résultats mathématiques dans le cadre de l'informatique. Les résultats mathématiques visés portent sur les ordres et relations, l'algèbre, la logique (et ses paradoxes), le principe de récurrence, etc. L'idée est de présenter quelques concepts mathématiques élémentaires en montrant comment ils permettent de répondre au cas concret étudié. Cette étude donnera lieu à une implantation, visant à faciliter l'appropriation des concepts étudiés.

Nous proposons de bâtir ce cours sur trois ou quatre exemples concrets, chacun d'entre eux étant traité sur trois ou quatre semaines.

Dans tout le cours, nous ferons largement appel au principe de récurrence sur les entiers pour spécifier ou prouver des propriétés attendues.

Préalables et buts pédagogiques

Bibliographie

• Hopcroft & Ulman. Introduction to Automata Theory, Languages and Computation. Addison Wesley.

• Delmas et R. Lalement. La logique ou l'art de raisonner. Editions du Pommier

• Graham, Knuth & Patashnik. Concrete Mathematics. Fondations for computer science. Addison Wesley.

Contenu indicatif par semaine

1. Calcul booléen. Exemples concrets (e.g. circuits booléens).

2. Concepts mathématiques: fonctions booléennes, tables de vérité, simplification, représentations.

3. Calcul séquentiel. Exemple concret (e.g. programmation d'un robot Lego, modélisation d'un ascenseur, d'une machine à café, d'un système de gestion des feux de croisement, d'un contrôleur d'aiguillage de trains).

4. Concepts mathématiques (I): Automates finis, automates de Mealy/Moore, état accessible, état bloqué.

5. Concepts mathématiques (II): Equivalence d'automates, suites récurrentes et fonctions de suites.

6. Les ensembles. Exemple concret (e.g. modélisation d'un problème de gestion d'annuaire).

7. Concepts mathématiques: ensemble, cardinalité, produit d'ensembles, union disjointe, relation, relation d'ordre, équivalence, injection, bijection, ensemble ordonné. Ensembles définis inductivement.

8. Compter/dénombrer. Exemple concret (e.g. fable des grains de riz sur un échiquier, croissance des lapins). Introduction aux problèmes de complexité (fonctions à croissance constante vs quadratique vs exponentielle).

9. Qu'est ce qu'une propriété logique? Exemple concret (e.g. modélisation d'un système de gestion d'annuaire, de gestions des feux de croisement, d'un système d'aiguillage de trains).

10. Concepts mathématiques (I): formule logique, tautologie, syllogismes, paradoxes, invariant, preuve.

11. Concepts mathématiques (II): propriété sur les ensembles, preuves par récurrence.

    Récurrence et récursivité. Exemples concrets (e.g. fractales, systèmes de Lindenmayer).

12. Concepts mathématiques: intérêt d'une description récurrente d'un problème, preuve par récurrence, sensibiliser les étudiants aux problèmes de terminaison.