2. Diplômes
  3. Diplôme ingénieur ISIMA (statut étudiant)
  4. 3ème année
  5. Semestre 9
  6. f2
  7. ue-modelisation
  8. Algorithmique avancée et complexité

Algorithmique avancée et complexité

Objectifs

L’algorithmique donne des méthodes générales pour résoudre différents types de problèmes. Ce cours se penche sur la résolution efficace de problèmes complexes par des algorithmes. L’efficacité est fonction des temps de calcul, de leur utilisation mémoire, de leur précision et de leur possibilité de parallélisation. Ce cours permet de s’initier à différents types d’algorithmes performant tout en prédisant l'évolution des temps calcul nécessaires pour résoudre un problème en fonction du volume des données à traiter. Il permet de se préparer d’une part aux problèmes complexes de l’industrie mais aussi aux qu’aux entretiens des meilleures entreprises spécialisées en informatique pour qui la capacité à résoudre algorithmiquement des problèmes complexe est un précieux indicateur du niveau du candidat. Le niveau abordé est celui des concours du type ACM/ICPC ou Google Jam. Une introduction est donnée au calcul quantique avec l’étude de l’algorithme de Grover et les soucis de reproductibilité des expériences.

Plan du cours

I Introduction au cours

     I.1 Objectifs et enjeux de l’algorithmique avancée

         I.1.1 Importance des algorithmes dans l'industrie et les entretiens techniques.

     I.1.2 Critères d’évaluation d’un algorithme : temps de calcul, mémoire, précision, parallélisation.

I.2 Rappels et fondations

       I.2.1  Complexité algorithmique : notations O, Ω, et Θ.

       I.2.2 Structures de données avancées (arbres, graphes, tables de hachage, etc.).

       I.2.3  Paradigmes de base : diviser pour régner, programmation dynamique, recherche gloutonne.

 

II. Conception et analyse d’algorithmes avancés - Rappels

 

II.1 Algorithmes efficaces pour les structures de données courantes

     II.1.1 Opérations sur les arbres (AVL, arbres B, arbres de segment)

     II.1.2 Graphes : parcours en profondeur/largeur, Dijkstra, A*, Floyd-Warshall

     II.1.3 Structures spécialisées : heaps, tries, skip-lists.

 

     II.2 Techniques d’optimisation algorithmique - Rappels

         II.2.1 Programmation dynamique avancée : espace optimisé, mémoïsation, tabulation.

         II.2.2 Techniques de réduction de la complexité : matrice sparses, Fast Fourie                                                       Transform (FFT).

         II.2.3 Approches probabilistes : Monte Carlo, Las Vegas.

 

     II.3 Analyse amortie et algorithmes des flux      

         II.3.1 Applications aux structures comme les union-find.

    II.3.2 Algorithmes pour flux de données.                                                                           

 

III. Rappel des Techniques de Résolution de problèmes complexes

    

     III.1   Algorithmes de recherche et optimisation

         III.1.1 Recherche exhaustive et heuristiques.

         III.1.2 Algorithmes d’optimisation combinatoire : Branch-and-Bound, Branch-and Cut

         III.1.3 Optimisation convexe et non convexe.

 

     III.2 Traitement des grands ensembles de données

     III.2.1 Algorithmes de streaming

     III.2.2 Approches pour les big data : MapReduce, algorithmes distribués.

 

III.3 Rappel sur les Problèmes NP-complets

     III.3.1 Identification et classification des problèmes NP-complets.

     III.3.2 Approches exactes (SAT-solvers, backtracking) et approximations

     III.3.3 Algorithmes FPT (Fixed Parameter Tractable).

 

IV. Découverte de l’informatique quantique

     IV.1 Définitions et principes quantiques
     IV.2 Eléments de calcul tensoriel et produits de Kronecker

     IV.3 Suprématie (avantage) quantique ?

IV.4 Les limites actuelles
IV.5 Epistémologie & reproductibilité des calculs : exemple sur l’algorithme de Grover

IV.6 Conclusion et questionnement éthique

Description des TP

2 TPs longs – travail en binôme en eXtreme Programming

Choix et codage de 2 algorithmes complexes
Découverte de 2 autres algorithmes – présentation dans un rapport et rédaction de tests
 

Connaissances requises

Cours d’Algorithmique, de Recherche Opérationnelle, de Structures des données, d’Analyse Numérique et de Simulation (étudiés en 1ère et 2nde année de Tronc commun et de 2ème année F2).

RSE (Responsabilité Sociale et Environnementale)

Bibliographie