Revision sheet: Introduction aux fondamentaux de l'algorithmique

📋 Plan du Cours

1. Introduction à l’algorithmique
2. Terminaison et variant de boucle
3. Correction et invariant de boucle
4. Complexité des algorithmes
5. Algorithme de tri par sélection

📖 1. Introduction à l’algorithmique

🔑 Notions clés & Définitions

Algorithme
AUTEUR (date) : une suite finie d'opérations élémentaires ordonnées qui transforme une ou plusieurs valeurs d'entrée en une ou plusieurs valeurs de sortie. Il s'agit d'une méthode systématique permettant de résoudre un problème en suivant un enchaînement précis.

Opération élémentaire
Action simple, compréhensible et facilement réalisable par une personne, qui ne prête pas à interprétation. Par exemple, "Peser 100 g de farine" est une opération élémentaire, tandis que "faire un gâteau" ne l'est pas.

Procédure de calcul bien définie
Méthode précise qui, à partir d'une ou plusieurs valeurs d'entrée, aboutit à une ou plusieurs valeurs de sortie, en suivant un ensemble d'étapes claires.

Enchaînement déterminé
Ordre précis dans lequel les opérations d’un algorithme doivent être exécutées, garantissant la cohérence et la reproductibilité du processus.

Calcul
Processus d'exécution d'opérations permettant de transformer des valeurs d'entrée en résultats, selon une suite d'étapes définies.

📝 Points essentiels

Un algorithme est une procédure de calcul bien définie, qui prend en entrée une ou plusieurs valeurs et produit en sortie une ou plusieurs valeurs. La notion d’algorithme précède l’informatique, puisqu’elle vient du mathématicien perse Muhammad Ibn Mūsā al-Khuwārizmī. La spécification d’un algorithme repose sur une suite finie d’opérations élémentaires, ordonnées selon un enchaînement déterminé. La précision de ces opérations est essentielle pour éviter toute ambiguïté lors de leur exécution, garantissant ainsi la fiabilité du processus.

💡 À retenir

Un algorithme est une méthode rigoureuse, composée d’opérations simples et ordonnées, permettant de résoudre un problème de manière systématique et précise.

📖 2. Terminaison et variant de boucle

🔑 Notions clés & Définitions

Terminaison : La terminaison est une propriété fondamentale des algorithmes qui garantit que celui-ci s’arrêtera pour toutes les entrées possibles. Elle évite ainsi les boucles infinies, assurant que le processus de calcul aboutira à une conclusion. La terminaison doit être vérifiée indépendamment des données initiales de l’algorithme.

Variant de boucle : Un variant de boucle est une expression entière et positive qui décroît strictement à chaque itération d’une boucle. Il sert à justifier la terminaison d’une boucle en montrant que, à force de diminution, elle finira par atteindre une valeur limite, ce qui entraîne l’arrêt de la boucle.

Boucle "tant que" : Il s’agit d’une structure itérative qui peut ne pas se terminer si aucune condition ne force sa sortie. Elle n’est pas nécessairement bornée, ce qui peut conduire à une non-terminaison.

Expression entière positive décroissante : C’est une expression numérique qui, à chaque étape de la boucle, diminue strictement et reste toujours positive jusqu’à ce qu’elle atteigne zéro ou une valeur limite, garantissant ainsi la fin de la boucle.

📝 Points essentiels

La terminaison d’un algorithme doit être assurée pour toutes les données initiales. Elle garantit que l’algorithme s’arrêtera, évitant ainsi les boucles infinies. Les structures itératives non bornées, comme la boucle "tant que", peuvent ne pas se terminer si aucune mesure n’est prise pour assurer leur arrêt. Pour cela, on utilise un variant de boucle : une expression entière et positive qui décroît strictement à chaque itération. La présence d’un tel variant dans une boucle permet de démontrer sa terminaison, car il ne peut pas décroître indéfiniment. La terminaison est ainsi assurée si toutes les boucles d’un algorithme possèdent un variant de boucle.

💡 À retenir

La démonstration de la terminaison d’un algorithme repose sur l’existence d’un variant de boucle : une expression entière positive qui décroît strictement à chaque étape. La présence de ce variant dans chaque boucle garantit que l’algorithme se terminera, assurant ainsi la fin effective du processus.

📖 3. Correction et invariant de boucle

🔑 Notions clés & Définitions

Correction totale : Un algorithme est correct s'il termine et produit un résultat conforme aux spécifications pour toutes les entrées valides. Cela implique que l’algorithme ne doit pas seulement donner la bonne réponse, mais aussi terminer dans un délai fini.

• AUTEUR : voir section 1

Préconditions : Conditions qui doivent être vérifiées avant l’exécution de l’algorithme ou de la boucle pour garantir leur bon fonctionnement.

Postconditions : Propriétés qui doivent être vraies après l’exécution de l’algorithme ou de la boucle, assurant que le résultat respecte les spécifications.

Initialisation, Conservation, Terminaison (méthode de preuve) : Approche structurée pour démontrer la correction par invariant de boucle :

• Initialisation : Vérifier que l’invariant est vrai avant la première itération.
• Conservation : Montrer que si l’invariant est vrai avant une itération, il le reste après.
• Terminaison : voir section 2

📝 Points essentiels

Un algorithme est considéré correct s’il termine et si le résultat qu’il produit est conforme aux spécifications pour toutes les entrées valides. La preuve de cette correction repose sur l’utilisation d’un invariant de boucle, propriété qui doit être vérifiée à chaque étape de l’itération. La méthode de preuve se décompose en trois étapes :

• Initialisation : Vérifier que l’invariant est vrai avant la première itération.
• Conservation : Assurer que l’invariant reste vrai après chaque itération si il l’était avant.
• Terminaison : Lors de la sortie de boucle, l’invariant doit permettre de conclure que l’algorithme est correct, en particulier que le résultat est conforme aux spécifications.

💡 À retenir

La maîtrise de la méthode de preuve de correction via l’invariant de boucle garantit que l’algorithme produit un résultat conforme et termine, assurant ainsi sa validité pour toutes les entrées valides.

📖 4. Complexité des algorithmes

🔑 Notions clés & Définitions

Complexité en temps : La complexité en temps mesure le nombre d'opérations élémentaires nécessaires à l'exécution d'un algorithme en fonction de la taille de l'entrée. Elle permet d’évaluer l’efficacité d’un algorithme en estimant son comportement face à de grandes données.

Complexité en mémoire : La complexité en mémoire concerne la quantité d’espace mémoire requise par un algorithme. (Note : non développée ici, car non mentionnée dans la source).

Notation O (Landau) : La notation O permet d'exprimer l'ordre de grandeur asymptotique de la complexité d’un algorithme. Elle indique le comportement dominant pour de grandes tailles d’entrée, en ignorant les constantes et termes de moindre importance.

Ordre de grandeur asymptotique : C’est une estimation du comportement de la complexité en fonction de la taille de l’entrée, lorsque cette taille tend vers l’infini. Elle permet de comparer l’efficacité relative des algorithmes pour de très grandes entrées.

Opérations élémentaires : Ce sont des opérations simples telles que les additions, comparaisons ou affectations, dont le nombre est comptabilisé pour mesurer la complexité en temps d’un algorithme. La définition précise dépend de l’algorithme étudié.

📝 Points essentiels

La complexité en temps indique le nombre d’opérations élémentaires nécessaires pour résoudre un problème, en fonction de la taille de l’entrée. Elle n’est pas toujours facile à évaluer précisément, notamment à cause de cas litigieux. Il s’agit plutôt d’estimer son ordre de grandeur asymptotique, qui reflète le comportement pour des valeurs de n très grandes.

La notation O (Landau) sert à exprimer cet ordre de grandeur asymptotique. Par exemple, si le nombre d’opérations s’exprime par 3n+4, on dira que l’algorithme est en O(n), c’est-à-dire linéaire. Si le nombre d’opérations est 6n²+5n+10, l’algorithme est en O(n²), c’est-à-dire quadratique. Ces estimations permettent de comparer efficacement des algorithmes, surtout pour de grandes tailles d’entrée, en privilégiant leur comportement asymptotique.

💡 À retenir

L’évaluation de l’efficacité d’un algorithme repose principalement sur son comportement asymptotique, ce qui permet d’anticiper ses performances sur de grandes données. La notation O est l’outil standard pour exprimer cette complexité, facilitant la comparaison entre algorithmes.

📖 5. Algorithme de tri par sélection

🔑 Notions clés & Définitions

Tri par sélection :
Le tri par sélection consiste à parcourir le tableau à trier, à chaque étape, sélectionner l’élément minimal parmi les éléments non triés, puis l’échanger avec l’élément à la position courante. Ce processus est répété jusqu’à ce que tous les éléments soient triés.

Principe du tri par sélection :
À chaque étape, on identifie l’élément le plus petit dans la partie non triée du tableau. On le place à la position de départ de cette partie en échangeant avec l’élément présent. La partie triée s’accroît d’un élément à chaque étape, garantissant que cette partie reste ordonnée.

Terminaison du tri par sélection :
L’algorithme se termine lorsque la boucle parcourant la tableau est entièrement exécutée, c’est-à-dire après avoir effectué n-1 passages pour un tableau de taille n. La terminaison est assurée par des boucles bornées, dont la limite est la taille du tableau.

Correction du tri par sélection :
La correction est démontrée par un invariant de boucle : à chaque étape, la partie du tableau située avant la position courante est toujours triée et ordonnée. Cet invariant est maintenu à chaque itération, garantissant que le tableau final est trié.

Complexité du tri par sélection :
La complexité dans le pire des cas est en O(n²). En effet, pour chaque élément, il faut rechercher le minimum dans la partie non triée, ce qui nécessite un nombre d’opérations proportionnel à la taille restante du tableau, et ce pour chaque étape.

📝 Points essentiels

Le tri par sélection fonctionne en sélectionnant à chaque étape l’élément minimal parmi les éléments non triés et en le plaçant à sa position correcte. La terminaison est assurée par des boucles bornées, parcourant le tableau de manière systématique. La correction repose sur un invariant de boucle : la partie triée du tableau est toujours ordonnée, ce qui est maintenu à chaque étape. La complexité de cet algorithme est en O(n²) dans le pire des cas, ce qui en fait un algorithme simple mais peu efficace pour de grandes tailles de données.

💡 À retenir

Le tri par sélection est un algorithme simple dont la terminaison est assurée par des boucles bornées, et sa correction repose sur un invariant de boucle garantissant que la partie triée reste ordonnée. Sa complexité en O(n²) en fait une méthode peu efficace pour de grands tableaux, illustrant néanmoins bien les notions de terminaison, correction et complexité.

📊 Tableaux de Synthèse

Thème	Notions clés	Définition	Auteur / Source	Remarques
Algorithme	Suite finie d'opérations élémentaires	Méthode systématique pour résoudre un problème, transformant des valeurs d’entrée en valeurs de sortie	Muhammad Ibn Mūsā al-Khuwārizmī	La spécification repose sur une suite finie d’opérations ordonnées selon un enchaînement déterminé
Terminaison	Variant de boucle	Expression entière positive décroissante à chaque itération garantissant la fin de la boucle	-	Permet de démontrer la terminaison d’une boucle en assurant qu’elle ne peut pas durer indéfiniment
Correction	Invariant de boucle	Propriété vérifiée à chaque étape, permettant de prouver la correction totale d’un algorithme	-	La méthode repose sur initialisation, conservation et terminaison
Complexité	Notation O (Landau)	Estimation asymptotique du nombre d’opérations nécessaires en fonction de la taille de l’entrée	-	La complexité en temps est une mesure clé pour évaluer l’efficacité

⚠️ Pièges & Confusions Fréquentes

1. Confondre opération élémentaire et étape complexe non décomposable.
2. Négliger la nécessité d’un variant de boucle pour garantir la terminaison.
3. Supposer qu’un algorithme correct donne forcément le résultat optimal ou le plus efficace.
4. Confondre correction partielle (pour une entrée spécifique) et correction totale (pour toutes les entrées).
5. Oublier que la terminaison doit être vérifiée indépendamment des données initiales.
6. Confondre invariant de boucle et condition d’arrêt.
7. Sous-estimer l’impact de la complexité en mémoire dans l’évaluation globale.
8. Mal interpréter la notation O : ne pas considérer uniquement le comportement asymptotique.

✅ Checklist Examen

• Connaître la définition d’un algorithme selon Muhammad Ibn Mūsā al-Khuwārizmī et ses caractéristiques essentielles.
• Savoir ce qu’est une opération élémentaire et donner des exemples concrets.
• Expliquer ce qu’est un enchaînement déterminé dans un algorithme.
• Comprendre la notion de terminaison et l’importance du variant de boucle pour assurer cette propriété.
• Savoir démontrer qu’une boucle termine grâce à un variant décroissant.
• Maîtriser la méthode de preuve de correction par invariant : initialisation, conservation, terminaison.
• Connaître la différence entre correction partielle et correction totale.
• Savoir définir et utiliser la notation O pour exprimer la complexité en temps.
• Être capable d’estimer l’ordre de grandeur asymptotique d’un algorithme à partir du nombre d’opérations élémentaires.
• Connaître le rôle des opérations élémentaires dans le calcul de la complexité.
• Identifier les pièges courants liés à l’analyse des algorithmes (ex : confusion invariant / condition d’arrêt).
• Savoir expliquer le concept de complexité en mémoire (même si non développé ici).
• Vérifier que chaque boucle possède un variant pour garantir sa terminaison.