Implementation adaptative d'algorithmes de balayage

De Ensiwiki
Révision de 9 octobre 2017 à 08:59 par Wagnerf (discussion | contributions) (Page créée avec « {{Sujet irl | labo = LIG | titre = Implementation adaptative d'algorithmes de balayage. | equipe = Datamove | encadrants = frederic.wagner@imag.fr }} Catégorie:IRL =... »)

(diff) ← Version précédente | Voir la version courante (diff) | Version suivante → (diff)
Aller à : navigation, rechercher


Implementation adaptative d'algorithmes de balayage.

Labo LIG
Equipe Datamove
Encadrants frederic.wagner@imag.fr

Thème général

Algorithmique, profiling, geometrie, rust.

Compétences attendues

s'en etre bien sorti au projet d'algo de 1a. bon niveau de programmation.

Contexte du travail

On s'interesse ici a l'implementation d'algorithmes de calcul de chemins pour les machines outils a commandes numeriques.

Par exemple dans le cadre d'une utilisation d'une imprimante 3d.

Les algorithmes etudies ici forment les briques de base d'algorithmes plus complexes et leurs performances sont donc cruciales.

Sujet

On s'interesse dans ce sujet a differents algorithmes de geometrie, de balayage (de plan ou d'espace). En particulier, nous considerons une version de l'algorithme de bentley ottmann etendu aux arcs de cercles ainsi qu'un algorithme similaire permettant la classification d'objets geometriques. Tous ces algorithmes sont actuellement implementes en Rust et on s'interesse ici a leur optimisation. Le stage comprend donc une part importante de mesure et d'analyse de performances. Les pistes d'amelioration sont les suivantes:

- les algorithmes en brute force (quadratiques) peuvent etre interessants pour les instances de petites tailles. peut-on determiner facilement quel algorithme utiliser pour une instance donnee ?
- les algorithmes de balayage reposent sur des dictionnaires ordonnes. il se pose donc la question du choix du meilleur dictionnaire. actuellement il s'agit d'ABR mais on pourrait envisager de re-implementer les sorted containers de python en rust et de comparer les deux implementations.


Résultats attendus

- beaucoup de mesures de performanes, sur differentes entrees et differentes architectures
- implementation d'algorithmes brute force
- implementation d'algorithmes adaptatifs (choisissant un sous-algorithme en fonction de l'instance donnee)