Notes de cours — Algorithmique II et rappel d’algorithmique I

Objectifs et plan du module

• Ce cours vise à répondre à trois questions majeures sur un algorithme:
  • Sa correction?
  • Son efficacité?
  • Comment comparer deux algorithmes résolvant le même problème P lorsque les deux donnent des résultats corrects?
• Problèmes abordés: comparaison d’algorithmes A1 et A2, mesure de l’efficacité, et choix du meilleur algorithme à exploiter.

Plan du module

• Organisation du module: cours, TDs, mini-projet à réaliser.
• Évaluation: notes (concours/examens) 60%, mini-projet 40%.
• Thèmes principaux: Complexité algorithmique; applications (Trie et Recherche); récursivité et le paradigme ''diviser pour régner''; enregistrements et fichiers; rappels d’algorithmique I (Lecture/Écriture; structures conditionnelles; structures itératives).

Rappels fondamentaux sur l’algorithmique

• Définition d’un algorithme: une suite finie d’opérations élémentaires (instructions) qui, exécutée correctement, conduit à un résultat donné.
• Un algorithme prend des entrées et produit des sorties via une suite d’instructions.
• On peut obtenir le même résultat via une infinité d’algorithmes différents.
• Le concept de logique commune à tous les langages de programmation: la logique de programmation est un algorithme; c’est indépendant de l’architecture matérielle ou logicielle.
• Un programme est l’implémentation d’un algorithme dans un langage donné sur une architecture donnée.

Résolution d’un problème: démarche et étapes

• Résolution d’un problème: phase d’optimisation et de compréhension du problème, puis analyse et conception.
• Étapes typiques:
  • Compréhension du problème; analyse des données en entrée et du résultat attendu; traitement; décomposition du problème (top-down design); représentation et algorithme logique du sous-problème; programmation.
• Top-down design (Conception par décomposition):
  • Décomposer le problème en sous-problèmes hiérarchisés.
  • Spécifier chaque sous-problème et son interface (entrée/sortie).
  • Exemple: décomposer un problème en « Sous-problème 1 », « Sous-problème 2 », etc., puis préciser les traitements de chaque sous-problème.
• Représentation de l’algorithme: organigrammes et pseudo-code.

Étude de cas: trouver la surface et la circonférence d’un cercle

• Analyse (exemple simple):
  • Entrée: rayon r (réel); constante PI = 3.14; sortie: surface et circonférence.
  • Traitement:
  • Surface: $S = ext{PI} imes r^2$
  • Circonférence: $C = 2 imes ext{PI} imes r$
• Décomposition Top-Down:
  • Calculer la surface et la circonférence; saisir le rayon; décomposer en sous-problèmes: Surface(r) et Circonférence(r).
• Représentation structurée: variables, constantes; instruction d’entrée et affichage.

Structure d’un algorithme: éléments et exemple

• Structure générale: Lecture du rayon → Début → Calculer surface → Fin → Calculer circonférence → Afficher les résultats.
• Exemple d’algorithme cercle (avec structure et variables):
  • Déclarations: rayon: réel; PI = 3.14.
  • Début: écrire saisir rayon; lire r; surface = PIrr; circonférence = PI2r; écrire résultats.
• Remarque: usage de sous-procédures et sous-algorithmes pour modulariser les calculs (Surface(r), Circonférence(r)).

Variables, opérateurs et types

• Variables: entités mémoires pouvant changer de valeur. Déclaration: nom et type (entier, réel, booléen, chaîne de caractères, tableau, etc.).

• Déclaration: au début de l’algorithme, avant la première instruction.

• Règles de nommage: alphabétique; autorise chiffres et _; commence par une lettre.

• Types de données: Entier, Réel (nombres réels), Booléen (Vrai/Faux), Chaine de caractères.

• Affectation: assigner une valeur à une variable; remplace l’ancienne valeur.

• Opérateurs:

  • Arithmétiques: $+, ext{ }-, imes,\frac{}{} , ext{mod}$, puissance.

  • Comparaison: =,

  • Logique: ET, OU, NON.

• Tables de vérité (logic): exemples de résultats selon A et B.

Lecture et écriture; saisie et affichage

• Instruction d’écriture: Ecrire(…);
• Instruction de saisie: Lire(…);
• Exemple: afficher “la valeur est:”, x.
• Exécution d’un exemple: a = 5 donnera l’affichage correspondant à la valeur de a.

Exemples simples et exercices d’application

• Exercice type: calculer et afficher des valeurs à partir d’entrées (par exemple, division a/b avec vérification de zéro).
• Exemple donné: algorithme division - Lire A, lire B; écrire A/B; mais vérifier B ≠ 0 avant la division.
• Exemples d’écriture et de structure conditionnelle simples:
  • Condition: Si (B ≠ 0) alors écrire le résultat; Sinon écrire erreur.

Structures conditionnelles

• Définition: une condition est une expression booléenne; résultats vrai ou faux.
• Opérateurs de comparaison: =, ≠, >, <, ≥, ≤.
• Conditions composées: liées par ET, OU et NON.
• Structures conditionnelles à deux alternatives: Sinon; Syntaxe générale: Si Condition Alors Traitement1 Sinon Traitement2 FinSi.
• Exemples d’algorithmes divisions sécurisées (vérification du diviseur non nul).
• Structure conditionnelle avec une seule alternative: Si Condition Alors Traitement FinSi.
• Avantages: simplification et optimisation par réduction des branches inutiles; NB: chaque Si…Sinon doit être correctement fermé par FinSi.
• Conditions imbriquées: SI condition1 ALORS … SINON SI condition2 ALORS … FIN SI; Avantages et complexité accrues lorsque de nombreuses conditions s’appliquent.
• Structure SI-SINON-SI: syntaxe consolidée pour éviter les imbriqués excessifs!
• Structure sélective: Selon expression; équivalent d’un switch-case. Déclaration: Selon expression Faire valeur1: traitement1; valeur2: traitement2; … Sinon traitement par défaut; FinSelon.

Boucles et structures itératives

• Structures itératives:
  • TantQue (While): TantQue condition Faire bloc FinTantQue; test effectué avant chaque itération; peut ne pas entrer dans la boucle.
  • Pour (For): Pour i de valeurinitiale à valeurfinale Pas incrément faire ListeInstructions FinPour; utile lorsque le nombre d’itérations est connu.
  • Répéter…jusqu’à (do-while): Répéter ListeInstructions Jusqu’à Condition; le bloc s’exécute au moins une fois.
• Choix de boucle: si le nombre d’itérations est connu, préférer Pour; si inconnu, TantQue; si au moins une exécution est nécessaire, Répéter.
• Exemples: calculer la puissance via une boucle: r ← 1; Pour i ← 1 à p faire r ← r * n; FinPour; résultat = n^p.
• Exemples pratiques: factoriel, division avec répétition de saisies, etc.

Parcours et tableaux

• Tableaux à une dimension: une variable indicée pour stocker des valeurs du même type; indices commencent à 0; dimension fixe (taille déclarée).
• Déclaration: Tableau tab[dimension] : Type; accès via tab[indice].
• Remarques: on peut ne pas remplir complètement le tableau; la taille est fixe à la déclaration; les langages diffèrent sur l’indice de départ (0 ou 1 selon le langage).
• Saisie et affichage: saisie des éléments dans un tableau et affichage des éléments avec parcours par boucle (Pour i de 0 à dimension-1).
• Parcours complet vs partiel: parcourt complet des éléments; parcours partiel selon une condition; imbriqué lorsque nécessaire.
• Parcours imbriqué (tableaux multi-dimensionnels): Boucles imbriquées correspondent à chaque dimension.
• Exemple simple: somme des éléments d’un tableau; parcours pour lire puis parcours pour sommer.
• Parcours d’un tableau pour détecter des caractéristiques (par exemple, vérifier si tous les éléments sont positifs).
• Tableaux multidimensionnels: 2D et 3D; accès via T[i,j] ou T[i][j] selon l’implémentation; notion de lignes et colonnes; déclare des tableaux de dimensions 20x30 comme exemple, et explique la logique d’accès et de parcours par boucles imbriquées.
• Déclaration et usage d’un matrice A[N, M] dans lequel on peut lire les éléments et effectuer des recherches.

Tableaux dynamiques et multidimensionnels

• Tableaux dynamiques: dimensionnement à l’exécution; redimensionnement via des mécanismes comme Redim; permettent d’ajuster la taille du tableau selon les données réelles.
• Avantages: évite d’allouer des tableaux gigantesques et inutilisés; limite des coûts mémoire et améliore la performance lorsque la taille varie.
• Exemple: saisie d’un nombre variable de notes: demander le nombre de notes n, Redim t[n], puis lire les notes dans t[i].
• Tableaux multidimensionnels: extensions à plusieurs dimensions (par exemple, 3D); l’accès se fait par plusieurs indices; les exemples montrent des matrices et des ensembles de noms et notes, etc.

Sous-algorithmes: fonctions et procédures

• Objectif: gérer des blocs séparés d’un algorithme pour modulariser et réutiliser le code.
• Types de sous-programmes: fonctions (retournent une valeur) et procédures (ne retournent pas de valeur).
• Appel des sous-algorithmes: un sous-algorithme est caractérisé par son nom; il peut être appelé depuis l’algorithme appelant; les paramètres permettent de transmettre des données.
• Paramètres et arguments:
  • Paramètres formels: déclarés dans l’en-tête du sous-algorithme; décrivent le nombre et le type des valeurs attendues.
  • Paramètres effectifs: valeurs réelles passées lors de l’appel.
  • Trois types de paramètres: en entrée, en sortie, en entrée/sortie (E, S, E/S).
• Passage des paramètres: deux modes principaux:
  • Par valeur (passage par copie): l’algorithme appelé travaille sur une copie; les modifications ne se répercutent pas sur l’appelant.
  • Par référence (par adresse): l’algorithme appelé opère sur l’objet réel via son adresse; les modifications se répercutent sur l’argument effectif.
• Schéma de fonctionnement et terminologie:
  • Appel: l’algorithme appelant transmet des valeurs via des paramètres effectifs vers des paramètres formels.
  • Remise de valeur: les paramètres en sortie/E/S transmettent leurs résultats vers les paramètres effectifs.
• Types de sous-algorithmes:
  • Fonction: retourne une valeur unique; peut ou non avoir des paramètres; a une signature qui précise le type du résultat; appelle et reçoit une valeur retournée par la fonction.
  • Procédure: n’a pas de valeur retournée; peut avoir des paramètres avec passage par valeur ou par référence; peut être utilisée pour modifier des paramètres en sortie ou en entrée/sortie.
• Exemple pratique: calculer la circonférence via une procédure Circonférence(a: réel): retourne la valeur via un paramètre en sortie; Programme appelant: Circonférence(r) avec PI comme constante.
• Passage de paramètres et types de valeurs:
  • Paramètres en entrée: la valeur effectif est copiée dans le paramètre formel; modifications dans le corps n’affectent pas le paramètre effectif.
  • Paramètres en sortie: la valeur calculée est renvoyée au paramètre effectif à la fin de l’appel.
  • Paramètres en entrée/sortie: modifications dans le sous-programme affectent directement le paramètre effectif (référence).
• Exemples illustratifs: usage de Circonférence avec passage par valeur et/ou par référence; échange de valeurs via une procédure echanger(E/S; val1: entier, E/S; val2: entier).
• Variation des paramètres et signature: l’en-tête des sous-programmes indique les paramètres formels et leurs types; lors de l’appel, les paramètres effectifs et leur ordre doivent correspondre; on peut avoir des paramètres optionnels ou des modes (E, S, E/S).

Portée et durée de vie des variables

• Portée (scope):
  • Variable globale: déclarée dans le programme principal et accessible par tous les sous-programmes.
  • Variable locale: déclarée à l’intérieur d’un sous-programme et accessible uniquement à l’intérieur de ce sous-programme.
• Durée de vie:
  • Variable locale: créée lors de l’appel du sous-programme et détruite à la fin de son exécution.
  • Variable globale: connue et modifiable par l’ensemble des sous-programmes et du programme principal; persiste pendant toute l’application.
• Bonnes pratiques: privilégier les variables locales pour économiser la mémoire et garantir l’indépendance des procédures/fonctions; éviter les variables globales lorsque cela est possible.
• Cas particulier: si une variable locale porte le même nom qu’une variable globale, la locale masque la globale dans son contexte (conseil: éviter les masqués involontaires).

Réutilisation des modules et conception modulaire

• L’objectif de Top-down design et des sous-programmes est de rendre le code réutilisable et plus facile à maintenir.
• Exemples de réutilisation:
  • Calculer la surface totale d’un cylindre en combinant la surface latérale et les surfaces des extrémités (surface cylindre = surface latérale + 2 x surface d’un cercle).
  • La surface latérale du cylindre correspond à un rectangle dont la hauteur est h et la largeur est égale à la circonférence du cercle de rayon r.
  • La circonférence d’un cercle est la même que dans l’exemple simple: $C = 2 \pi r$, et la surface d’un cercle est $S = \pi r^2.$
• Avantages du découpage en sous-problèmes: approcher le problème progressivement, réutiliser la résolution de sous-problèmes pour de nouveaux problèmes.

Combinaisons et factorielle: applications illustratives

• Combinaisons: nombre de façons de choisir k éléments parmi n: $\binom{n}{k} = \frac{n!}{k!(n-k)!}.$
• Factorielle: $n! = 1 \times 2 \times \cdots \times n = \prod_{i=2}^{n} i.$
• Exemple d’utilisation: le calcul de la combinaison implique généralement la factorielle.
• Exemples pratiques présentés: structure du code pour factorielle et utilisation dans des appels de fonction (fonction factorielle avec paramètres formels et effectifs; appels multiples avec des arguments différents).

Problèmes et exercices typiques

• Diplôme dépendant de notes sur deux modules: le premier module a un coefficient double de celui du second; la moyenne d’un module accorde un coefficient double à la meilleure des deux notes; les conditions: moyenne globale ≥ 10 et aucune moyenne de module < 8.
• Décomposition du problème: comprendre les entrées (quatre notes), les sorties (diplôme oui/non), et le traitement (moyennes des modules, choix de la meilleure note dans chaque module, et pondération par les coefficients).

Décomposition du problème: inputs, outputs et traitement

• Input: Quatre notes (deux modules et leurs coefficients).
• Output: Décision (diplômé ou non).
• Traitement: calcul des moyennes par module; sélection de la meilleure note dans chaque module; calcul de la moyenne globale pondérée; vérification des conditions de diplôme.

Notation et formules importantes à retenir

• Surface et circonférence d’un cercle:
  • $S = ext{PI} imes r^2$
  • $C = 2 imes ext{PI} imes r$
• Puissance: $n^p$, généré par boucle.
• Puissance par boucle: résout le calcul de $r^p = \prod_{i=1}^{p} r$ (exemple dans les notes).
• Combinaisons et factorielle:
  • $\binom{n}{k} = \frac{n!}{k!(n-k)!}$
  • $n! = \prod_{i=2}^{n} i$
• Pour les structures et les types: pas de symboles mathématiques spécifiques, mais les notions de paramètre en entrée, en sortie et en entrée/sortie utilisent des notations comme E (entrée), S (sortie) et E/S (entrée/sortie).

Récapitulatif conceptuel

• Un algorithme est une suite d’instructions finie et logique qui transforme des entrées en sorties.
• Le design top-down consiste à décomposer un problème en sous-problèmes de plus en plus simples et réutilisables.
• Les structures de contrôle (conditionnelles et itératives) permettent d’imiter le raisonnement humain et de contrôler le flux d’exécution.
• Les tableaux et les structures de données permettent de manipuler des collections d’éléments et d’effectuer des calculs sur ces collections (moyennes, recherches, etc.).
• Les sous-programmes (fonctions et procédures) permettent de modulariser un programme; les paramètres et leur passage (par valeur ou par référence) déterminent comment les données circulent entre le programme principal et les sous-programmes.
• La portée (locale vs globale) et la durée de vie des variables influent sur la conception et la robustesse des programmes.
• La réutilisation et la modularité permettent de construire des programmes plus petits et plus fiables, et de réutiliser des modules dans des contextes différents (par exemple, surface d’un cercle, surface d’un cylindre, etc.).

Remarques de contexte et implications éthiques/pratiques

• L’importance de la lisibilité et de la clarté du code est soulignée par l’usage de structures claires (Si…Alors…Sinon; Selon; Boucles).
• L’utilisation judicieuse des variables locales plutôt que globales réduit l’usage mémoire et les effets secondaires, ce qui est une pratique éthique et professionnelle en développement logiciel.
• Les choix de conception (top-down, modularité, réutilisation) favorisent la maintenance, la traçabilité et la reproductibilité des résultats, essentiels en contexte réel.

Conseils pour l’examen

• Maîtriser les formules essentielles et leurs contexts d’application: surface et circonférence d’un cercle, puissance, factorielle, combinaisons.
• Savoir identifier et décomposer un problème en sous-problèmes en utilisant Top-down design.
• Savoir distinguer et décrire les trois types de paramètres (entrée, sortie, entrée/sortie) et les modes de passage (par valeur, par référence).
• Savoir comparer les structures de boucle et leurs cas d’utilisation: Pour quand le nombre d’itérations est connu; TantQue ou Répéter lorsque l’on ignore; Déterminer le choix optimal pour l’efficacité et la lisibilité.
• Comprendre la différence entre les fonctions et les procédures et leur rôle dans la modularité.
• Appréhender l’usage des tableaux (un et multidimensionnels) pour la saisie et l’analyse; savoir les parcours complets et partiels; comprendre les enjeux des tableaux dynamiques.
• Connaître les notions de portée et durée de vie des variables et leur impact sur la conception des programmes.
• Avoir des exemples concrets de décomposition top-down, de réutilisation et de passage de paramètres dans des contextes simples et complexes.