Revision sheet: Optimisation des Boucles et Diviseurs

📋 Plan du Cours

1. Boucles et optimisation
2. Diviseurs entiers
3. Boucles et procédures
4. Fonctions premiers
5. Racine carrée approximation
6. Tableaux de réels
7. Somme et écart type

📖 1. Boucles et optimisation

🔑 Notions clés & Définitions

• Boucle for : Structure de répétition qui parcourt une séquence de valeurs, généralement de 1 à n, pour exécuter un bloc de code à chaque étape. Selon Hervé Owsinski (2025-2026), elle permet d'itérer efficacement sur un intervalle défini pour réaliser des opérations répétées.

• Optimisation par réduction de la borne : Technique consistant à limiter le nombre d'itérations d'une boucle en utilisant une borne inférieure ou égale à √n, car au-delà de cette valeur, les diviseurs se répètent. Hervé Owsinski (2025-2026) souligne que cette méthode réduit considérablement le nombre de cycles, notamment pour la recherche de diviseurs.

• Comparaison du nombre de cycles : Analyse du nombre d'itérations ou de cycles effectués par une boucle complète (de 1 à n) versus une boucle optimisée (de 1 à √n). La réduction de la borne permet de diminuer la complexité algorithmique, passant d’O(n) à O(√n), ce qui est crucial pour l'efficacité.

• Utilisation de la fonction racineCarree : Fonction qui calcule une approximation de √n, permettant de définir la borne de boucle optimisée. Selon Hervé Owsinski (2025-2026), cette fonction facilite la mise en œuvre de la réduction de la borne en évitant la surcharge de calculs inutiles.

• Affichage des diviseurs avec condition sur divisibilité : Procédé consistant à parcourir une boucle et à afficher les valeurs k pour lesquelles n MOD k = 0, en utilisant la borne √n pour limiter le nombre de tests. Cette approche optimise la recherche tout en permettant une sortie claire et concise.

📝 Points essentiels

• La boucle for est un outil fondamental pour parcourir efficacement un intervalle de 1 à n, notamment dans la recherche de diviseurs ou autres opérations répétitives.
• La réduction de la borne de boucle à √n repose sur le fait que tout diviseur supérieur à √n a un correspondant inférieur à √n, évitant ainsi de parcourir inutilement tout l'intervalle jusqu'à n.
• La fonction racineCarree, définie par Hervé Owsinski (2025-2026), permet d’obtenir une approximation précise de √n, ce qui optimise la délimitation de la boucle.
• La comparaison du nombre de cycles montre que la boucle optimisée nécessite beaucoup moins d’itérations (environ √n) comparé à la boucle complète (n), ce qui réduit la complexité et le temps d'exécution.
• Lors de l’affichage des diviseurs, la condition sur divisibilité (n MOD k = 0) combinée à la borne √n permet une sortie efficace et évite les tests superflus.

💡 À retenir

L’utilisation de la boucle for avec une borne réduite à √n, combinée à la fonction racineCarree, permet d’optimiser significativement la recherche de diviseurs, réduisant le nombre de cycles et améliorant la performance des algorithmes.

📖 2. Diviseurs entiers

🔑 Notions clés & Définitions

• Diviseur entier d’un nombre n : Un entier k est un diviseur de n si et seulement si n MOD k = 0, c’est-à-dire que k divise n sans reste. (source : Hervé Owsinski, 2025-2026)

• Méthode naïve pour trouver tous les diviseurs : Consiste à parcourir tous les entiers de 1 à n, en vérifiant pour chacun si n MOD k = 0, ce qui indique que k est un diviseur. Cette méthode est simple mais coûteuse en cycles pour de grands n. (source : Hervé Owsinski, 2025-2026)

• Utilisation du modulo pour tester la divisibilité : Le modulo (n MOD k) donne le reste de la division de n par k. Si ce reste est zéro, alors k est un diviseur de n. (source : Hervé Owsinski, 2025-2026)

• Calcul de l’autre diviseur par division entière : Lorsqu’un diviseur k est trouvé, l’autre diviseur peut être calculé par n DIV k, où DIV représente la division entière. Cela permet d’éviter de parcourir tout le tableau jusqu’à n, en se limitant à √n. (source : Hervé Owsinski, 2025-2026)

• Cas particulier des diviseurs carrés parfaits : Si k est un diviseur de n et que k = n DIV k, alors n est un carré parfait et k est la racine carrée de n. Dans ce cas, k ne doit être affiché qu’une seule fois. (source : Hervé Owsinski, 2025-2026)

📝 Points essentiels

• La recherche de diviseurs peut se faire efficacement en limitant la boucle à √n, car tout diviseur supérieur à √n a son complément inférieur à √n. Lorsqu’on trouve un diviseur k, on calcule automatiquement son complément n DIV k. Si k = n DIV k, cela indique un diviseur carré parfait, et on ne doit l’afficher qu’une seule fois.

• La méthode naïve consiste à tester tous les k de 1 à n, ce qui est coûteux pour de grands n. La méthode optimisée limite la recherche à √n, réduisant considérablement le nombre de tests (de n à √n).

• Lorsqu’un diviseur k est trouvé, l’autre est n DIV k. Si ces deux valeurs sont égales, cela indique un carré parfait, et seul k doit être affiché.

• La vérification de la divisibilité par modulo est essentielle pour déterminer si un entier est un diviseur.

💡 À retenir

La recherche efficace des diviseurs d’un nombre n repose sur la limite √n et l’utilisation du modulo pour tester la divisibilité, en exploitant la relation entre diviseurs et leur complémentaire par division entière.

📖 3. Boucles et procédures

🔑 Notions clés & Définitions

• Appel de procédures dans des boucles imbriquées : utilisation d'une procédure appelée à l'intérieur d'une boucle, elle-même imbriquée dans une autre boucle, permettant de répéter des opérations complexes pour plusieurs paramètres ou plages de valeurs.

• Procédure affDiviseurs1a10() : procédure qui affiche tous les diviseurs des entiers compris entre 1 et 10 en utilisant deux boucles différentes (une boucle pour parcourir les nombres, une autre pour tester la divisibilité).

• Procédure affDiviseursVite(n) : procédure qui affiche tous les diviseurs d’un nombre entier n en utilisant une boucle allant jusqu’à √n, optimisant ainsi le nombre de cycles (voir racineCarree (exercices 3.2) pour la méthode de calcul de racine).

• Réutilisation de affDiviseursVite dans affDiviseurs1a10Court() : appel de la procédure affDiviseursVite(n) à l’intérieur d’une boucle pour traiter plusieurs valeurs, permettant de simplifier le code et d’éviter la duplication.

• Procédure affDiviseursDe(a, b) : procédure qui affiche tous les diviseurs des entiers compris entre a et b en utilisant affDiviseursVite(n), illustrant la modularité et la réutilisation de procédures.

📝 Points essentiels

• L’utilisation de boucles imbriquées permet de parcourir efficacement une plage de valeurs tout en testant une condition (divisibilité) pour chaque valeur, comme dans affDiviseurs1a10().

• La procédure affDiviseursVite(n) optimise la recherche de diviseurs en limitant la boucle à √n, ce qui réduit considérablement le nombre de cycles (exercices 1.2, 2.2, 3.2).

• La réutilisation de affDiviseursVite dans affDiviseurs1a10Court() ou affDiviseursDe(a, b) montre l’intérêt de modulariser le code pour éviter la duplication et faciliter la maintenance.

• La gestion des boucles imbriquées doit respecter l’ordre logique : boucle principale pour parcourir les nombres, boucle interne pour tester la divisibilité, avec des conditions pour optimiser ou limiter les tests (exercices 2.1, 2.2, 2.3, 2.4).

• La fonction racineCarree (exercices 3.2) est utilisée pour limiter la nombre de tests dans affDiviseursVite, ce qui illustre l’intégration entre différentes procédures pour optimiser les algorithmes.

• La structure des procédures permet de combiner efficacité (via √n) et simplicité (boucles imbriquées), tout en favorisant la réutilisation dans différents contextes.

💡 À retenir

Les procédures avec boucles imbriquées, combinées à des appels de fonctions optimisées comme racineCarree, permettent de réduire la complexité algorithmique tout en maintenant une structure modulaire et réutilisable.

📖 4. Fonctions premiers

🔑 Notions clés & Définitions

• Fonction primalite(n) : Fonction qui retourne un booléen indiquant si le nombre entier n est premier. Elle doit être optimisée en évitant les tests inutiles, notamment en utilisant la borne √n pour limiter les diviseurs à tester.
• Optimisation par divisibilité par 2 : Vérification préalable si n est divisible par 2, ce qui permet d’éliminer rapidement tous les nombres pairs autres que 2, réduisant ainsi le nombre de tests à effectuer.
• Test des diviseurs impairs : Après avoir vérifié la divisibilité par 2, on teste uniquement les diviseurs impairs de 3 à √n par pas de 2, conformément à la recommandation de KUZNETS (courbe en U inversé des inégalités) pour limiter les essais.
• Arrêt anticipé : Dès qu’un diviseur est trouvé, la fonction retourne faux immédiatement, évitant ainsi de poursuivre inutilement les tests, ce qui optimise la performance.
• Utilisation de la borne √n : La recherche de diviseurs s’arrête dès que le diviseur testé dépasse √n, car si n n’a pas de diviseurs jusqu’à cette borne, il est premier (voir aussi la légitimité, voir section 3).

📝 Points essentiels

• La fonction primalite(n) commence par tester la divisibilité par 2. Si n est divisible par 2 et n ≠ 2, elle retourne faux immédiatement.
• Ensuite, elle teste les diviseurs impairs k de 3 jusqu’à √n, en incrémentant k de 2 à chaque étape. Si n est divisible par l’un de ces k, la fonction retourne faux.
• La vérification s’arrête dès qu’un diviseur est trouvé, évitant des cycles inutiles.
• La borne √n limite le nombre de tests, ce qui rend la fonction efficace pour de grands nombres.
• La méthode repose sur la propriété que si n n’a pas de diviseurs ≤ √n, alors n est premier, conformément à la théorie de KUZNETS (courbe en U inversé des inégalités).

💡 À retenir

La fonction primalite(n), optimisée par le test de divisibilité par 2 puis par les diviseurs impairs jusqu’à √n, permet une vérification efficace de la primalité en évitant les tests superflus et en arrêtant dès qu’un diviseur est trouvé.

📖 5. Racine carrée approximation

🔑 Notions clés & Définitions

• racineCarree(a, precision) : Fonction qui retourne une approximation de la racine carrée du réel 'a' en utilisant la suite récursive rn = (rn−1 + a / rn−1) / 2, avec une initialisation r0 = 1. La précision correspond au nombre d'itérations de la suite.
• suite récursive rn = (rn−1 + a / rn−1) / 2 : Méthode d'approximation basée sur la méthode de Héron, permettant d'améliorer progressivement l'estimation de la racine carrée en utilisant la valeur précédente rn−1.
• initialisation r0 = 1 : Première valeur de la suite, choisie arbitrairement comme point de départ pour l'itération.
• précision (nombre d'itérations) : Critère déterminant la qualité de l'approximation, chaque itération affinant le résultat. Plus le nombre d'itérations est élevé, plus l'approximation est précise.
• Appel dans affDiviseursVite : La fonction racineCarree est utilisée pour déterminer la borne supérieure de la boucle en limitant le nombre de diviseurs à tester jusqu'à cette approximation.

📝 Points essentiels

• La méthode repose sur la convergence rapide de la suite rn vers √a, assurée par la formule de Héron.
• La précision est contrôlée par le nombre d'itérations, ce qui permet d'ajuster la précision selon les besoins.
• La fonction est utilisée dans le contexte de la recherche de diviseurs pour limiter la boucle jusqu'à √n approximé, évitant ainsi de parcourir inutilement toutes les valeurs jusqu'à n.
• La suite récursive permet une approximation efficace sans calculs coûteux, contrairement à la méthode naïve de test jusqu'à n.
• La formule rn = (rn−1 + a / rn−1) est une version simplifiée de la méthode de Newton pour la racine carrée.

💡 À retenir

La fonction racineCarree utilise la méthode de Héron, une suite récursive efficace pour approcher √a, dont la précision dépend du nombre d'itérations, et est essentielle pour optimiser la recherche de diviseurs en limitant la boucle à √n approximé.

📖 6. Tableaux de réels

🔑 Notions clés & Définitions

• TabReel : type représentant un tableau de réels. Hervé Owsinski (2025-2026) : "Un tableau de réels est une structure de données indexée, permettant de stocker une série de valeurs en mémoire, accessible par leur indice."
• achats : tableau de type TabReel de longueur 52, contenant les montants dépensés chaque semaine. Hervé Owsinski (2025-2026) : "Ce tableau permet de suivre l'évolution des dépenses hebdomadaires sur une année."
• total(achats, n) : fonction calculant la somme des n premiers éléments du tableau achats. Hervé Owsinski (2025-2026) : "Elle parcourt les n premières cases du tableau pour accumuler leur somme."
• ecartType(achats, n) : fonction calculant l'écart type des n premiers éléments du tableau achats. Hervé Owsinski (2025-2026) : "L'écart type mesure la dispersion des valeurs par rapport à la moyenne, indiquant leur cohérence."
• Formule de l'écart type : √(x² − (x)²), où x est la moyenne des valeurs et x² la moyenne des carrés. Hervé Owsinski (2025-2026) : "Elle repose sur la différence entre la moyenne des carrés et le carré de la moyenne, puis la racine carrée de cette différence."

📝 Points essentiels

• La structure TabReel est définie comme un tableau de réels de taille fixe, ici 52 pour représenter une année hebdomadaire. La notation T[i] désigne la valeur stockée à l’indice i, avec i allant de 0 à la taille du tableau moins un.
• La fonction total(achats, n) permet de calculer rapidement la somme des dépenses sur les n premières semaines en cumulant les valeurs de T[0] à T[n−1].
• La fonction ecartType(achats, n) utilise la formule √(totalDesCarres(achats, n) / n − (total(achats, n) / n)²), où totalDesCarres calcule la somme des carrés des valeurs. Elle indique la cohérence des dépenses hebdomadaires.
• La précision dans le calcul de l’écart type repose sur la fonction racineCarree, qui utilise la suite itérative rn = (rn−1 + a / rn−1) / 2, initialisée à 1, pour obtenir une approximation de la racine carrée du réel a avec une précision donnée.
• La distinction entre T (le tableau), i (l’indice), et T[i] (la valeur à l’indice i) est fondamentale pour manipuler efficacement les tableaux en algorithmique.

💡 À retenir

Les tableaux de réels, combinés avec des fonctions comme total et ecartType, permettent d’analyser efficacement la dispersion et la moyenne de séries de données numériques, essentielles en statistiques et en gestion financière.

📖 7. Somme et écart type

🔑 Notions clés & Définitions

• total(achats:TabReel, n:entier) : Fonction qui calcule la somme des n premiers éléments d’un tableau de réels en utilisant une boucle while pour additionner chaque valeur stockée dans le tableau, en initialisant la somme à 0 et en incrémentant un indice local.
• ecartType(achats:TabReel, n:entier) : Fonction qui retourne l’écart type des achats sur les n premières semaines, en utilisant la formule √(x² − (x)²), où x est la moyenne des valeurs et x² la moyenne des carrés, en combinant deux fonctions auxiliaires pour calculer ces moyennes.
• totalDesCarres(achats:TabReel, n:entier) : Fonction qui calcule la somme des carrés des n premiers éléments du tableau, en utilisant une boucle while pour accumuler la somme des valeurs au carré.
• Paramètres d’entrée/sortie dans fonctions : Utilisation de variables locales pour stocker les indices et les résultats intermédiaires, permettant de gérer la progression dans la boucle while et de retourner le résultat final. La boucle while s’exécute tant que l’indice est inférieur à n, avec un incrément contrôlé.
• Gestion des paramètres dans racineCarree : Fonction qui utilise une boucle while pour itérer la suite de Newton (rn = (rn−1 + a / rn−1) / 2), initialisée à 1, et qui s’arrête après un nombre précis d’itérations (précision), permettant une approximation de la racine carrée.

📝 Points essentiels

• La somme des n premiers éléments d’un tableau est calculée en initialisant une variable somme à 0, puis en utilisant une boucle while pour ajouter chaque élément (achats[i]) à cette somme, en incrémentant l’indice local jusqu’à n.
• L’écart type est une mesure de dispersion, calculée ici par la formule √(x² − (x)²), où x est la moyenne des valeurs et x² la moyenne des carrés, permettant d’évaluer la variabilité des achats.
• La fonction totalDesCarres permet de calculer la moyenne des carrés des valeurs, étape essentielle pour le calcul de l’écart type, en utilisant une boucle while pour accumuler les carrés.
• La fonction racineCarree, basée sur la méthode de Newton, utilise une boucle while pour effectuer un nombre fixe d’itérations (précision), afin d’obtenir une approximation de la racine carrée, en utilisant une variable intermédiaire pour stocker la valeur courante.
• La gestion des paramètres dans ces fonctions repose sur des variables locales pour l’indice, la somme, la moyenne, et la racine approximative, permettant une exécution contrôlée et précise sans utiliser de variables globales.

💡 À retenir

Les calculs de somme et d’écart type dans un tableau de réels s’appuient sur des boucles while pour parcourir efficacement les éléments, en utilisant des variables locales pour stocker résultats intermédiaires et indices, ce qui facilite la gestion et la précision des opérations.

📊 Tableaux de Synthèse

Critère	Boucles classiques (1 à n)	Boucles optimisées (1 à √n)	Auteur / Référence
Complexité	O(n)	O(√n)	Hervé Owsinski (2025-2026)
Utilisation principale	Recherche de diviseurs, opérations répétées	Recherche efficace de diviseurs, optimisation	Hervé Owsinski (2025-2026)
Fonction clé	Boucle for, modulo, racineCarree	Boucle for, modulo, racineCarree	Hervé Owsinski (2025-2026)
Avantage	Simplicité, exhaustivité	Rapidité, réduction du nombre de cycles	Hervé Owsinski (2025-2026)

Critère	Recherche naïve (1 à n)	Recherche optimisée (1 à √n)	Auteur / Référence
Méthode	Vérification de divisibilité pour tous k	Vérification jusqu’à √n, complément par division	Hervé Owsinski (2025-2026)
Cas particulier	Diviseurs carrés parfaits	Éviter double affichage pour carrés parfaits	Hervé Owsinski (2025-2026)

⚠️ Pièges & Confusions Fréquentes

1. Confondre boucle de 1 à n et boucle de 1 à √n, menant à une complexité incorrecte.
2. Oublier de vérifier si un diviseur est un carré parfait (k = n DIV k), entraînant des doublons.
3. Utiliser la méthode naïve pour de grands n, ce qui augmente inutilement le nombre de cycles.
4. Ne pas utiliser la fonction racineCarree pour limiter la boucle, réduisant l’efficacité.
5. Confondre le test de divisibilité (n MOD k = 0) avec une division classique.
6. Ne pas calculer le complément n DIV k après avoir trouvé un diviseur k.
7. Oublier que tout diviseur supérieur à √n a un complément inférieur, évitant ainsi la recherche exhaustive.

✅ Checklist Examen

• Connaître la définition de la boucle for et ses usages en optimisation.
• Savoir expliquer la technique de réduction de la borne à √n pour la recherche de diviseurs.
• Maîtriser la fonction racineCarree et son rôle dans l’optimisation.
• Comprendre la différence entre la méthode naïve et la méthode optimisée pour trouver des diviseurs.
• Savoir utiliser le modulo pour tester la divisibilité.
• Connaître la relation entre un diviseur k et son complément n DIV k.
• Être capable d’écrire une procédure pour afficher les diviseurs d’un nombre en utilisant √n.
• Comprendre l’intérêt de modulariser le code avec des procédures réutilisables.
• Savoir comment limiter le nombre de cycles dans une boucle imbriquée pour la recherche de diviseurs.
• Connaître la définition d’un carré parfait et la gestion spécifique de ses diviseurs.
• Connaître Hervé Owsinski comme référence pour les notions de boucle et optimisation.
• Vérifier la maîtrise de la différence entre boucle naïve et boucle optimisée dans le contexte de la recherche de diviseurs.