Aller au contenu  Aller au menu Aller à la recherche

accès rapides, services personnalisés

Rechercher

Recherche détaillée

Contact

Jacqueline Collet-Narboni
Responsable administrative

courriel : jacqueline.collet-narboni@upmc.fr

Cette page est la page de garde du site consacré à l' unité d'enseignement « Conception Pratique de l'Algorithmique (4I505) »

Ressources annuelles

Responsable de l'UE : Bui-Xuan, binh-minh


Site de l'UE

Description de l'UE :

Cette UE consiste en l'étude et la mise en oeuvre efficace d'algorithmes usuels, i.e. non triviaux, en développement logiciel. Le spectre des problèmes abordés couvrira un vaste panorama allant du traitement de texte à la géométrie algorithmique. On étudiera tout autant le fondement structurel de ces domaines que solutions algorithmiques et un soin particulier sera pris pour leur implantation dans des langages de programmation modernes.

La séance typique de l'UE se déroule clavier aux doigts et feuilles de brouillon à portée de mains.


Semainier indicatif :

  • Semaine 1 : Introduction à la géométrie algorithmique: collision, conteneur, diamètre (algorithmes en N^4 puis N^3 puis N).
  • Semaine 2 : Enveloppe convexe: pré-calcul, tri radix, produit scalaire, produit vectoriel.
  • Semaine 3 : Diamètre et rectangle minimum (kick-off du projet principal): paires antipodales, AABB (axis-aligned bounding box), OBB (oriented bounding box).
  • Semaine 4 : Arbre couvrant (mini projet): algorithme linéaire, testbeds, RGG (random geometric graphs), échantillon de contrôle.
  • Semaine 5 : Plus courts chemins et arbre de Steiner (mini projet): algorithme de programmation dynamique, problèmes NP-difficiles, heuristique.
  • Semaine 6 : Arbre de Steiner avec et sans restriction (mini concours de programmation): I/O des échantillons de test, évaluateur, heuristiques de recherche locale (local searching) sans perte et avec pertes.
  • Semaine 7 : k-means (mini projet): jeux de données des îles (de St Louis, de Man, de Malte, de France), algorithmes de répartition d'espace multi-dimensionnel.
  • Semaine 8 : Plus sur la programmation dynamique (mini projet): préparation aux concours de programmation en ligne.
  • Semaine 9 : Gestion de factures et réservations (!!): structure d'arbres de segments, indexage, routines sous-linéaires et logarithmiques.
  • Semaine 10 : Voyageur de commerce et variants (mini concours de programmation): heuristique de recherche locale multi-critère.