Algorithmes et résolution de problèmes

Objectif : Appliquer une démarche rigoureuse pour résoudre un problème avec un programme.

Algorithmes et résolution de problèmes

Résoudre un problème en informatique

right

  • But : faire déterminer automatiquement la solution par l’ordinateur.
  • Déterminer d’abord la méthode de résolution sous forme d’algorithme.
  • Transmettre ensuite cette méthode à l’ordinateur sous forme de programme.
  • Pour y arriver, il faut suivre une démarche rigoureuse.
Algorithmes et résolution de problèmes

Exemple : calculer une moyenne

  • Entrées : deux nombres saisis au clavier, par exemple 10 et 20.
  • Algorithme : calculer la moyenne des deux nombres.
  • Sortie : afficher le résultat, ici 15.

Algorithmes et résolution de problèmes

Exemple : trouver le plus petit nombre

  • Entrées : trois nombres saisis au clavier, par exemple 10, 20 et 5.
  • Algorithme : comparer les trois nombres.
  • Sortie : afficher le plus petit nombre, ici 5.
  • Le programme fonctionne avec n’importe quelles valeurs fournies en entrée.
Algorithmes et résolution de problèmes

Démarche de résolution de problème

Étape Travail Livrable
1 — Analyse Comprendre l’énoncé Spécifications
2 — Conception Trouver une démarche Algorithme
3 — Implémentation Coder Code source
4 — Tests Valider Programme fonctionnel
Algorithmes et résolution de problèmes

Étape 1 : analyse

  • Partir d’un énoncé de problème.
  • Comprendre l’énoncé et recueillir les données.
  • Identifier ce qui est fourni : les entrées.
  • Identifier ce qui doit être calculé : les sorties.
  • Décrire le lien entre les entrées et les sorties.
  • Livrable : les spécifications.
Algorithmes et résolution de problèmes

Étape 2 : conception

  • Partir des spécifications produites durant l’analyse.
  • Proposer une démarche de résolution : l’algorithme.
  • Décrire l’environnement :
    • variables d’entrée et de sortie;
    • constantes et autres variables;
    • nom, type et valeur de chaque donnée.
  • Décrire les actions : opérations élémentaires, du début à la fin.
  • Livrable : l’algorithme.
Algorithmes et résolution de problèmes

Conception : environnement de l’algorithme

  • Représente le contenu de la mémoire vive.
  • Décrit les variables et les constantes du problème.
Rôle Nom Type Valeur éventuelle
Entrées
Sorties
Constantes
Autres
Algorithmes et résolution de problèmes

Conception : actions de l’algorithme

  • Représentent les traitements effectués par le processeur.
  • Peuvent modifier l’environnement.
  • S’enchaînent dans un ordre chronologique.
  • Peuvent être représentées en :
    • langage naturel — risque d’ambiguïté;
    • pseudocode — représentation privilégiée;
    • ordinogramme — représentation visuelle.
Algorithmes et résolution de problèmes

Étape 3 : implémentation

  • Partir de l’algorithme produit durant la conception.
  • Choisir un langage de programmation, par exemple Java.
  • Traduire l’algorithme en code source, ligne par ligne.
  • C’est l’étape de la programmation.
  • Livrable : un fichier de code source.
Algorithmes et résolution de problèmes

Étape 4 : tests

  • Exécuter le programme avec plusieurs données en entrée.
  • Choisir des jeux de tests variés.
  • Comparer les résultats observés aux résultats attendus.
  • En cas d’anomalie, trouver sa source dans le code et la réparer.
  • Livrable : un programme fonctionnel.
Algorithmes et résolution de problèmes

Exemple de problème

Énoncé : écrire un programme qui calcule l’aire d’un cercle à partir de son rayon.

  • Entrée : le rayon saisi au clavier.
  • Algorithme : calculer l’aire du cercle.
  • Sortie : l’aire affichée à l’écran.
  • Nom du programme : AireCercle.
Algorithmes et résolution de problèmes

Exemple — 1. Analyse

À partir de l’énoncé « Calculer l’aire d’un cercle à partir de son rayon » :

  • Entrée : le rayon du cercle.
  • Sortie : l’aire du cercle.
  • Lien : le résultat est l’aire du cercle dont le rayon est fourni.
  • Formule connue : aire = PI × rayon².
  • Livrable : les spécifications.
Algorithmes et résolution de problèmes

Exemple — 2. Environnement

Rôle Nom Type ou valeur
Entrée rayon Nombre réel
Sortie aire Nombre réel
Constante PI 3.14, nombre réel
Autres
Algorithmes et résolution de problèmes

Exemple — 2. Actions en langage naturel

Calcul de l’aire d’un cercle :

  1. Saisir la valeur du rayon du cercle.
  2. Calculer le produit de PI (3.14) par le rayon au carré.
  3. Afficher le résultat obtenu.

Cette représentation est déconseillée, car le langage naturel peut être ambigu.

Algorithmes et résolution de problèmes

Exemple — 2. Actions en pseudocode

AireCercle :
  début
    lire(rayon)
    PI ← 3.14
    aire ← PI × rayon × rayon
    afficher(aire)
  fin

Cette représentation est la plus appropriée et la plus utilisée.

Algorithmes et résolution de problèmes

Exemple — 2. Actions en ordinogramme

right

  • Calculer l’aire d’un cercle.
  • Les symboles rendent l’enchaînement des actions visible.
  • Cette représentation est appropriée pour les personnes débutantes.
Algorithmes et résolution de problèmes

Exemple — 3. Implémentation en Java

import javax.swing.*;

public class AireCercle {
  public static void main(String args[]) {
    double rayon, aire;
    final double PI = 3.14;

    rayon = Double.parseDouble(
      JOptionPane.showInputDialog("Entrer le rayon"));
    aire = PI * rayon * rayon;
    JOptionPane.showMessageDialog(
      null, "L'aire du cercle est: " + aire);
  }
}
Algorithmes et résolution de problèmes

Exemple — 4. Tests

1er test 2e test 3e test
Rayon entré 0 10 100
Aire observée 0 314 31 400
Aire attendue 0 314… 31 400…
  • Exécuter le programme avec les trois valeurs.
  • Comparer chaque résultat observé au résultat attendu.
  • Une divergence indique une anomalie à réparer.
Algorithmes et résolution de problèmes

Résumé

  • L’algorithme décrit une démarche de résolution.
  • Son environnement représente les données en mémoire vive.
  • Ses actions représentent les opérations du processeur.
  • L’algorithme est traduit en code source pour produire un programme.
  • Le programme est validé avec un jeu de tests.
Algorithmes et résolution de problèmes

Références

Algorithmes et résolution de problèmes