Objectif

Introduire l'étudiant à l'algorithmique avancée et à ses applications, en mettant l'accent sur le domaine des jeux vidéo.

Contenu

Revue des notions fondamentales de l'algorithmique: Algorithmes voraces, méthode diviser-pour-régner, programmation dynamique, algorithmes probabilistes et parallèles. Théorie de la NP-complétude. Principales classes de complexité. Mesures de complexité : temps et espace mémoire.

Formules pédagogiques

Applications: Détection de collision en temps réel: géométrie algorithmique, volumes englobants, hiérarchies de volumes, partitionnement spatial en 2D et en 3D, arbres BSP, méthodes basées sur la convexité, optimisation par utilisation de caches, etc. Algorithme sur les graphes: recherche de chemins optimaux, A*, aide à la décision, etc.