Algorithmique et Programmation Parallèles et Distribuées

Algorithmique et Programmation Parallèle et Distribuée

Cours du M1 2015-2016, premier semestre.

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 et distribués efficaces, et aborde leur mise
en œuvre pratique sous forme de TPs.
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 quatorze séances de cours seront accompagnées de sept séances de
TDs et de sept séances de TPs. Les TPs auront pour but l’initiation
la programmation parallèle et distribuée par passage de messages
(MPI). Un petit projet de programmation est organisé sous forme de
devoir à la maison.

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.
  • Algorithmique distribuée: modèles, élection, consensus, détection de
    terminaison
  • 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, du devoir à la maison de programmation, et d’un
examen final.

OLD – Stage de recherche M1, évaluation

Préambule: contactez D. Hirschkoff (ou votre tuteur) si vous avez des problèmes durant le stage, ou pour toute question.

Re-préambule : vous ne pouvez pas supposer qu’un(e) spécialiste du domaine où vous avez travaillé en stage relira votre rapport ou assistera à votre soutenance. Il faut donc que vous adaptiez votre rendu en conséquence. Cela ne signifie pas jeter toute la technique à la poubelle, mais il faut être capable de choisir les points techniques que vous souhaitez traiter, et de les amener. En règle générale, les étudiants de M1 ont plutôt tendance à vouloir mettre trop de technique, comme s’ils s’adressaient à leur encadrant de stage.

Rapport

Vous devez envoyer votre rapport à Daniel Hirschkoff au plus tard le 28 août 2018 à midi (heure de Lyon), par mail. 20 pages maximum, vous pouvez au besoin pointer vers une « annexe » en ligne (l’annexe peut être un fichier contenant des preuves, un fichier contenant tous vos résultats numériques, un article écrit avec vos encadrants, du code que vous avez produit..). Vous pouvez écrire en anglais, mais ne le faites que si votre niveau d’anglais rend cela possible. Il est souhaitable que votre encadrant valide votre rapport en le relisant (ce qui signifie l’écrire suffisamment en avance pour qu’il y ait le temps d’une relecture et de corrections).

Au sujet du contenu:

  • décanter / situer

sachez expliquer et motiver la question que vous avez étudiée: d’où vient-elle, pourquoi on se pose cette question, quel était l’état de la science au début de votre stage, quels sont les travaux existants pertinents.

  • présenter

si vous avez 10 résultats, ne les présentez pas tous de façon détaillée, faites un « travail éditorial » de sélection; si vous en n’avez aucun, racontez ce qui aurait pu marcher, quelles pistes ont été tentées.

  • commenter la démarche

vous êtes encouragés à raconter dans votre rapport comment se sont passées les choses: les pistes qui n’ont pas marché, des interactions/collaborations avec votre encadrant et d’autres chercheurs dans le cadre du stage, des initiatives que vous avez prises.

  • ne mettez pas les aspects expérimentaux sous le tapis: si vous avez codé quelque chose de non ridicule, ou utilisé des outils, parlez-en (taille du  code, outils/langages utilisés, utilisations futures escomptées, choix d’implémentation, etc.).

Présentation

Informations préliminaires: les soutenances auront lieu les 5 et 6 septembre 2018, à l’ENS Lyon, dans les salles B1 et B2. 20 minutes de soutenance, suivies de 5 minutes de questions. Le planning est disponible ici.

Faites au moins deux répétitions! On vous coupera la parole brutalement au bout du temps imparti, et c’est une catastrophe si à ce moment-là vous n’avez pas encore abordé la partie 3 de votre expose qui en comporte 5. C’est aussi catastrophique si vous terminez au bout de 8 minutes. Mettez-vous la pression, faire une présentation propre/claire n’est pas un exercice qui s’improvise, et c’est très différent d’une discussion scientifique à bâtons rompus. Pour ce qui est du contenu de la présentation, mêmes remarques que pour le rapport. Cela ne sert a rien de noyer l’auditoire sous des tonnes de détails techniques. Tâchez de faire comprendre la question que vous avez traitée, et votre contribution, de façon compréhensible pour un auditoire non spécialiste, tout en évitant de trop glisser sous le tapis les choses plus techniques.

Points organisationnels : ayez vos transparents au format pdf sur une clef usb, pour le cas où il y aurait les sempiternels problèmes techniques pour la projection.  Ayez de quoi projeter vos transparents (nous fournissons le vidéoprojecteur, pas la machine). Une bonne solution consiste à vous mettre d’accord entre étudiants qui présentent à la même session, afin de partager un ordinateur, que l’on connecte pendant la pause qui précède la session).

Vous pouvez sauf cas particulier assister à la présentation de vos camarades, à partir du moment où ceux-ci sont d’accord.

Vous pouvez présenter en français ou en anglais, mais ne soyez pas prétentieux, n’optez pour l’anglais que si votre niveau le permet.

PROG – Théorie de la Programmation (1er semestre, 6 ECTS)

Cours : Daniel Hirschkoff

TD : Adrien Durier & Alexis Ghyselen & Julien Braine

Il existe de nombreux langages de programmation, et ce foisonnement est sans cesse alimenté par l’apparition de nouveaux langages. Ce cours propose une introduction à un certain nombre de méthodes ouvrant la voie à l’analyse rigoureuse des langages de programmation et des programmes. Ces méthodes fournissent un cadre dans lequel représenter les programmes, et prouver des propriétés sur leur comportement à l’exécution. Ce faisant, il est possible d’analyser des transformations de programmes, d’établir des comparaisons entre langages de programmation, et, plus généralement, de prendre du recul par rapport à la richesse du paysage des langages de programmation.

Les sujets suivants sont traités dans le cours:

  • définitions inductives, sémantique opérationnelle des programmes (pour un mini-langage impératif et un mini-langage fonctionnel)
  • garanties sur l’exécution des programmes: sémantique axiomatique (logique de Floyd-Hoare), typage
  • propriétés abstraites sur l’exécution des programmes, notions de réécriture: terminaison, confluence, unification

Bibliographie

  • G. Winskel, The semantics of programming languages, MIT Press.
  • J. Reynolds, Theories of Programming Languages, CUP.
  • F. Baader et T. Nipkow, Term Rewriting and All That, Cambridge University Press
  • une page web liée au cours sera disponible à partir de la page http://perso.ens-lyon.fr/daniel.hirschkoff

Le cours est organisé selon le schéma hebdomadaire suivant: 2h de cours; 2h de travaux pratiques sur machine ou de travaux dirigés. En travaux pratique, une initiation à l’assistant de preuves Coq sera
proposée.

Prérequis: une expérience de la programmation, quel que soit le langage, est souhaitée.

PROJ2 – Projet Programmation (2ème semestre, 6 ECTS)

Cours : Daniel Hirschkoff

TP : Etienne Moutot & Valentin Lorentz

Prérequis : Connaissances de base en algorithmique, et connaissance (même peu avancée) du langage OCaml, langage qui est imposé pour ce cours.

Objectif

L’objectif de ce module est multiple :

  • apprendre ou consolider des pratiques de programmation ayant trait à la structuration du code et à la modularité ;
  • apprendre des notions en lien avec l’exécution des programmes (interprétation, transformation de programmes) ;
  • mieux comprendre la programmation fonctionnelle en OCaml ;
  • travailler en binôme à un projet logiciel, en organisant le travail sur plusieurs semaines.

Organisation

Le module comprend une série de cours magistraux, accompagnée de séances sur machine. Les étudiants sont répartis en binômes, suivant leur expérience de la programmation et leur connaissance de Caml. 3 ou 4 rendus sont proposés au long du semestre, dont la difficulté est adaptée au niveau d’expérience du binôme. L’évaluation se fait à la fois sur la qualité du logiciel obtenu, et sur l’organisation du travail au long du semestre.

Une page www sera mise à disposition afin de rassembler des ressources utiles pour le cours.

Calcul formel

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

Optimisation et programmation linéaire

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

ER03: Problèmes de satisfaction de contraintes

21-25 Janvier 2013, ENS Lyon.

Orateurs: Manuel Bodirsky, Michael Pinsker.

Une description plus complète se trouve sur la version anglaise de cette page.

Lundi 21/01. Introduction. Exemples de CSPs de l’intelligence artificielle. Les formules primitives positives et des preuves de NP-difficulté. Des algorithmes efficaces. La conjecture de Feder et Vardi.

Mardi 22/01. L’approche d’algèbre universelle. La correspondance de Galois Inv-Pol, le noyau d’une structure, la conjecture de faisabilité, les operations cycliques.

Mercredi 23/01. Des CSPs sur des domaines infinis. Les limites de Fraïssé, le théorème de Ryll-Nardzewski. La correspondence Inv-Pol sur des domaines infinis. La topologie de convergence simple. Les graphes de Henson et autres exemples.

Jeudi 24/01. Introduction à la théorie de Ramsey. Fonctions canoniques. Classification de problèmes de Graph-SAT

Vendredi 25/01. Problèmes ouverts, projets de recherche.

Inscription

Inscription gratuite, dans la limite des places disponibles. L’inscription n’inclut ni le logement, ni la nourriture, mais un accès au restaurant universitaire de l’ENS Lyon est possible pour les participants le midi. L’inscription est à compléter avant le 8 janvier en cliquant ici, remplissant le formulaire et envoyant le mail. Une confirmation vous sera envoyée dans les meilleurs délais.

Alternatvement, vous pouvez copier/coller le formulaire suivant, le remplir et l’envoyer par courrier électronique à research.school.1@gmail.com, avec le sujet « Registration form — research school 3 »


First Name:
Last Name:
Institution:
Position (MSc student, PhD student, researcher, etc.):
E-mail address:

wishes to attend the research school ‘Constraint satisfaction problems’, taking place at ENS Lyon, from Jan. 21 to Jan. 25.

Géométrie discrète et images numériques

Programme de l’UE

L’objectif de ce cours est d’introduire les notions de base d’analyse et de traitement d’images. Après quelques séances durant lesquelles on se focalisera sur des problèmes de représentation de données, on se focalisera plus particulièrement sur des problèmes algorithmiques et théoriques liés à l’analyse géométrique de formes numériques. Ainsi, on sera amené à s’intéresser des outils de géométrie discrète, de géométrie algorithmique voire d’arithmétique et de combinatoire.

Le cours sera accompagné de séances de TP ayant comme objectif de s’intéresser à l’implémentation de certains outils théoriques présentés dans le cours.

Plan indicatif:

  • Représentation images/formes
  • Traitement et analyse d’images (filtrage, segmentation)
  • Géométrie discrète pour l’analyse de formes
  • Géométrie algorithmique et structures de données

Pré-requis: Des connaissances élémentaires en algorithmique

Livres:

  • « Géométrie discrète et images numériques », D. Coeurjolly, A. Montanvert and J.-M. Chassery, Ouvrage collectif, Traité IC2, Hermès, 416 pages, 2007
  • « Computational Geometry: Algorithms and Applications », Mark de Berg, TU Eindhoven (the Netherlands) Otfried Cheong, KAIST (Korea),Marc van Kreveld, Mark Overmars, Utrecht University (the Netherlands), Springer-Verlag

Fiche d’évaluation

Intervenants

Cryptographie et sécurité

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

Analyse de programmes et vérification de systèmes

Programme de l’UE :

  1. Structures ordonnées
    Ordres et topologies. Points fixes. Approximations et correspondances de Galois. Domaines de Scott
  2. Sémantiques dénotationnelles
    Domaines d’interprétation. Sémantique directe et par continuations.

    Correction et complétude de la Sémantique Axiomatique.
  3. Analyse de programmes
    3.1. Analyses dynamique et statique. Systèmes de types.

    3.2. Interprétation abstraite : principes, élargissement/rétrécissement,
    analyses avant et arrière, analyse polyédrale.
  4. Vérification
    4.1. Logiques modales. Structures de Kripke. Model checking.

    4.2. Systèmes réactifs. Logiques temporelles LTL et CTL.

Intervenants

ER 04 (2011) : Separation logics and applications

Cette école de recherche se déroulera durant la semaine 31 janvier – 4 février 2011. Les cours de cette école seront dispensés en anglais.

Intervenants:

  • Hongseok Yang (Lecturer, Queen Mary University of London, UK)
  • Alexey Gotsman (Assistant Professor, IMDEA, Spain)
  • Matthew Parkinson (Researcher, Microsoft Research, Cambridge, UK)

Voir la version anglaise de cette page pour un descriptif du cours, et des informations à jour (remarque importante: les cours seront dispensés en anglais).

Responsable local: Daniel Hirschkoff (LIP), avec l’aide bienveillante d’Etienne Lozes (LSV).