Fiche de révision : Algorithmique et complexité

📋 Plan du Cours

1. Fondements des algorithmes
2. Propriétés d’un algorithme
3. Algorithme d’Euclide
4. Coût et complexité
5. Parcours séquentiel
6. Recherche dichotomique
7. Algorithmes de tri
8. Terminaison et variants
9. Algorithmes gloutons
10. K plus proches voisins

📖 1. Fondements des algorithmes

🔑 Notions clés & Définitions

• Algorithme : Succession d’instructions permettant d’aboutir à un résultat souhaité.
• Algorithmique : Étude et conception de règles permettant d’écrire des algorithmes.

📝 Points essentiels

📌 Un algorithme prend des données en entrée, décrit un traitement particulier et fournit des données en sortie.

💡 Astuce mémo

Entrées → traitement → sorties

📖 2. Propriétés d’un algorithme

🔑 Notions clés & Définitions

• Programme : Traduction d’un algorithme dans un langage de programmation comme Python ou Java.

★ À maîtriser

• Les cinq caractéristiques importantes d’un algorithme sont (Donald Knuth, 1968):
  • se terminer après un nombre fini d’étapes
  • définir précisément chaque action
  • accepter zéro ou plusieurs entrées
  • produire une ou plusieurs sorties
  • utiliser des instructions exécutables exactement en un temps fini

Compléments

• Le terme algorithme vient du nom du mathématicien perse du IXe siècle Muhammad Ibn Mūsā al-Khuwārizmī, et les premières traces connues remontent notamment à la civilisation babylonienne.

💡 Astuce mémo

Finir, définir, entrer, sortir, exécuter

📖 3. Algorithme d’Euclide

★ À maîtriser

• L’algorithme d’Euclide choisit deux entiers m et n, calcule le reste r de la division de m par n, renvoie n si r vaut zéro, puis remplace m et n par n et r et recommence sinon.

Compléments

• Vers 300 av. J.-C., Euclide a décrit dans le livre VII des Éléments un algorithme permettant de calculer le plus grand commun diviseur de deux entiers.

💡 Astuce mémo

Diviser → tester le reste → remplacer → recommencer

📖 4. Coût et complexité

🔑 Notions clés & Définitions

• Complexité : Nombre d’opérations élémentaires arithmétiques ou logiques et d’affectations nécessaires à son exécution.

📝 Points essentiels

📐 Formule — Une complexité linéaire s’écrit sous la forme $\alpha n + \beta$ avec $\alpha>0$, et se note $O(n)$.

📐 Formule — Une complexité quadratique s’écrit sous la forme $\alpha n^2+\beta n+\gamma$ avec $\alpha>0$, et se note $O(n^2)$.

💡 Astuce mémo

Linéaire : doubler n double le temps ; quadratique : le quadruple

📖 5. Parcours séquentiel

★ À maîtriser

• La recherche linéaire parcourt un tableau élément par élément jusqu’à trouver la valeur recherchée ou atteindre sa fin, avec un coût linéaire dans le pire cas.

Compléments

• Le calcul séquentiel d’un extremum conserve une référence au premier élément, la compare aux suivants et la remplace lorsqu’un élément plus grand ou plus petit est rencontré.

• Le calcul séquentiel d’une moyenne utilise un accumulateur initialisé à zéro, auquel sont ajoutées successivement les valeurs de la liste.

📖 6. Recherche dichotomique

🔑 Notions clés & Définitions

• Recherche dichotomique : Recherche d’une valeur dans un espace ordonné en divisant successivement l’intervalle de recherche en deux parties.

📝 Points essentiels

• La recherche dichotomique examine l’élément central, s’arrête s’il correspond à la valeur recherchée, puis conserve la moitié gauche ou droite selon la comparaison et recommence jusqu’au succès ou à l’intervalle vide.

• La recherche dichotomique a une complexité temporelle logarithmique, notée $O(\log n)$, généralement inférieure à la complexité linéaire.

💡 Astuce mémo

Milieu → moitié gauche ou droite → intervalle réduit

📖 7. Algorithmes de tri

📝 Points essentiels

• Le tri par insertion parcourt le tableau et insère chaque élément à sa place parmi les éléments précédents en décalant ceux qui sont plus grands.

• Dans le pire cas d’un tableau trié à l’envers, le tri par insertion effectue une complexité quadratique notée $O(n^2)$.

• Le tri par sélection recherche le plus petit élément de la partie non triée, l’échange avec l’élément de position courante et répète l’opération jusqu’au tri complet.

💡 Astuce mémo

Insertion : décaler ; sélection : chercher puis échanger

📖 8. Terminaison et variants

🔑 Notions clés & Définitions

• Variant de boucle : Quantité entière positive ou nulle dans la boucle et qui décroît strictement à chaque itération.

★ À maîtriser

📌 L’existence d’un variant de boucle garantit la terminaison d’une boucle while, car un entier positif ou nul ne peut décroître indéfiniment.

Compléments

• Dans la fonction de calcul de 2^n, la quantité $n-compteur$ est un variant car elle reste positive ou nulle dans la boucle et décroît d’une unité à chaque itération.

💡 Astuce mémo

Variant positif et décroissant → sortie nécessaire de la boucle

📖 9. Algorithmes gloutons

🔑 Notions clés & Définitions

• Algorithme glouton : Construction d’une solution pas à pas en choisissant à chaque étape l’option qui semble la meilleure sans revenir sur ses décisions précédentes.

★ À maîtriser

📌 Un algorithme glouton peut fournir une solution optimisée sans fournir la solution optimale globale, sauf dans certaines situations canoniques.

• Pour rendre une somme avec un algorithme glouton, on choisit la plus grande pièce inférieure ou égale à la somme restante, on la déduit, puis on recommence jusqu’à obtenir une somme nulle.

Compléments

• Pour rendre 63 euros avec les pièces 1, 2, 20 et 50, l’algorithme glouton produit huit pièces ou billets, alors que la solution optimale globale est composée de 20, 20, 20, 2 et 1.

💡 Astuce mémo

Solution optimisée locale ≠ toujours solution optimale globale

📖 10. K plus proches voisins

🔑 Notions clés & Définitions

• K plus proches voisins : Algorithme d’apprentissage supervisé qui classe une nouvelle donnée à partir de données déjà étiquetées.
• Distance de Hamming : Nombre de positions auxquelles les caractères de deux chaînes diffèrent.

★ À maîtriser

• L’algorithme des k plus proches voisins trie les données selon leur distance à la cible, extrait les k premières données et choisit la classification majoritaire.

Compléments

• La complexité des k plus proches voisins est celle du tri, soit $O(n\log n)$ en Python.

💡 Astuce mémo

Mesurer → trier → extraire k → voter

📊 Tableaux de synthèse

Comparaison des recherches et tris