Revision sheet: Introduction aux algorithmes et structures

📋 Plan du Cours

1. Algorithme
2. Structure et étapes
3. Complexité et optimisation
4. Applications et exemples

📖 1. Algorithme

🔑 Notions clés & Définitions

• Algorithme : Une suite finie d'instructions permettant de résoudre un problème. Il s'agit d'une procédure précise, structurée et délimitée dans le temps, conçue pour transformer des données d'entrée en résultats attendus.

• Instruction : Une étape ou une commande unique dans un algorithme. Elle indique une opération à effectuer, comme une calcul ou une décision.

• Entrée : Les données ou informations initiales fournies à l'algorithme pour qu'il puisse effectuer ses opérations. Elles constituent le point de départ du traitement.

• Sortie : Le résultat ou la réponse produite par l'algorithme après traitement des entrées. Elle correspond à l'objectif final de la procédure.

• Finitude : Caractère d’un algorithme qui doit se terminer après un nombre fini d’étapes. Il ne doit pas entrer dans une boucle infinie.

• Déterminisme : Qualité d’un algorithme dont le comportement est entièrement prévisible : pour une même entrée, il produit toujours la même sortie, sans ambiguïté ni hasard.

📝 Points essentiels

Un algorithme est une suite finie d'instructions permettant de résoudre un problème. Chaque algorithme doit comporter des entrées, qui sont les données initiales nécessaires au traitement, et des sorties, qui sont les résultats obtenus après exécution. Il doit également se terminer après un nombre fini d'étapes, ce qui garantit qu'il ne tourne pas indéfiniment. La finitude assure que l'algorithme est praticable et exploitable dans un contexte réel. La déterminisme implique que pour une même entrée, l'algorithme produit toujours la même sortie, assurant ainsi la fiabilité et la prévisibilité de la procédure.

💡 À retenir

L'algorithme peut être considéré comme une recette précise et finie, qui transforme des données d'entrée en résultats attendus, tout en garantissant une exécution limitée dans le temps.

📖 2. Structure et étapes

🔑 Notions clés & Définitions

Séquence
Une séquence désigne l’enchaînement linéaire d’instructions ou d’opérations dans un algorithme, exécutées dans un ordre précis. Elle constitue la structure de base pour organiser le déroulement des actions.

Conditionnelle
Une conditionnelle permet de faire des choix dans un algorithme en exécutant une partie du code uniquement si une condition spécifique est remplie. Elle introduit une branchement dans le flux d’exécution.

Boucle
Une boucle est une structure qui répète un ensemble d’instructions tant qu’une condition est vérifiée ou jusqu’à ce qu’elle ne le soit plus. Elle sert à automatiser la répétition d’actions.

Variable
Une variable est un espace de stockage temporaire permettant de conserver une donnée ou une valeur pendant l’exécution de l’algorithme. Elle peut être modifiée au cours du processus.

Pseudocode
Le pseudocode est une représentation simplifiée et informelle d’un algorithme, utilisant une syntaxe proche du langage naturel ou d’un langage de programmation, pour décrire la logique sans souci de syntaxe précise.

📝 Points essentiels

Les algorithmes sont structurés en trois blocs fondamentaux :

• La séquence organise l’ordre d’exécution des instructions.
• La conditionnelle introduit des choix en permettant d’exécuter certaines instructions uniquement si une condition est remplie, ce qui permet de contrôler le flux selon des critères spécifiques.
• La boucle permet de répéter des instructions plusieurs fois, facilitant l’automatisation de tâches répétitives.

Les structures de contrôle mentionnées (séquences, conditionnelles et boucles) sont essentielles pour gérer le flux d’exécution d’un algorithme.

Les variables jouent un rôle clé en stockant temporairement des données, ce qui permet à l’algorithme de manipuler et de traiter ces informations durant son déroulement.

💡 À retenir

L’apprentissage de la construction d’un algorithme repose sur la maîtrise de ses blocs fondamentaux — séquences, conditions, boucles — et leur organisation logique, notamment via l’utilisation de variables pour gérer les données.

📖 3. Complexité et optimisation

🔑 Notions clés & Définitions

• Complexité temporelle : La complexité temporelle désigne la mesure du temps nécessaire à un algorithme pour s'exécuter en fonction de la taille de l'entrée. Elle permet d’évaluer la rapidité d’un algorithme dans le cadre d’un problème donné.

• Complexité spatiale : La complexité spatiale correspond à la quantité de mémoire ou d’espace de stockage requise par un algorithme pour traiter une entrée de taille donnée. Elle permet d’évaluer l’efficacité en termes de ressources mémoire.

• Notations Big O : Les notations Big O sont des symboles utilisés pour exprimer la limite supérieure de la croissance de la complexité d’un algorithme. Elles permettent de caractériser la performance en termes de temps ou d’espace en fonction de la taille de l’entrée, en ignorant les constantes et les termes de moindre importance.

• Optimisation : L’optimisation consiste à modifier un algorithme pour réduire sa complexité en temps ou en espace, afin d’améliorer ses performances sans en altérer la validité ou la précision.

• Algorithme efficace : Un algorithme efficace est celui qui minimise la complexité en temps et en espace tout en assurant la correction et la fiabilité du résultat. Il permet de traiter des problèmes de grande taille de manière raisonnable.

📝 Points essentiels

La complexité mesure les ressources (temps, mémoire) nécessaires à l'exécution d'un algorithme. La compréhension de ces coûts est essentielle pour évaluer la performance d’un algorithme et pour comparer différentes solutions à un même problème.

L’optimisation vise à réduire la complexité pour améliorer la performance sans altérer la validité de l’algorithme. Elle consiste à analyser et à ajuster les aspects de l’algorithme afin de diminuer ses ressources consommées.

💡 À retenir

L’évaluation et l’amélioration de la performance d’un algorithme passent par l’analyse de ses coûts en temps et en espace, permettant ainsi de développer des solutions plus efficaces et adaptées aux contraintes du problème.

📖 4. Applications et exemples

🔑 Notions clés & Définitions

• Tri
  Processus consistant à organiser des éléments selon un ordre précis (croissant ou décroissant). Il existe plusieurs méthodes de tri, chacune adaptée à différents contextes.

• Recherche
  Procédé permettant de retrouver un élément spécifique dans un ensemble de données. Elle peut être linéaire ou plus efficace, comme la recherche binaire.

• Algorithme glouton
  Méthode qui construit une solution étape par étape en choisissant à chaque étape l’option la plus avantageuse sans revenir en arrière, dans le but d’obtenir une solution optimale ou approchée.

• Divide and Conquer
  Approche algorithmique qui divise un problème en sous-problèmes plus simples, résout chacun d’eux indépendamment, puis combine leurs solutions pour résoudre le problème initial.

• Algorithme de Dijkstra
  Algorithme de recherche de plus court chemin dans un graphe pondéré sans arêtes négatives, utilisant une stratégie gloutonne pour explorer les chemins optimaux à partir d’un point de départ.

📝 Points essentiels

Les algorithmes sont appliqués dans divers domaines comme le tri, la recherche et l’optimisation. Par exemple, le tri permet d’organiser efficacement des données pour faciliter leur traitement ou leur recherche. La recherche, notamment la recherche binaire, optimise la localisation d’un élément dans une structure ordonnée. Les algorithmes gloutons sont utilisés pour résoudre des problèmes d’optimisation rapides, en choisissant localement la meilleure option à chaque étape, comme dans le cas du problème du sac ou de la couverture. La méthode Divide and Conquer facilite la résolution de problèmes complexes en les décomposant en sous-problèmes plus simples, illustrée par l’algorithme de tri fusion. L’algorithme de Dijkstra, quant à lui, est un exemple concret d’application dans la recherche de chemins optimaux dans un graphe, utilisé notamment dans la navigation ou la gestion de réseaux.

💡 À retenir

Les algorithmes se traduisent en solutions concrètes dans différents contextes réels, permettant d’optimiser le traitement des données, la recherche d’informations ou la résolution de problèmes complexes.

📊 Tableaux de Synthèse

Aspect	Définition	Exemple / Commentaire	Auteur / Référence
Algorithme	Suite finie d'instructions pour résoudre un problème	Transformation de données d'entrée en sortie	-
Instruction	Commande unique dans un algorithme	Calcul, décision	-
Entrée	Données initiales fournies à l'algorithme	Exemple : un nombre à traiter	-
Sortie	Résultat produit par l'algorithme	Exemple : le résultat du calcul	-
Finitude	L'algorithme doit se terminer après un nombre fini d'étapes	Éviter boucle infinie	-
Déterminisme	Même entrée → même sortie, comportement prévisible	Fiabilité de l'algorithme	-
Séquence	Enchaînement linéaire d'instructions	Ordre d'exécution simple	-
Conditionnelle	Choix selon une condition	Si x > 0, alors faire y	-
Boucle	Répétition d'instructions jusqu'à une condition	Répéter tant que la condition est vraie	-
Variable	Stockage temporaire de données	Stocker la valeur d’un compteur	-
Notation Big O	Expression de la croissance de la complexité en fonction de la taille	O(n), O(log n)	-
Complexité temporelle	Temps d'exécution en fonction de la taille de l'entrée	Plus l'entrée est grande, plus le temps peut augmenter	-
Complexité spatiale	Mémoire requise en fonction de la taille de l'entrée	Mémoire utilisée par l'algorithme	-
Algorithme efficace	Minimise ressources tout en étant correct	Tri rapide, recherche binaire	-
Tri	Organisation des éléments selon un ordre	Tri croissant ou décroissant	-
Recherche	Localisation d’un élément dans un ensemble	Recherche linéaire, recherche binaire	-
Algorithme glouton	Choix local optimal à chaque étape pour une solution globale	Problème du sac à dos, couverture	-
Divide and Conquer	Diviser pour mieux régner, résolution par sous-problèmes	Tri fusion, recherche binaire	-
Algorithme de Dijkstra	Plus court chemin dans un graphe pondéré sans arêtes négatives	Exploration gloutonne des chemins	-

⚠️ Pièges & Confusions Fréquentes

1. Confondre algorithme et programme : un algorithme est une méthode abstraite, pas un code précis.
2. Oublier la finitude : certains pensent qu’un algorithme peut tourner indéfiniment, ce qui est faux.
3. Confondre déterminisme et hasard : un algorithme déterministe donne toujours le même résultat pour une même entrée.
4. Mauvaise utilisation des structures (séquence, conditionnelle, boucle) : leur organisation est essentielle.
5. Négliger la complexité : sous-estimer le coût en temps ou mémoire peut conduire à des solutions inefficaces.
6. Confusion entre optimisation et correction : optimiser ne doit pas compromettre la validité.
7. Mauvaise compréhension des notations Big O : elles expriment une limite supérieure, pas une valeur exacte.

✅ Checklist Examen

1. Connaître la définition d’un algorithme selon Perroux : suite finie d’instructions permettant de résoudre un problème.
2. Savoir distinguer entrée et sortie dans un algorithme.
3. Expliquer pourquoi la finitude est une propriété essentielle d’un algorithme.
4. Définir le déterminisme et donner un exemple illustrant cette propriété.
5. Identifier les trois blocs fondamentaux d’un algorithme : séquence, conditionnelle, boucle.
6. Savoir décrire le rôle des variables dans un algorithme.
7. Connaître la notation Big O et sa signification pour la complexité temporelle.
8. Expliquer ce qu’est une complexité spatiale et comment elle influence le choix d’un algorithme.
9. Définir ce qu’est un algorithme efficace et donner un exemple (ex : tri rapide).
10. Illustrer le principe du tri et donner deux méthodes courantes.
11. Expliquer la différence entre recherche linéaire et recherche binaire.
12. Décrire le principe de l’algorithme glouton avec un exemple simple.
13. Présenter l’approche Divide and Conquer avec un exemple (ex : tri fusion).
14. Connaître l’algorithme de Dijkstra et son domaine d’application.
15. Être capable d’identifier les pièges liés à la confusion entre structures et propriétés des algorithmes.