Scheda di revisione: Introduction aux algorithmes et complexité

📋 Plan du Cours

1. Algorithme & Définition
2. Propriétés & Caractéristiques
3. Structures de contrôle & Syntaxe
4. Complexité & Notations
5. Recherche séquentielle & Fonctionnement
6. Recherche dichotomique & Conditions
7. Boucles & Types
8. Analyse de complexité & Cas d'usage

📖 1. Algorithme & Définition

🔑 Notions clés & Définitions

• Algorithme : Suite finie d’instructions précises permettant de résoudre un problème ou d’accomplir une tâche spécifique.
• Propriétés d’un algorithme :
  • Fini : doit comporter un nombre limité d’étapes.
  • Déterministe : pour une même entrée, produit toujours le même résultat.
  • Non ambigu : chaque étape doit être claire et sans ambiguïté.
• Structures de contrôle :
  • Condition (if-else) : permet de choisir entre différentes instructions selon une condition.
  • Boucle bornée (for) : répète un bloc d’instructions un nombre fixe de fois.
  • Boucle non bornée (while) : répète tant qu’une condition est vraie.

📝 Points essentiels

• Un algorithme doit être fini, précis, et déterministe.
• La complexité d’un algorithme mesure le temps ou l’espace qu’il nécessite, exprimée en notation Big O (ex : O(1), O(log n), O(n), O(n²)).
• La recherche séquentielle parcourt chaque élément pour trouver une valeur (complexité O(n)).
• La recherche dichotomique, efficace sur une liste triée, divise l’espace de recherche par deux à chaque étape (complexité O(log n)).
• La compréhension des structures de contrôle est essentielle pour la logique algorithmique.

💡 À retenir

Un algorithme est une méthode précise et finie, dont l’efficacité se mesure par sa complexité, essentielle pour optimiser la résolution de problèmes en informatique.

📖 2. Propriétés & Caractéristiques

🔑 Notions clés & Définitions

• Algorithme : Suite finie d'instructions permettant de résoudre un problème précis. Il doit être clair, précis et exécutable par une machine ou un humain.
• Propriétés d’un algorithme :
  • Finité : doit se terminer après un nombre fini d’étapes.
  • Déterminisme : chaque étape doit produire un seul résultat, sans ambiguïté.
  • Non ambiguïté : chaque instruction doit être claire et sans équivoque.
• Structures de contrôle :
  • Condition (if...else) : permet de choisir entre plusieurs instructions selon une condition.
  • Boucle bornée (for) : répète un bloc d'instructions un nombre fixe de fois.
  • Boucle non bornée (while) : répète tant qu'une condition est vraie.
• Complexité algorithmique : mesure du temps ou de l’espace utilisé par un algorithme, exprimée en notation Big O (ex : O(1), O(log n), O(n), O(n²)).

📝 Points essentiels

• Un algorithme doit être fini, déterministe et non ambigu pour garantir sa fiabilité.
• Les structures de contrôle permettent de gérer la logique conditionnelle et la répétition dans un algorithme.
• La complexité permet d’évaluer l’efficacité d’un algorithme : O(1) est constant, O(log n) logarithmique, O(n) linéaire, O(n²) quadratique.
• La recherche séquentielle parcourt tous les éléments d’une liste pour trouver une valeur, avec une complexité O(n).
• La recherche dichotomique, efficace sur une liste triée, divise par deux la recherche à chaque étape, avec une complexité O(log n).

💡 À retenir

Un algorithme efficace doit respecter ses propriétés fondamentales et utiliser judicieusement les structures de contrôle pour optimiser la complexité, notamment en choisissant la méthode de recherche adaptée à la nature des données.

📖 3. Structures de contrôle & Syntaxe

🔑 Notions clés & Définitions

• Algorithme : Suite finie d’instructions permettant de résoudre un problème. Propriétés : fini, déterministe, non ambigu.
• Structure de contrôle : Instruction permettant de modifier le flux d'exécution d'un programme (ex : condition, boucle).
• Condition (if) : Permet d'exécuter une instruction si une condition est vraie, sinon une autre instruction.
• Boucle bornée (for) : Répète un bloc d'instructions un nombre déterminé de fois.
• Boucle non bornée (while) : Répète un bloc d'instructions tant qu'une condition est vraie.
• Complexité algorithmique : Mesure du temps d'exécution en fonction de la taille des données, notée en O(n), O(log n), etc.

📝 Points essentiels

• Les structures conditionnelles (if/else) permettent de faire des choix dans le programme.
• Les boucles (for, while) permettent de répéter des instructions, avec ou sans limite.
• La complexité d'une recherche séquentielle est O(n), ce qui est linéaire.
• La recherche dichotomique, efficace sur liste triée, a une complexité O(log n).
• La syntaxe doit être claire et précise pour assurer la non ambiguïté du programme.
• La propriété déterministe garantit que l'algorithme donne le même résultat pour les mêmes entrées.

💡 À retenir

Les structures de contrôle sont essentielles pour gérer le flux d'exécution d’un programme, permettant de réaliser des opérations conditionnelles ou répétitives, avec une importance capitale pour l'efficacité algorithmique.

📖 4. Complexité & Notations

🔑 Notions clés & Définitions

• Algorithme : Suite finie d’instructions permettant de résoudre un problème. Il doit être fini, déterministe et non ambigu.
• Complexité algorithmique : Mesure de l'efficacité d’un algorithme en fonction de la taille de l’entrée, généralement exprimée en notation asymptotique.
• Notations de complexité :
  • O(1) : Temps constant, indépendant de la taille de l’entrée.
  • O(log n) : Temps logarithmique, croît lentement avec la taille.
  • O(n) : Temps linéaire, croît proportionnellement à la taille.
  • O(n²) : Temps quadratique, croît avec le carré de la taille.
• Structures de contrôle : Mécanismes permettant de contrôler l’ordre d’exécution des instructions (condition, boucle bornée, boucle non bornée).

📝 Points essentiels

• La complexité permet de comparer l’efficacité des algorithmes.
• La notation Big O donne une limite supérieure du temps d’exécution en fonction de la taille de l’entrée.
• La recherche séquentielle a une complexité O(n), adaptée pour des listes non triées.
• La recherche dichotomique, efficace sur une liste triée, a une complexité O(log n).
• La propriété de déterminisme garantit que l’algorithme produit toujours le même résultat pour une même entrée.
• La propriété de non ambiguïté assure que chaque instruction est claire et ne prête pas à confusion.

💡 À retenir

La maîtrise des notations de complexité et des structures de contrôle est essentielle pour analyser et optimiser la performance des algorithmes. La recherche dichotomique est particulièrement efficace sur des listes triées, avec une complexité logarithmique.

📖 5. Recherche séquentielle & Fonctionnement

🔑 Notions clés & Définitions

• Algorithme : Suite finie d’instructions permettant de résoudre un problème.
• Recherche séquentielle : Méthode de recherche d’un élément dans une liste en parcourant chaque élément jusqu’à trouver une correspondance ou atteindre la fin.
• Complexité : Mesure du temps ou des ressources nécessaires à l’exécution d’un algorithme, exprimée en notation Big O.
• Recherche dichotomique : Méthode efficace de recherche dans une liste triée, qui divise l’espace de recherche par deux à chaque étape.
• Structures de contrôle : Instructions permettant de gérer le flux d’exécution (condition, boucle bornée, boucle non bornée).

📝 Points essentiels

• La recherche séquentielle fonctionne dans tous les cas, mais sa complexité est linéaire O(n), ce qui peut être lent pour de grandes listes.
• La recherche dichotomique est beaucoup plus rapide (O(log n)), mais nécessite une liste préalablement triée.
• La propriété fini garantit que l’algorithme se termine, déterministe qu’il donne toujours le même résultat pour une même entrée, et non ambigu qu’il n’y a pas d’interprétation multiple des instructions.
• La complexité permet d’évaluer la performance : O(1) pour une opération constante, O(log n) pour une recherche dichotomique, O(n) pour une recherche séquentielle.

💡 À retenir

La recherche séquentielle est simple mais peu efficace pour de grandes listes, tandis que la recherche dichotomique, plus performante, nécessite une liste triée. La compréhension de leur complexité est essentielle pour optimiser les algorithmes.

📖 6. Recherche dichotomique & Conditions

🔑 Notions clés & Définitions

• Recherche dichotomique : Méthode de recherche dans une liste triée qui consiste à diviser l'espace de recherche en deux parties à chaque étape pour réduire rapidement le nombre d'éléments à examiner.
• Condition : Expression booléenne qui détermine l'exécution d'une instruction ou d'un bloc d'instructions (ex : if condition:).
• Boucle bornée : Structure itérative qui s'exécute un nombre fixe de fois, généralement avec une variable de contrôle (ex : for i in range(n)).
• Boucle non bornée : Structure itérative qui s'exécute tant qu'une condition est vraie (ex : while condition:).
• Complexité algorithmique : Mesure de la performance d’un algorithme, exprimée en notation Big O (ex : O(1), O(log n), O(n), O(n²)).

📝 Points essentiels

• La recherche dichotomique nécessite une liste triée pour fonctionner efficacement.
• La complexité de la recherche dichotomique est logarithmique : O(log n), ce qui la rend très efficace pour de grandes listes.
• La recherche séquentielle, moins efficace, a une complexité linéaire : O(n).
• La structure conditionnelle if permet de faire des choix dans le flux d'exécution selon une condition.
• Les boucles for et while permettent de répéter des instructions, for étant bornée et while pouvant être non bornée.
• La compréhension des conditions et des structures de contrôle est essentielle pour optimiser la recherche et la prise de décision dans un algorithme.

💡 À retenir

La recherche dichotomique, grâce à sa complexité logarithmique, est une méthode efficace pour rechercher dans une liste triée, mais elle nécessite que la liste soit préalablement triée.

📖 7. Boucles & Types

🔑 Notions clés & Définitions

• Algorithme : Suite finie d'instructions permettant de résoudre un problème.
• Propriétés d’un algorithme : Finité, déterminisme, non ambiguïté.
• Structures de contrôle : Mécanismes permettant de diriger l'exécution du programme (conditions, boucles).
• Condition (if) : Instruction qui exécute un bloc de code si une condition est vraie, sinon un autre.
• Boucle bornée (for) : Répétition d’un bloc d’instructions un nombre fixe de fois.
• Boucle non bornée (while) : Répétition jusqu’à ce qu’une condition devienne fausse.
• Complexité algorithmique : Mesure du temps ou de l’espace consommé par un algorithme, exprimée en notation Big O (ex : O(1), O(log n), O(n), O(n²)).
• Recherche séquentielle : Parcours linéaire d’une liste pour trouver un élément, complexité O(n).
• Recherche dichotomique : Recherche dans une liste triée en divisant par deux à chaque étape, complexité O(log n).

📝 Points essentiels

• Les algorithmes doivent être finis, déterministes et non ambigus pour garantir leur fiabilité.
• Les structures de contrôle (if, for, while) permettent de gérer la logique et la répétition dans un programme.
• La complexité permet d’évaluer l’efficacité d’un algorithme : plus la notation Big O est faible, plus l’algorithme est performant.
• La recherche séquentielle est simple mais peu efficace pour de grandes listes. La recherche dichotomique est beaucoup plus rapide mais nécessite une liste triée.
• La boucle for est adaptée pour un nombre fixe d’itérations, tandis que la boucle while est utilisée quand le nombre d’itérations dépend d’une condition.

💡 À retenir

Les structures de contrôle et la gestion de la complexité sont essentielles pour écrire des algorithmes efficaces et optimisés, notamment lors de recherches dans des collections de données.

📖 8. Analyse de complexité & Cas d'usage

🔑 Notions clés & Définitions

• Algorithme : Suite finie d’instructions permettant de résoudre un problème. Il doit être précis, déterministe, et fini.
• Complexité algorithmique : Mesure du temps ou de l’espace mémoire utilisé par un algorithme en fonction de la taille de l’entrée, généralement exprimée en notation Big O.
• Notation Big O : Notation asymptotique qui caractérise la croissance du coût d’un algorithme. Exemples : O(1), O(log n), O(n), O(n²).
• Recherche séquentielle : Méthode de recherche d’un élément dans une liste non triée en parcourant chaque élément. Complexité : O(n).
• Recherche dichotomique : Méthode de recherche dans une liste triée en divisant par deux à chaque étape. Complexité : O(log n).

📝 Points essentiels

• La complexité permet d’évaluer la performance d’un algorithme en termes de temps (nombre d’opérations) ou d’espace.
• La notion de complexité varie selon la structure de contrôle utilisée (boucles, conditions).
• La recherche séquentielle est simple mais peu efficace pour de grandes listes (O(n)), tandis que la recherche dichotomique est beaucoup plus performante (O(log n)) mais nécessite une liste triée.
• La structure de contrôle (boucles, conditions) influence directement la complexité.
• La notion de cas d’usage concerne le choix de l’algorithme adapté selon la taille des données et la nature du problème.

💡 À retenir

L’analyse de complexité permet d’anticiper la performance d’un algorithme et d’optimiser le choix de la méthode en fonction du contexte, notamment entre recherche séquentielle et dichotomique selon la triabilité des données.

📊 Tableaux de Synthèse

Critère	Recherche séquentielle	Recherche dichotomique
Prérequis	Liste non triée	Liste triée
Méthode	Parcours linéaire	Division répétée de l’espace de recherche
Complexité	O(n)	O(log n)
Efficacité	Faible pour grandes listes	Très efficace pour grandes listes
Facilité d’implémentation	Simple	Plus complexe

Critère	Structures de contrôle	Complexité & Notations
Types	Condition (if-else), Boucles (for, while)	O(1), O(log n), O(n), O(n²)
Rôle	Gérer le flux d’exécution	Évaluer l’efficacité des algorithmes
Caractéristiques principales	Déterministe, Non ambigu	Limite supérieure du temps d’exécution

⚠️ Pièges & Confusions Fréquentes

1. Confondre algorithme fini et infini.
2. Oublier que la recherche dichotomique nécessite une liste triée.
3. Confondre complexité O(n) et O(log n).
4. Croire qu’un algorithme déterministe peut produire des résultats différents pour la même entrée.
5. Négliger l’importance de la propriété non ambiguë pour la clarté du code.
6. Confondre boucle bornée (for) et boucle non bornée (while) dans leur utilisation.
7. Sous-estimer l’impact de la complexité sur la performance pour de grandes données.
8. Confondre la complexité en temps et en espace.
9. Penser que la simplicité d’un algorithme garantit sa performance.
10. Oublier que la propriété finie assure la terminaison de l’algorithme.

✅ Checklist Examen

• Vérifier si l’algorithme est fini, déterministe et non ambigu.
• Identifier si la liste est triée pour appliquer la recherche dichotomique.
• Connaître la différence entre recherche séquentielle et dichotomique.
• Savoir calculer et interpréter les notations Big O : O(1), O(log n), O(n), O(n²).
• Pouvoir décrire le fonctionnement d’une boucle for et while.
• Expliquer le rôle des structures conditionnelles (if-else).
• Analyser la complexité d’un algorithme donné.
• Comprendre la propriété de déterminisme et son importance.
• Identifier la structure de contrôle utilisée dans un algorithme.
• Savoir quand utiliser une recherche séquentielle ou dichotomique.
• Connaître les principales propriétés d’un algorithme.
• Vérifier la terminaison d’un algorithme.