Introduire l'étudiant à l'algorithmique avancée et à ses applications, en mettant l'accent sur le domaine des jeux vidéo.
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.
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.
Formule pédagogique : Cours Magistral
| 0784 | Programme court de deuxième cycle en informatique pour étudiants en séjour d'études |