3. Attribution des crédits - Département Informatique

Le cours sera complété pas des TD-papiers de préparation à l'examen écrit et des TD sur machine permettant de prendre .... Imagerie du tenseur de diffusion. 7 .


un extrait du document



systèmes dynamiques discrets
Programme :
Phénomènes réels et modèles
Points périodiques et stabilité
Familles des systèmes dynamiques
Systèmes linéaires
La fonction logistique
Questions de décidabilité
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. Y. Delmas-Rigoutsos et R. Lalement : La logique ou l’art de raisonner, à quate Quatre, Editions Le pommier. 2009
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.
"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 :
The Formal Semantics of Programming Languages, Glyn Winskel, The MIT Press, 1993.
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 Suvre 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ésiens
" Aperçu des autres techniques
" Exemples
7. Facteurs de succès d'un processus de Data Mining


Bibliographie :

Gilbert Saporta, Data mining et statistique décisionnelle, Éditions Technip,.2005.
Ian Witten and Eibe Frank, Data Mining, Practical Machine Learning Tools and Techniques, 2nd edition, Morgan Kaufman, 2005.
Michael Berry & Gordon Linoff, Data Mining Techniques: For Marketing, Sales, and Customer Relationship Management, 2nd edition, InterEditions, 2004
Jiawei Han, Micheline Kamber, Data Mining : Concepts and Techniques, Morgan Kaufmann, David T. Connolly & C. Begg, Systèmes de bases de données, Eyrolles, 2005.
Hand, Heikki Mannila, Padhraic Smith, Principles of Data Mining, MIT Press,
L. Hobbs & al., Oracle 10g Data Warehousing. Elseiver, 2005
R.Kimball & M. Ross, Entrepôts de données – guide de modélisation multi-dimensionnelle, 2ème ed. Wiley, 2003.

o-O-o

Nom UE : Systèmes
Intervenant : Fabrice Huet
Structure : 9 CM, 12 TP
Objectifs:
Étudier les systèmes d'exploitation à travers les services qu'ils proposent
Détailler les structures de données et algorithmes utilisés dans l'implémentation de certains de leurs mécanismes
Programme:
Les cours aborderont les points suivants
Principes et Architecture des Systèmes d'exploitation
Processus et Threads (création, ordonnancement, deadlocks)
Caches (principes, fonctionnement, algorithmes)
Gestions de la mémoire
Périphériques et Systèmes de fichiers
Les concepts étudiés seront mis en pratique dans des Tps de programmation.
Bibliographie :
Le cours est basé sur les livres suivants
Modern Operating Systems by Andrew S. Tanenbaum
Operating Systems : Design and Implementation by Andrew S. Tanenbaum

o-O-o

Nom UE : Programmation système 1
Intervenant : Fabrice Huet
Structure : 9 CM, 12 TP
Objectifs :
Comprendre les services fournis par un système d'exploitation aux programmeurs
Apprendre la programmation Système
Programme :
Les cours aborderont les points suivants
Rappels sur les systèmes d'exploitation (Principes, architecture)
Fichiers
Signaux
Utilisation des processus et threads
Communications inter-processus
Les concepts étudiés seront mis en pratique dans des Tps de programmation.

Bibliographie :
Le cours est basé sur les livres suivants :
Advanced Programming in the Unix Environment by Richard W. Stevens and Stephen A. Rago
Linux Device Drivers, by Jonathan Corbet, Alessandro Rubini, and Greg Kroah-Hartman

o-O-o


Nom UE : Synthèse d'images
Intervenant : Michel Buffa
Structure : 9 CM, 12 TP
Programme :
o-O-o

Nom UE : Génie logiciel orientée objet
Intervenants : Philippe Collet, Philippe Lahire
Structure : 9 CM, 12 TP
Objectifs :
Maîtriser les principes et techniques de génie logiciel, en se focalisant sur les apports de l'approche par objets. Mise en oeuvre de techniques de test, de réflexivité, de gestion prévisionnelle et adaptative de l'évo-lution. Découverte de patrons de conception.
Programme :
- prise en main d'un environnement de développement professionnel
- outil de construction et de gestion des sources associé
- test OO, principes et applications de l'eXtreme Programming
- introspection et réflexivité
- chargement dynamique
- héritage vs. Généricité
- patrons de conception

o-O-o


Nom UE : Programmation des systèmes distribués
Intervenant : Denis Caromel
Structure : 15 CM, 6 TP
Programme :
La construction des applications parallèles et réparties est marquée par l'importance croissante des méthodes utilisant l'assemblage, l'intégration et l'adaptation de logiciels existants, et par le développement du support logiciel correspondant (intergiciel). Ce module présente les principaux modèles d'interaction (exécution, partage d'information) des applications parallèles et réparties, le principe des supports logiciels (objets ré-partis, composants) et des algorithmes qui les mettent en œuvre (algorithmique distribués, synchronisation).

o-O-o

Nom UE : Théorie de l'information
Intervenant : Andrei Romashchenko
Structure : 12CM, 9TD
Programme :

The number of information in a finite object: combinatorial approach
a) Searching a faulty element
b) Secrete sharing
Probabilistic approach to the measure of information
a) Shannon entropy: definition and basic properties
b) Kraft's inequality, the Shannon/Fanno code
c) Shannon's noiseless coding theorem
Transmission of the information in noisy channels
a) Channels with bounded number of errors. Simple upper and lower bounds for capacity of a channel
b) Hamming's codes
c) Reed-Solomon codes
d) Shannon's noisy channel coding theorem
Algorithmic definition of the measure of information
a) Kolmogorov complexity of a nite word
b) The Kolmogorov-Levin theorem about symmetry of the mutual information
c) Connections between Kolmogorov complexity and Shannon's entropy
d) Applications of Kolmogorov complexity in combinatorics

Bibliographie :

M. Li and P. Vitanyi. An introduction to Kolmogorov complexity and its applications. Second Edition. Springer Verlag, 1997.
T. M. Cover and J. A. Thomas. Elements of information theory. Wiley, 2004.

o-O-o

Nom UE : Théorie des graphes : coloration
Intervenant : F. Havet
Structure : 12 CM, 9 TD
Programme :

Coloration des sommets, coloration des arêtes
Coloration par listes
Méthode probabiliste
Méthode de déchargement
Application aux problèmes de télécommunications

o-O-o

Nom UE : Théorie des jeux – Evaluation de performances
Intervenant : P. Bernhard
Structure : 12 CM, 9 TD
Programme :

Introduction historique et épistémologique
• Objectifs et un peu d'historique de la théorie des jeux.
• Points de vue épistémologiques : science normative des ingénieurs vs la science positive des économistes.
• Exemples. (Bordures et Syldaves, dilemme du prisonnier, duopole de Cournot.)
Jeux statiques
• Jeux à deux joueurs et somme nulle
• Jeux à deux joueurs et somme non nulle
• Jeux à N joueurs et somme non nulle
Jeux évolutionnaires
• Jeux de population, équilibre de Wardrop et ESS
• Équation du réplicateur, et dynamique de l'évolution,
• sélection naturelle et diversité biologique
Jeux dynamiques à deux joueurs et somme nulle
• Jeux en forme extensive et information parfaite : programmation dynamique
• Jeux en information imparfaite, principe d'équivalence à la certitude.
• Jeux différentiels, équation d'Isaacs

o-O-o


Nom UE : Programmation par contraintes, analyse par intervalles et applications
Intervenant : Michel Rueher, Jean-Pierre Merlet
Structure : 12 CM, 9 TD
Programme :

Fondements logiques de la programmation par contraintes (sémantique dénotationnelle et opérationnelle)
Algorithmes et heuristiques de résolution (techniques de filtrage, stratégies de recherche, algorithme de RO) ; mise en oeuvre sur les domaines finis, booléens et continus (calcul d¿intervalles)
Traitement des symétries, explications, langages (Ilog CP)
Géométrie algébrique et intervalles: traitement des polynômes à coefficients intervalles (bornes sur les racines, nombre de racines réelles)
Algèbre linéaire et intervalles: résolution de systèmes linéaires intervalles, régularité de matrices à coefficients intervalles, problème de calcul de valeurs propres
Résolution de systèmes d'équations: opéra