Les programmes des unités d'enseignement du M1

Table des matières

1  Comment lire les pastilles?

SI: spécialité “Ingénierie Informatique”, parcours “Systèmes d'Information”

SRI: spécialité “Ingénierie Informatique”, parcours “Système, Réseaux, Internet”

LC: spécialité “Ingénierie Informatique”, parcours “Logiciels Critiques”

ISIFAR: spécialité “Ingénierie statistique et informatique pour la finance, l'assurance et le risque”

MPRI: spécialité “Master parisien de Recherche en Informatique”

MPRI - Math Info: spécialité “Master parisien de Recherche en Informatique - Mathématiques Informatique”



Parcours SI SRI LC ISIFAR MPRI MPRI
            Math-Info
Obligatoire
Optionnel

2  Génie logiciel ()

Objectifs

Apporter aux étudiants les connaissances théoriques, techniques et pratiques leur permettant d'étudier, concevoir et réaliser des logiciels correspondant aux besoins de l'organisme auquel ces logiciels sont destinés.

Plan du cours

Méthodologie
Schéma directeur d'un projet permettant de replacer le travail à accomplir dans le cadre stratégique général du système d'information de l'organisme.
Approche de la gestion de projet en vue d'acquérir les bases de l'organisation des développements, de pouvoir en évaluer les coûts, les risques et les délais.

Méthodes formelles de spécification et vérification
La méthode Z : spécification en logique du premier ordre. Abstraction et raffinement.
Les ASM (abstract state machines) de Yuri Gurevich. Modélisation de l'environnement par des algèbres et du déroulement du calcul par une évolution de ces algèbres selon des systèmes finis d'équations pour la mise a jour.
Le langage ASML et ses variantes : spécification exécutable.

Outils et langages de modélisation
Merise et UML et logiciels associés (Power designor, Rose,...) afin d'acquérir les connaissances pratiques de la formalisation et atteindre un niveau de compétence opérationnelle compatible avec leur rôle professionnel.

Comparaison de quelques langages de programmation d'usage courant
afin d'être aptes à effectuer des choix techniques raisonnés.

Etude de cas
Travail demandé aux étudiants qui devront étudier un cas, l'analyser, le résoudre et y apporter des solutions concrètes, opérationnelles et réalistes sur les plans scientifiques, organisationnels, techniques et économiques.

Pré-requis

Avoir une bonne pratique de la programmation.

Bibliographie

  1. J. SPIVEY. The Z Notation : A reference Manual. Traduit en francais par M. Lemoine, Coll. Méthodologies du logiciel, Paris, Masson.

  2. Pascal ANDRE et Alain VAILLY. Tome 1 : Conception des systèmes d'information; Tome 2 : Spécification des logiciels : Deux exemples de pratiques récentes, Z et UML. Editions Ellipses, dans la collection TECHNOSUP.

  3. James K. HUGGINS and Charles WALLACE. An Abstract State Machine Primer, Technical Report CS-TR-02-04, Computer Science Department, Michigan Technological University, 4 December 2002. (Accessible sur le web)

  4. Pierre-Alain MULLER. Modélisation objet avec UML. Editions Eyrolles.

  5. Nathalie LOPEZ, Jorge MIGUEIS et Emmanuel PICHON. Intégrer UML dans vos projets. Editions Eyrolles.

  6. H. TARDIEU, A. ROCHEFELD, R. COLETTI. La méthode Merise, Tome 1 Principes et outils. Editions d'organisation.

  7. H. TARDIEU, A. ROCHEFELD, R. COLETTI, G. PANET, G. VAHÉE. La méthode Merise, Tome 2 Démarche et pratiques. Editions d'organisation.

  8. AFNOR, Secrétariat Général de la commission Centrale des Marchés - Informatique et Communication. Conduite de projets informatiques, le référentiel SAPHIR.

  9. Pham Thu QUANG et Jean-Jacques GONNIN. Réussir la Conduite de Projets Informatiques. Editions Eyrolles.

3  Droit de l'informatique ()

Objectifs

Ce cours se propose de fournir aux étudiants des connaissances de base sur les aspects juridiques liés à la création, usage et diffusion de logiciels et systèmes d'information.

Plan du cours

  1. Notions de base en droit
  2. Droit informatique en entreprise :

Bibliographie

4  Logiciels Libres ()

Objectifs

Ce cours se propose de fournir aux étudiants des connaissances de base sur les nouveaux modes de développement du logiciel qui se généralisent aujourd'hui, comme le logiciel libre et l'open source, qui nécessitent une bonne compréhension des nouveaux modèles économiques et des nouvelles modalités de license qu'ils mettent en oeuvre.

Le cours se concentre sur les nouveaux modes de développement du logiciel (en particulier, le logiciel libre), ses modèles économiques, ses mécanismes de fonctionnement et les moyens juridiques disponibles pour protéger l'investissement en développement logiciel.

Plan du cours

  1. Mécanismes de protection de l'investissement informatique, différences entre les normatives en France, en Europe et dans le monde, évolutions législatives
  2. Nouveaux modes de développement et diffusion du logiciel :

Bibliographie

5  Intelligence Artificielle ()

Objectifs

Connaître les problèmes qui relèvent de l'IA et les méthodes permettant de les traiter.

Plan du cours

6  Interfaces graphiques ()

Objectifs

Pouvoir programmer une interface graphique sur n'importe quel système.

Plan du cours

Pré-requis

Langage Java et programmation orientée objet.

Bibliographie

7  Bases de données avancées ()

Objectifs

Ayant comme pré-requis des connaissances des éléments des bases de données relationnelles cette UE approfondit ces connaissance en mettant l'accent sur les aspects système avancés. Ensuite les récentes évolution du domaine sont abordées, en particulier les entrepôts de données, les BD déductives, BD objets et BD Internet.

Plan du cours

Pré-requis

Bibliographie

  1. Serge ABITEBOUL, Richard HULL, Victor VIANU, Fondements des bases de données, Vuibert informatique, 2000
  2. Serge Abiteboul, Dan Suciu, Peter Buneman Data on the Web: From Relations to Semistructured Data and XML, Morgan Kaufmann Series in Data Management Systems, 1999
  3. Database Systems - The complete book. Hector Garcia-Molina, Jeffrey D. Ullman, Jennifer Widom Prentice Hall.

8  Circuits et architecture ()

Objectifs

Ce cours est une introduction au fonctionnement d'un processeur. L'objectif est de montrer comment la combinaison de composants électroniques très simples (transistors, portes logiques) peut permettre d'aboutir à l'outil puissant qui constitue le cerveau d'un ordinateur.

Une présentation des circuits élémentaires aboutit au concept d'instruction, qui permet ensuite de définir un jeu d'instructions de base avec lequel on aborde la programmation en langage machine et la traduction d'un langage de programmation de bas niveau comme C.

Des développements comme les multiprocesseurs, les entrées/sorties ou l'optimisation de code pourront être évoqués en fonction de l'avancée du cours et de la demande des étudiants.

Plan du cours

Pré-requis

Connaissance d'un langage de programmation impérative.

Bibliographie

  1. B. Goossens, Architecture et micro-architecture des processeurs
    Springer, 2002.
  2. D. Patterson, J. Hennessy, Conception et organisation des ordinateurs,
    Dunod, 1994.

9  Systèmes ()

Objectifs

Initier les étudiants au concept d'exécution concurrente.

Plan du cours

Pré-requis

Programmation en C, Unix utilisateur, API POSIX de manipulation des fichiers.

Bibliographie

  1. Jean-Marie Rifflet et Jean-Baptiste Yunès. UNIX: programmation et communication. Dunod 2003.
  2. W. Richard Stevens. Advanced Programming in the UNIX Environment. Addison-Wesley 1993.
  3. Abraham Silberschatz, Peter Galvin and Greg Gagne. Applied Operating System Concepts. John Wiley and Sons 2000.

10  Compilation ()

Objectifs

Etude des techniques de compilation. L'application de ces techniques consiste en la réalisation d'un mini compilateur sous forme de projet, en s'appuyant sur la méthode d'analyse ascendante et les outils Lex et Yacc sous Unix. On suppose connue l'analyse lexicale et syntaxique, et on se concentre sur les parties propres d'un compilateur, de l'arbre de syntaxe abstraite à la génération de code pour une machine cible.

Plan du cours

Pré-requis

Langages formels, analyse syntaxique, une bonne connaissance du langage Ocaml.

Bibliographie

  1. Aho, Sethi, Ullman : Compilateurs : Principes, techniques et outils, Interéditions, 1989.

  2. Appel: Modern Compiler Implementation in ML, Cambridge University Press, 1998

  3. Levine, Mason, Brown : Lex et Yacc (Traduction), Editions O'Reilly Internationnal Thomson, 1994.

11  PROLOG et programmation logique par contraintes ()

Objectifs

Connaître la programmation logique et la programmation logique par contraintes.

Plan du cours

Pré-requis

Programmation, Logique

Bibliographie

  1. Bratko : Programmation en PROLOG pour l'Intelligence artificielle, Interéditions , 1988, ou version anglaise de 2001 (Addison Wesley).
  2. Shapiro, Sterling: L'art de Prolog.
  3. Marriott, Stuckey: Programming with Constraints, an Introduction, MIT Press, 1998.

12  Algorithmique ()

Objectifs

Maitriser les bases de l'algorithmique des graphes et des mots. Connaitre les grands principes de la conception et de l' analyse des algorithmes.

Plan du cours

  1. Algorithmes dans les graphes :
  2. Algorithmes sur les mots :
  3. Thème transversal: “Grands principes” de l'algorithmique

Pré-requis

Tri, files de priorités et tas. Arbres.

Bibliographie

  1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001.

  2. D. Beauquier, J. Berstel, Ph. Chretienne : Eléments d'algorithmique, Masson.

13  Calculabilité et complexité ()

Objectifs

Discerner les problèmes que l'on peut théoriquement résoudre avec une machine. Évaluer la difficulté en temps et en espace des problèmes que l'on peut résoudre.

Plan du cours

Pré-requis

Théorie des automates.

Bibliographie

  1. J. E. Hopcroft and J. D. Ullman, Introduction to Automata Theory, Languages and Computation. Addison-Wesley, 1974.

  2. M. Sipser, Introduction to the Theory of Computation. PWS publishing Company, 1997.

  3. J.-M. Autebert, Calculabilité et Décidabilité. Masson, 1992.

  4. P. Wolper, Introduction à la calculabilité. InterÉditions, 1991.

  5. H. R. Lewis and C. Papadimitriou, Elements of the theory of computation. Prentice-Hall, 1981.

  6. C. Papadimitriou, Computational complexity. Addison-Wesley, 1995.

  7. D. Welsh, Codes and Cryptography. Clarendon Press, 1988.

  8. J. Stern, Fondements mathématiques de l'informatique. McGraw-Hill, 1990.

14  Automates avancés et applications ()

Objectifs

Les automates sont extrêmement utiles pour modéliser des phénomènes complexes et pour développer des algorithmes efficaces sur ces modèles. Le plus souvent, on utilise des extensions de la notion classique d'automate fini. Ces extensions peuvent porter sur l'objet à reconnaître : mot infini, arbre, fonction, relation, ...ou sur la méthode de reconnaissance : non déterminisme, alternance, condition d'acceptation, ...Ces généralisations d'automates sont utilisées avec succès pour de nombreuses applications : vérification automatique de systèmes, calcul de propriétés quantitatives, compression, algorithmique du génôme, algorithmique du texte, systèmes de numération, ...

L'objectif du cours est de présenter certaines extensions des automates et certaines de leurs applications.

Plan du cours

Pour compléter, on traitera certains des points suivants :

Pré-requis

Automates finis.

Bibliographie

  1. G. Rozenberg and A. Salomaa Eds., Handbook of Formal Languages (volumes 1, 2, 3), Springer, 1997.

  2. D. Perrin et J.-E. Pin, Infinite Words, Pure and Applied Mathematics vol. 141, Academic Press, 2003.

  3. M. Crochemore, C. Hancart and T. Lecroq, Algorithmique du texte, Vuibert, 2001

15  Infographie ()

Objectifs

Présentation des principes et des méthodes à la base de l'Infographie. Une large place est faite à la géométrie algorithmique et aux développements récents liés à la synthèse d'images. Les projets sont réalisés en Java.

Plan du cours

Pré-requis

Bibliographie

  1. B. Péroche : La synthèse d'image, 1988, Hermes.

  2. D.F. Rogers: Procedural Elements for Computer Graphics, 1985, International Student Edition.

  3. J.D. Foley, A. Van dam, S.K. Feiner, J.F. Hugues: Computer Graphics, 1990, Addison Wesley.

16  Théorie et pratique de la concurrence ()

Objectifs

Ce cours s'adresse aux étudiants en M1 qui suivront soit la filière recherche soit la filière professionnelle orientée logiciels critiques.

Il a comme but de former les étudiants à construire des applications concurrentes et distribuées ainsi qu'à raisonner sur leur propriétés. Pour cela, on des langages de programmation spécialisés et des outils CAD basés sur différents modèles formels de la concurrence.

A la fin du cours, l'étudiant devra être capable :
  1. de comprendre les concepts fundamentaux de la concurrence,
  2. de construire des programmes concurrents et distribués élémentaires en C et Java,
  3. de modéliser quelques algorithmes concurrents et distribués, et
  4. d'utiliser au moins un outil de CAD basé sur des modèles formels.

Plan du cours

Pré-requis

Bibliographie

  1. R. Milner, Communication and Concurrency, Prentice-Hall, 1989.
  2. M. Ben-Ari, Principles of Concurrent and Distributed Programming 1/e, Prentice Hall, 1990.
  3. G. Holzmann, The Spin Model Checker - Primer and Reference Manual, Addison-Wesley Publ., 2003.
  4. J.-M. Rifflet et J.-B. Yunes, Programmation sous Unix, Dunod 2003.
  5. G. Roussel, E. Duris, N. Bedon et R. Forax, Java et Internet, Vuibert 2002.

17  Protocoles Réseaux ()

Objectifs

Maîtriser les protocoles non-applicatifs du réseau Internet.

Plan du cours

Internet comme interconnexion de réseaux et de machines.

Protocoles des couches physique, liaison de données, réseau et transport:

Bibliographie

18  Preuves assistées par ordinateur ()

Objectifs

L'objectif de ce cours est de présenter les principales techniques utilisées dans le domaine de la preuve assistée par ordinateur, que ce soit dans le cadre de la formalisation effective des mathématiques sur machine ou dans le cadre de la certification logicielle.

La problématique de la démonstration sur machine recouvre en réalité deux approches. D'une part la démonstration automatique, dans laquelle la recherche et la construction de la preuve est entièrement confiée à la machine, mais qui n'est réalisable que dans des fragments restreints des mathématiques. D'autre part la vérification de preuve, dans laquelle la machine se contente de vérifier la correction formelle d'une preuve fournie par l'utilisateur, mais qui est en revanche susceptible de traiter tous les domaines des mathématiques. En pratique, la plupart des assistants à la démonstration (HOL/Isabelle, PVS, Coq, PhoX, etc.) combinent les deux approches: les grandes lignes de la preuve sont développées par l'utilisateur et vérifiées par la machine, tandis que ses détails sont construits de manière plus ou moins automatisée par la machine.

Ce cours se propose d'introduire les principales notions qui sous-tendent ces deux approches. On présentera donc non seulement les principales méthodes de recherche de preuve (résolution, recherche de preuve sans coupure dans le calcul des séquents) en logique du premier ordre, mais aussi les techniques qui permettent de représenter les objets mathématiques en logique d'ordre supérieur (lambda-calcul simplement typé et théorie des types simples de Church), lesquelles sont à la base des assistants à la preuve tels que HOL/Isabelle, PVS, PhoX et Coq. En parallèle avec le cours, les notions introduites seront illustrées par des travaux pratiques effectués à l'aide de l'assistant à la démonstration Coq.

Plan du cours

Pré-requis

Bibliographie

  1. R. David, K. Nour, C. Raffalli. Introduction à la logique, Dunod.
  2. R. Cori, J.-L. Krivine. Logique mathématique I, Masson.
  3. M. Fitting. First-Order Logic And Automated Theorem Proving, Springer.
  4. The Coq Proof Assistant Reference Manual (V7.4):
    http://coq.inria.fr/doc/main.html

19  Sémantique des langages de programmation ()

Objectifs

Décrire les outils théoriques dont on dispose pour définir une sémantique formelle des langages de programmation.

Plan du cours

Pré-requis

Bibliographie

  1. Lallement : Logique, Réduction, Résolution, Masson, 1990.

  2. Gunter : Semantics of Programming Languages, MIT Press, 1992.

  3. Gordon : The denotational description of programming languages, Spinger Verlag, 1977.

20  Algorithmique avancée ()

Objectifs

Etudier des techniques avancées d'algorithmique dans des domaines d'application de base. Le cours comprendra des éléments dans les domaines suivants.

Plan du cours

Pré-requis

Techniques d'algorithmique de base.

Bibliographie

  1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. Chapter 29: Linear Programming.

  2. F. Preparata, M. Shamos. Computational Geometry, An Introduction, Springer, 1985.

  3. J. Jaja. An Introduction to Parallel Algorithms, Addison-Wesley, 1992.

21  Analyse de performances et simulation ()

Objectifs

Etude de méthodes permettant d'effectuer des raisonnements corrects sur de réseaux probabilistes représentant des informations incertaines. Application aux problèmes de diagnostic de pannes.

Plan

  1. Réseaux Bayesiens

  2. Méthodes de calcul: méthodes exactes, méthodes statistiques, autres méthodes approchées

  3. Messages locaux: étude de cas particuliers, chemin arborescence, etc..

Pré-requis

Probabilités.

Bibliographie

  1. F.V. Jensen, Introduction to Bayesian networks, Springer Verlag, 1996.

22  Probabilités et systèmes à événements discrets ()

Objectifs

Le but de ce cours est double:

Plan du cours

  1. Simulation et tables d'événements
    Tirage de variables aléatoires, méthode de l'inverse et du rejet, tables d'événements, intervalles de confiance.

  2. Chaînes de Markov à temps discret et modélisation en informatique et communications


  3. Chaînes de Markov à temps continu et réseaux stochastiques

  4. Graphes aléatoires et réseaux dynamiques

  5. Théorie algébrique de la dynamique des réseaux

Pré-requis

Probabilités discrètes élémentaires.

23   Fondements de l'interprétation abstraite ()

Objectifs

Les raisonnements sur les systèmes informatiques, qu'ils soient purement intellectuels ou automatisés, requièrent tous de disposer de modèles du comportement de ces systèmes informatiques à l'exécution. La conception de tels modèles mathématiques fait l'objet de la sémantique des langages de programmation.

Selon les propriétés d'intérêt de ces systèmes informatiques, le modèle utilisé comme base du raisonnement ou de la preuve doit être plus ou mois concret ou raffiné (s'il faut tenir compte des moindres détails du fonctionnement du système) ou au contraire plus ou moins abstraits, (pour pouvoir faire des raisonnements globaux en faisant abstraction des détails non pertinents).

L'interprétation abstraite est une théorie de l'approximation qui permet de formaliser cette notion d'abstraction et de construire des modèles à partir d'autres déjà connus par raffinement ou par abstraction.

Si l'abstraction est suffisamment grossière pour être calculable, on peut dériver de la sémantique du système informatique des algorithmes de typage, de vérification exhaustive (model checking), d'analyse statique, etc.

Plan du cours

  1. Éléments de la théorie de l'ordre ;
  2. Éléments de la théorie des points fixes ;
  3. Correspondance de Galois ;
  4. Abstractions exactes de points fixes ;
  5. Application à la conception de sémantiques par abstraction d'une sémantique de traces ;
  6. Approximation constructive de points fixes ;
  7. Inférence de type pour le lambda-calcul par interprétation abstraite ;
  8. Conception d'algorithmes de vérification exhaustive de modèles finis (model checking) par interprétation abstraite ;
  9. Correction et la complétude de méthodes de preuves de programmes ;
  10. Treillis des interprétations abstraites, exemples.

Pré-requis

Éléments de logique mathématique et informatique, compilation.

Bibliographie

24  Initiation à la cryptologie ()

Objectifs

Ce cours sert à la fois d'initiation à la cryptologie et de préparation au cours de niveau 2. Il s'adresse aux étudiants ayant un goût pour l'algorithmique, à la fois dans ses aspects mathématiques et dans ses aspects pratiques. Le but de ce cours est d'enseigner la problématique de la cryptologie, et les principaux outils utilisés par la cryptologie pour proposer des solutions aux problèmes de sécurité.

Plan du cours

  1. Introduction à la cryptographie.
  2. Cryptographie symétrique.
  3. Compléments d'algorithmique.
  4. Cryptographie asymétrique.
  5. Protocoles.
  6. Applications.

Pré-requis

On aura besoin des notions de classes de complexité, de machine de Turing, de problèmes NP. Un minimum de connaissance en algèbre et en probabilité sera aussi requis. Enfin les outils algorithmiques de base doivent être maîtrisés.

Bibliographie

25   Géométrie discrète et algorithmique ()

Objectifs

Dans ce cours d'introduction aux objets, techniques et applications de la géométrie algorithmique nous développons plus particulièrement l'étude des problèmes de recherche multidimensionnelle, la théorie des polytopes convexes et la programmation linéaire.

Plan du cours

  1. Configurations de points et arrangements de droites

  2. Polytopes convexes et programmation linéaire

Pré-requis

Aucun pré-requis spécifique n'est attendu.

Bibliographie

26  Théorie de l'information ()

Objectifs

Les questions abordées dans ce cours sont motivées par des applications : le stockage, la numérisation et la transmission des données. Motivé par des questions d'ingénieur, le cours s'adresse à des étudiants en Informatique et en Mathématiques. Il vise à présenter les bases mathématiques de la théorie de Shannon et les solutions algorithmiques à ces problèmes. Il prépare les étudiants à utiliser les résultats et les méthodes de la théorie de l'information en Informatique (Compression/Télécommunications) et/ou en Mathématiques (Probabilités/Statistiques).

Plan du cours

Codage source
  1. Entropie d'une source, théorème de codage sans bruit de Shannon. Codage arithmétique.
  2. Codage universel I : modèles paramétriques.
  3. Codage universel II : techniques de dictionnaires (LZ).
  4. Codage universel III : transformée de Burrows-Wheeler.
  5. Codage universel IV : codage par transformation grammaticale.
  6. Codage avec pertes d'information, théorème de débit-distorsion.
  7. Codages des sources Gaussiennes. Application aux codage linéaire prédictif.
  8. Débit-distorsion. Algorithmes de calcul de la fonction de débit-distorsion. Codage progressif.
Codage canal
  1. Codage canal. Capacité, random coding exponents, sphere packing bounds
  2. Méthodes effectives, codage algébrique, codes de Reed-Solomon.
  3. Constructions de bonnes familles de codes codables et décodables en temps linéaire, LDPPC
  4. Le principe de séparation.
  5. Questions de théorie de l'information multi-utilisateurs I : diffusion
  6. Questions de théorie de l'information multi-utilisateurs II : accès multiple

Pré-requis

Algorithmique et probabilités discrètes.

27  Programmation 2 ()

Objectifs

Ce cours de programmation approfondie est orienté vers la manipulation de syntaxes (notion de syntaxe abstraite) et les techniques d'implantation de langages (Compilation vers une machine virtuelle). Il introduit aussi le lambda-calcul comme formalisme permettant de décrire l'évaluation des langages de programmation et la notion de règle formelle pour le typage et l'évaluation. On utilise le langage Objective Caml comme support des notions présentées, des exercices et des projets.

Plan du cours

Prérequis

Ce document a été traduit de LATEX par HEVEA