Algorithme et Programmation

Chapitre 1:
L’Algorithme

Dr. Hanen GRICHI

1
[Link]@[Link]
2022/2023
 Algorithme

 Vous avez déjà ouvert un livre de recettes de cuisine?

 Avez-vous déjà déchiffré un mode d’emploi traduit du
coréen pour faire fonctionner une machine ?
 Si oui?
 Sans le savoir vous avez déjà exécuté des
algorithmes.

 Encore plus fort :

 Avez-vous indiqué un chemin à un touriste égaré?
 Avez-vous fait chercher un objet à quelqu’un par
téléphone?
 Si oui?
 Vous avez déjà fabriqué - et fait exécuter- des
algorithmes

2
 Algorithme

 Définition : Un algorithme est une suite d’instructions

(enchaînement des actions) qui une fois exécutée correctement,
conduit à un résultat donnée (résoudre un problème).

 Un peu de vocabulaire…
o Différentes appellations
o langage algorithmique
o pseudo-langage de programmation
o pseudo-code

o Exemples d’algorithme dans la vie courante

o pour tricoter un pull : (maille à l’endroit, …)
o pour faire la cuisine : recette
o pour jouer une sonate : partition

3
 Structures de
données

 Définition : une structure de donnée est un moyen

de

coder et de structurer les données manipulées.

 Tableaux, listes chaînées

 Piles, files
 Sets et Maps
 Graphes, arbres, arbres binaires de recherche

4
 Structures de
données

 Définition : une structure de donnée est un moyen

de

coder et de structurer les données manipulées.

Données

Structures
Algorithme de
données

Résultats

Programme = Algorithme + Structures de

données
5
 Résolution de problèmes

 Lire l’énoncé du problème, être certain de bien le

comprendre
 utiliser une loupe
 ressortir les informations pertinentes
 données ? résultats ?

 Réfléchir à la résolution du problème en ignorant

l’existence de l’ordinateur
 déterminer les points principaux à traiter
 exploiter l’ensemble de vos connaissances
 adapter ou réutiliser des recettes existantes
 encore difficile ?

 Décomposer le problème!! Analyse descendante!!

6
6
 Résolution de problèmes

 Écrire formellement la solution (algorithme) sur papier

 utiliser un pseudo langage

 Vérifier votre solution sur un exemple

 preuve formelle de l ’algorithme : encore mieux !!

 Traduire dans un langage de programmation

 Tester le programme sur différents jeux de tests

 le jeux de tests doit être « suffisant »
 ne pas oublier les cas particuliers, …

7
 Résolution de problèmes

Exemple 3 ( Ex  Ds ) 1
Note  Sup ( , Ex)  Tp
4 2 4

Données Ex, Ds, Tp

- Lire les données

Algorithme - Calculer la moyenne
- Afficher le résultat

Résultats Note
8
 Algorithmes et programmes

 Programme :

 Codage d’un algorithme afin que l’ordinateur puisse

exécuter les actions décrites

 doit être écrit dans un langage compréhensible par

l’ordinateur

Langage de programmation (Assembleur , Basic, C,

Fortran, Pascal, Cobol …)

• Un programme est donc une suite ordonnée

d’instructions élémentaires codifiées dans un langage

9 de programmation
 Langages de programmation

 L’ordinateur

 Traite des signaux assimilables à 0 ou 1

 Une opération élémentaire

 suite de 0 et de 1 = suite de bits.

Pour que les programmes et les données soient

compréhensibles par l’ordinateur il faut effectuer un

10 codage binaire
 Langages de programmation

 Langage machine

 langage binaire
 ses opérations sont directement
compréhensibles par l’ordinateur

Pour pouvoir manipuler du langage machine, on est

obligé de passer par de l'Assembleur.

11
 Exemple d’un programme

PROGRAMME monProgr

/* Constantes: initialisation obligatoire */

CONST const1 <- 10 : entier
const2 <- "bonjour!" : chaîne
déclarations
// les variables au sens strict
VAR varReel1, varReel2 : réels
varChaine : chaîne

DEBUT
Instruction1
Instruction2 Corps du programme
…
FIN

12
 Rappel

 Algorithme & programme : quelques briques fondamentales

 l’affectation de variables
 la lecture/écriture
 les tests
 les boucles
 - un algorithme(programme ) se ramène toujours à une
combinaison de ces quatre petites briques.
- ces briques opèrent sur des données (variables,
constantes) de différents types.

13
 Les Données

 Un programme manipule deux types de données :

 Variable : une variable est un objet bien identifié dont

les valeurs peuvent être altérées au cours de l’exécution
du programme.

 Constante : une constante est un objet bien identifié

dont la valeur est fixée une fois pour toute, et ne peut
être modifiée au cour de l’exécution du programme.

14
 Les Données

 Déclaration :

const NOM_CONST = valeur;

var nomVar : type; type de la variable (entier, réel, caractère)

nom de la variable (identificateur)

 Exemples :
const PI = 3.14;
var rayon, surface: réel;

15
 Les Types

 Type de données standard

Type de Exemple de type Exemple

données
Simple Entier 2 10 147
Réel 2547
Booléen 74.5 0.14
Caractère Vrai Faux
‘a’ ‘+’ ‘.’
Chaine Chaine de caractères « bonjour »
« cac40 »
Structuré Tableau Tableau T[10]:
Enregistrement entier
Structure Etud {
Id :
Entier,
16
 Les Types

 Les Tableaux

 3 éléments fondamentaux définissent un tableau à un

indice :
o Son nom : identificateur respectant les règles
classiques des identificateurs d’un programme
o Le nombre de ses éléments
o Le type de données qu’il contient

Tableau NOMTABLEAU [nbvaleurmax] :

type
i : entier (indice)
Tableau Note[11] :Entier

17
 Les Types

 Les enregistrements

structure
 Les tableaux sont des paquets de Nom_de_structure
données de même type. { La liste des données
contenues dans la
 Les structures sont des structure
}
ensembles de données non
Structure etd {
homogènes. char nom[20];

 Les données peuvent avoir des char prenom[20];

float note_info;
types différents.
float note_phi;
 Les structures sont déclarées ou float moyenne;

définies selon le modèle : } Jean;

18
 Les Opérations

 Type Entier

Opérations Signification Exemple

+, -, *, / … 9/5 =1.8
div Division entière 9 div 5 = 1
mod Reste de la division 9 mod 5 = 4
<, ≤, >, ≥, =, ≠ Comparaisons

 Type Réel

Opérations Signification Exemple

+, -, *, / … 9*5 =45
<, ≤, >, ≥, =, ≠ Comparaisons

19
 Les Opérations

 Type caractère : char

o chiffres :‘ 0 ’.. ‘ 9 ’,
o lettres :‘ A’.. ‘ Z ’, ‘ a ’.. ’z ’,
o caractères spéciaux : ‘ + ’,- ’, … ’? ’, ‘ * ’, ‘ ’, ‘_’,…
o les caractères sont ordonnées selon un code, unique
pour chaque caractère : le plus courant est le code ASCII.
 Les opérations possibles sur les caractères sont:
 les comparaisons : =, <>, <=, <, >=, >
 succ, et pred.
 Quelques soit le code utilisé, on a toujours :
 ‘A’<‘B’<…<‘Z’
 ‘a’<‘b’<…<‘ z’
 ‘0’<‘1’<…<‘9’

20
 Entrées/Sorties

 Lecture :
 Lire (suite de variables) permet de saisir des données au clavier.
 Permet à un utilisateur de communiquer des données au programme
 Assigne une valeur entrée au clavier dans une variable

 Exemple :

Lire (v1, v2, ..., vn); équivaut à Lire(v1); Lire(v2);...

Lire(vn);

21
 Entrées/Sorties

 Ecriture:
 Ecrire(« suite de variables ») permet de fournir des résultats à
l'utilisateur à travers l'écran
 Permet de fournir un résultat
 Permet de guider l’utilisateur
 Permet d’afficher des valeurs intermédiaires

 Exemple :

Ecrire « le résultat de x + y est : », x + y

On peut afficher plusieurs trucs grâce à la virgule !

22
 Affectation

 En pseudo : variable  expression

 Exemple : moyTp  (projetTp+controleTp)/2;

 Remarque :
o le type de la variable et de la valeur de l’expression
doivent être identique (dépend du langage).

23
 Tests

 En pseudo : si condition
alors instruction_1
sinon instruction_2;
fin si

 condition est une expression booléenne

24
 Boucles

 L’itération (ou boucle) est une structure qui permet de

faire répéter un ensemble d’actions, un certain
nombre de fois dans un ordre préalablement défini.
 Il existe trois types de structures itératives :
Tant que condition faire
[Link] structure « TANT QUE… FAIRE » séquence d’instructions
Le nombre de répétitions n’est pas connu et peut Ftq
être nul : 0 à n répétitions
[Link] structure « REPETER… JUSQU’À » Repeter instruction jusqu’à
Le nombre de répétitions n’est pas connu mais ne condition
peut pas être nul : 1 à n répétitions Frepete
[Link] structure « POUR… FIN POUR »
Le nombre de répétitions est connu (i= 1 à 20) Pour var v1 à v2 faire
séquence d’instructions
Fpour
25
 Boucles

 Le choix multiple

 Supposons que l'on veuille demander à l'utilisateur de

choisir dans un menu une des 3 possibilités offertes.
 Le choix présenté ne se limite pas à une alternative (soit
- soit).
 Mais plutôt à une expression du type « selon que… »
selon i
i=1 : faire bloc1
i=2: faire bloc2
sinon bloc3
Fselon

26
 Procédures et Fonctions

 Jusqu’ici nous avons étudié les algorithmes selon une

approche simple :
o Un seul algorithme exprime une fonction
o qui à partir de données initiales produit un
résultat

Cas plus général :

o Le calcul d’une fonction est le résultat de plusieurs

algorithmes disjoints

o À chaque algorithme va donc correspondre un

programme

27
 Procédures et Fonctions

 Dans le principe, un bon algorithme ne devrait

pas dépasser une page !

 Pour respecter ce principe, il convient de

NOMMER certaines séquences d’actions qui
correspondront à des procédures ou à des fonctions

 Ainsi, ces actions nommées seront décrites

dans des algorithmes auxiliaires et seront
utilisées dans un algorithme principal.

28
 Procédures et Fonctions

 Échanger le contenu des variables entières A et B.

 Diviser l ’entier A par l’entier B pour obtenir le quotient

Q et le reste R
 Trier la suite de N éléments contenu dans le tableau T

 Élever A à la puissance B fonctions

procédures

29
 Fonctions

 Il existe deux catégories de fonctions :

[Link] fonctions standards : fonctions de base offertes

par le langage utilisé

[Link] fonctions utilisateurs : Tôt ou tard, l’utilisateur

devra développer ses propres fonctions à partir du
langage utilisé. En effet, elles doivent répondre à un
besoin précis et elles ne seront pas disponibles dans la
bibliothèque du langage de programmation utilisé…

[Link]@[Link]
30 2020/2021
 Fonctions prédéfinies

 Les fonctions de texte

 Len(chaîne) : Renvoie le nombre de caractères d’une
chaîne
 Mid(chaîne, n1, n2) : Renvoie un extrait de la chaîne,
commençant au caractère n1 et faisant n2 caractères de long.
 Left(chaîne,n) : Renvoie les n caractères les plus à gauche
dans chaîne.
 Right(chaîne,n) : Renvoie les n caractères les plus à droite
dans chaîne.
 Trouve(chaîne1,chaîne2) : renvoie un nombre
correspondant à la position de chaîne2 dans chaîne1. Si
chaîne2 n’est pas comprise dans chaîne1, la fonction renvoie
zéro.

[Link]@[Link]
31 2020/2021
 Fonctions prédéfinies

 Les fonctions de texte (exemple)

[Link]@[Link]
32 2020/2021
 Fonctions prédéfinies

 Les fonctions Modulo

Cette fonction permet de récupérer le reste de la division

d’un nombre par un deuxième nombre.

Par exemple :

[Link]@[Link]
33 2020/2021
 Fonctions récursives

 Il existe deux types de solution pour résoudre des

problèmes nécessitant plusieurs calculs similaires et
répétitifs:  les solutions itératives et
récursives.
 Dans les deux cas, un mécanisme différent est mis en
place afin d’exécuter plusieurs fois la même séquence
d’instruction. Ces mécanismes se traduisent par :

 des boucles de contrôle pour les solutions itératives

 des fonctions qui s’appellent elles même

[Link]@[Link]
34 2020/2021
 Fonctions récursives

 Exemple calcul du factoriel d’un nombre entier :

 1ère définition :
n! = 1 * 2 * 3 * 4 * … * n
Traduction par une boucle :
Je vous écoute
 2ème définition :
 n! = 1 si n=0
= n * (n-1)! si non

[Link]@[Link]
35 2020/2021
 Fonctions récursives

 Procédure factoriel

fonction factoriel (Donnée n: entier): entier

Entier fac
Début
si n = 0 alors
fac  1
sinon
fac  n * factoriel(n-1)
fsi
Retour fac;
Fin

36
 Fonctions récursives

 Dérouler cet algorithme pour : Factoriel(5)

 Factoriel(5) 5 * 24 =120
 5 * Factoriel(4)
4 * 6 = 24
 4 * Factoriel(3)
3*2=6
 3 * Factoriel(2)
 2 * Factoriel(1) 2*1=2

 1 * Factoriel(0) 1*1=1
1
[Link]@[Link]
37 2020/2021
 Fonctions récursives

 La recherche d’un mot dans le dictionnaire

 La solution itérative, simple mais peu efficace, correspond

à parcourir dans l’ordre, du premier vers le dernier, tous
les éléments du dictionnaire jusqu’à ce que le mot
recherché soit identifié

 Une solution plus efficace et plus élégante consiste à faire

ce que nous faisons intuitivement : une recherche binaire

Comment procède-t-on pour résoudre ce problème?

[Link]@[Link]
38 2020/2021
 Fonctions récursives

 Pseudo code d’un algorithme de recherche binaire :

Fonction-Recherche-binaire (Dictionnaire, Mot)

SI Dictionnaire est réduit à une seule page
ALORS parcourir la page pour localiser Mot
SINON
Trouver la partie du Dictionnaire séparé par
le milieu où se trouve Mot
SI Mot se trouve dans la première partie du
Dictionnaire
Fonction-Recherche-Binaire( première
partie de Dictionnaire, Mot)
Sinon
Fonction-Recherche-Binaire( deuxième
partie de Dictionnaire, Mot)

[Link]@[Link]
39 2020/2021