revision algos - progr

R2-ALGO-01 : Révision Algorithmes 1M#

Objectifs pédagogiques#

  • consolider les concepts algorithmiques nécessaires à la 2M

    • début et fin

    • liaison

    • instruction

    • condition

    • sous-programme

    • entrées

    • sorties

Caractéristiques des algorithmes#

Un algorithme est une succession d’instructions permettant d’aboutir à un résultat souhaité. Il possède les caractéristiques (proriétés) suivantes :

  1. il doit toujours se terminer après un nombre fini d’étapes (finitude)

  2. chaque étape d’un algorithme doit être définie précisément, les actions à mener doivent être spécifiées rigoureusement et sans ambigüité pour chaque cas

  3. un algorithme a des entrées, zéro ou plus, quantités qui lui sont données avant ou pendant son exécution

  4. un algorithme a une ou plusieurs sorties, quantités qui ont une relation spécifiée avec les entrées

  5. les instructions doivent être suffisament basiques pour pouvoir être en principe exécutées de manière exacte, en un temps fini par une personne utilisant un papier et un crayon.

Formalisme : algorigrammes#

Dans ce cours nous utilisons le formalisme des algorigrammes.

algorigrammes

Règles de construction#

  • Il faut centrer l’algorigramme au centre de la feuille ou du programme informatique pour le créer

  • Il faut que la lecture de l’algorigramme puisse se faire verticalement

  • Les lignes de liaisons entre les symboles ne doivent pas se couper.

  • Une ligne de liaison doit toujours arriver sur le haut et au centre d’un symbole.

  • Les commentaires sont à placer de préférence à droite et les renvois de branchement à gauche.

A cela on ajoute :

  • aucune liaison orpheline (qui part d’un symbole et qui arrive nulle part)

Exercice 1 : Un algorithme simple#

Sur une feuille de papier et avec un crayon, dessinez l’algorigramme correspondant à l’algorithme suivant :

  • demander un entier A

  • demander un entier B

  • calculer la somme C  = A + B en calculant:

    • tant que A != 0 faire :

      • A = A - 1

      • B = B + 1

Exercice 2#

Modifiez votre algorigramme pour qu’il calcule la différence C = A - B

(Vous pouvez vous restreindre aux nombre non négatifs)

Exercice 3 (Si vous avez du temps)#

Il existe un algorithme simple appelé méthode de la bissection qui permet de calculer une racine carrée simplement.

Méthode pour calculer \(\sqrt{x}\):

  1. Choisir un intervalle entre 1 et x

  2. affecter \(b_{inf} = 1\) et \(b_{sup} = x\)

  3. Approximer la racine \(\sqrt{x}\) :

    1. Calculer la moitié de l’intervalle : \(m = \frac{b_{inf} + b_{sup}}{2}\)

    2. Calculer \(m^2\)

    3. Si \(m^2 > x\) alors \(b_{sup} = m\) (\(m\) devient la borne supérieure)

    4. Sinon \(b_{inf} = m\) (\(m\) devient la borne inférieure)

    5. Recommencer

Dessinez l’algorigramme correspondant

Correction#

Exercice 1#

addition

Exercice 2#

soustraction

Exercice 3#

Voir le code Python