L'unité d'enseignement ENSIN6U4
« Géométrie algorithmique »

Présenter, analyser et implémenter des algorithmes de géométrie algorithmique et de graphes.

• Triangulation d'un polygone et applications. Cartes et graphes planaires, localisation d'un point. Recherche et structures de données multidimensionnelles.
• Enveloppes convexes, diagrammes de Voronoï et triangulations de Delaunay : propriétés, algorithmes, applications.
• Flot maximum et flot de coût minimum : dualité, algorithmes et applications. Connexité : théorèmes de Menger et liens avec le flot. Couplages.

ENSIN3U1 Algorithmique

Rendu de projets notés ; pas d'examens.