Master d'Informatique (les annexes) - Présentation

CAMPAGNE D'HABILITATION
2008


Master D'Informatique





ANNEXES Spéc. IF

A renseigner obligatoirement (1 dossier par annexe)



ANNEXE 1

Fournir le programme pédagogique pour chacune des Unités d'Enseignement, en
précisant à chaque fois les éléments constitutifs et les intervenants

Nom UE : Systèmes dynamiques discrets
Intervenant : Enrico Formenti
Structure : 21 CM, 21 TD (parcours IF) - 12 CM, 9 TD (parcours PENSUNS)
Objectifs : comprendre les éléments essentiels et l'utilité de la
modélisation par systèmes dynamiques discrets
Programme :
1. Phénomènes réels et modèles
2. Points périodiques et stabilité
3. Familles des systèmes dynamiques
4. Systèmes linéaires
5. La fonction logistique
6. Questions de décidabilité
7. Applications pratiques

Les volumes et le contenu précis de chaque chapitre seront modulés en
fonction deux parcours.

Bibliographie :
. A First Course in Discrete Dynamical Systems, Richard A. Holmgren -
Mathematics - 1996.
. Discrete Dynamical SystemsTheory and Applications, James T. Sandefur -
Mathematics - 1990.
. Discrete Dynamical Modeling, James T. Sandefur - Mathematics - 1993.

o-O-o

Nom UE : Logique
Intervenant : Emmanuel Kounalis
Structure : 21 CM, 21 TD

Objectif : Ce cours présente d'abord formellement les bases de la Logique
classique qui est fondée sur l'opposition du vrai et du faux. Ensuite, on
montre comment elle sert la vie quotidienne, la mathématique et
l'informatique.

Programme :

Unité1 : Formaliser : des objets aux énoncés
Unité2 : Interpréter : des énoncés aux objets
Unité3 : Prouver : des énoncés aux énoncés
Unité4 : Appliquer : Mathématiques, Vie Athénienne, Informatique.


Bibliographie :


1. 1. Y. Delmas-Rigoutsos et R. Lalement : La logique ou l'art de
raisonner, à quate Quatre, Editions Le pommier. 2009
2. A.Aho et J.Ullman, Concepts fondamentaux de l'informatique, Dunod,
1993.

o-O-o

Nom UE : Optimisation combinatoire
Intervenant : Bruno Beauquier
Structure : 18 CM, 24 TD

Objectifs :

L'Optimisation Combinatoire est une branche de l'optimisation en
Mathématiques Appliquées et en Informatique, également liée à
l'Algorithmique, la Théorie de la Complexité et la Recherche
Opérationnelle.

Un problème d'Optimisation Combinatoire consiste à trouver une solution
optimale, selon une fonction objectif, dans un ensemble discret de
solutions réalisables. En général, cet ensemble est fini mais compte un
très grand nombre d'éléments, et il est décrit de manière implicite, c'est-
à-dire par une liste de contraintes que doivent satisfaire les solutions
réalisables.

L'enseignement proposé aborde la plupart des problèmes classiques en
Optimisation Combinatoire et se situe au carrefour de la Théorie des
Graphes, de l'Informatique Théorique et de la Programmation Mathématique.
Ses objectifs principaux sont :

- l'étude de méthodes exactes, à base d'algorithmes de graphes et de
programmation mathématique;
- l'application de ces méthodes sur les problèmes classiquement rencontrés
;
- la modélisation et la résolution de problèmes combinatoires concrets.

Programme :

- Théorie des graphes : graphes orientés et non-orientés, voisinages et
degrés, chemins et diamètre, arbres, graphes bipartis, graphes Eulériens
;
- Connexité : parcours d'un graphe, calcul des composantes connexes, k-
connexité et théorèmes de Menger, caractérisations de certaines
connexités ;
- Couplages : chemins augmentants, couplages parfaits, couplages dans les
graphes bipartis, couvertures (dualité), couplages de poids maximal,
couvertures en chemins ;
- Réseaux de flot : réseaux de capacités et flots simples, problème du flot
maximal, coupes, théorème min-max, algorithmes de poussée, applications
aux problèmes de connexité et de couplage ;
- Coloration : nombre et indice chromatique, bornes inférieures et
supérieures, coloration des graphes planaires ;
- Programmation linéaire : programmes linéaires, algorithme du simplexe,
dictionnaires, théorème fondamental.

Bibliographie :

1. "Graph Theory", par Reinhard Diestel, Springer-Verlag, Graduate Texts
in Mathematics, Volume 173, 2005, 431 pages, ISBN 3-540-26182-6 ou 3-540-
26183-4.
2. "Combinatorial Optimization", par W.J. Cook, W.H. Cunningham, W.R.
Pulleyblank, et A. Schrijver, John Wiley and Sons, 1998, 355 pages,
ISBN 0-471-55894-X.

o-O-o

Nom UE : Sémantique des langages de programmation
Intervenant : Yves Bertot.
Structure : 14 CM, 14 TD, 14 TP
Objectifs :
Le but de ce cours est d'apprendre démontrer la correction d'outils de
manipulation de programmes.
Trois outils sont visés: un outil de génération de conditions, un outil
d'analyse statique, et un interprète. L'ensemble est décrit de manière à
permettre une vérification par ordinateur et la génération automatique des
outils à partir des spécifications et des preuves.

Unité 1 : description du langage de programmation, sémantique naturelle
+sémantique à petit pas

Unité 2 : preuves par récurrence sur les dérivations, exemple sur
l'équivalence entre sémantique naturelle et la sémantique à petits pas

Unité 3 : introduction orale à Coq, description en Coq des spécifications
sémantiques, techniques de raison-nement par récurrence et inversion,
encodage de la preuve d'équivalence.

Unité 4 : démonstration sur machine en Coq: preuve de correction d'une
transformation de programmes
Unité 5 : introduction à la sémantique axiomatique, preuve de correction de
la sémantique axiomatique (oralement en Coq).
Unité 6 : preuve de correction d'un générateur de conditions de
vérification (décrit en Coq).
Unité 7 : introduction à l'interprétation abstraite: cas des intervalles
(description de la preuve de correction)
Unité 8 : description formelle d'un interprète concret et vérification de
sa correction vis-à-vis de la séman-tique naturelle.


Bibliographie :
1. The Formal Semantics of Programming Languages, Glyn Winskel, The MIT
Press, 1993.
2. Des notes de cours personnelles seront distribués en cours.

o-O-o

Nom UE : Introduction aux Bases de données décisionnelles
Intervenant : Martine Collard
Structure : 9h CM, 4,5h TD, TP 7,5h
Objectifs :
Présenter les principes et les méthodes spécifiques du domaine des bases de
données décisionnelles, et en particulier l'entreposage de données ou
"Datawarehousing"' et la fouille de données encore appelé "Extraction
automatique de connaissances à partir de données" ou "Data Mining" pour les
anglo-saxons.
Un entrepôt de données, ou "datawarehouse", permet, d'unifier les données
de production issues de sources hétérogènes de manière à les rendre
exploitables par une analyse décisionnelle.
La fouille de données est focalisée sur les données précédemment stockées
par des processus divers, éventuellement dans un entrepôt ; ces données
sont réutilisées pour exploration par des techniques d'analyse qui
permettent de mettre à jour et restituer des connaissances sur des
phénomènes inconnus ou oubliés. Au travers des multiples tentatives pour
caractériser ce domaine, on peut retenir quatre objectifs fondamentaux qui
justifient la métaphore de l'extraction et de la transformation de mineral
:
- fouiller, creuser, extraire ce qui est caché
- prendre en compte le volume de données
- transformer des données brutes en connaissances expertes
- fournir des connaissances précieuses car nouvelles, valides et utiles à
un utilisateur expert

Cet enseignement est organisé en cours magistraux et séances de TD et TP.
Nous présentons, dans les cours magistraux, les principes de modélisation
et d'utilisation d'un entrepôt de données et les algorithmes et méthodes
d'extraction les plus standard dans le domaine de la fouille de données.
Les séances de TD permettent de comprendre le fonctionnement des
algorithmes en les appliquant à des jeux de données simples et peu
volumineux. Lors des séances de TP, différents outils implémentant les
méthodes présentées en cours et TD sont mis en ?uvre dans le cadre du
logiciel Weka (http://www.cs.waikato.ac.nz/~ml/weka/).

Programme :

1. Panorama des systèmes décisionnels
- Problématiques
- Déroulement d'une étude de data mining
- Méthodologie CRISP-DM
- Types d'application
- Aperçu des techniques
2. Entrepôts de données
- Modélisation multidimensionnelle
- Niveaux d'abstraction : Conceptuel, Logique, Physique
- Algèbre de manipulation multidimensionnelle
3. Exploration et Préparation des données
- Détection et traitement des valeurs manquantes
- Détection et traitement des valeurs erronées
- Détection des dépendances entre variables
- Transformation des variables
- Discrétisation
4. Méthodes de classification non supervisée
- Définition, Calcul de distance, Problème des variables continues
- Evaluation de la qualité de la classification
- Interprétation des classes obtenues
- Méthodes par partitionnement - Exemple des K-Moyennes
- Méthodes hiérarchiques ascendantes et descendantes
- Méthodes mixtes
- Exemples
5. Techniques de recherche d'associations
- Principes,
- Algorithme fondateur Apriori et optimisations
- Exemples
6. Méthodes de classement et de modélisation prédictive
- Ensemble d'apprentissage et de test, taux d'erreur, sur-apprentissage

- Techniques de classement par arbres de décision
- Techniques de classement par réseaux bayésie