2.Les bases de l’algorithmique2.Les bases de l’algorithmique

P. Costamagna – ISEN N1

P. Costamagna 2

A. Décomposition en sous-problèmesA. Décomposition en sous-problèmes

Exemple :

P. Costamagna 3

B. Langage intermédiaireB. Langage intermédiaire

Son rôle

Notion de blocExemple :

Séquence

P. Costamagna 4

B. Langage intermédiaire B. Langage intermédiaire (suite1)(suite1)

Alternative

La condition énoncée doit être décidable sans ambiguïté par l’exécutant

si une condition est remplie, alors telle action sera exécutée (sinon telle autre action sera exécutée).

Exemple :

P. Costamagna 5

B. Langage intermédiaire B. Langage intermédiaire (suite2)(suite2)

Répétition ou itération

Pour chaque poche faire la recherche de la clé.

Tant que la clé n’a pas été trouvée fouiller une autre poche.

Répéter la fouille de chaque poche l’une après l’autre jusqu’à ce que la clé soit trouvée.

Exemple :

P. Costamagna 6

C. Exemple : C. Exemple :

Environnement

Fournir au robot la marche à suivre qui va lui permettre de peler la quantité de pommes de terre suffisante pour remplir la marmite.

Le robot peleur de pommes de terre Le robot peleur de pommes de terre

But

Les instructions d’action élémentaire - REMPLIS = le robot remplit le panier

- PELE = il prend une pomme de terre dans le panier,

la pèle et la place dans la marmite.

P. Costamagna 7

C. Exemple C. Exemple (suite1)(suite1)

Les conditions que l’exécutant peut tester - La marmite est remplie ? oui / non

- Le panier est vide ? oui / non

Possibilité de former des conditions plus complexes :

        - en énonçant le contraire des conditions précédentes

        - en les liant par les mots ET et OU

Précisions - Aucune supposition quant à l’état initial du panier

- Aucune indication sur la taille du panier

- Idem pour la marmite

P. Costamagna 8

C. Exemple C. Exemple (suite2)(suite2)

Première propositionSI le panier est vide ALORS

Remplis

TANT QUE la marmite n’est pas remplie

Pèle

1ère situation :

P. Costamagna 9

C. Exemple C. Exemple (suite3)(suite3)

SI le panier est vide ALORS

Remplis

TANT QUE la marmite n’est pas remplie

Pèle

2ème situation :

Tester un programme peut éventuellement montrer qu’il ne fonctionne pas mais jamais

prouver qu’il est correct.

P. Costamagna 10

C. Exemple C. Exemple (suite4)(suite4)

SI le panier est vide ALORS

Remplis

TANT QUE la marmite n’est pas remplie

Pèle

3ème situation :

Le problème crucial sera de s’assurer que la marche à suivre donnée conduit à des exécutions

satisfaisantes dans tous les cas imaginables !

P. Costamagna 11

C. Exemple C. Exemple (suite5)(suite5)

Deuxième propositionTANT QUE la marmite n’est pas remplie

TANT QUE le panier n’est pas vide

SI la marmite n’est pas remplie ALORS

Pèle

Remplis

1ère situation :

L’exécutant travaille sans jamais s’arrêter !

P. Costamagna 12

C. Exemple C. Exemple (suite6)(suite6)

Troisième propositionREPETER

Fais tout ce qu’il faut pour mettre une pomme de terre en plus dans la marmite

TANT QUE la marmite n’est pas remplie

Le problème n’est alors plus d’expliquer

  comment faire pour remplir la marmite ?

mais

comment faire pour ajouter une pomme de terre supplémentaire dans la marmite ?

P. Costamagna 13

C. Exemple C. Exemple (suite7)(suite7)

TANT QUE la marmite n’est pas remplie

Fais tout ce qu’il faut pour mettre une pomme

de terre en plus dans la marmite

Tout fonctionne correctement

sauf si aucune pomme de terre ne doit être pelée

parce que la marmite fournie est déjà remplie.

La question de savoir si la marmite est remplie ou non

est posée trop tard.

Le problème du remplissage de la marmite a disparu.

P. Costamagna 14

C. Exemple C. Exemple (suite8)(suite8)

TANT QUE la marmite n’est pas remplie

SI le panier est vide ALORS

Remplis

Pèle

Reste à expliquer comment ajouter une pomme de terre

supplémentaire

Le seul paramètre gênant à ce propos concerne l’état

du panier.

Proposition finale

P. Costamagna 15

D. FonctionD. Fonction Savoir décomposer un problème en actions, sous-actions … est important pour programmer. Mais il faut pouvoir réutiliser des choses faites auparavant.

Exemple :

Il faut que la forme s’y prête Brique de base = Fonction ou sous-programme

sin (x)

P. Costamagna 16

E. Programme principalE. Programme principal

Une fonction fonctionne exactement comme un programme informatique tout entier

Le programme principal = fonction principale doit toujours porter le même nom.

En C, cette fonction principale porte tout simplement le nom de main.

P. Costamagna 17

F. Qualité d’écriture du codeF. Qualité d’écriture du code

Bug

Conventions:-  écrire le code le plus simplement

possible ;- commenter le plus possible le code;- utiliser des indentations comme dans les

exemples précédents pour visualiser rapidement les blocs d’instructions.