doc - LAGA - Université Paris 13

CONTRAT 2009 2012 DEMANDE D'HABILITATION DE DIPLOME DE MASTER
Master Mention Mathématiques et Informatique
Université Paris 13 ------- Descriptifs des unités d'enseignement Spécialité Algorithmique, Modélisation, Images -------
Intitulé de l'UE : Remise à niveau S1
Semestre : S1, obligatoire Crédits : 2 Heures de cours : CM 19,5 TP 19,5 But du cours : Outils de base en Mathématiques et pour la programmation C Responsable : Yueyun Hu, Sophie Toulouse Pré requis : Aucun Contenu : Mathématiques : Outils de base de probabilités et d'analyse : intégration,
loi des grands nombres, théorème central limite. Informatique :
1. Variables, fonctions, structure d'un programme C
2. Type, adresse, pointeur
3. Structures complexes, programmation modulaire
4. Algorithmique, structures de données, complexité
Intitulé de l'UE : Analyse de Fourier et théorie du signal S1
UE commune avec la spécialité Mathématiques fondamentales et Protection de
l'information Semestre : S1, obligatoire Heures de cours : CM 19,5 TD 19,5 But du cours : Analyse hilbertienne et de Fourier et applications en
théorie du signal Responsable : LAGA Pré requis : Aucun Contenu : Compléments sur les espaces de Hilbert. Bases hilbertiennes, séries de
Fourier. Théorème de Riesz, dualité. Transformation de Fourier dans L^1, dans L^2 et sur l'espace de Schwartz.
Convolution, régularisation. Transformation de Fourier discrète, transformation de Fourier rapide.
Filtrage. Echantillonnage, théorème de Shannon.
Intitulé de l'UE Graphes S1
Semestre : S1, obligatoire Crédits : 4 Heures de cours : CM 19,5 TD 19,5 But du cours : Introduire les concepts classiques et modernes de la
théorie des graphes Responsable : Mario Valencia Pabon Pré requis : Aucun Contenu : 1. Concepts préliminaires : chemins, cycles, arbres et forêts, connexité,
graphes bipartis, contractions et mineurs, chemins et circuits Eulériens.
Algorithmes de plus court chemin (ex. : Dijkstra) et d'arbres couvrants
(ex. : Kruskal). 2. Couplage : graphes bipartis, graphes généraux, recouvrement des
graphes par des chemins. 3. Connexité : graphes et sous-graphes 2-connexes, structure des graphes
3-connexes, théorème de Menger, théorème de Mader, arbres de recouvrement
arête disjoints, chemins entre pairs de sommets. 4. Graphes Planaires : concepts topologiques, théorème de Kuratowski,
critères algébriques, dualité planaire. 5. Coloration : coloration des sommets, coloration des arêtes, coloration
par listes, multi-coloration, graphes parfaits. 6. Réseaux électriques et flux : définitions, k-flux, dualité flux-
coloration, conjectures de Tutte sur le flux. Algorithmes de flots (Ford-
Fulkerson). 7. Sous-structures dans les graphes : graphes denses, lemme de régularité
de Szemerédi, graphes disperses, mineurs topologiques, conjecture de
Hadwiger. 8. Théorie de Ramsey dans les graphes : notions basiques et théorèmes
principaux. 9. Cycles Hamiltoniens : conditions suffisantes et applications. 10. Graphes aléatoires : la méthode probabiliste, propriétés pour presque
tous les graphes. 11. Mineurs, arbres et largeur arborescente : théorie des mineurs,
décompositions arborescentes des graphes, largeur arborescente et mineurs
interdits. Intitulé de l'UE : Modèles aléatoires 1 S1
UE commune avec la spécialité Mathématiques fondamentales et Protection de
l'information Semestre : S1 Crédits : 4 Heures de cours : CM 19,5 TD 19,5 But du cours : Responsable : LAGA Pré requis : Contenu : Rappels de probabilités, fonction génératrice des moments ; propriété de
Markov. Probabilités de transition ; lois invariantes et lois limites. Exemples de chaînes de Markov (marches aléatoires, modèles génétiques,
files d'attente, chaînes de branchement, chaîne de naissance ou de mort. États transients, états récurrents. Temps et probabilité d'absorption.
Temps moyen de première visite et de récurrence. Intitulé de l'UE : Programmation linéaire S1
UE mutualisée avec le Master Informatique et la formation d'ingénieurs
spécialité Informatique Semestre : S1 Crédits : 4 Heures de cours : CM 18 TD 18 TP 12 (UE
mutualisée INFO 2) Responsable : Gérard Plateau But du cours : Fournir la théorie et les principes généraux de la
programmation linéaire (convexité, solutions de base, dualité) pour établir
les algorithmes du simplexe (primal et dual) avec l'extension à la
paramétrisation. Pré requis : Algèbre linéaire Contenu : 1. modélisation et formulation d'un programme linéaire 2. convexité 3. théorèmes fondamentaux de la programmation linéaire 4. algorithme primal du simplexe 5. algorithme dual du simplexe 6. post-optimisation : analyses de sensibilité et paramétrisation
Intitulé de l'UE : Algorithmes et graphes aléatoires S1
Semestre : S1 Crédits : 4 Heures de cours : CM 19,5 TD 19,5 But du cours : L'objectif de ce cours est d'initier les étudiants aux
graphes aléatoires [3] qui sont des objets dont l'importance couvre
plusieurs domaines : algorithmique et informatique fondamentale bien-sûr
mais aussi physique, biologie, probabilités pour ne citer que ceux là. Il
s'agît d'étudier ces objets algébriques du point de vue algorithmique et
structurel en utilisant : la combinatoire analytique [1, 2] et les méthodes
dites probabilistes [4]. Responsable : Vlady Ravelomanana Pré requis : Concepts élémentaires de théorie des graphes. Contenu : 1. Concepts préliminaires d'analyse combinatoire : graphes étiquetés et
séries génératrices exponentielles [1,2]. 2. Concepts préliminaires de probabilité: inégalités de concentration,
graphes et algorithmes [3,4]. 3 Concepts avancés : méthode du col et analyses de singularité [1]. 4. Description des transitions de phases dans le processus de génération de
graphes aléatoires [3]. 5 Algorithmes pour les CSP binaires. Nous montrerons que ces problèmes
difficiles peuvent être rendu polynomial en moyenne. 6. Le problème du plus grand ensemble indépendant. Il représente un exemple
concret permettant de mettre en exergue les méthodes citées dans les
concepts (1) et (2) ci-dessus. En effet, nous verrons comment montrer
l'existence d'un ensemble indépendant d'une certaine taille T en utilisant
les méthodes de moments (2) et nous montrerons que les meilleurs
algorithmes n'exhibent que des ensembles indépendants de taille T/2 dans
les graphes aléatoires G(n, 1/2). Intitulé de l'UE : Complexité algorithmique S1
UE commune avec la spécialité Mathématiques fondamentales et Protection de
l'information Semestre : S1 Heures de cours : CM 19,5 TD 19,5 But du cours : Introduire les concepts de la complexité en temps et en
espace. Responsable : Christophe Tollu Pré requis : Aucun Contenu : 1. Rappel sur la notion de calculabilité. 2. Machine de Turing. 3. Classes PSPACE, P et NP. 4. Problèmes NP-difficiles ; exemples issus de l'arithmétique et de la
cryptographie. 5. Classes probabilistes.
Intitulé de l'UE : Analyse fonctionnelle S1
UE commune avec la spécialité Mathématiques fondamentales et Protection de
l'information Semestre : S1 Crédits : 4 Heures de cours : CM 19,5 TD 19,5 But du cours : Théorèmes généraux et outils fondamentaux de l'analyse
fonctionnelle. Responsable : LAGA Pré requis : Contenu : Espaces fonctionnels : exemples classiques, théorème de Baire, de Banach-
Steinhaus, du graphe fermé et de l'application ouverte. Théorème d'Ascoli. Dualité, Théorème de Hahn-Banach. Topologies faibles. Eléments de théorie spectrale des opérateurs.
Intitulé de l'UE : Modèles aléatoires 2 S1
Semestre : S1 Crédits : 4 Heures de cours : CM 19,5 TD 19,5 But du cours : Responsable : Yueyun Hu Pré requis : Il est vivement conseillé de suivre l'unité modèle aléatoire 1
Contenu : Existence d'une loi invariante limite, périodicité (pour une chaîne de
Markov). Algorithme de Métropolis, processus de Bernoulli, processus de Poisson et
relation avec les files d'attente.
Intitulé de l'UE : Traitement statistique du signal S1
UE commune avec la spécialité Mathématiques fondamentales et Protection de
l'information Semestre : S1 Crédits : 4 Heures de cours : CM 19,5 TD 19,5 TP 12 But du cours : Apprendre aux étudiants à utiliser les processus
stochastiques stationnaires du second ordre (principalement à temps
discret) comme outils de modélisation permettant de résoudre, de manière
statistiquement optimale (au sens du minimum de variance) des problèmes de
filtrage, d'estimation et de prédiction Responsables : Caroline Kulcsár et Henri-François Raynaud (L2TI) Pré requis : notions de base de la théorie des probabilités, et de
l'algèbre linéaire et quadratique Contenu : Processus aléatoires à temps discret : moments, processus stationnaires,
processus gaussiens scalaires et vectoriels. Notions d'espace de Hilbert
stochastique. Ergodicité. Représentation spectrale, fonction d'autocorrélation, densité spectrale de
puissance, bruit blanc. Modèles paramétriques AR et ARMA. Modèles markoviens, représentations
d'état, problème de réalisation. Filtrage et prédiction à variance minimale. Filtre de Kalman. Estimation des paramètres d'un modèle AR/ARMA. Méthode de Yule-Walker. Introduction aux processus à temps continu. Problème de discrétisation.
Intitulé de l'UE : Statistique exploratoire multidimensionnelle S1
Semestre : S1 Crédits : 4 Heures de cours : CM 19,5 TD 19,5 But du cours : Responsable : LAGA Pré requis : Contenu : Description unidimensionnell