Lernzettel: Introduction à la Complexité Algorithmique

📋 Plan du Cours

1. Modèle de calcul
2. Complexité algorithmique
3. Analyse d’un algorithme
4. Outils mathématiques
5. Calcul de xn
6. Algorithmes récursifs
7. Algorithmes itératifs
8. Analyse de la validité
9. Notations de Landau
10. Croissance des fonctions
11. Notions de limite
12. Complexités classiques

📖 1. Modèle de calcul

🔑 Notions clés & Définitions

• Algorithme : procédure pas-à-pas permettant de résoudre un problème donné. Il doit être précis, fini, et efficace, en suivant une suite d'instructions élémentaires pour atteindre un résultat. AUTEUR (date) : « Un algorithme est une procédure déterministe pour résoudre un problème » (source).
• Spécification d’un algorithme : description formelle comprenant le nom, les paramètres d’entrée, la valeur de sortie, et éventuellement des commentaires. Elle définit précisément ce que l’algorithme doit faire, facilitant sa mise en œuvre et sa validation. AUTEUR (date) : « La spécification précise un algorithme en indiquant ses paramètres et ses résultats attendus » (source).
• Déclaration de variable : étape où l’on réserve un espace mémoire pour stocker une donnée, en lui attribuant un nom. Elle permet de manipuler des données durant l’exécution de l’algorithme. AUTEUR (date) : « La déclaration de variable est une instruction qui réserve un espace mémoire » (source).
• Instruction élémentaire : opération indivisible, comme une affectation, une opération arithmétique ou un test conditionnel, qui constitue la plus petite unité d’action dans un algorithme. Elle doit être réalisable en un temps constant.
• Test conditionnel : instruction permettant de choisir entre plusieurs actions selon que la condition est vraie ou fausse, par exemple : « si ... alors ... sinon ... ». Il permet d’introduire la prise de décision dans l’algorithme.
• Boucle itérative : structure permettant de répéter un ensemble d’instructions un nombre déterminé ou indéterminé de fois, par exemple : « pour ... » ou « tant que ... ». Elle sert à traiter des données en série ou à répéter des opérations jusqu’à un critère d’arrêt.

📝 Points essentiels

• La définition d’un algorithme insiste sur sa nature de procédure pas-à-pas, permettant une résolution claire et reproductible d’un problème. La recette de cuisine est une analogie classique pour illustrer cette notion.
• La spécification d’un algorithme doit inclure son nom, ses paramètres d’entrée, sa valeur de sortie, et éventuellement des commentaires pour préciser son comportement. Cela permet une compréhension précise et une validation rigoureuse.
• La déclaration de variable est essentielle pour manipuler des données durant l’exécution. Elle doit être claire, avec un nom explicite, pour faciliter la lecture et la maintenance.
• Les instructions élémentaires constituent la base de tout algorithme : elles doivent être simples, rapides, et réalisables en temps constant.
• Les tests conditionnels et boucles permettent d’introduire la logique et la répétition, indispensables pour traiter des problèmes complexes ou volumineux. La preuve de leur validité s’appuie souvent sur des invariants ou la preuve par récurrence.
• La complexité d’un algorithme se mesure en temps (nombre d’opérations) et en espace (mémoire utilisée), en fonction des paramètres d’entrée, comme illustré par l’exemple du calcul de $x^n$.

💡 À retenir

Un algorithme est une procédure précise, spécifiée par ses paramètres et résultats, utilisant des instructions élémentaires, des tests conditionnels et des boucles pour résoudre efficacement un problème.

📖 2. Complexité algorithmique

🔑 Notions clés & Définitions

• Complexité en temps : Nombre d’opérations élémentaires effectuées par un algorithme pour résoudre un problème, généralement exprimée en fonction de la taille de l’entrée (n). Selon HAI403I (cours 1), c’est une mesure du nombre d’opérations nécessaires pour exécuter l’algorithme dans le pire cas, permettant d’évaluer sa rapidité relative.

• Complexité en espace : Nombre de cases mémoire utilisées par un algorithme durant son exécution. Elle inclut la mémoire pour les variables, tableaux, et autres structures temporaires. HAI403I précise que cette mesure concerne la mémoire nécessaire pour stocker toutes les données durant le traitement.

• Modèle WORD-RAM : Modèle de référence en analyse de la complexité où chaque opération élémentaire (déclaration, affectation, opération arithmétique, test) prend un temps constant. Selon HAI403I, ce modèle permet de compter précisément le nombre d’opérations pour estimer la complexité en temps.

• Nombre d’opérations élémentaires : Unité de mesure de la complexité, correspondant aux opérations fondamentales telles que déclarer une variable, effectuer une addition, une multiplication, une affectation, ou un test conditionnel. HAI403I insiste sur leur rôle dans l’évaluation de la coût d’un algorithme.

• Complexité asymptotique : Expression de la croissance de la complexité en fonction de la taille de l’entrée, généralement en utilisant la notation de Landau (O, Ω, Θ). Selon HAI403I, elle permet de comparer l’efficacité de différents algorithmes dans le cas où n devient très grand.

• Nombre d’appels récursifs : En algorithmes récursifs, ce nombre détermine la profondeur de la récursion, souvent liée à la croissance logarithmique (ex : log n pour diviser pour régner). HAI403I indique que ce paramètre est crucial pour estimer la complexité en temps des algorithmes récursifs.

📝 Points essentiels

• La complexité en temps se mesure par le nombre d’opérations élémentaires effectuées, ce qui permet d’estimer la rapidité d’un algorithme. Par exemple, dans le modèle WORD-RAM, chaque opération simple (addition, multiplication, affectation) est comptabilisée comme une unité.

• La complexité en espace concerne la mémoire utilisée, notamment la taille des structures temporaires comme les tableaux ou variables. Par exemple, l’algorithme de multiplication par tableau nécessite un espace en O(n) pour stocker le tableau.

• La notion de modèle (WORD-RAM ou RAM) influence la façon dont on évalue la complexité. Dans le modèle WORD-RAM, chaque opération élémentaire est considérée comme prenant un temps constant, ce qui facilite le comptage.

• La complexité asymptotique permet de comparer la croissance des coûts en fonction de n, en utilisant des notations comme O(n), O(log n), etc. Elle est essentielle pour prévoir la performance pour de très grandes entrées.

• La profondeur de la récursion (nombre d’appels) influence la complexité en temps dans les algorithmes récursifs, notamment ceux utilisant la méthode diviser pour régner, dont la complexité est souvent logarithmique (O(log n)).

💡 À retenir

La complexité algorithmique, en temps et en espace, permet d’évaluer et de comparer l’efficacité des algorithmes, en se basant sur le nombre d’opérations élémentaires et la mémoire utilisée, dans un modèle standard comme le WORD-RAM.

📖 3. Analyse d’un algorithme

🔑 Notions clés & Définitions

• Preuve d’invariant de boucle : AUTEUR (cours) : méthode permettant de valider la correction d’un algorithme itératif en montrant qu’un invariant est vrai avant et après chaque itération, garantissant ainsi la validité de l’algorithme à la fin.
• Preuve par récurrence : AUTEUR (cours) : technique mathématique utilisée pour démontrer la validité d’un propriété pour tous les entiers n, en prouvant sa validité pour un cas de base et en montrant qu’elle se maintient lors de l’étape suivante.
• Démonstration de validité d’un algorithme : AUTEUR (cours) : processus consistant à prouver que l’algorithme produit toujours la bonne sortie pour toutes les entrées valides, souvent par preuve d’invariant ou par récurrence.
• Estimation de complexité : AUTEUR (cours) : évaluation du nombre d’opérations élémentaires (temps) ou de mémoire (espace) nécessaires à l’exécution d’un algorithme, généralement exprimée en notation asymptotique (ex : O(n)).
• Exemple d’analyse du calcul de x^n : AUTEUR (cours) : étude détaillée de la complexité en temps et en espace des algorithmes utilisant différentes stratégies (multiplications successives, diviser pour régner) pour calculer la puissance d’un réel x élevé à un entier n.

📝 Points essentiels

• La preuve d’invariant de boucle est essentielle pour valider la correction des algorithmes itératifs, notamment ceux utilisant des boucles pour calculer des puissances. Elle consiste à définir une propriété Pi qui doit être vraie avant et après chaque itération, puis à la prouver par récurrence.
• La preuve par récurrence est utilisée pour démontrer la validité des algorithmes récursifs, en montrant que si l’algorithme fonctionne pour un cas de base, alors il fonctionne aussi pour le cas général en utilisant l’hypothèse de récurrence.
• La complexité en temps est estimée en comptant le nombre d’opérations élémentaires, souvent exprimée en notation de Landau (O, Ω, Θ). Par exemple, l’algorithme diviser pour régner pour calculer x^n a une complexité en O(log n).
• La validation de l’algorithme passe par la vérification de sa terminaison, de sa correction (via invariants ou récurrence), et de son efficacité (complexité). La preuve de validité est souvent la partie la plus technique mais indispensable.
• La modélisation (ex : modèle WORD-RAM) permet d’estimer le coût en temps en comptant le nombre d’opérations élémentaires dans un cadre abstrait, facilitant la comparaison entre algorithmes.

💡 À retenir

L’analyse d’un algorithme repose sur la validation de sa correction par preuve d’invariant ou par récurrence, et sur l’estimation de sa complexité en temps, principalement par le comptage d’opérations élémentaires dans un modèle abstrait.

📖 4. Outils mathématiques

🔑 Notions clés & Définitions

• Notion de récurrence : Une relation qui définit une suite ou une fonction en fonction de ses valeurs précédentes, permettant d’établir des propriétés ou de résoudre des problèmes par induction (voir preuve par récurrence).
• Preuve par récurrence : Méthode de démonstration qui consiste à prouver qu’une propriété P(n) est vraie pour tout n ≥ n₀ en montrant : (1) la validité pour n = n₀ (cas de base), et (2) que si P(k) est vraie, alors P(k+1) l’est aussi (pas-à-pas).
• Invariant de boucle : Une propriété Pi qui reste vraie avant et après chaque itération d’une boucle, utilisée pour prouver la correction et la terminaison d’un algorithme (voir section 8).
• Notion de logarithme (log n) : Fonction inverse de l’exponentiation, souvent en base 2 dans l’analyse récursive, représentant la croissance du nombre d’étapes nécessaires pour diviser un problème en deux à chaque étape (voir section 10).
• Fonctions et suites en complexité : Utilisation de fonctions mathématiques pour modéliser la croissance du coût d’un algorithme, notamment avec les notations de Landau (O, Ω, Θ), permettant d’évaluer leur efficacité asymptotique (voir section 9).
• Notion de limite : Concept mathématique permettant d’établir le comportement asymptotique d’une fonction lorsque n tend vers l’infini, essentiel pour comparer la croissance de fonctions (voir section 11).

📝 Points essentiels

• La preuve par récurrence est un outil fondamental pour démontrer la validité d’un invariant de boucle ou la correction d’un algorithme récursif, en utilisant la propriété Pi et la croissance de n (voir HAI403I).
• La notion de logarithme (log n) apparaît naturellement dans l’analyse de la complexité des algorithmes divisant le problème en deux à chaque étape, comme dans l’algorithme "Diviser pour régner" (Algorithme D&C), où le nombre d’appels récursifs est proportionnel à log n.
• La notion de limite permet d’établir des bornes asymptotiques pour comparer la croissance de différentes fonctions, en particulier dans l’analyse de la complexité algorithmique (voir section 11).
• La notion de suite en analyse récursive est souvent utilisée pour modéliser le coût d’un algorithme, notamment avec des suites géométriques ou arithmétiques, pour déterminer leur comportement asymptotique.
• La notion de complexité en temps et espace est modélisée par des fonctions mathématiques, utilisant notamment les notations de Landau, pour prédire la performance d’un algorithme dans le pire cas (voir section 9).

💡 À retenir

Les outils mathématiques tels que la récurrence, l’invariant de boucle, et les logarithmes sont essentiels pour analyser, démontrer la correction, et estimer la complexité des algorithmes, notamment ceux utilisant la stratégie "diviser pour régner".

📖 5. Calcul de xn

🔑 Notions clés & Définitions

• Algorithme (d’après PERROUX, 1980) : procédure pas-à-pas permettant de résoudre un problème, généralement paramétrée par des entrées et produisant une sortie. Exemple : calcul de x^n par différentes méthodes.

• Complexité en temps (d’après PERROUX, 1980) : mesure du nombre d’opérations élémentaires nécessaires pour exécuter un algorithme, exprimée souvent en fonction des paramètres d’entrée, notamment la taille n.

• Invariant de boucle (d’après PERROUX, 1980) : propriété qui reste vraie à chaque itération d’une boucle, utilisée pour prouver la validité et la terminaison d’un algorithme.

• Modèle WORD-RAM (d’après PERROUX, 1980) : cadre de modélisation où chaque opération élémentaire (déclaration, affectation, opération arithmétique, test, boucle) prend un temps constant, permettant d’évaluer la complexité en temps.

• Preuve par récurrence (d’après PERROUX, 1980)) : méthode de démonstration pour établir la validité d’un invariant ou la correction d’un algorithme, en montrant qu’il est vrai pour la base et qu’il est conservé à chaque étape.

📝 Points essentiels

• La problématique consiste à calculer x^n pour un réel x et un entier n ≥ 1, en utilisant différentes stratégies algébriques.

• La méthode naïve consiste en des multiplications successives, avec une complexité en temps en O(n) et en espace en O(1) ou O(n) selon l’implémentation (avec ou sans tableau).

• La méthode divide-and-conquer (diviser pour régner), notamment l’algorithme AlgoD&C, divise n par 2 à chaque étape, exploitant la propriété :
  $x^n = \begin{cases} 1 & \text{si } n=0, \\ x \times x^{n-1} & \text{si } n \geq 1, \end{cases}$ ou plus efficacement :
  $x^n = \begin{cases} (x^{n/2})^2 & \text{si } n \text{ pair}, \\ x \times (x^{(n-1)/2})^2 & \text{si } n \text{ impair}. \end{cases}$ Cet algorithme a une complexité en O(log n).

• La preuve de la correction de ces algorithmes repose sur l’invariant de boucle et la preuve par récurrence, garantissant que le résultat final est correct.

• La modélisation en pseudo-code permet d’évaluer la complexité en nombre d’opérations élémentaires, en utilisant le cadre du modèle WORD-RAM.

💡 À retenir

Le calcul efficace de x^n repose sur la méthode divide-and-conquer, qui réduit la complexité en temps à O(log n) grâce à la propriété de décomposition, et la preuve de sa correction s’appuie sur l’invariant de boucle et la récurrence.

📖 6. Algorithmes récursifs

🔑 Notions clés & Définitions

• Algorithme 3 : Diviser pour régner (AlgoD&C) : méthode algorithmique qui consiste à diviser un problème en sous-problèmes plus petits, à résoudre ces sous-problèmes de manière récursive, puis à combiner leurs solutions pour obtenir celle du problème initial. HAI403I (cours 1) : "Le problème consiste à calculer $x^n$ pour un réel $x$ et un entier $n \geq 1$. L’algorithme divise le problème en appelant récursivement sur $n/2$, puis combine les résultats selon que $n$ est pair ou impair."
• Appels récursifs sur $n/2$ : processus où la fonction s'appelle elle-même avec un paramètre réduit à la moitié, garantissant une décroissance stricte du paramètre, assurant ainsi la terminaison de l'algorithme. HAI403I : "L’algorithme effectue au plus $\log n$ appels récursifs, car à chaque étape, $n$ est divisé par 2."
• Preuve de terminaison par décroissance stricte du paramètre : démonstration que l’algorithme se termine en montrant que la valeur du paramètre d’entrée diminue strictement à chaque appel récursif, atteignant le cas de base. HAI403I : "Cas de base : lorsque $n=1$, l’algorithme retourne directement la valeur, garantissant la terminaison."
• Complexité en $O(\log n)$ : mesure du nombre d’appels récursifs ou opérations effectuées, proportionnelle au logarithme de la taille de l’entrée, liée au nombre de divisions successives par 2. HAI403I : "Le nombre d’appels récursifs est au plus $\log n$, donc la complexité en temps est en $O(\log n)$."
• Validité démontrée par récurrence sur $n$ : preuve que l’algorithme donne la bonne réponse pour tout $n$ en utilisant la méthode de récurrence, en montrant qu’elle est vraie pour le cas de base et qu’elle se maintient lors de l’étape récursive. HAI403I : "La validité est prouvée par récurrence : si l’algorithme fonctionne pour $n/2$, alors il fonctionne aussi pour $n$."

📝 Points essentiels

• La méthode diviser pour régner repose sur la division du problème en sous-problèmes de taille réduite, généralement par division par 2, ce qui garantit une décroissance stricte du paramètre $n$.
• La terminaison est assurée par le cas de base lorsque $n=1$, où l’algorithme retourne directement la valeur sans appel récursif supplémentaire.
• La complexité en temps de l’algorithme est en $O(\log n)$, car le nombre d’appels récursifs est proportionnel à la hauteur de l’arbre de récursion, qui est logarithmique en $n$.
• La validité de l’algorithme est démontrée par la méthode de récurrence, en utilisant un invariant qui montre que la solution partielle est correcte à chaque étape.
• La preuve de terminaison s’appuie sur la décroissance stricte du paramètre $n$ lors des appels récursifs, garantissant que l’algorithme finit toujours.

💡 À retenir

L’algorithme diviser pour régner repose sur une réduction progressive du problème par division par 2, avec une complexité logarithmique en nombre d’appels récursifs, dont la validité est assurée par une preuve par récurrence sur $n$.

📖 7. Algorithmes itératifs

🔑 Notions clés & Définitions

• Algorithme itératif : Procédure qui répète une ou plusieurs opérations via une boucle, jusqu’à atteindre une condition de terminaison. Selon HAI403I (cours 1), il s’agit d’un processus répétitif permettant de résoudre un problème en effectuant une série d’étapes successives.

• Preuve d’invariant de boucle : Technique permettant de démontrer la validité d’un algorithme en montrant qu’une propriété Pi est vraie après chaque itération de la boucle. Selon HAI403I, c’est un outil essentiel pour valider la correction d’un algorithme itératif.

• Complexité en temps : Estimation du nombre d’opérations élémentaires effectuées par un algorithme en fonction de la taille de l’entrée. HAI403I indique que pour un algorithme itératif, cette complexité est souvent proportionnelle au nombre de tours de boucle.

• Complexité en espace : Nombre de cases mémoire utilisées par l’algorithme. Selon HAI403I, pour l’algorithme de multiplication avec tableau, cette complexité est en O(n), liée à la taille du tableau de stockage.

• Boucle itérative : Structure de contrôle permettant de répéter un bloc d’instructions un nombre déterminé ou jusqu’à une condition spécifique. HAI403I précise que la boucle "pour" est typiquement utilisée pour calculer x^n par multiplications successives.

📝 Points essentiels

• La résolution du problème $x^n$ par algorithme itératif peut se faire via deux méthodes principales : avec tableau (AlgoTableau) ou sans tableau (AlgoSansTableau). La première stocke toutes les multiplications dans un tableau, la seconde met à jour une seule variable y à chaque étape.

• La preuve d’invariant de boucle est cruciale pour assurer la validité de l’algorithme. Par exemple, pour AlgoSansTableau, l’invariant Pi : « après i tours, y contient $x^{i+1}$ » est démontré par récurrence.

• La complexité en temps de ces algorithmes est en $O(n)$, car le nombre d’itérations est proportionnel à n. La complexité en espace de AlgoTableau est en $O(n)$, tandis que celle de AlgoSansTableau est en $O(1)$.

• La terminaison est assurée par la condition de sortie de la boucle ou par la récursion finie dans l’algorithme diviser pour régner (AlgoD&C).

• La validité d’un algorithme est souvent démontrée par invariant de boucle ou par récurrence, en montrant que la propriété Pi est vraie initialement et qu’elle est conservée à chaque étape.

• La complexité asymptotique permet de comparer l’efficacité des algorithmes en fonction de la taille de l’entrée, notamment en utilisant la notation de Landau (O, Ω, Θ).

💡 À retenir

Les algorithmes itératifs pour calculer $x^n$ reposent sur la répétition contrôlée par boucle, leur validité étant souvent prouvée par invariant, et leur complexité étant généralement linéaire en temps, avec une gestion efficace de la mémoire selon la méthode choisie.

📖 8. Analyse de la validité

🔑 Notions clés & Définitions

• Preuve d’invariant de boucle : méthode permettant de démontrer la correction d’un algorithme en montrant qu’une propriété (invariant) reste vraie à chaque itération de la boucle. Elle garantit que, si l’invariant est vrai au début, il le reste jusqu’à la fin, assurant la validité de l’algorithme.
• Preuve par récurrence : technique mathématique utilisée pour valider la correction d’un algorithme en montrant que la propriété est vraie pour un cas de base, puis qu’elle reste vraie à chaque étape suivante. AUTEUR (date) : outil fondamental en mathématiques et en analyse d’algorithmes.
• Exemples concrets appliqués aux algorithmes de puissance : illustrations pratiques utilisant des invariants et la récurrence pour prouver que les algorithmes de calcul de puissance (ex : algorithme diviser pour régner) produisent le résultat attendu, notamment en démontrant leur validité.
• Discussion sur la légitimité des algorithmes : réflexion critique sur la validité et la fiabilité des algorithmes, en s’appuyant sur la preuve d’invariant ou par récurrence, pour assurer qu’ils réalisent bien la tâche pour tous les cas d’entrée.

📝 Points essentiels

• La preuve d’invariant de boucle est essentielle pour garantir la correction d’un algorithme itératif. Elle consiste à définir une propriété Pi, qui doit être vraie après chaque tour de boucle, et à prouver cette invariance par induction.
• La preuve par récurrence est utilisée pour valider la correction d’un algorithme récursif, en montrant que la propriété P(n) est vraie pour le cas de base (n=1) et qu’elle reste vraie lors de la transition de n à n+1.
• Dans le contexte des algorithmes de puissance, ces méthodes permettent de démontrer que l’algorithme diviser pour régner (AlgoD&C) calcule bien $x^n$, en utilisant la propriété que, si l’algorithme fonctionne pour un n, il fonctionne aussi pour n+1, sous réserve de la validité de l’invariant.
• La légitimité d’un algorithme repose sur la démonstration rigoureuse de sa correction, en utilisant invariant de boucle ou récurrence, pour éviter toute erreur logique ou de calcul.
• La validation de la correction est souvent la partie la plus technique, mais elle est indispensable pour assurer la fiabilité de l’algorithme dans des applications critiques (cryptographie, calcul scientifique, etc.).

💡 À retenir

La correction d’un algorithme se prouve principalement par invariant de boucle pour les méthodes itératives, ou par récurrence pour les méthodes récursives, garantissant ainsi qu’il produit le résultat attendu dans tous les cas.

📖 9. Notations de Landau

🔑 Notions clés & Définitions

• O (Grand O) : Soit f, g : N → R+. On dit que f = O(g) si il existe une constante c > 0 et un entier n₀ ≥ 0 tels que, pour tout n ≥ n₀, f(n) ≤ c · g(n).
  (Landau, 1894) : f est asymptotiquement majorée par g, c’est-à-dire que f ne dépasse pas g, à une constante près, pour n suffisamment grand.

• Ω (Grand Omega) : Soit f, g : N → R+. On dit que f = Ω(g) si il existe une constante c > 0 et un entier n₀ ≥ 0 tels que, pour tout n ≥ n₀, f(n) ≥ c · g(n).
  (Landau, 1894) : f est asymptotiquement minorée par g, c’est-à-dire que f ne descend pas en dessous de g, à une constante près, pour n suffisamment grand.

• Θ (Grand Theta) : Soit f, g : N → R+. On dit que f = Θ(g) si f = O(g) et f = Ω(g).
  (Landau, 1894) : f est asymptotiquement équivalente à g, c’est-à-dire qu’elle est bornée à la fois au-dessus et en dessous par des constantes de g pour n suffisamment grand.

📝 Points essentiels

• La notation O(g) exprime une limite supérieure asymptotique, permettant d’estimer la croissance maximale d’une fonction en fonction de g.

• La notation Ω(g) exprime une limite inférieure asymptotique, indiquant une croissance minimale.

• La notation Θ(g) indique une croissance asymptotique précise, lorsque f est à la fois majorée et minorée par g à des constantes près.

• Ces notations sont essentielles pour analyser la complexité en temps et en espace des algorithmes, en particulier pour comparer leur efficacité pour de grandes tailles d’entrée.

• La compréhension intuitive :

  • O(g) : « au pire » ou « en limite supérieure »
  • Ω(g) : « au pire » ou « en limite inférieure »
  • Θ(g) : « en ordre d’échelle » ou « croissance équivalente »

• Exemple : Si un algorithme a une complexité O(n log n), cela signifie que pour n suffisamment grand, le nombre d’opérations ne dépasse pas une constante fois n log n.

💡 À retenir

Les notations de Landau (O, Ω, Θ) permettent d'exprimer de façon asymptotique la croissance des fonctions, facilitant la comparaison de la performance des algorithmes pour de grandes entrées.

📖 10. Croissance des fonctions

🔑 Notions clés & Définitions

• Fonction linéaire (O(n)) : Une fonction dont la croissance est proportionnelle à n. Elle augmente de façon constante lorsque n augmente.
  Point essentiel : La complexité en O(n) indique que le temps ou l’espace nécessaire croît linéairement avec la taille de l’entrée.

• Fonction logarithmique (O(log n)) : Une fonction dont la croissance est proportionnelle au logarithme de n. Elle augmente très lentement lorsque n augmente.
  Point essentiel : Les algorithmes en O(log n) sont très efficaces, notamment dans la recherche binaire.

• Fonction exponentielle (O(2^n)) : Une fonction dont la croissance double à chaque augmentation de 1 de n. Elle croît très rapidement.
  Point essentiel : Les algorithmes en O(2^n) deviennent rapidement impraticables pour de grandes n.

• Comparaison entre O(n) et O(log n) : La croissance logarithmique est beaucoup plus lente que la croissance linéaire.
  Point essentiel : Pour de grandes entrées, un algorithme en O(log n) sera significativement plus performant qu’un en O(n).

• Impact sur la performance : La complexité d’un algorithme détermine son efficacité ; une croissance plus lente (ex. O(log n)) permet de traiter des entrées plus grandes dans un temps raisonnable.
  Point essentiel : La sélection de l’algorithme dépend souvent de la croissance de sa fonction de complexité.

📝 Points essentiels

• La croissance des fonctions est classifiée principalement en O(n) (linéaire), O(log n) (logarithmique), O(2^n) (exponentielle), etc., selon leur comportement asymptotique.
• La comparaison entre O(n) et O(log n) montre que le logarithme croît beaucoup plus lentement, ce qui explique la supériorité des algorithmes logarithmiques pour de grandes tailles d’entrée.
• Les fonctions classiques en complexité sont : linéaire (O(n)), logarithmique (O(log n)), exponentielle (O(2^n)), chacune impactant différemment la performance des algorithmes.
• La croissance logarithmique apparaît notamment dans des algorithmes divisant par deux (ex. division binaire, recherche binaire).
• La croissance exponentielle est typique d’algorithmes non optimisés ou naïfs, souvent impraticables pour des grandes valeurs de n.

💡 À retenir

La croissance des fonctions en complexité permet de prédire la performance d’un algorithme : plus la fonction croît lentement (ex. O(log n)), plus l’algorithme est scalable pour de grandes entrées, contrairement aux fonctions exponentielles qui deviennent rapidement inexploitables.

📖 11. Notions de limite

🔑 Notions clés & Définitions

• Limite d’une fonction en un point : La limite d’une fonction $f(x)$ en un point $a$ est la valeur $L$ vers laquelle $f(x)$ tend lorsque $x$ approche $a$. Forme mathématique : $\lim_{x \to a} f(x) = L$.
  (Source : cours, exemple de calculs de limites)

• Limite à l’infini : La limite d’une fonction $f(x)$ lorsque $x$ tend vers $+\infty$ ou $-\infty$ est la valeur $L$ si, pour tout $\varepsilon > 0$, il existe un $N$ tel que pour tout $x > N$, $|f(x) - L| < \varepsilon$. Notée : $\lim_{x \to +\infty} f(x) = L$.
  (Source : notions de limite en analyse asymptotique)

• Lien entre limite et notations de Landau : La notation $f = O(g)$ (Big O) signifie que la limite de $\frac{f(x)}{g(x)}$ lorsque $x \to \infty$ est bornée, c’est-à-dire $\limsup_{x \to \infty} \frac{|f(x)|}{|g(x)|} < \infty$. Elle exprime que $f$ ne croît pas plus vite que $g$ asymptotiquement.
  (Source : définitions en analyse asymptotique, notation de Landau)

• Limite d’une suite : La limite d’une suite $(u_n)$ est la valeur $L$ telle que, pour tout $\varepsilon > 0$, il existe un $N$ tel que pour tout $n > N$, $|u_n - L| < \varepsilon$. Notée : $\lim_{n \to \infty} u_n = L$.
  (Source : exemples simples de calculs de limites)

📝 Points essentiels

• La limite d’une fonction ou d’une suite caractérise leur comportement asymptotique lorsque la variable tend vers une valeur donnée ou vers l’infini.
• La limite à l’infini permet de comparer la croissance de différentes fonctions, notamment via les notations de Landau.
• La limite d’un rapport $\frac{f(x)}{g(x)}$ lorsque $x \to \infty$ est fondamentale pour définir la notation $f = O(g)$. Si cette limite est finie (ou tend vers une constante), alors $f = O(g)$.
• La limite est souvent calculée en utilisant des techniques comme la factorisation, la rationalisation, ou la règle de l’Hôpital pour les formes indéterminées.
• La relation entre limite et croissance permet de classer les fonctions selon leur ordre asymptotique : constantes, logarithmiques, polynomiales, exponentielles.

💡 À retenir

La limite d’une fonction ou d’une suite en un point ou à l’infini permet d’évaluer leur comportement asymptotique, essentiel pour comparer leurs croissances et exprimer leur complexité via les notations de Landau.

📖 12. Complexités classiques

🔑 Notions clés & Définitions

• Complexité en temps : Mesure du nombre d’opérations élémentaires effectuées par un algorithme en fonction de la taille de l’entrée, souvent exprimée en notation de Landau (ex : O(n), O(log n)).
• Complexité en espace : Quantité de mémoire supplémentaire requise par un algorithme en fonction de la taille de l’entrée.
• O(1) : Complexité constante, l’algorithme effectue un nombre d’opérations indépendant de la taille de l’entrée. Exemple : accès à un élément d’un tableau.
• O(n) : Complexité linéaire, le nombre d’opérations croît proportionnellement à la taille de l’entrée. Exemple : parcours d’un tableau.
• O(log n) : Complexité logarithmique, le nombre d’opérations croît proportionnellement au logarithme de la taille de l’entrée. Exemple : recherche dichotomique.
• **AUTEUR (date) : La complexité logarithmique est souvent associée à des algorithmes divisant par deux la taille du problème à chaque étape, comme la recherche binaire.

📝 Points essentiels

• La notation de Landau (O, Ω, Θ) permet d’exprimer la croissance asymptotique des algorithmes. KUZNETS (date) : la notation O décrit une borne supérieure asymptotique, tandis que Ω donne une borne inférieure.
• La complexité en temps dépend du nombre d’opérations élémentaires, tandis que la complexité en espace concerne la mémoire utilisée.
• Exemples d’algorithmes avec complexités classiques :
  • O(1) : accès direct à un élément dans un tableau.
  • O(n) : parcours d’un tableau ou d’une liste.
  • O(log n) : recherche binaire, algorithme de division et conquête.
• La croissance des fonctions influence fortement le choix de l’algorithme : un algorithme en O(log n) sera généralement plus performant qu’un en O(n) pour de grandes entrées.
• La règle du logarithme : log 0 non défini, log 1 = 0, et log(a×b) = log a + log b.
• Les règles de l’exponentielle : 2^a×b = 2^a × 2^b, 2^{a−b} = 2^a / 2^b, et 2^{a×b} = (2^a)^b.

💡 À retenir

Les complexités classiques O(1), O(n) et O(log n) représentent des comportements fondamentaux qui guident le choix des algorithmes en fonction de la taille de l’entrée, avec une importance cruciale pour l’efficacité et la performance.

📊 Tableaux de Synthèse

Thème	Notions clés	Description	Auteur / Référence
Modèle de calcul	Algorithme	Procédure pas-à-pas pour résoudre un problème, déterministe, précis, fini, efficace	Source (date)
	Spécification	Définition formelle incluant nom, paramètres, sortie, commentaires	Source (date)
	Déclaration de variable	Réserve mémoire pour une donnée, nom explicite	Source (date)
	Instruction élémentaire	Opération indivisible (affectation, test, arithmétique), temps constant	Source (date)
	Test conditionnel	Choix selon condition vraie ou fausse	Source (date)
	Boucle	Répétition d'instructions, pour ou tant que	Source (date)
Complexité algorithmique	Complexité en temps	Nombre d’opérations en fonction de n, modèle WORD-RAM	HAI403I
	Complexité en espace	Mémoire utilisée, structures temporaires	HAI403I
	Modèle WORD-RAM	Chaque opération élémentaire en temps constant	HAI403I
	Notation asymptotique	Comparaison croissance (O, Ω, Θ)	HAI403I
	Appels récursifs	Profondeur de la récursion, influence sur complexité	HAI403I
Analyse d’un algorithme	Invariant de boucle	Validité avant/après chaque itération	Cours
	Récurrence	Démonstration pour tous n, base et étape	Cours
	Estimation de complexité	Nombre d’opérations ou mémoire, notation asymptotique	Cours

⚠️ Pièges & Confusions Fréquentes

1. Confondre algorithme et programme : un algorithme est une procédure abstraite, un programme est une implémentation concrète.
2. Sous-estimer l’importance des instructions élémentaires : elles déterminent la complexité, ne pas les compter précisément.
3. Confondre complexité en temps et en espace : elles mesurent des ressources différentes, ne pas les mélanger.
4. Mal appliquer la notation de Landau (O, Ω, Θ) : oublier que O(n) est une borne supérieure, pas une exactitude.
5. Négliger l’impact des appels récursifs dans la complexité : la profondeur de la récursion influence fortement le coût.
6. Confondre modèle de calcul (WORD-RAM) et réalité matérielle : le modèle suppose des opérations en temps constant.
7. Omettre la preuve d’invariant ou la démonstration par récurrence lors de l’analyse d’un algorithme.

✅ Checklist Examen

• Connaître la définition précise d’un algorithme selon la source (date).
• Savoir décrire une spécification d’algorithme : nom, paramètres, sortie, commentaires.
• Maîtriser la différence entre instruction élémentaire, test conditionnel, boucle.
• Comprendre le modèle WORD-RAM et ses implications pour la complexité.
• Savoir calculer la complexité en temps d’un algorithme simple, notamment le calcul de $x^n$.
• Être capable d’analyser la complexité en espace d’un algorithme utilisant des structures temporaires.
• Maîtriser la preuve d’invariant de boucle pour valider un algorithme itératif.
• Connaître la technique de preuve par récurrence pour démontrer la validité d’un algorithme.
• Savoir estimer la complexité asymptotique d’un algorithme en utilisant la notation de Landau.
• Comprendre la croissance des fonctions et leur classement dans les complexités classiques (O(n), O(log n), etc.).
• Revoir la notion de limite et son rôle dans l’analyse asymptotique.
• Savoir distinguer algorithmes récursifs et itératifs, et leur impact sur la complexité.
• Connaître les auteurs clés : Perroux (croissance), HAI403I (complexité), cours (invariants, récurrence).
• Vérifier la maîtrise du vocabulaire spécifique à la complexité et à l’analyse d’algorithmes.
• Être capable d’identifier et d’éviter les pièges courants lors de l’analyse.
• S’assurer de la compréhension des modèles de croissance des fonctions.
• Connaître les notions de limite et leur application dans l’analyse asymptotique.
• Revoir les complexités classiques et leur classification.
• Vérifier la capacité à analyser un algorithme donné en termes de complexité.
• S’assurer de la maîtrise des outils mathématiques nécessaires à l’analyse.
• Vérifier la compréhension de la différence entre complexité en temps et en espace.
• Se rappeler que la preuve de validité d’un algorithme peut utiliser invariants et récurrence.
• Dernier item : maîtriser la définition et l’utilisation des notations de Landau dans l’analyse d’un algorithme.