Année : 2013

Cours : Guillaume Hanrot

TD : Marc De Visme & Pierre Pradic

Cours d’introduction aux modèles de calcul en informatique, indispensables pour formaliser la notion de calcul et d’algorithme et par conséquent au fondement de toute la science informatique. Présentation de la thèse de Church-Turing (« toutes les tentatives de formalisation de la notion intuitive d’algorithme sont équivalentes ») qui permet de définir formellement et précisément tout ce qui est calculable, et présentation des limites du calcul (fonction « non-calculable », problèmes ne pouvant pas être résolus par un algorithme).

Contenu indicatif du cours :

Premiers modèles de calcul :

• Automates finis / langages rationnels : déterministe vs non déterministe, équivalence automates / expressions rationnelles, minimisation, limites du rationnel avec pompage.
• Grammaires : hiérarchie de Chomski, équivalence hors contexte / automates à pile, limites du context-free avec pompage.

Thèse de Church-Turing :

• Machines de Turing : illustration avec robustesse par rapport aux variations (simulation des variantes par modèle standard), machines universelles.
• Illustration avec équivalence aux : Fonctions récursives, Lambda-calcul.

« Calculable » / « non-calculable » :

• Problèmes indécidables, dont l’arrêt.
• Théorème de Rice, théorème de point fixe de Kleene.

Introduction à la théorie de la complexité:

• Classes en temps, classes en espace, déterministes et non-déterministes.
• Résultats élémentaires d’inclusion et de séparation.
• Classes P et NP ; caractérisation de NP par certificats, théorème de Cook.

Prérequis : même si toutes les définitions et résultats seront donnés en cours, quelques connaissances de base sur les automates finis sont recommandées (cf programme de L1/L2/CPGE sur les automates).

Cours : Yves Robert

TD : Marc De Visme & Laureline Pinault

Ce cours propose une introduction approfondie aux concepts et techniques pour concevoir des algorithmes efficaces.

Cette introduction fait suite à la formation de base dispensée dans l’option Informatique des classes préparatoires et dans les L1 et L2 d’informatique. Ce module suppose donc une familiarité élémentaire avec les concepts de base: notion d’algorithme, de complexité, de correction; structures de données de base (tableaux, listes, arbres, etc.); algorithmes classiques de recherche et de tri, etc. Il s’agit d’une formation résolument orientée vers les concepts fondamentaux et non pas vers l’applications de techniques toutes faites.

Le cours est indépendant du cours de Théorie de la Programmation et du Projet Programmation. Les travaux dirigés font l’objet d’exercices « papier & crayon », et il n’y a aucune implémentation sur machine. On peut donc le suivre en le considérant comme un cours de mathématiques discrètes … mais ce serait dommage ! Les paradigmes algorithmiques prennent tout leur sens quand on les met en oeuvre. Nous conseillons donc vivement de suivre en parallèle le Projet Programmation où seront implémentées les techniques vues en cours d’Algorithmique.

Plan

Quelques sujets abordés dans ce module:

• Paradigmes: diviser-pour-régner, programmation dynamique, algorithmes gloutons;
• Complexité: coûts en temps et en espace, complexité pire cas, complexité en moyenne, analyse amortie;
• NP-complétude: les problèmes NP-complets, les réductions, les méthodes de résolution heuristiques;
• Grands thèmes: algorithmes de recherche & de tri, calcul matriciel (eh oui, des surprises!), systèmes cryptographiques, géométrie algorithmique, reconnaissance de motifs, etc…

Le cours se prolonge au second semestre par le cours Algorithmique Avancée.

Organisation

Le cours est organisé selon le schéma hebdomadaire suivant:

• 2h de cours;
• 2h de travaux dirigés.

La note de contrôle continu est obtenue à partir de plusieurs devoirs à la maison et d’un partiel organisé en milieu de semestre. Un examen final est organisé en fin de semestre.

Bibliographie

1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, Introduction to Algorithms, The MIT Press, 1990. Version française: Introduction à l’Algorithmique, 2e édition, Dunod, 2004.
2. G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi, Complexity and Approximation: Combinatorial optimization problems and their approximability properties, Springer Verlag, ISBN 3-540-65431-3.
3. Voir aussi la liste des problèmes d’optimisation NP tenue à jour par Pierluigi Crescenzi et Viggo Kann
4. Herbert S. Wilf,Algorithms and Complexity , A K Peters Ltd, ISBN: 9781568811789. La première édition est accessible en ligne.
5. La page wikipedia est claire et concise : http://fr.wikipedia.org/wiki/Théorème_de_Cook
6. Jon Kleinberg & Éva Tardos, Algorithm Design, Addison-Wesley, ISBN-10: 0321295358
7. M. R. Garey & D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, ISBN-10: 0716710455
8. D. Knuth, The Art of Computer Programming, Volumes 1-3, Addison-Wesley, ISBN-10: 0201485419
9. Polycopié du cours des années précédentes (largement repris dans le plan du cours de cette année).

Cours : Florent de Dinechin

TD : Florent de Dinechin & Guilhem Gamard & Alexandre Talon

L’objectif de ce module est de donner de solides notions de bases sur le fonctionnement d’un ordinateur, tant dans ses aspects matériels que dans ses logiciels de base. L’accent est mis sur ce qu’il y a de plus algorithmique dans cette problématique, toutefois le cours sera illustré de nombreuses parenthèses concernant la technologie contemporaine des circuits VLSI.

Plan indicatif

1. Petite histoire du calcul mécanique.
2. Représentation et transmission de l’information: des codes aux protocoles.
3. Circuits combinatoires: des portes aux opérateurs arithmétiques.
4. Circuits séquentiels: des registres aux automates.
5. L’ordinateur de Von Neumann.
6. Le processeur RISC.
7. Interruptions et temps partagé.
8. Entrées/sorties.
9. Mémoire virtuelle et notion de cache.

Bibliographie

• A. Tanenbaum. Architecture de l’ordinateur. 5e ed., Pearson Education, 2006
• F. Wahid: Digital Design. Wiley, 2006.
• Hennessy & Patterson. Computer Architecture: A Quantitative Approach. 3rd ed., Morgan Kaufmann, 2003.

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.

Cours/TP : Eddy Caron & Dominique Barbe & Julien Braine

Apprentissage de la syntaxe et des principes de plusieurs langages de programmation : C / C++ / Caml / Python, et d’autres pour les étudiants ayant déjà une expertise de programmation.

Cours : Véronique Rancurel, Hélène Windish, Karen Rizo, David Alzapiedi (Veronique.Rancurel)

Hommes de Science, Science pour l’homme. Ce thème structure le cours d’anglais et sous-tend un travail d’expression écrite, compréhension écrite, expression orale, compréhension orale dans les quatre groupes de niveau. Rapidement, l’accent sera mis sur les compétences orales.

Cours : Natacha Portier

TD : Guilhem Gamard & Alexis Ghyselen

Cours de Logique Mathématique, partant des bases de la logique jusqu’aux résultats majeurs du tournant des années 30 (dont les théorèmes d’incomplétude de Gödel).

Contenu indicatif du cours :

Théorie naïve des ensembles :

•  Constructions en théorie des ensembles, théorème de Cantor-Bernstein.
• Ordinaux, cardinaux, bonne fondation, hiérarchie de Veblen.
• L’axiome du choix et ses différentes formes.

Théories du premier ordre :

• Langages du premier ordre, système de déduction (déduction naturelle).
• Notion de théorie du premier ordre, d’extension conservative.
• Exemples: l’Arithmétique de Peano (PA) et la Théorie des ensembles de Zermelo-Fraenkel (ZF).

Modèles de Tarski :

• Structures, notions d’isomorphisme et d’équivalence élémentaire
• Théorèmes de complétude, de compacité et de Löwenheim-Skolem.
• Applications à PA et à ZF.

Théorèmes d’incomplétude :

• Indécidabilité de l’arithmétique, lien avec les fonctions récursives,
• Théorèmes d’incomplétude de Gödel.

Prérequis : pas de prérequis particulier si ce n’est une connaissance élémentaire des objets manipulés (ensembles, connecteurs/quantificateurs logiques, démonstrations usuelles en mathématiques).

Cours : Anne Benoit

TD : Valentin Le Fèvre & Valentin Lorentz

C’est la suite du cours d’algorithmique ALGO1 proposé au premier semestre. Le cours est centré principalement sur les graphes (algorithmique et éléments de théorie), et offre également une courte introduction à l’algorithmique des mots. Les livres de références sont :

• Introduction to Graph Theory (West) pour la théorie des graphes et certaines questions algorithmiques.
• et bien sûr toutes les références du cours d’ALGO1 !

Contenu indicatif du cours :

• Compléments sur les structures de données utiles et sur les paradigmes
• Algorithmique des graphes (arbres, parcours, connexité, arbres couvrants de poids min, plus courts chemins, couplages, flots)
• Algorithmique des mots (recherche de motifs)

Prérequis : avoir suivi le cours d’ALGO1 au premier semestre, ou bien maitriser les premiers chapitres du Cormen.

Cours : Michaël Rao

TD : Guilhem Gamard & Rémy Grunblatt & Etienne Moutot

Objectif

L’objectif de ce cours est d’apprendre à programmer des applications interagissant avec le système, et implicitement de comprendre le fonctionnement du système d’exploitation.

Nous aborderons les points suivants : la gestion des entrée/sorties, des fichiers, des processus, de la mémoire, des communications réseau. Il y aura également une sensibilisation aux problèmes de sécurité. Le système choisi est Linux et le langage le C/C++. Mais comme le cours suivra au plus près la norme POSIX, les connaissances acquises seront aisément transportables aux autres systèmes.

Bibliographie

•  Jean-Marie Rifflet et Jean-Baptiste Yunès, « UNIX : programmation et communication », Dunod, 2003.
•  Andrew S. Tanenbaum et Herbert Bos, « Modern Operating Systems, 4th Ed »,Pearson 2015..

Cours : Guillaume Aubrun

TD : Alice Pellet-Mary & ?

Présentation

Ce cours propose une introduction approfondie aux concepts de probabilités, avec de nombreuses illustrations en informatique et en mathématiques discrètes (algorithmes probabilistes, analyse en moyenne, méthode probabiliste en combinatoire).

Plan

• Fondements de la théorie des probabilité:Espace d’événements, espace probabilité, probabilité conditionnelle, indépendance ;
• Variables aléatoires réelles: exemple de lois, moment, caractérisation ;
• Vecteurs aléatoires
• Inégalités de concentration : Markov, Chebychev, Chernoff, Azuma …
• Théorèmes limites : loi forte des grands nombres, théorème central limite
• Chaînes de Markov discrètes
• Quelques notion de statistiques
  

Organisation

Le cours est organisé selon le schéma hebdomadaire suivant:

• 32h de cours;
• 32h de travaux dirigés.

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.

TD/TP : Eric Thierry & Alexandre Talon & Paul Iannetta

Présentation

L’écriture d’un programme est souvent l’objet d’un compromis entre son temps d’exécution (efficacité algorithmique de la solution codée) et son temps de développement (réflexion, implantation et débuggage). Deux attitudes caricaturales sont :

1. rechercher la solution la plus efficace théoriquement (c.-à-d. quand n temps vers l’infini) même si elle est très compliquée à implémenter ou
2. implémenter la première idée venue.

Le but de ce module est de s’entraîner à la résolution effective de problèmes algorithmiques. Pour cela, il faudra trouver un équilibre entre ces deux façons d’agir.

Le choix de la solution à retenir repose typiquement sur le temps disponible d’une part et les caractéristiques particulières des instances à résoudre d’autre part (taille, décomposition éventuelle,…). Le choix de la structure de données est également un paramètre crucial d’efficacité.

Dans ce module, nous étudierons différents problèmes (algorithmiques purs) que nous cherchons à résoudre effectivement en écrivant un programme (en C, C++, Java…) qui sera testé/validé sur des jeux de données.

Les objectifs sont les suivants :

• Mieux comprendre comment se comportent en pratique les algorithmes classiques (de graphes, arithmétique, géométrie…)
• S’exercer à écrire des programmes rapidement, mais surtout éviter au maximum d’avoir à déboguer (notamment en écrivant d’abord un pseudo-code)
• Enfin, pour ceux qui le souhaitent, se préparer au concours de programmation ACM-ICPC. La première étape de ce concours a lieu chaque année fin octobre, en général deux équipes de 3 personnes y participent à l’ENS Lyon.

Le module aura lieu au second semestre, sous la forme de TD/TP en salle machine (3h par semaine).

Plan

Voici à titre indicatif une liste des sujets qui seront abordés :

• Graphes : plus courts chemins, composantes fortement connexes, flots, couplages, union-find
• Géométrie : enveloppe convexe, algorithmes de balayage, tests d’inclusion
• Arithmétique : tests de primalité

Références

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, Introduction to Algorithms (Second Edition).
• Site du concours ACM-ICPC : http://icpc.baylor.edu/

Cours : Véronique Rancurel, Hélène Windish, Karen Rizo, David Alzapiedi (Veronique.Rancurel)

Scientific english level B2