Définition
Un algorithme est une suite finie et non ambiguë d’opérations ou d’instructions permettant de résoudre une classe de problèmes. Le mot algorithme vient du nom d’un mathématicien perse du IXe siècle, Al-Khwârizmî (en arabe : الخوارزمي). Le domaine qui étudie les algorithmes est appelé l’algorithmique. On retrouve aujourd’hui des algorithmes dans de nombreuses applications telles que le fonctionnement des ordinateurs3, la cryptographie, le routage d’informations, la planification et l’utilisation optimale des ressources, le traitement d’images, le traitement de textes, la bio-informatique, etc.
Algorithmes en traitement d’images
Les algorithmes les plus récents de traitement numérique de la géométrie ou bien encore de simulation numérique de type CFD (Computational Fluid Dynamics) utilisent à présent de nouveaux types de grilles composées de polyèdres arbitraires, autrement dit des grilles fortement non-structurées. Dans le cas de simulations de type CFD, ces grilles peuvent servir de support à des champs scalaires ou vectoriels qui représentent des grandeurs physiques (par exemple : densité, porosité, perméabilité).
La problématique de cette thèse concerne la définition de nouveaux outils de visualisation et de calcul sur de telles grilles. Pour la visualisation, cela pose à la fois le problème du stockage et de l’adaptativité des algorithmes à une géométrie et une topologie variables. Pour le calcul, cela pose le problème de la résolution de grands systèmes linéaires creux non-structurés. Pour aborder ces problèmes, l’augmentation incessante ces dernières années de la puissance de calcul parallèle des processeurs graphiques nous fournit de nouveaux outils. Toutefois, l’utilisation de ces GPU nécessite de définir de nouveaux algorithmes adaptés aux modèles de programmation parallèle qui leur sont spécifiques.
Nos contributions sont les suivantes : (1) Une méthode générique de visualisation tirant partie de la puissance de calcul des GPU pour extraire des isosurfaces à partir de grandes grilles fortement non structurées. (2) Une méthode de classification de cellules qui permet d’accélérer l’extraction d’isosurfaces grâce à une présélection des seules cellules intersectées. (3) Un algorithme d’interpolation temporelle d’isosurfaces. Celui-ci permet de visualiser de manière continue dans le temps l’évolution d’isosurfaces. (4) Un algorithme massivement parallèle de résolution de grands systèmes linéaires non-structurés creux sur le GPU. L’originalité de celui-ci concerne son adaptation à des matrices de motif arbitraire, ce qui le rend applicable à n’importe quel système creux, dont ceux issus de maillages fortement non-structurés.
Cours PDF
-
Algorithmes sur GPU de visualisation et de calcul pour des maillages non-structurés
-
Algorithmes SLAM (Simultaneous Localization et Mapping): Vers une Implémentation Embarquée
-
Les optimisations d’algorithmes de traitement de signal sur les architectures modernes parallèles et embarquées
-
TER : Algorithmes de compression d’images et quadtree
-
Principes du traitement d’images Champs d’applications, rappel d’optique Algorithmes et notions mathématiques
-
Principes du traitement d’images Champs d’applications, rappel d’optique Algorithmes et notions mathématiques
-
Introduction à l’intelligence artificielle (algorithmes avec adversaires)
-
Les algorithmes de l’intelligence artificielle