Revision sheet: Introduction aux fondamentaux de l'algorithmique

📋 Plan du Cours

1. Définition d'un algorithme
2. Opérations élémentaires
3. Variables et affectation
4. Types de variables
5. Structures conditionnelles
6. Boucles et répétitions
7. Parcours de tableau
8. Complexité d'un algorithme
9. Notion de notation 𝑂

📖 1. Définition d'un algorithme

🔑 Notions clés & Définitions

Algorithme
Selon AUTEUR (date), un algorithme est une suite finie d'opérations élémentaires ordonnées qui prend des entrées et produit des sorties. En d'autres termes, c'est une procédure précise permettant de transformer des données initiales en résultats souhaités par une série d'étapes successives. Le terme « algorithme » provient du nom du mathématicien perse Muhammad Ibn Mūsā al-Khuwārizmī, actif au 9ème siècle, ce qui montre que cette notion est antérieure à l'informatique moderne. La définition insiste sur la nature finie et ordonnée de la suite d'opérations, ainsi que sur la capacité de l'algorithme à traiter des entrées pour produire des résultats.

Procédure de calcul bien définie
Ce concept désigne une méthode claire et précise pour effectuer un calcul, qui doit spécifier de manière univoque chaque étape à suivre. Elle doit prendre en entrée une ou plusieurs valeurs et fournir en sortie une ou plusieurs valeurs. La procédure doit être sans ambiguïté pour garantir que chaque étape est compréhensible et reproductible.

Suite finie d'opérations élémentaires
Il s'agit d'une séquence limitée dans le temps, c'est-à-dire comportant un nombre fini d'étapes, où chaque étape est une opération élémentaire. La finitude garantit que l'algorithme ne tourne pas indéfiniment, et la nature d'opérations élémentaires assure que chaque étape est simple et facilement compréhensible.

Enchaînement déterminé
Ce terme indique que l'ordre dans lequel les opérations sont effectuées est strictement défini. La séquence doit être suivie dans un ordre précis, sans ambiguïté, pour que l'algorithme fonctionne correctement. Cet enchaînement est crucial car il assure la cohérence et la reproductibilité du processus.

Calcul
Le calcul désigne l'ensemble des opérations effectuées dans le cadre de l'algorithme. Il s'agit de transformer des données d'entrée en résultats en appliquant une série d'opérations successives, conformément à la procédure définie.

📝 Points essentiels

Un algorithme est une suite finie d'opérations élémentaires ordonnées qui prend des entrées et produit des sorties. Le terme « algorithme » trouve ses origines dans le nom du mathématicien perse Muhammad Ibn Mūsā al-Khuwārizmī, datant du 9ème siècle, ce qui montre que cette notion est très ancienne et antérieure à l'informatique. La définition insiste sur deux aspects fondamentaux : d'une part, la nature de la procédure comme étant bien définie, c’est-à-dire précise et sans ambiguïté, et d'autre part, le fait que cette procédure consiste en une suite d'opérations élémentaires. L'ordre de ces opérations est crucial pour assurer le bon fonctionnement de l'algorithme, car chaque étape doit suivre strictement la précédente selon un enchaînement déterminé. La notion d'opération élémentaire désigne une action simple, facilement compréhensible, comme « peser 100 g de farine », ce qui garantit que chaque étape peut être réalisée et vérifiée aisément.

💡 À retenir

Un algorithme est une recette précise et ordonnée d'actions simples, conçue pour résoudre un problème en transformant des entrées en sorties. Son efficacité repose sur la clarté de ses étapes et leur enchaînement déterminé.

📖 2. Opérations élémentaires

🔑 Notions clés & Définitions

Opération élémentaire
Une opération élémentaire est une action simple, claire et non ambiguë, compréhensible par l'exécutant. Elle doit pouvoir être réalisée sans confusion ni interprétation multiple. Par exemple, « peser 100 g de farine » constitue une opération élémentaire car sa réalisation est précise, compréhensible par tous et ne prête pas à ambiguïté.

Action simple
Une action simple correspond à une opération élémentaire. Elle se caractérise par sa simplicité, sa clarté et sa compréhension immédiate. Elle ne nécessite pas de décomposition supplémentaire pour être exécutée ou comprise.

Opération complexe
Une opération complexe est une action qui ne peut pas être considérée comme une seule opération élémentaire. Elle regroupe plusieurs actions ou étapes, souvent ambiguës ou nécessitant une interprétation, comme « prendre de la farine, des œufs, du sucre et du chocolat afin de faire un gâteau au chocolat ». Cette opération manque de précision, ce qui la rend difficile à exécuter ou à comprendre sans décomposition.

Précision d'une opération
La précision d'une opération désigne le degré de détail et de clarté avec lequel l'action doit être effectuée. Une opération précise est décomposée en opérations élémentaires ou formulée de manière à éviter toute ambiguïté. Par exemple, « mettre la balance à zéro (faire la tare), puis verser la farine jusqu'à ce que le chiffre 100 s'affiche » est une opération précise, décomposée en étapes élémentaires.

Interprétation unique
L'interprétation unique désigne une situation où une opération peut être comprise et réalisée de la même manière par tous, sans ambiguïté. Elle garantit que l'action sera effectuée de façon identique par différents exécutants, ce qui est essentiel pour la fiabilité d’un algorithme ou d’un processus.

📝 Points essentiels

Une opération élémentaire est une action simple, claire et non ambiguë, compréhensible par la personne chargée de l’effectuer. Elle doit être formulée de manière à ce que sa réalisation ne prête ni à confusion ni à interprétation multiple. Par exemple, « peser 100 g de farine » est une opération élémentaire, car tout le monde peut comprendre ce que cela implique, et sa réalisation est sans ambiguïté.

La distinction entre opération élémentaire et opération complexe dépend du niveau de précision et de compréhension nécessaire. Une opération complexe, comme « faire un gâteau au chocolat », regroupe plusieurs actions qui, sans décomposition, peuvent prêter à confusion ou nécessiter une interprétation. Cependant, une opération complexe peut être décomposée en opérations élémentaires plus fines pour assurer une meilleure clarté et un meilleur contrôle.

Certaines opérations, initialement considérées comme complexes, peuvent être décomposées en opérations élémentaires plus fines. Par exemple, « peser 100 g de farine » pourrait être encore plus précis en indiquant « mettre la balance à zéro, puis verser la farine jusqu’à ce que le chiffre 100 s’affiche ». Cette décomposition permet d’assurer une précision optimale et d’éviter toute ambiguïté dans l’exécution.

La granularité des actions dans un algorithme doit être suffisamment fine pour éviter toute confusion ou interprétation erronée. La précision dans la définition des opérations garantit leur compréhension unique et leur exécution fiable, ce qui est essentiel pour la cohérence et la réussite de l’ensemble du processus.

💡 À retenir

La granularité des actions dans un algorithme doit être suffisamment fine pour garantir une compréhension claire et une exécution sans ambiguïté. La distinction entre opération élémentaire et complexe repose sur le niveau de précision et de compréhension nécessaire, et une opération complexe peut souvent être décomposée en opérations élémentaires pour plus de clarté.

📖 3. Variables et affectation

🔑 Notions clés & Définitions

Variable
Une variable est un conteneur nommé qui stocke une valeur modifiable. Elle permet de représenter une donnée dans un programme ou un algorithme, et cette donnée peut être modifiée au cours de l'exécution. La variable est identifiée par un nom appelé identificateur.
Exemple : si l’on écrit b = faux, alors b est une variable qui contient la valeur booléenne faux.

Identificateur
L’identificateur est le nom donné à une variable. Il sert à désigner de façon unique le conteneur dans lequel on stocke une valeur. L’identificateur doit respecter certaines règles de nommage, mais celles-ci ne sont pas précisées ici.
Exemple : dans x = 5, x est l’identificateur.

Affectation
L’affectation consiste à stocker une valeur dans une variable. Elle se réalise en utilisant un symbole spécifique, soit le signe égal =, soit le signe flèche <-. Lorsqu’on effectue une affectation, la valeur située à droite du symbole est placée dans la variable située à gauche.
Exemple :

• a = 10 : la valeur 10 est affectée à la variable a.
• b <- 20 : la valeur 20 est affectée à la variable b.

Initialisation
L’initialisation correspond à la première affectation d’une variable. C’est la première fois qu’une variable reçoit une valeur, permettant ainsi de lui donner une identité et une valeur de départ.
Exemple : si on écrit x = 0 pour la première fois, cela constitue l'initialisation de x.

Signe égal (=)
Le signe égal sert uniquement à réaliser une affectation. Il ne doit pas être confondu avec le symbole de comparaison. Lorsqu’on écrit x = 5, cela signifie que la variable x reçoit la valeur 5.
Important : ce symbole ne sert pas à tester l’égalité entre deux valeurs, mais à leur assignation.

Signe flèche (<-)
Le signe flèche <- est une autre notation pour l’affectation. Il fonctionne de la même façon que le signe égal, en plaçant la valeur de droite dans la variable de gauche.
Exemple : y <- 15 affecte la valeur 15 à la variable y.

📝 Points essentiels

• Une variable est un conteneur nommé qui stocke une valeur modifiable, permettant de représenter et de manipuler des données dans un algorithme.
• L’affectation consiste à stocker une valeur dans une variable en utilisant le signe égal = ou la flèche <-. La valeur située à droite du symbole est placée dans la variable située à gauche.
• La première affectation d’une variable est appelée initialisation. Elle permet de donner une valeur de départ à la variable.
• Le signe = sert uniquement à faire une affectation, et non à comparer deux valeurs. La comparaison d’égalité entre deux nombres utilise le symbole ==.

💡 À retenir

Visualiser les variables comme des boîtes nommées où l'on peut ranger et modifier des valeurs au cours de l'algorithme permet de mieux comprendre leur rôle : elles sont des conteneurs dont le contenu peut évoluer, facilitant la gestion dynamique des données dans un programme.

📖 4. Types de variables

🔑 Notions clés & Définitions

Type basique : Il s'agit d'un type de variable qui représente une catégorie simple de données, généralement définie par le langage de programmation. Les types basiques incluent notamment l’entier, le réel et le booléen. Ces types sont fondamentaux car ils permettent de manipuler des données élémentaires et sont souvent utilisés comme base pour construire des types plus complexes.

Entier : Selon le contenu source, un entier est un type basique représentant des nombres entiers, c’est-à-dire sans partie décimale. Il peut être positif, négatif ou nul. Par exemple, 0, -3, 42 sont des entiers. La manipulation d’entiers est essentielle pour compter, indexer ou effectuer des opérations arithmétiques précises.

Réel : Le type réel désigne un nombre pouvant contenir une partie fractionnaire, c’est-à-dire une valeur décimale. Par exemple, 3.14, -0.001, 2.71828 sont des réels. Ce type est utilisé pour représenter des valeurs continues ou approximatives, notamment dans les calculs scientifiques ou mathématiques.

Booléen : Ce type représente une valeur logique qui ne peut prendre que deux états : vrai ou faux. Il est souvent utilisé pour les conditions, les tests logiques ou les décisions dans un programme. Par exemple, une expression booléenne peut être « n > 0 » ou « estActif == vrai ».

Type construit : Ce terme désigne un type de variable qui est constitué à partir de types plus simples ou d’autres types. Il permet de créer des structures de données plus complexes, adaptées à des besoins spécifiques. Par exemple, un enregistrement ou une structure composée de plusieurs variables de types différents peut être considéré comme un type construit.

Tableau dynamique : Un tableau dynamique est un ensemble ordonné de variables du même type, dont la taille peut varier durant l’exécution du programme. Contrairement à un tableau statique, sa capacité n’est pas fixée à l’avance, ce qui permet d’ajouter ou de retirer des éléments selon les besoins. L’accès aux éléments se fait via un indice, qui est un entier compris entre 1 et N, où N est la taille du tableau à un instant donné.

📝 Points essentiels

Les types basiques incluent donc trois principaux types : entier, réel et booléen. Ces types fondamentaux permettent de représenter des données simples et d’effectuer des opérations de base. Un tableau est un ensemble ordonné de variables du même type, indexées de 1 à N, ce qui facilite la gestion de collections de données homogènes. La liste est une variante particulière de tableau, qualifiée de dynamique, car sa taille peut varier durant l’exécution du programme. La gestion des tableaux implique l’utilisation d’indices pour accéder à leurs éléments, ces indices étant compris entre 1 et N, permettant une organisation structurée et un accès direct aux données.

💡 À retenir

Les variables sont associées à des types qui déterminent la nature des données qu’elles contiennent ainsi que leur organisation. Les types basiques comme l’entier, le réel et le booléen sont essentiels pour manipuler des données élémentaires, tandis que les tableaux, notamment dynamiques, permettent d’organiser et d’accéder efficacement à des collections de variables du même type.

📖 5. Structures conditionnelles

🔑 Notions clés & Définitions

Instruction conditionnelle
Une instruction conditionnelle est une commande permettant d'exécuter un ou plusieurs blocs d'instructions en fonction de la véracité d'une condition. Elle sert à orienter le flux d'exécution d'un programme selon des tests logiques, en réalisant des choix. La structure conditionnelle permet ainsi de faire varier le comportement du programme selon les résultats de ces tests.

Expression booléenne
Une expression booléenne est une expression qui peut être évaluée à l'une des deux valeurs possibles : VRAI ou FAUX. Elle sert à représenter une condition dans une instruction conditionnelle. Par exemple, une comparaison comme x > 5 est une expression booléenne qui sera vraie si x est supérieur à 5, sinon elle sera fausse.

Bloc d'instructions
Un bloc d'instructions est un ensemble d'instructions regroupées et exécutées ensemble. Dans le contexte des structures conditionnelles, un bloc d'instructions est délimité par une indentation ou par des délimiteurs spécifiques (comme des accolades en certains langages). Il s'agit de l'ensemble des opérations qui seront réalisées si la condition est vérifiée ou si la partie 'sinon' est choisie.

Si... alors... sinon
Il s'agit d'une structure conditionnelle courante permettant de réaliser deux chemins d'exécution différents selon que la condition est vraie ou fausse. La syntaxe générale est :

• si (condition) alors (bloc d'instructions)
• sinon (optionnel, autre bloc d'instructions)
  Elle permet d'exécuter un bloc si la condition est vérifiée, et un autre si elle ne l'est pas.

Condition
La condition est une expression booléenne qui est évaluée lors de l'exécution. Elle détermine le chemin à suivre dans la structure conditionnelle. La condition doit être formulée de manière à pouvoir être évaluée à vrai ou faux, et elle constitue le test logique qui guide la prise de décision.

📝 Points essentiels

La structure conditionnelle permet d'exécuter des blocs d'instructions selon la véracité d'une condition. Elle fonctionne en évaluant une expression booléenne, qui doit être vraie ou fausse. Si cette condition est vraie, le bloc d'instructions associé est exécuté ; si elle est fausse, le programme peut exécuter un autre bloc, celui de la partie 'sinon' (qui est optionnelle). L'importance de l'indentation est capitale pour délimiter ces blocs, notamment dans certains langages où elle remplace les délimiteurs explicites. La partie 'sinon' n'est pas obligatoire, ce qui permet une prise de décision simple ou plus complexe selon les besoins. En somme, cette structure est essentielle pour orienter le flux d'exécution d’un algorithme en fonction de tests logiques.

💡 À retenir

La structure conditionnelle permet de prendre des décisions dans un algorithme en utilisant des tests logiques qui orientent le flux d'exécution. La condition, une expression booléenne évaluée à vrai ou faux, détermine le chemin à suivre, et l'indentation est essentielle pour délimiter clairement les blocs d'instructions. La partie 'sinon' est optionnelle mais offre une flexibilité supplémentaire pour gérer plusieurs cas.

📖 6. Boucles et répétitions

🔑 Notions clés & Définitions

• AUTEUR : voir section 1

Boucle 'pour' : La boucle 'pour' s'utilise lorsque le nombre d'itérations est connu à l'avance. Elle permet d'exécuter un bloc d'instructions un nombre précis de fois, souvent en utilisant un compteur qui s'incrémente ou se décrémente à chaque étape. Elle est particulièrement adaptée pour parcourir un tableau ou une liste d'éléments, ou pour répéter une opération un nombre fixe de fois.

Compteur de boucle : Le compteur de boucle est une variable utilisée pour compter le nombre d'itérations effectuées dans une boucle. Il est généralement initialisé à une valeur de départ, modifié à chaque passage dans la boucle (par exemple, incrémenté de 1), et souvent utilisé comme index ou pour arrêter la boucle lorsque sa valeur atteint une limite. La gestion du compteur est essentielle pour contrôler la durée d'exécution de la boucle.

Boucle infinie : Une boucle infinie est une boucle qui ne possède pas de condition de sortie ou dont la condition ne devient jamais fausse. Elle entraîne une répétition continue et indéfinie, ce qui peut provoquer un blocage ou un arrêt du programme si elle n’est pas contrôlée ou interrompue. La prévention des boucles infinies nécessite de s’assurer que la condition de sortie finira par devenir fausse.

Condition de boucle : La condition de boucle est une expression qui détermine si la boucle doit continuer ou s’arrêter. Elle doit être soigneusement conçue pour éviter les boucles infinies, en garantissant qu’elle deviendra fausse à un moment donné lors de l’exécution de la boucle. La condition est évaluée avant chaque itération dans le cas de 'tant que' et généralement dans la structure 'pour'.

📝 Points essentiels

La boucle 'tant que' répète un bloc tant qu'une condition est vraie. Elle commence par vérifier cette condition, et si elle est remplie, elle exécute le bloc d'instructions. La vérification se fait avant chaque itération, ce qui signifie que si la condition est fausse dès le départ, le bloc ne sera pas exécuté du tout. Par exemple, dans un algorithme, on peut écrire :

tant que i < 10 faire 
   i ← i + 1 
fin tant que 

Cela signifie que tant que la variable i est inférieure à 10, on incrémente i de 1 à chaque passage. La boucle s’arrête dès que la condition n’est plus vraie, c’est-à-dire lorsque i atteint ou dépasse 10.

La boucle 'pour' s’utilise lorsque le nombre d’itérations est connu à l’avance. Elle est souvent structurée ainsi :

pour i allant de 1 à 10 faire 
   // instructions 
fin pour 

Dans cet exemple, le bloc d’instructions sera exécuté exactement 10 fois. La boucle 'pour' est particulièrement utile pour parcourir un tableau ou pour répéter une tâche un nombre précis de fois, grâce à un compteur qui s’incrémente à chaque étape.

Le compteur de boucle est une variable qui sert à compter le nombre d’itérations. Il est initialisé à une valeur de départ (souvent 0 ou 1), puis modifié à chaque passage dans la boucle (par exemple, i ← i + 1). Il permet de suivre le nombre d’exécutions et peut aussi servir d’index pour accéder à des éléments dans une structure de données.

Il faut éviter les boucles infinies en s’assurant que la condition de boucle devienne fausse à un moment donné. Cela implique de définir correctement la condition de sortie et de veiller à ce que les modifications apportées à la variable de contrôle (comme le compteur) soient suffisantes pour faire évoluer la résultat de la condition. Par exemple, si l’on écrit une boucle 'tant que' avec la condition i < 10, il faut que, dans le corps de la boucle, i soit modifié de façon à ce qu’elle finisse par atteindre ou dépasser 10, ce qui met fin à la boucle.

💡 À retenir

Maîtriser la répétition contrôlée d'instructions, via les boucles 'tant que' et 'pour', permet d’automatiser efficacement des tâches répétitives dans un algorithme. La gestion du compteur et la vérification rigoureuse de la condition de boucle sont essentielles pour éviter les boucles infinies et assurer la bonne exécution du programme.

📖 7. Parcours de tableau

🔑 Notions clés & Définitions

Parcours séquentiel
Le parcours séquentiel consiste à examiner chaque élément d'un tableau un par un, dans l'ordre, jusqu'à ce que l'on ait vérifié tous les éléments ou obtenu le résultat souhaité. Il s'agit d'une méthode systématique pour parcourir un tableau afin d'extraire ou de vérifier des informations spécifiques.

Indice de tableau
L'indice de tableau désigne la position d'un élément dans un tableau. En algorithmique, l'indice du premier élément d'un tableau est traditionnellement 1, ce qui signifie que le premier élément est accessible via l'indice 1, le deuxième via 2, et ainsi de suite. Cet indice permet d'accéder directement à un élément précis dans le tableau.

Fonction longueur
La fonction 'longueur' retourne le nombre d'éléments présents dans un tableau. Elle permet de connaître la taille du tableau, ce qui est essentiel pour déterminer la limite de parcours lors d'une itération. Elle est souvent utilisée pour éviter de dépasser la dernière position du tableau lors du parcours.

Recherche d'occurrence
La recherche d'occurrence consiste à vérifier si une valeur spécifique est présente dans un tableau. L'algorithme associé parcourt le tableau et compare chaque élément à la valeur recherchée. Si la valeur est trouvée, l'algorithme peut retourner vrai, sinon faux.

Booléen de présence
Le booléen de présence est une variable de type booléen (VRAI ou FAUX) utilisée pour indiquer si une valeur donnée est présente dans le tableau. Il est initialisé généralement à FAUX, puis mis à VRAI dès que la valeur recherchée est trouvée lors du parcours.

📝 Points essentiels

Le parcours séquentiel consiste à examiner chaque élément d'un tableau un par un. Lorsqu'on souhaite vérifier si une valeur est présente dans un tableau, on parcourt tous ses éléments dans l'ordre, en comparant chaque élément à la valeur recherchée. La recherche s'arrête dès que l'on trouve la valeur, ce qui permet d'optimiser le processus en évitant de parcourir inutilement le reste du tableau.

L'indice du premier élément d'un tableau est traditionnellement 1 en algorithmique. Cela signifie que pour accéder au premier élément, on utilise l'indice 1, au deuxième indice 2, etc. Cette convention facilite la lecture et la compréhension des parcours séquentiels.

La fonction 'longueur' est essentielle pour connaître la taille du tableau. Elle permet de définir la limite supérieure de la boucle de parcours, évitant ainsi de dépasser la dernière position du tableau. Par exemple, si un tableau a une longueur n, la boucle de parcours s'effectue de i = 1 jusqu'à i = n.

Lorsqu'on souhaite déterminer si une valeur x est présente dans un tableau t, on peut utiliser un algorithme de recherche d'occurrence. Cet algorithme parcourt le tableau en comparant chaque élément t[i] à x. Si une correspondance est trouvée, un booléen de présence tr est mis à VRAI et la recherche peut s'arrêter. Sinon, après avoir vérifié tous les éléments, tr reste FAUX, indiquant que x n'est pas dans le tableau.

Le booléen de présence est un outil simple mais puissant pour indiquer si une valeur a été trouvée lors du parcours. Il commence généralement à FAUX, puis devient VRAI dès que la valeur recherchée est rencontrée. Il permet de gérer efficacement la vérification de la présence d'une valeur dans un tableau.

💡 À retenir

Le parcours séquentiel est une méthode systématique pour examiner chaque élément d'un tableau, essentielle pour la recherche ou l'extraction d'informations. La connaissance de l'indice de départ, de la longueur du tableau et l'utilisation d'un booléen de présence permettent de réaliser efficacement cette opération.

📖 8. Complexité d'un algorithme

🔑 Notions clés & Définitions

Complexité en temps : La complexité en temps d’un algorithme mesure le nombre d’opérations élémentaires nécessaires pour résoudre un problème en fonction de la taille des données d’entrée. Elle permet d’évaluer la rapidité avec laquelle un algorithme s’exécute lorsque la taille des données augmente. La complexité en temps est souvent exprimée en fonction d’une variable n, représentant la taille de l’entrée, et se mesure en nombre d’opérations élémentaires effectuées par l’algorithme.

Complexité en mémoire : La complexité en mémoire désigne la quantité d’espace mémoire supplémentaire requise par un algorithme pour traiter une donnée d’entrée. Elle inclut la mémoire nécessaire pour stocker les données, mais aussi pour les variables temporaires ou les structures auxiliaires utilisées durant l’exécution. La complexité en mémoire dépend également de la taille de l’entrée et de la manière dont l’algorithme gère ses ressources.

Nombre d'opérations élémentaires : Il s’agit du comptage précis des opérations fondamentales effectuées par un algorithme, telles que les comparaisons, les affectations ou les opérations arithmétiques simples. Le nombre d’opérations élémentaires est une mesure concrète permettant d’évaluer la complexité en temps. Par exemple, dans le cas d’un algorithme de recherche dans un tableau, le nombre d’opérations peut inclure la vérification de chaque élément jusqu’à trouver la valeur recherchée ou atteindre la fin du tableau.

Cas pire : Le cas pire d’un algorithme correspond à la situation où le nombre d’opérations élémentaires nécessaires est maximal. Il représente donc la limite supérieure de la complexité en temps, indépendamment des autres cas possibles. Par exemple, pour une recherche linéaire dans un tableau, le cas pire survient lorsque l’élément recherché n’est pas présent ou se trouve en dernière position, nécessitant de parcourir tout le tableau.

Efficacité d'algorithme : L’efficacité d’un algorithme se mesure principalement par sa complexité en temps dans le pire des cas, car cela garantit une limite supérieure de ses performances. Elle permet de comparer différents algorithmes en fonction de leur capacité à traiter rapidement de grandes quantités de données. Une efficacité élevée correspond à une faible complexité asymptotique, ce qui signifie que l’algorithme nécessite peu d’opérations pour des entrées de grande taille.

📝 Points essentiels

La complexité en temps est une mesure du nombre d’opérations élémentaires nécessaires pour résoudre un problème, et elle dépend directement de la taille des données d’entrée. Lorsqu’on analyse un algorithme, on distingue généralement la complexité dans le pire des cas, qui correspond au maximum d’opérations à effectuer. Ce cas est crucial car il garantit la performance minimale de l’algorithme dans toutes les situations possibles. Plus la taille des données augmente, plus la complexité en temps influence le temps d’exécution de l’algorithme. En pratique, pour comparer plusieurs algorithmes, on se concentre souvent sur leur complexité asymptotique, c’est-à-dire leur comportement lorsque la taille de l’entrée tend vers l’infini. Cela permet d’évaluer leur efficacité relative pour traiter de grandes quantités de données, en se concentrant sur leur ordre de grandeur plutôt que sur des valeurs précises.

💡 À retenir

L’évaluation de l’efficacité d’un algorithme repose principalement sur sa complexité en temps dans le pire des cas, qui indique le nombre maximal d’opérations nécessaires pour traiter des données de grande taille. Cette analyse permet de comparer la performance de différents algorithmes et de choisir celui qui sera le plus adapté à des situations où la rapidité est essentielle.

📖 9. Notion de notation 𝑂

🔑 Notions clés & Définitions

Notation 𝑂 (grand O) : La notation 𝑂 exprime la complexité asymptotique d'un algorithme pour des entrées très grandes. Elle permet de caractériser la croissance du nombre d'opérations ou du temps d'exécution en fonction de la taille de l'entrée, en se concentrant sur le comportement à grande échelle. La notation 𝑂 fournit une limite supérieure asymptotique, c'est-à-dire qu'elle indique une borne supérieure sur la croissance du coût de l'algorithme lorsque la taille de l'entrée tend vers l'infini.

Ordre de grandeur asymptotique : C'est une mesure qui indique comment la complexité d'un algorithme évolue lorsque la taille de l'entrée devient très grande. Elle permet de comparer la croissance des coûts entre différents algorithmes, en se concentrant uniquement sur le terme dominant de la fonction de complexité.

Suppression des constantes : Lorsqu'on utilise la notation 𝑂, on supprime systématiquement les constantes multiplicatives et les termes de moindre ordre. Par exemple, dans l'expression 3𝑛 + 4, on ne conserve que 𝑛, car la constante 3 et le terme constant 4 ne changent pas la croissance asymptotique pour des n très grands.

Dominance asymptotique : Un terme est dit dominer asymptotiquement un autre si, lorsque n devient très grand, le premier terme croît plus rapidement que le second. Par exemple, dans 6𝑛² + 3𝑛 + 10, le terme 6𝑛² domine asymptotiquement, car sa croissance est plus rapide que celle de 3𝑛 ou de 10.

Polynôme de complexité : Un polynôme de degré quelconque, par exemple 6𝑛² + 3𝑛 + 10, est caractérisé par ses termes de degré supérieur. La notation 𝑂 ne conserve que le terme de plus haut degré, en supprimant les coefficients et constantes, pour exprimer la croissance asymptotique.

📝 Points essentiels

La notation 𝑂 exprime la complexité asymptotique d'un algorithme pour des valeurs de n très grandes. Elle sert à analyser la croissance du nombre d'opérations ou du temps d'exécution en ignorant les constantes et les coefficients devant les termes dominants. Par exemple, dans l'expression 3𝑛 + 4, la notation 𝑂(𝑛) indique que, pour n suffisamment grand, la complexité est proportionnelle à n, en ignorant la constante 3 et le terme constant 4.

Pour un polynôme comme 6𝑛² + 3𝑛 + 10, seule la composante de plus haut degré, ici 𝑛², est conservée dans la notation 𝑂, ce qui donne 𝑂(𝑛²). La suppression des constantes et des termes de moindre ordre permet de simplifier la comparaison entre différents algorithmes en se concentrant uniquement sur leur croissance asymptotique.

Ce processus consiste à :

• supprimer la constante multiplicative (par exemple, 10 dans 6𝑛² + 3𝑛 + 10),
• conserver uniquement le terme de plus haut degré (ici 𝑛²),
• supprimer le coefficient devant ce terme (donc 6 dans 6𝑛²), pour obtenir 𝑂(𝑛²).

💡 À retenir

Utiliser la notation 𝑂 permet de simplifier et de standardiser l’expression de la complexité des algorithmes à grande échelle, en se concentrant sur leur croissance asymptotique. Elle facilite la comparaison des performances des algorithmes lorsque la taille des données devient très grande.

📅 Repères chronologiques

(aucun date explicitement mentionnée dans le contenu fourni, section omise)

📊 Tableaux de Synthèse

Thème	Concept	Définition	Exemple / Détails	Auteur
Définition d’un algorithme	Algorithme	Suite finie d’opérations élémentaires ordonnées, prenant des entrées et produisant des sorties	-	Muhammad Ibn Mūsā al-Khuwārizmī (9ème siècle)
Opérations élémentaires	Opération élémentaire	Action simple, claire, non ambiguë, facilement réalisable et compréhensible	Peser 100 g de farine	-
Variables et affectation	Variable	Conteneur nommé stockant une valeur modifiable, identifiée par un nom (identificateur)	b = faux	-

⚠️ Pièges & Confusions Fréquentes

1. Confondre opération élémentaire et opération complexe : une opération complexe peut être décomposée en opérations élémentaires pour plus de précision.
2. Négliger la granularité : des actions trop grossières peuvent entraîner des ambiguïtés ou erreurs d’interprétation.
3. Confusion entre enchaînement déterminé et aléatoire : l’ordre doit être strictement défini pour garantir la fiabilité.
4. Omettre la notion de finitude : un algorithme doit comporter un nombre fini d’étapes.
5. Interprétation multiple d’une opération : doit garantir une compréhension unique pour éviter les erreurs.
6. Nier l’importance de la précision dans la formulation des opérations pour assurer leur exécution fiable.
7. Confusion entre variable et valeur : la variable est un conteneur, la valeur est ce qu’elle contient.

✅ Checklist Examen

• Connaître la définition d’un algorithme selon Muhammad Ibn Mūsā al-Khuwārizmī.
• Savoir que l’algorithme est une suite finie d’opérations élémentaires ordonnées.
• Comprendre la différence entre opération élémentaire et opération complexe.
• Maîtriser la notion de granularité dans la définition des opérations.
• Savoir définir une opération élémentaire (action simple, claire, non ambiguë).
• Connaître le rôle et la nature d’une variable (conteneur nommé modifiable).
• Savoir ce qu’est une affectation et comment elle modifie la valeur d’une variable.
• Identifier un identificateur comme le nom donné à une variable.
• Reconnaître l’importance de l’enchaînement déterminé pour le bon fonctionnement d’un algorithme.
• Comprendre le concept de suite finie d’opérations pour garantir la terminaison.
• Maîtriser la notion de précision dans la formulation des opérations pour éviter toute ambiguïté.
• Savoir que chaque étape doit suivre strictement l’ordre défini dans l’algorithme.