Algorithmique et Programmation A. Alikacem. Semaine 2 Semaine 2 Les outils algorithmiques Lecture:...

Algorithmique et Algorithmique et ProgrammationProgrammation

A. AlikacemA. Alikacem

Semaine 2 Semaine 2 Les outils algorithmiques

Lecture: chapitre 2 des notes de cours

Étapes de la construction d'un programme

Composantes de base d'un ordinateur

Structures de base d'un algorithme

Algorithme

Programme

Ordinateur

Description formelle

Transcription

CompilationLangage de programmation

Langage machine

ExécutionSolution

Problème

Étapes de la construction Étapes de la construction d’un programmed’un programme

Vous avez dit algorithme ?

Le pseudo-code (pseudo-langage) Dérivé du langage Pascal. Permet d’être précis, sans syntaxe lourde lisible sans effort Peut être traduit facilement dans un langage de programmation Il nous évite de rattacher la résolution d’un problème à un langage

de programmation particulier Il nous prépare à l’acquisition de bonnes habitudes

de programmation:

il conduit à la programmation structurée

il favorise la conception des algorithmes car il est

compatible avec la démarche descendante.

Expression des algorithmes

Pseudo-Code

#include <stdio.h>int main () {

int n, i;scanf ("%d", &n);for (i=0; i<=n; i++) {

if (i%2) {printf ("%d\n", i);

}}return 0;

}

Demander n

Répéter i [0,n] début

si (i % 2) 0 alorsdébut

Afficher ifin

fin

Plus abstrait, plus lisible, plus concis...

Faire la différence entre les contraintes propres à un langage et les difficultés

inhérentes à un problème donné

Met en avant l'essence de l'algorithme

Expression des algorithmesExpression des algorithmesLe pseudo-code (pseudo-langage)

Cette représentation a un intérêt pédagogique, elle facilite l’apprentissage.

Introduit les caractéristiques de la machine théorique :

Un algorithme va être représenté comme une suite d’actions pouvant être exécutées par une une machine idéalemachine idéale.

Notion d’action

Les actions élémentaires (primitives)Les actions élémentaires (primitives)

Définition Une instruction qui peut être comprise

directement par le système que l'on désire programmer.

Exemple : une tortue radio-commandée Les primitives

Les actions élémentaires (primitives)Les actions élémentaires (primitives)

Les actions élémentaires (primitives)Les actions élémentaires (primitives)

Les actions élémentaires (primitives)Les actions élémentaires (primitives)

Les actions élémentaires (primitives)Les actions élémentaires (primitives)

??

Les actions élémentaires (primitives)Les actions élémentaires (primitives)

Les actions élémentaires (primitives)Les actions élémentaires (primitives)

Quelle suite d’instruction doit-on utiliser pour obtenir l’ordre :

« avanceravancer d’une case » ?

Les actions élémentaires (primitives)Les actions élémentaires (primitives)

Quelle suite d’instruction doit-on utiliser pour obtenir l’ordre :

« reculerreculer d’une case » ?

+ + =

Les actions élémentaires (primitives)Les actions élémentaires (primitives)

Quelle suite d’instruction doit-on utiliser pour obtenir l’ordre :

« avanceravancer d’une case en diagonale » ?

Les actions élémentaires (primitives)Les actions élémentaires (primitives)

Quelle suite d’instruction doit-on utiliser pour obtenir l’ordre :

« avanceravancer d’une case en diagonale » ?

+

Les actions élémentaires (primitives)Les actions élémentaires (primitives)

Quelle suite d’instruction doit-on utiliser pour obtenir l’ordre :

« avanceravancer d’une case en diagonale » ?

+ +

Les actions élémentaires (primitives)Les actions élémentaires (primitives)

Quelle suite d’instruction doit-on utiliser pour obtenir l’ordre :

« avanceravancer d’une case en diagonale » ?

+ + +

Les actions élémentaires (primitives)Les actions élémentaires (primitives)

Quelle suite d’instruction doit-on utiliser pour obtenir l’ordre :

« avanceravancer d’une case en diagonale » ?

+ + + =

Les actions élémentaires (primitives)Les actions élémentaires (primitives)

Architecture de Von Architecture de Von NeumanNeuman

Un ordinateur devrait être composé de:

- unité de commande et contrôle (ucc)- unité arithmétique et logique (ual)- mémoire principale (mp)- périphériques d’entrée/sortie (pe/ps)

ucc mpual

pe

ps

Les composantes d’un ordinateurLes composantes d’un ordinateur

Les périphériques d’entrée De l’usager à l’ordinateur Stockées dans la mémoire principale de l’ordinateur afin

d’être manipulées.

Dans un algorithme

DEMANDER DEMANDER informationinformation

action élémentaire

Les périphériques de sortie De l’ordinateur à l’utilisateur On les utilisera donc pour montrer les

résultats du travail d’un programme.Dans un algorithme

AFFICHER AFFICHER informationinformation

IMPRIMER IMPRIMER informationinformation

Les composantes d’un ordinateurLes composantes d’un ordinateur

actions élémentaires

La mémoire principale

Conserver les données entrées par l’usager et de stocker les résultats intermédiaires et finaux.

Pour traiter de l’information par un ordinateur, il faut que cette dernière se retrouve en mémoire principale.

Les composantes d’un ordinateurLes composantes d’un ordinateur

La mémoire principaleLa mémoire principale

Plusieurs cellules (cases, mots)

…0x010

901000000

0x010a

01100111

0x010b

00111111…

Chaque cellule a sa propre adresse contient toujours

une suite de bits

Plusieurs cellules (cases, mots)…

a 01000000

lettre 01100111

temp 00111111…

Nous pouvons leurassocier un nom

La mémoire principaleLa mémoire principale

Notion d’identificateurNotion d’identificateur

…

a ‘@’lettre ‘e’temp ‘?’

…

Nous pouvons interpréter la signification du contenu différemment (associer un type)

La mémoire principaleLa mémoire principalePlusieurs cellules (cases, mots)

Notion de typeNotion de type

a ‘@’lettre ‘e’temp 4

nom + type = variable une abstraction d’un

emplacement mémoire.

La mémoire principaleLa mémoire principalePlusieurs cellules (cases, mots)

Notion de variableNotion de variableComment l’utiliser ?

temp temp 4temp temp temp + 1 temp + 1

Le symbole “  ” est appelé opérateur d’affectation ou d’assignation.

Un exempleUn exemple

DEBUTDEMANDER xy xx 0AFFICHER xAFFICHER y

FIN

xy

??????

???

UnUn exempleexemple

DEBUTDEMANDER xy xx 0AFFICHER xAFFICHER y

FIN

xy

5

???

5Un exempleUn exemple

DEBUTDEMANDER xy xx 0AFFICHER xAFFICHER y

FIN

xy??

?5

5Un exempleUn exemple

DEBUTDEMANDER xy xx 0AFFICHER xAFFICHER y

FIN

5 xy

0

5

0Un exempleUn exemple

DEBUTDEMANDER xy xx 0AFFICHER xAFFICHER y

FIN

xy

Un exempleUn exemple

DEBUTDEMANDER xy xx 0AFFICHER xAFFICHER y

FIN

5

0 xy

Un Un exempleexemple

DEBUTDEMANDER xy xx 0AFFICHER xAFFICHER y

FIN

5

0 xy

Les Les composantescomposantes d d’un ordinateur’un ordinateur

L’unité arithmétique et logique (UAL) Composante d’un ordinateur en charge de toutes

les opérations de calcul, de comparaison et de logique.

Primitives pour le calcul arithmétique

L’L’uunité nité aarithmétique et rithmétique et llogiqueogique

OpérateurOpérateur ExempleExemple x=9 & y=4x=9 & y=4+ x + y 13- x – y 5* x * y 36/ x / y 2,25 x y 2% x % y 1

Opérateurs arithmétiques

OpérateurOpérateur ExempleExemple x=9 & y=4x=9 & y=4= x = y FAUX x y VRAI> x > y VRAI x y VRAI< x < y FAUX x y FAUX

Opérateurs relationnels

L’L’uunité nité aarithmétique et rithmétique et llogiqueogique

ConditionsConditions NONNON conditions conditionsVRAI FAUXFAUX VRAI

Il fait soleil Il ne fait pas soleil

Opérateurs logiquesNONNON

L’L’uunité nité aarithmétique et rithmétique et llogiqueogique

Opérateurs logiquesETET

x y x ET y

FAUX FAUX FAUX

FAUX VRAI FAUX

VRAI FAUX FAUX

VRAI VRAI VRAI

L’L’uunité nité aarithmétique et rithmétique et llogiqueogique

Opérateurs logiquesOUOU

x y x OU y

FAUX FAUX FAUX

FAUX VRAI VRAI

VRAI FAUX VRAI

VRAI VRAI VRAI

L’L’uunité nité aarithmétique et rithmétique et llogiqueogique

NON , + , - (monadiques) + élevée* , / , , % .+,- (dyadiques) .> , , < , .= , .ET .OU + faible

Évaluation des expressionsLes parenthèses et :Les parenthèses et :

L’L’uunité nité aarithmétique et rithmétique et llogiqueogique

Un exemple d’évaluation d’expression:

x * x 0 ET ( x + 1 ) * ( x + 1 ) < 162 2 2 2

3 3

94

V V

V

L’L’uunité nité aarithmétique et rithmétique et llogiqueogique

L’unité de commande et de contrôle (UCC) En charge de contrôler le déroulement d’un programme. Elle dirige le

fonctionnement de toutes les autres unités (UAL, mémoire, entrée/sortie) Normalement, un programme s’exécute instruction par instruction, dans

l’ordre (de haut en bas) ou elles sont écrites. Cependant, et très souvent, on aura besoin de briser la séquentialité:

en utilisant des structures de contrôle d’alternatives; en utilisant des structures de contrôle de répétitions; en faisant des appels de sous-programmes, caractérisés par une référence (appel) à un bloc à l’intérieur d’un autre bloc

Les Les composantescomposantes d d’un ordinateur’un ordinateur

Primitives de structures de contrôle

SI condition est vrai alors

DÉBUT

Instructions

FIN

Condition

Instructions

VRAI

FAUX

UUnité de nité de ccommande et ommande et ccontrôleontrôle

Structures alternatives

SI x < 100 alors

DÉBUT

x x + 1

y 25

FIN

X < 100

x x + 1

y 25

VRAI

FAUX

UUnité de nité de ccommande et ommande et ccontrôleontrôle

Structures alternatives

SI condition est vrai alors

DÉBUT

Instructions v

FIN

SINON

DÉBUT

Instructions f

FIN

Condition

Instructions v

VRAI

FAUX

Instructions f

UUnité de nité de ccommande et ommande et ccontrôleontrôle

Structures alternatives

SI x = 0 alors

DÉBUT

x 100

FIN

SINON

DÉBUT

x x - 1

FIN

x = 0

X 100

VRAI

FAUX

x x - 1

UUnité de nité de ccommande et ommande et ccontrôleontrôle

Structures alternatives

RÉPÉTER n FOIS

DÉBUT

Instructions

FIN

n fois?

Instructions

FAUX

VRAI

UUnité de nité de ccommande et ommande et ccontrôleontrôle

Compteur implicite

Structures itératives

Exemple Exemple Le factoriel nLe factoriel n 0.

DébutSi n = 1 ou n = 0 alors

Débutfact 1Fin

SinonDébutfact 1

Répéter n-1 foisDébutfact fact * i

FinFin

Fin

i 2

i i + 1

RÉPÉTER i [1,n] DÉBUT

Instructions

FIN

n fois?

Instructions

FAUX

VRAI

UUnité de nité de ccommande et ommande et ccontrôleontrôle

Compteur explicite

Structures itératives

Exemple Exemple Le factoriel nLe factoriel n 0.

DébutSi n = 1 ou n = 0 alors

Débutfact 1Fin

SinonDébutfact 1

Répéter i [2, n]Débutfact fact * iFin

FinFin

Condition

FAUX

VRAI

InstructionsRÉPÉTER

DÉBUT

Instructions

FIN

TANT QUE condition

UUnité de nité de ccommande et ommande et ccontrôleontrôle

Structures itératives

Début Si n = 1 ou n = 0 alors

Début fact 1 

Fin Sinon

Début fact 1 i 1Répéter

Début fact fact * i

i i + 1Fin

Tant Que i < n+1Fin

Fin

Exemple Exemple Le factoriel nLe factoriel n

TANT QUE condition

DÉBUT

Instructions

FIN

condition

Instructions

VRAI

FAUX

UUnité de nité de ccommande et ommande et ccontrôleontrôle

Structures itératives

Début Si n = 1 ou n = 0 alors

Début fact 1 

Fin Sinon

Début fact 1 i 2Tant Que i < n+1

Début fact fact * i

i i + 1Fin

Fin Fin

Exemple Exemple Le factoriel nLe factoriel n

Propriétés :

Un nombre fini d’étapesUn nombre fini d’opérations par étapeUne suite d’opérations primitivesFournit un résultat (décidabilité)Chaque opération est

non ambiguë Effective

calculabilité

L’algorithmique impérative

Propriétés :Un algorithme doit être indépendant du langage de

programmation utilisé.Un programme est un algorithme exprimé dans un langage de

programmation capable d’être exécuté par un ordinateur.

Peut être exprimé de manière formelle :

- en pseudo-code

- par un algorigramme- dans un arbre algorithmique

- dans un diagrammes structurés

L’algorithmique impérative

Algorithme

Programme

Ordinateur

Description formelle (?)

Transcription (?)

Compilation

Langage de programmation

Langage machine (?)

Exécution (?)Solution

Problème

Algorithme, programme et ordinateur

Lab#2

Algorithme: un traitement de texte! début Demander CP {A: CP est un caractère}Afficher CP TANT QUE CP ‘!’

début Demander CL

{A: CL est un caractère}SI CL = CP ALORS

début Afficher le caractère de soulignement '_ '

fin Afficher CL CP CL

fin fin

Qu’affiche cet algorithme si les données lues sont:" Etes vous efficace? ... Bonne chance!! "(Les guillemets ne font pas partie des données)

Rosalie dans le labyrinthe

Entrée

Sortie

Faire un pas devant elle (se rendre au centre du carré situé immédiatement devant elle). Tourner d'un quart de tour à gauche ou à droite. Détecter un mur placé devant lui (c'est à dire répondre à la question "y a-t-il un mur en face?"; la réponse est oui ou non. Détecter l'entrée du labyrinthe (en l'absence de ce test, Rosalie pourrait sortir par là où elle est entrée!). Détecter la sortie du labyrinthe (en l'absence de ce test, Rosalie ne s'arrêterait pas et continuerait à longer le mur à l'extérieur!).

Les primitives

Algorithme: Sortir du labyrinthe en longeant le mur de gauche DébutAvancer d'un pasFaire un quart de tour à gaucheTant que Rosalie n'est pas sortie

DébutFaire un quart de tour à gaucheTant que mur en face Début

Faire un quart de tour à droiteFinAvancer d'un pas

FinFin.

Il a été démontré que tout cube est égal à la somme de nombres impairs consécutifs.

Par exemple : 1 = 1 8 = 3 + 5 27 = 7 + 9 + 11 64= 13 + 15 + 17 + 19

Décrivez un algorithme qui lit un entier n strictement positif et donne une décomposition de n3.

Détermination des nombres de début et de fin de la sérieDébut

n3 n*n*ns 0p 1k 1

Tant que (s n3)début

si (s>n3) alors début

s s - (2*k-1)k k + 1

finsi ( s<n3) alors

débuts s + (2*p -1)p p + 1

finfinx 2*k -1y 2* (p-1) -1

fin

Affichage du développement du cube de ndébut

n3 n*n*nAfficher n3 " = "k premier

Tant que (k < dernier)début

Afficher k " + " k k+2

fin

Afficher dernierfin