Quel type de performance ?

• Intuitivement, nous cherchons à capturer la vitesse et l’espace qu’un algorithme occupe sur votre ordinateur.

• Contrainte – Les mesures de performance doivent être indépendantes de la machine.

Complexité

• Solution – Pour une entrée de taille donnée, compter le nombre d’opérations à temps fixe effectuées par l’algorithme pour terminer.

• Selon les algorithmes étudiés, on peut se concentrer sur d’autres types de mesures telles que la taille de la mémoire utilisée, le nombre de tours, le nombre de messages échangés.

$\rightarrow$ Pour le reste du cours, nous nous concentrerons sur la vitesse d’un algorithme.

Problème

• Le temps pris par un algorithme peut varier d’une exécution à une autre.

Pourquoi ?

• Disponibilité des ressources système (comme le CPU, la mémoire, et l’accès au disque).
• Processus en arrière-plan s’exécutant simultanément.
• Effets de mise en cache.
• Exécution randomisée.

• Il existe plusieurs méthodes pour l’analyse de complexité :

  • Analyse pessimiste – La plus étudiée, se concentre uniquement sur le pire cas.
  • Analyse moyenne – Habituellement une borne supérieure sur le temps moyen pris par un algorithme. Classique en apprentissage automatique.
  • Dans les deux cas, on se concentre sur le calcul de bornes inférieures (ce que l’on peut espérer), et de bornes supérieures (ce que l’on a atteint).

• La complexité d’un algorithme est toujours liée à une entrée mesurable :

  • Taille des données à traiter.
  • Nombre d’ordinateurs à atteindre.
  • …

• Lorsqu’on fait une analyse pessimiste, on veut généralement ignorer les facteurs constants et les termes d’ordre faible.

• Notations – Bornes supérieures ($O$), bornes inférieures ($\Omega$), bornes serrées ($\Theta$).

Temps approximatif sur une machine monocœur à 1 GHz

Un exemple

• Défi – Planifier des tâches d’apprentissage automatique dans un cluster de calcul haute performance, où les tâches ont une urgence variable basée sur des facteurs comme les délais, les besoins en calcul, et l’impact.

• Scénario – Les tâches urgentes (e.g., ajustement fin d’un modèle de diagnostic médical) doivent recevoir des ressources avant les tâches moins critiques (e.g., entraînement d’un modèle de recommandation de films), indépendamment du temps de soumission.

• Question – Comment prioriser efficacement et sélectionner la tâche la plus urgente alors que de nouvelles tâches arrivent continuellement dans le système ?

Qu’en pensez-vous ?

• Quelle structure de données choisiriez-vous pour facilement ajouter de nouvelles tâches et rapidement retirer la plus urgente ?

• Pourquoi est-ce une mauvaise idée de stocker les tâches dans une liste ou dans une liste triée ?

Propriété de l’arbre binaire de recherche

• On dit qu’un arbre binaire satisfait la propriété de l’arbre binaire de recherche si pour chaque nœud :

  • Les clés dans le sous-arbre gauche d’un nœud sont inférieures à la clé stockée dans ce nœud.
  • Les clés dans le sous-arbre droit du nœud sont supérieures à la clé stockée dans ce nœud.

Opérations classiques

• Insertion – Ajouter un nouveau nœud tout en maintenant la propriété BST.
• Recherche – Trouver un nœud en parcourant depuis la racine, en suivant à gauche ou à droite selon la comparaison des clés.
• Suppression – Supprimer un nœud et ajuster l’arbre pour maintenir la propriété BST, en gérant les cas comme pas d’enfant, un enfant, ou deux enfants.
• Parcours – Visiter tous les nœuds dans un ordre spécifique (in-order, pre-order, post-order) pour traiter ou afficher le contenu de l’arbre.
• Trouver minimum/maximum – Trouver la valeur minimale (nœud le plus à gauche) ou maximale (nœud le plus à droite) dans l’arbre.

Remarque

La complexité de toutes ces opérations est de $O(h)$, où $h$ est la hauteur de l’arbre.

Algorithme probabiliste

• Un algorithme qui génère un nombre aléatoire $r \in \{ 1, \ldots, R \}$ et prend des décisions basées sur la valeur de $r$.

• Notez que donné la même entrée sur différentes exécutions, un algorithme randomisé peut :

  • Effectuer un nombre différent d’étapes.
  • Produire une sortie différente.

Types d’algorithmes probabilistes