LDD3 Informatique cursus ENS

Lambda-calcul pur, (non-)terminaison, confluence, standardisation 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) Machines, lambda-calculs à substitutions explicites, et propriétés mathématiques d'iceux

À choisir entre :

Projet Programmation 2
Projet Base de Données
Projet Logique

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

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.

Introduction à la gestion de données, le modèle relationnel, l'algèbre relationnelle, SQL
Aspects logiques : calcul relationnel, indépendance du domaine, théorème de Codd
Récursion, Datalog, langages à point fixe, logique du second-ordre
Complexité computationnelle des langages de requêtes
Contraintes sur les données : dépendances fonctionnelles, dépendances d'inclusion, poursuite
Conception de schémas, normalisation
Analyse statique : minimisation de requêtes, requêtes acycliques, réécriture de requêtes
Vues virtuelles et vues matérialisées, maintenance de vues, mises à jour de vues, intégration de données
Optimisation de requêtes : génération de plans, modèles de coût, histogrammes
Indexation et stockage
Transactions et gestion de concurrence : sérialisabilité, verrlage à deux phases, estampillage
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.

Recherche de chaînes de caractères
Polynômes et transformée de Fourier rapide
Compression de données
Algorithmes d'approximation
Algorithmes et probabilités
Programmation linéaire

Préparation au IELTS.

Stage de recherche de 6 à 8 semaines dans une instutition de recherche hors région Île-de-France

Module libre à choisir dans une autre formation, validé par la direction des études.

À choisir entre :

Projet Programmation 2
Projet Base de Données
Projet Logique

À choisir entre :

Projet Programmation
Projet Base de Données
Projet Logique

Ce cours commence par les notions de base de cryptographie symétrique (chiffrement par blocs et par flot, fonctions de hachage, et cryptanalyse) et asymétrique (RSA, Diffie-Hellman et ElGamal), puis présente de façon informelle plusieurs techniques plus avancées :

Preuves zero-knowledge
Cryptographie distribuée
Cryptographie à base de couplages sur courbes elliptiques
Cryptographie à base de réseaux euclidiens (cryptographie post-quantique)
La Blockchain et bitcoin

THEORIE DE LA MESURE

    Tribus, mesures, théorème de Dynkin. Intégration abstraite : intégration des fonctions mesurables positives, théorème de convergence monotone et de Fatou ; fonctions intégrables, convergence dominée, de dérivation sous le signe somme.    Construction de mesures : théorème d'extension de Carathéodory. Cas de la mesure de Lebesgue sur R^d. Formule de changement de variables. Intégrale de Stieljes, mesures de Radon, théorème de représentation de Riesz.    Mesures produits, théorèmes de Fubini-Tonelli et Fubini-Lebesgue. Intégration par parties.    Espaces Lp, inégalité de Jensen, Hölder et Minkowski, théorèmes de densité (pas de preuves ici, la théorie générale n'est pas faite dans ce cours). Dérivée de Radon Nykodyn. INTRODUCTION AUX PROBABILITES    Introduction historique. Langage probabiliste et modélisation.    Variables aléatoires, espérance mathématiques. Loi d'une variable aléatoire et lois classiques. Moments, fonctions caractéristiques, théorème d'injectivité. Fonctions génératrices.    Indépendance: définitions et caractérisations. Théorème des coalitions. Tribu asymptotique, loi du tout ou rien, lemmes de Borel-Cantelli. Loi fortes des grands nombres. Applications.    Convergence en loi : définitions et caractérisations, théorème de Levy. Comparaison des différents modes de convergences. Théorème central limite. Applications.

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.

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. 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 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 Algorithmes de recherche (implémentation des dictionnaires)    recherche dichotomique    Arbres binaires de recherche, arbres équilibrés    Tables de hachage Implémentation des files de priorité    Tas, tas binomiaux, tas de Fibonacci 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 Partitions : union et recherche Paradigmes    Diviser pour régner    Algorithmes gloutons    Programmation dynamique 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)

Le cours est structuré comme suit :
Calculabilié :

Machines de Turing Fonctions récursives

Complexité :

Introduction aux classes de complexité La classe NP La classe PSPACE La classe PTIME La classe NLOGSPACE Inclusions strictes entre classes

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

Calcul propositionnel
Calcul des prédicats
Théorèmes d'incomplètude (Gödel)
Théorie décidables

Langages reconnaissables
Grammaires
Langages algébriques
Automates à pile
Analyse syntaxique
Reconnaissance par monoïde
Logique monadique du second ordre

Chapitre I : ensembles finis Chapitre II : ensembles infinis Chapitre III : relations binaires, structures ordonnées et points fixes Chapitre IV : récurrences Chapitre V : monoïdes Chapitre VI : groupes Chapitre VII : proba intro Chapitre VIII : chaîne de Markov Chapitre IX : théorie des jeux

Contenu

Circuits logiques, mémoire
Architecture câblée, RISC/CISC
Représentation de données (entiers, virgule flottane, texte)
Processus
Signaux
Entrée/sortie
Threads, sémaphores
Algorithmes distribués
Réseau