ENS de Cachan
Département
Informatique
Descriptif des enseignements de première année









Liste des cours

Cours du premier semestre (voir aussi les cours du département de math) : Cours du second semestre :

Calculabilité et complexité

Responsables : Hubert Comon-Lundh Serge Haddad
Le cours est structuré comme suit :
  1. Machines de Turing
  2. Fonctions récursives

  1. Introduction aux classes de complexité
  2. La classe NP
  3. La classe PSPACE
  4. La classe PTIME
  5. La classe NLOGSPACE
  6. Inclusions strictes entre classes

Algorithmique 1

Responsables : Paul Gastin, Michel Habib
Ce cours a pour objectif de donner les bases de l'algorithmique.
Il recouvre en particulier le programme d'algorithmique de l'option informatique de l'agrégation de mathématiques.
Il ne nécessite aucune connaissance préalable.
Il est indépendant de tout langage de programmation mais l'étudiant devra réaliser des mini-projets dans un langage de son choix, par exemple, Java, Caml, C++, ...

Les points suivants seront traités, pas forcément dans cet ordre.

  1. Preuves et complexité des algorithmes
    • Preuves de Hoare : assertions, pré et post conditions, invariants de boucles, terminaison des boucles
    • Complexité en temps et en espace. Coût au pire et coût en moyenne. coût amorti. Coût asymptotique. Récurrences de partition.
  2. Structures de données
    • Types de données abstraits : listes, files, piles, dictionnaires, files de priorités, ...
    • Implémentations des piles et des files par des tableaux ou des listes chaînées
  3. Algorithmes de tri
    • Tris par comparaison : insertion, tri fusion, tri rapide, tri par tas, ...
    • complexités au pire et en moyenne, borne inférieure des tris par comparaisons
  4. Algorithmes de recherche (implémentation des dictionnaires)
    • recherche dichotomique
    • Arbres binaires de recherche, arbres équilibrés
    • Tables de hachage
  5. Implémentation des files de priorité
    • Tas, tas binomiaux, tas de Fibonacci
  6. Recherche de motifs dans un texte
    • Algorithme naïf
    • Algorithme de Knuth Morris et Pratt
    • Algorithme de Boyer et Moore
    • Utilisation des automates finis : algorithme de Simon, Algorithme de Aho et Corasick
  7. Partitions : union et recherche
  8. Paradigmes
    • Diviser pour régner
    • Algorithmes gloutons
    • Programmation dynamique
  9. Algorithmes pour les graphes
    • Parcours de graphes, parcours en largeur, parcours en profondeur, applications au tri topologique et aux composantes fortement connexes
    • Arbres couvrants de poids minimum (Kruskal, Prim)
    • Plus courts chemins (Dijkstra, Floyd-Warshall)
    • Graphes pondérés, algorithmes de flots (Ford-Fulkerson)

Bibliographie

  • Introduction à l'algorithmique. Cormen, Leiserson, Rivest et Stein. Dunod.
  • Éléments d'algorithmique. Beauquier, Berstel, Chretienne. Masson.
  • Fundamentals of Algorithmics. Brassard et Bratley. Prentice Hall.
  • Introduction à l'analyse des algorithmes. Sedgewick et Flajolet. International Thomson Publishing.

Programmation 1

Responsable : Jean Goubault-Larrecq
Les objectifs du cours sont d'acquérir les concepts des langages de programmation (impératifs, fonctionnels, à objets) sans se focaliser en cours sur un langage de programmation. Pour cela des exemples seront donnés dans plusieurs langages (Java, C++, Caml). Par ailleurs les élèves devront mettre en pratique leurs connaissances en programmant dans un ou deux langages.
  • Architecture des machines:
    • représentation des données
    • CPU, registres, bus, cycles d'exécution, mémoire, cache
    • niveaux d'abstraction: circuit, langage machine, langage d'assemblage,...
  • Concepts fondamentaux de la programmation:
    • déclarations, environnement, mémoire
    • expressions, l'affectation, les différents modes d'évaluation
    • structures de contrôle
    • types de base, constructions simples (produits, sommes, tableaux)
    • fonctions et procédures, variables locales, passage de paramètres
    • récursion
    • exceptions
    • étiquetage
    • pointeurs
    • types de données récursifs
    • définitions par motifs et filtrage
    • polymorphisme
    • inférence de type
    • types abstraits
    • objets, attributs, héritage
    • modularité, interfaces, compilation séparée
    • threads
  • Eléments de preuve de programme
    • terminaison
    • assertions, pre et post-conditions, invariants
    • preuves de fonctions récursives
  • Compilation
    • arbres abstraits, calculs d'attributs sémantiques
    • analyse statique
    • appels de procédures, passages de paramètres
    • machines abstraites, exemple de la machine virtuelle Java
    • génération de code et optimisations
    • gestion mémoire

Architecture et système

Responsable : Stefan Schwoon
  • Introduction, Shell
  • Rappels de C
  • Processus et signaux, Gestion mémoire
  • Système de fichiers, Entrées/Sorties
  • Threads, Exclusion mutuelle

Projet de programmation 1

Responsable : Jean Goubault-Larrecq

Mathématiques discrètes

Responsable : Claudine Picaronny


Langages formels

Responsable : Paul Gastin
  1. Langages reconnaissables
  2. Automates d'arbre
  3. Grammaires
  4. Langages algébriques
  5. Automates à pile
  6. Analyse syntaxique
  7. Fonctions séquentielles

Logique

Responsable : Hubert Comon-Lundh
  1. Calcul propositionnel
  2. Calcul des prédicats
  3. Théorèmes d'incomplètude (Gödel)
  4. Théorie décidables

Programmation 2

Responsable : Giuseppe Castagna

Dans ce cours, nous étudions plusieurs aspects "de haut-niveau" des langages de programmation. Nous introduisons de nouveaux concepts qui complémentent la formation en programmation (modules, objets, sous-typage, concurrence) ainsi que des techniques qui enrichissent la vision des différents paradigmes de programmation (transformations monadiques pour différents types d'effets). Même si le langage de référence pour l'examen est OCaml, lors du cours nous utiliserons aussi des extraits de code Haskell, Scala, Perl 6, C#, Java, Erlang, Pascal, Python, Basic, CDuce, Xslt, etc. L'idée étant de mettre l'accent sur les concepts de la programmation plus que sur la programmation dans un langage particulier.

Systèmes de modules
  • 1. Introduction à la Modularité.
  • 2. Modules (simples) en ML.
  • 3. Foncteurs.
Classes vs. Modules
  • 4. Modularité dans les langages objets
  • 5. Mixins
  • 6. Dispatch multiple
  • 7. Les classes en OCaml
  • 8. Les Typeclasses d'Haskell
  • 9. Generics
Transformation de programmes
  • 10. A propos de la pureté
  • 11. Rappels de sémantique opérationnelle
  • 12. Closure conversion
  • 13. Défonctionalisation
  • 14. Exception passing style
  • 15. State passing style
  • 16. Continuations, générateurs et co-routines
  • 17. Continuation passing style
Programmation Monadique
  • 18. Votre première monade
  • 19. Exemples de monades
  • 20. Les lois monadiques
  • 21. Transformation de programmes et monades
  • 22. Monades comme technique de programmation
  • 23. Monades et foncteurs
Typage et Sous-typage
  • 24. Sous-typage des types simples
  • 25. Extensions: produits, enregistrements, références
  • 26. Types ensemblistes: unions, intersections et négations
  • 27. Covariance et contra-variance
  • 28. Filtrage par types ensemblistes: XML et CDuce
  • 29. Reconstruction de types : le typage de ML
Concurrence
  • 30. Notions de concurrence
  • 31. Multi-threading préemptif
  • 32. Mutexes, Conditional Variables, Monitors
  • 33. Travailler sans exclusion mutuelle
  • 34. Multi-threading coopératif
  • 35. Communication par canaux
  • 36. Software Transactional Memory

Algorithmique 2

Responsable : Serge Haddad
  1. Recherche de chaînes de caractères
  2. Polynômes et transformée de Fourier rapide
  3. Compression de données
  4. Algorithmes d'approximation
  5. Algorithmes et probabilités
  6. Programmation linéaire

Logique et informatique

Responsable : Jean Goubault-Larrecq
  1. Lambda-calcul pur, (non-)terminaison, confluence, standardisation
  2. Lambda-calcul typé, correspondances de Curry-Howard pour diverses logiques, classiques ou intuitionnistes, allant de la logique propositionnelle minimale (types simples) à l'arithmétique du second ordre (système F)
  3. Machines, lambda-calculs à substitutions explicites, et propriétés mathématiques d'iceux

Bases de données

Responsable : Pierre Senellart

Ce cours couvre les grands principes des systèmes de gestion de données (SGBD). Les SGBD sont des logiciels génériques permettant le stockage et la manipulation efficace de données pour une très large gamme d'applications. Du point de vue pratique, les SGBD sont des logiciels sophistiqués, très largement utilisés, omniprésents dans le monde industriel. Du point de vue théorique, la conception de ces systèmes repose sur des fondements conceptuels, logiques, algorithmiques, en lien avec d'autres domaines de la science informatique. Le cours ira des aspects théoriques aux aspects systèmes des SGBD, en particulier ceux basés sur le modèle relationnel.

Les thèmes suivants seront couverts dans les 12 sessions du cours, qui seront accompagnées de travaux dirigés et de travaux pratiques sur ces mêmes sujets.

  1. Introduction à la gestion de données, le modèle relationnel, l'algèbre relationnelle, SQL
  2. Aspects logiques : calcul relationnel, indépendance du domaine, théorème de Codd
  3. Récursion, Datalog, langages à point fixe, logique du second-ordre
  4. Complexité computationnelle des langages de requêtes
  5. Contraintes sur les données : dépendances fonctionnelles, dépendances d'inclusion, poursuite
  6. Conception de schémas, normalisation
  7. Analyse statique : minimisation de requêtes, requêtes acycliques, réécriture de requêtes
  8. Vues virtuelles et vues matérialisées, maintenance de vues, mises à jour de vues, intégration de données
  9. Optimisation de requêtes : génération de plans, modèles de coût, histogrammes
  10. Indexation et stockage
  11. Transactions et gestion de concurrence : sérialisabilité, verrlage à deux phases, estampillage
  12. Extensions et applications : distribution, modèles non relationnels, applications Web et sécurité
La validation du cours se fera en partie par contrôle continu, et en partie via un examen final.

Bibliographie :
- M. Benedikt et P. Senellart, « Databases ». E. K. Blum et A. V. Aho, éditeurs, Computer Science. The Hardware, Software and Heart of It, p. 169‑229. Springer-Verlag, 2012. http://pierre.senellart.com/publications/benedikt2012databases.pdf
- S. Abiteboul, R. Hull et V. Vianu, Foundations of Databases. Addison-Wesley, 1995. http://webdam.inria.fr/Alice/
- H. Garcia-Molina, J. Ullman, J. Widom, Database Systems: The Complete Book. Pearson, 2008.


Projet de programmation 2

Responsable : Nathan Grosshans, Stefan Schwoon

Ce projet offre une expérience de programmation orienté objet et met en pratique les enseignements du cours de Programmation 2. Il est donc recommandé, mais pas obligatoire, de suivre ces deux modules ensemble. Spécifiquement, le projet sera mené en petits groupes (2 à 3 élèves) et dans un langage orienté objet (à priori Scala). Il permettra de mettre en pratique les notions d'héritage, sous-typage, généricité, etc. Cette année, le projet tournera autour d'un simulateur du jeu d'échécs.


Projet de logique

Responsable : Hubert Comon

Projet de base de données

Responsable : Cristina Sirangelo

Ce cours a pour objectif de transmettre les techniques et les modèles nécessaires à la conception d'un système d'information. Ce type de système se concentre sur la gestion efficace de gros volumes de données et doit mettre à disposition de l'utilisateur un ensemble riche de fonctionnalités d'accès et de manipulation de ces données. Dans un premier temps les élèves apprendront les techniques classiques de conception d'un système d'information. Cela concerne à la fois la conception des données et celle des opérations et se fait en plusieurs phases. Les élèves apprendront à passer de l'analyse du cahier des charges à la production d'un modèle du système de moins en moins abstrait, jusqu'à la production d'un modèle prêt à l'implémentation. Ces concepts seront mis en oeuvre sur un exemple concret d'un système d'information pour la gestion des données de plusieurs compagnies aériennes. Des documents de présentation de chaque phase du projet seront demandés aux élèves à l'issue de chaque phase de la conception. Les élèves devront enfin implémenter le système sous forme d'une application Web en utilisant une technologie de leur choix (par exemple des scripts PHP communiquant avec un serveur de bases de données MySQL). L'application implementée devra être présentée en fin de cours.


Contacter le département
Dernières modifications : le 01/02/2017