Anglais 1 (1er semestre, 3 ECTS)

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.

ALGO2 – Algorithmique avancée (2ème semestre, 6 ECTS)

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.

ACM – Projet Concours ACM (2ème semestre, 6 ECTS)

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 :
a) 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
b) 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 en salle machine (2h 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/

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/

Evaluation de performance

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

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)

ER-02 (2010) : Graphes et optimisation combinatoire

du 18 au 22 janvier 2010 — ENS Lyon

Intervenants :

Lieu des cours et emploi du temps

Tous les cours auront lieu dans l’amphithéatre B, au 3ème étage du bâtiment GN1 (bâtiment principal du site « Sciences » de l’ENS Lyon), ENS Lyon, 46 allée d’Italie, Lyon 7ème.

Lundi : Frédéric Maffray (9h30-12h45) ; Louis Esperet (14h-17h15)
Mardi : Louis Esperet (8h-10h) ; Andras Sebö (10h15-12h15)
Mercredi : Andras Sebö (8h-10h) ; Myriam Preissmann (10h15-12h15) ; Andras Sebö (14h-16h)
Jeudi : Myriam Preissmann (9h30-12h45)
Vendredi : Frédéric Maffray (9h30-12h45) ; Louis Esperet (14h-16h)

Louis Esperet (slides -> cours1, cours2,cours3)

Cours 1 (Lundi 14h-17h15) Coloration vs. coloration par listes

  • méthodes inductives (Thomassen)
  • déchargement

Cours 2 (Mardi 8h-10h) Graphes sans triangles et coloration

  • constructions
  • méthodes probabilistes (premier moment)

Cours 3 (Vendredi 14h-16h) Coloration fractionnaire, coloration d’hypergraphes

  • méthodes algébriques (Borsuk-Ulam)
  • méthodes probabilistes (Lemme Local de Lovasz)

Frédéric Maffray (fiche exercices -> télécharger Fiche)

Cours 1 (Lundi 9h30-12h45):

  • Introduction du concept de graphes parfaits
  • Graphes triangulés, décomposition par clique d’articulation, sommets simpliciaux, ordre d’élimination, algorithme MCS,
  • utilisation de ces structures pour résoudre les problèmes d’optimisation (coloration, clique max, stable max).
  • Représentation d’un triangulé comme graphe d’intersection de sous-arbres d’un arbre.
  • Exemples de graphes triangulés: graphes d’intervalles, graphes « splits ».

Cours 2 (Vendredi 9h30-12h45):

  • Relation entre nombre chromatique et orientation (Gallai-Roy)
  • graphes de comparabilité, ensembles partiellement ordonnés,théorème de Dilworth.
  • théorème de Lovasz (parfait = complémentaire de parfait)

Myriam Preissmann

Cours 1 (Mercredi 10h15-12h15) :

  • Flot maximum
  • Algorithme « Push-Relabel » et flots paramétriques.
  • Calcul de l’arête-connectivité d’un graphe non orienté avec, et sans calcul de flot max.

Cours 2 (Jeudi 9h30-12h45) :

  • Flot de coût minimum.
  • Les k-flots non nuls.
  • Théorème du 8-flot.

Andras Sebö (fiches d’exercices -> télécharger Fiche 1, Fiche 2)

Cours 1 Mardi (10h15-12h15)

  • Quelques modèles d’optimisation combinatoire.
  • Matroïdes, algorithme glouton et polytôpe associé.

Cours 2 (Mercredi 8h-10h)

  • Algorithme de l’intersection de deux matroïdes.
  • Applications.

Cours 3 (Mercredi 14h-16h)

  • Algorithme de couplage de cardinalité maximum (Edmonds).
  • Théorème de caractérisation lié (Tutte-Berge).
  • Applications et généralisations.

S’il y a des questions sur les exercices de la fiche fournie ci-dessus, vous pourrez les poser après le premier cours.

Bibliographie : Schrijver: Combinatorial Optimization; Lovász, Plummer: MatchingTheory; Lovasz: Combinatorial Problems and Exercises,

Autres informations pratiques

Voir la page des Ecoles du Master d’Informatique.

Correspondant local

Eric Thierry (prenom.nom@ens-lyon.fr)