Introduction

L'un des but de l'algorithmique est de trouver la meilleure manière pour résoudre un problème donné, et ce, en terme de complexité temporelle et spatiale de calcul. Mais il peut ne pas toujours sembler évident au premier abord qu'une meilleure solution existe. Ce n'est que par un exemple que nous pourrons voir que même si une solution nous semble optimale, il est souvent possible de faire encore mieux.

On considère le problème de la triangulation du polynome convexe. On se donne les n sommets d'un polygone convexe plan et une mesure de la distance séparant chaque couple de sommets. Le problème consiste à sélectionner un ensemble de cordes (segments joignant deux sommets non adjacents) tel qu'il n'y ait aucune intersection de cordes et que le polygone entier soit divisé en triangles. La longueur totale (somme des longueurs de toutes les cordes choisies) doit être minimale. On appelle un tel ensemble de cordes une triangulation minimale.

Le TP consiste à écrire une procédure "triangulation" trouvant la triangulation minimale. On cherchera tout d'abord à résoudre le problème par une méthode de type "essais successifs" puis dans une seconde partie on envisagera une solution de type "programmation dynamique".