Catégorie : Ancien cours de M1

Programme de l’UE :

• Pgcd et pgcd étendu : algorithmes d’Euclide et d’Euclide étendu (coût algébrique, coût arithmétique, propriétés, …), algorithme quasi-linéaire de Knuth et Schonhage.
• Algorithmes sur les polynômes : évaluation, interpolation. Arbre des produits. Algorithmes quasi-linéaires pour l’évaluation multi-points et l’interpolation.
• Algorithmique de l’algèbre lineaire : pivot de Gauss (sur un corps), applications (calcul d’image, de noyau, de déterminant, systèmes linéaires), méthodes multimodulaires et relèvement de Hensel sur Z ou K[X].
• Résultant, élimination ; application au calcul de l’intersection de deux courbes algébriques planes.
• Factorisation des polynômes sur Z/pZ : algorithme de Berlekamp, de Cantor-Zassenhaus, relèvement de Hensel d’une factorisation.
• Application aux codes correcteurs d’erreurs : codes de Reed-Solomon. Algorithmes de décodage, de décodage en liste.

Nota: programme incomplet — à titre d’indication, voici le programme du cours de l’an dernier:

1. Évaluation en un point : schéma de Horner, interprétation en termes de division euclidienne, optimalité dans le modèle de complexité non scalaire (pgms straight-line).
2. Multiplication : racines (primitives) n-ièmes, transformée de Fourier discrète (DFT) et sa version rapide (FFT), DFT inverse, multiplication de polynômes par FFT, algorithme de Schonhage et Strassen, fonctionM(n).
3. Division euclidienne : calcul rapide du reste à partir du quotient, polynômes réciproques, itération de Newton pour l’inversion modulo x^n en O(M(n)), équivalence de complexité entre division et multiplication.
4. Évaluation multipoint et interpolation : algorithme de Lagrange, algorithme quadratique, arbre des sous-produits et algorithmes quasi-linéaires (somme de fractions, evaluation, interpolation), cas d’une progression géometrique (algorithme de Aho, Steiglitz, Ullman).
5. Pgcd et pgcd étendu : algorithmes d’Euclide et d’Euclide étendu (analyse de coût, propriétés, …), algorithme quasi-linéaire de Knuth et Schonhage.
6. Évaluation polynômiale en arithmétique flottante : standard IEEE 754, notations pour l’analyse des erreurs d’arrondi, stabilité (directe, inverse), conditionnement, error-free transforms et algorithmes TwoSum et TwoProd,technique de compensation appliquée au schéma de Horner.
7. Algorithmique de l’algèbre lineaire : pivot de Gauss (sur un corps, sur Z ou K[X]), applications (calcul d’image, de noyau, de déterminant, systèmes linéaires) méthodes multimodulaires
8. Résultant, élimination ; application au calcul de l’intersection de deux courbes algébriques planes ; sous-résultants et applications à l’analyse des variantes de l’algorithme d’Euclide étendu sur Z[X]
9. Rappels sur les corps finis ; factorisation des polynômes sur les corps finis : algorithme de Berlekamp, de Cantor-Zassenhaus
10. Relèvement de Hensel d’une factorisation ; bornes sur les facteurs d’un polynôme à coefficients entiers. Algorithme de Berlekamp-Zassenhaus pour la factorisation des polynômes à coefficients rationnels.

Intervenants

Cours: Guillaume Hanrot et Jean-Michel Muller

TDs: Silviu Filip

Programme de l’UE :

1. Les bases. Programme linéaire.
   Algorithme du Simplexe. Lemme de Farkas. Dualité. Ecarts complémentaires. Analyse de sensitivité.
2. Programmation en nombres entiers.
   Polyèdres et Polytopes. Relaxation fractionnaire. Matrices totalement unimodulaires et TDI. Arrondis déterministes et aléatoires. Générations de coupes.
3. Modélisation et applications classiques.
   Flots et réseaux de transport. Stratégies mixtes (jeux matriciels). Codes correcteurs. Compressed sensing.
4. Extensions possibles.
   Ellipsoide. Oracles de coupe (Grotschel Lovasz Schrijver). Programmation semi-définie (Capacité Shannon, Fonction Theta, coupe minimum de Goemans et Williamson). Minimisation des fonctions sous-modulaires.

Intervenants

Cours: Stephan Thomassé

TDs: Guillaume Aupy

Programme de l’UE :

La cryptographie a pour objectif de sécuriser les communications, en présence de parties malhonnêtes. Cette discipline a de nombreux liens avec l’informatique théorique (théorie de la complexité, preuves de sécurité) mais également de nombreuses retombées pratiques : Les protocoles cryptographiques sont omni-présents dans la vie quotidienne (commerce électronique, cartes de paiement, vote électronique, etc).

Ce cours est une introduction aux différents aspects de la cryptographie contemporaine. Nous aborderons les thèmes suivants :

• Chiffrement symétrique
• Chiffrement asymétrique
• Fonctions de hachage cryptographiques
• Authentification
• Générateurs pseudo-aléatoires
• Preuves à divulgation nulle de connaissance
• Infrastructure de clés publiques
• Crytanalyse
• Sécurité prouvée
• Partage de secret

Nous décrirons également plusieurs applications pratiques des concepts théoriques développés : PGP, TLS/SSL, vote électronique.

Intervenants

• Damien Stehlé, Pr ENS Lyon
• Benoit Libert
• Vincent Neiger

Programme de l’UE

Le parallélisme est devenu incontournable en informatique, le moindre processeur étant multi-cœurs. Cette UE a pour objet la conception d’algorithmes parallèles efficaces et leur mise en œuvre pratique.
Les séances de cours auront pour objet les modèles théoriques utilisés pour la conception et l’analyse des algorithmes et l’étude de problèmes algorithmiques particuliers (complexité, définition et analyse d’algorithmes, algorithmes d’approximations, etc.).
Les séances de cours seront accompagnées de six séances de TDs et de six séances de TPs. Les TPs auront pour but l’initiation à la programmation parallèle par passage de messages (MPI).

Plan indicatif des cours:

– Modèle théorique des réseaux de tri
– Modèle théorique des PRAMs
– Algorithmique sur anneau et grille de processeurs: produit matrice-vecteur, produit matrice-matrice, stencil 2D, etc.
– Ordonnancement de graphes de tâches avec et sans communications, avec ou sans contraintes de ressources: complexité, algorithmes d’approximations et heuristiques
– Analyse de dépendance et parallélisation automatique
– Exemple d’algorithme pour GPU

La note de contrôle continu est établie à partir d’un partiel organisé en milieu de semestre et d’un devoir à la maison de programmation.

Intervenants

• Frédéric Vivien, DR INRIA
• …

Programme de l’UE

L’objectif principal de ce cours est de présenter les techniques de base servant à l’évaluation qualitative et quantitative des performances de systèmes de communication et informatiques. L’accent sera mis sur les aspects théoriques mais sera illustré par l’analyse de plusieurs exemples de systèmes réels (réseaux de communication, de transport, de logistique). Ce cours comprendra aussi une introduction aux statistiques et abordera des questions de méthodologie expérimentale.

Plan indicatif :

1. Rappels de probabilités
2. Schémas de simulation & génération aléatoire
3. Chaînes de Markov à temps discret
4. Chaînes de Markov à temps continu & Files d’attente
5. Processus de décision markoviens
6. Réseaux de Petri
7. Statistiques

Intervenants

• Eric Thierry, MdC ENS Lyon (page web du cours)
• ….

Pré-requis

• Des connaissances élémentaires de probabilités sont fortement recommandées (typiquement cf le cours « Probabilités » du L3 Informatique dont le contenu est décrit dans les pages L3)

Programme de l’UE

Le compilateur est un outil fondamental pour l’informaticien, qui se situe au coeur de tout développement informatique. Le but de ce cours est de donner aux étudiants une compréhension globale du fonctionnement d’un compilateur en présentant les aspects fondamentaux de la compilation de code natif pour les langages impératifs et à objets. Un accent particulier sera mis sur les méthodes d’analyse sémantique et d’optimisation de programmes utilisées dans les compilateurs récents (icc, gcc, etc). Ces notions de base seront complétées par un panorama des développements récents de la recherche dans le domaine. Enfin, on insistera sur la mise en oeuvre logicielle des différents aspects de la compilation à travers l’écriture d’un compilateur pour un langage impératif simple dans le cadre des travaux pratiques.

Voir la page www du cours.

Plan indicatif du cours

1. Analyse lexicale
   Automates finis, théorie des analyseurs lexicaux, optimisations, outil Lex.
2. Analyse syntaxique
   Grammaires algébriques, analyse descendante/ascendante, gestion des erreurs, outil Yacc.
3. Grammaires attribuées
   Evaluation dynamique, test de Kennedy-Warren, grammaires S-attribuées, schémas de traduction.
4. Compilateur simple
   Organisation de la mémoire, traduction dirigée par la syntaxe, algorithme de Sethi-Ullman.
5. Fonctions
   Activations, pile de controle, conventions d’appel, fonctions imbriquées.
6. Production de code intermédiaire
   Représentations intermédiaires, forme SSA, optimisations élémentaires.
7. Sélection d’instructions
   Pavage, complexité, programmation dynamique, algorithme de Koes & Goldstein
8. Allocation de registres
   Interférences, coalescing, complexité, algorithmes « historiques » (Chaitin, Briggs), algorithmes de référence (IRC, Linear scan).
9. Analyse de programme
   Analyse statique/dynamique, complexité, analyse de flot de données, exemples, limites.
10. Compilation polyédrique
    Contrôle statique, opération, analyse de dépendences, ordonnancement, génération de code.
11. Compilation des langages à objet
    Descripteurs, liaison dynamique, résolution des méthodes abstraites, héritage multiple.

Références

1. Modern compiler implementation in C. Andrew Appel. Cambridge press.
2. Compilers: principles, techniques and tools. Alfred Aho, Monica Lam, Ravi Sethi et Jeffrey Ullman. Interéditions.
3. Parsing theory, volumes I et II. Seppo Sippu and Eljas Soisalon-Soininen. EATCS Monographs on Theoretical Computer Science.
4. Principles of program analysis. Flemming Nielson, Hanne Riis Nielson, Chris Hankin. Springer.
5. Theory of linear and integer programming. Alexander Schrijver. Wiley.

Intervenants

• Christophe Alias, CR Inria
• Guillaume Iooss, doctorant ENS Lyon

Résumé

Cet enseignement se focalise sur les aspects algorithmiques des systèmes distribués (ou répartis). La mise en œuvre d’algorithmes distribués pour résoudre les problèmes de communication, d’allocation de ressources et de synchronisation seront abordés. Ainsi les  les problèmes d’élection de leader, les algorithmes à vagues, la détection de terminaison, les algorithmes de routages, la tolérance aux fautes, l’auto-stabilisation, etc. sont autant d’illustrations des points qui seront abordés dans cet enseignement. Différents types de mise en oeuvre de systèmes distribués seront également abordés au travers d’ERLANG, de CORBA ou encore de l’intergiciel DIET.

Intervenants

• Eddy Caron, MdC ENS Lyon
• Vincent Lanore, doctorant ENS Lyon

Langue

Anglais ou Français en fonction de la demande.