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 : Trébuchet, philippe


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.


Semainier indicatif :

  • Semaine 1 : Collisions, algorithmes en N^4 puis N^3 puis N
  • Semaine 2 : Enveloppes convexes (projet)
  • Semaine 3 : Diamètre d'un nuage de points (projet)
  • Semaine 4 : Expressions régulières (projet début)
  • Semaine 5 : Automates algorithmes fondamentaux (projet suite)
  • Semaine 6 : Automates algorithmes optimisés (projet fin)
  • Semaine 7 : Voyageur de commerce, programmation dynamique
  • Semaine 8 : Voyageur de commerce, algorithmes d'approximation (projet)
  • Semaine 9 : Agencement de rayons, largeur de graphes
  • Semaine 10 : Synthèse théorique : NP complétude, algorithmique paramétrée.