Algorithmique et

Programmation

Mme Soumia ZITI-LABRIM
s.ziti@fsr.ac.ma
Universit Mohamed V
Facult des Sciences
Dpartement Informatique

1
Introduction
Elments de base
Structures conditionnelles
Structures itratives
Tableaux
Sous algorithme
Fichiers
Complexit
Algorithmes de tris

Plan
2
But de lenseignement
Obtenir de la machine quelle effectue un travail notre place
Problme: expliquer la machine comment elle doit s'y prendre
Mais... comment le lui dire ou le lui apprendre afin quil fasse le travail
aussi bien que nous, voir mieux que nous?
Objectifs
Rsoudre des problmes comme une machine
Savoir expliciter son raisonnement
Savoir formaliser son raisonnement
Concevoir et crire des algorithmes (squence dinstructions qui
dcrit comment rsoudre un problme particulier)
3
Introduction
Algorithme

Selon le Petit Robert : "ensemble des rgles opratoires propres un
calcul.
Un peu plus prcisment : Une squence de pas de calcul qui prend
un ensemble de valeurs comme entre et produit un ensemble de valeurs
comme sortie.
Un algorithme rsout toujours un problme de calcul. Lnonc du
problme spcifie la relation E/S souhaite.
4
Introduction
Algorithme
Un algorithme, traduit dans un langage comprhensible par lordinateur
(ou langage de programmation, ici le C), donne un programme, qui peut
ensuite tre excut, pour effectuer le traitement souhait.


5
Introduction
Algorithme

Savoir expliquer comment faire un travail sans la moindre ambigut
Langage simple : des instructions squentielle
Suite finie d'actions entreprendre en respectant une
chronologie impose

Un algorithme est indpendant de
Le langage dans lequel il est implant,
La machine qui excutera le programme correspondant.
6
Introduction
Structure dun algorithme

Un algorithme doit tre lisible et comprhensible par plusieurs personnes.

Algorithme : Nom dAlgorithme
Donnes : Les entres de lalgorithme
Rsultats : Les sorties de lalgorithme
Dclarations : Variables, constantes
Dbut
Ensemble dinstructions ;
Fin


7
Introduction
Les tapes dun algorithme

Prparation du traitement
Donnes ncessaires la rsolution du problme
Traitement
Rsolution pas pas, aprs dcomposition en sous-problmes si
ncessaire
Edition des rsultats
impression lcran, dans un fichier, etc.

8
Introduction
Exemple :

Algorithme CalculeInverse

Variables Nombre, Inverse: entiers {dclarations: rservation
d'espace-mmoire}
Dbut
{prparation du traitement}
Ecrire("Quel nombre voulez-vous lever au carr?")
Lire(Nombre)
{traitement : calcul de linverse}
Inverse 1 / Nombre
{prsentation du rsultat}
Ecrire("Linverse de ", Nombre,"c'est ", Inverse)
fin.
9
Introduction
Les problmes fondamentaux

Complexit
En combien de temps un algorithme va -t-il atteindre le rsultat
escompt?
De quel espace a-t-il besoin?
Calculabilit
Existe-t-il des tches pour lesquelles il n'existe aucun algorithme ?
Etant donne une tche, peut-on dire s'il existe un algorithme qui la
rsolve ?
Correction
Peut-on tre sr qu'un algorithme rponde au problme pour lequel
il a t conu?
10
Introduction
Logique propositionnelle :

La logique : une faon de formaliser notre raisonnement

La logique propositionnelle: modle mathmatique qui nous permet de
raisonner sur la nature vraie ou fausse des expressions logiques

Proposition: expression qui peut prendre la valeur VRAI ou FAUX

Exemple
x > y
1+1=2
1+1=1


11
Introduction
Elments de logique propositionnelle

Formule : expression logique compose de variables propositionnelles
et de connecteurs logiques
Variable propositionnelle : une proposition considre comme
indcomposable
Connecteurs logiques: ngation non , ; implication ; disjonction
ou, ; conjonction et ,
Exemple : p et q variables propositionnelles
(p q) ((p r) p )
Par un arbre syntaxique :
En utilisant la notation prfixe :
p q p r p
En utilisant la notation postfixe:
p q p r p
12
Introduction
Tables de vrit

Reprsentation des valeurs de vrit associes une expression logique

p et q : variables propositionnelles

13
Introduction
Equivalences classiques

Commutativit
p q quivalent q p
p q quivalent q p
Associativit
p (qr) quivalent (p q) r
p (q r) quivalent (p q) r
Distributivit
p (q r) quivalent (p q)(pr)
p (q r) quivalent (p q)(pr)
14
Introduction
Lois de Morgan

(p q) quivalent (p) (q)
(p q) quivalent (p) (q)
15
Introduction
Formules :

Les tautologies : vraies pour toute assignation de valeurs de vrit aux
variables.

Exemple: pp



Les formules contradictoires : fausses pour toute assignation de
valeurs de vrit aux variables.

Exemple: pp
16
Introduction
Formules

Les formules quivalentes: mme valeur de vrit pour toute
assignation de la mme valeur de vrit aux variables.

Exemples:
p q est quivalent p q
p q est quivalent q p
17
Introduction
Applications l'algorithmique

Interprter(et bien comprendre!) larrt des itrations
la sortie dune boucle.
tant que<condition> faire
la sortie :non(<condition>)est vrai
donc si condition= p et q
la sortie : non(p et q)
cest a dire non p ou non q
Exemple:
avec <condition> gal : val STOP et nbVal< MAX
non(<condition>) gal : val =STOP ounbValMAX
18
Introduction
Applications l'algorithmique

Simplifier une criture par substitution d'une formule quivalente
si (Age = "Mineur"
ou (non (Age = "Mineur") et non (Fisc = "Imposable"))) alors...
Equivalent :
si (Age = "Mineur" ou non (Fisc = "Imposable")) alors...

Vrifier la validit d'une condition

si Valeur< 10 et Valeur >100 alors cas improbable

Ecrire la ngation dune condition

si on veut P et Q et R :
rpter . tant que nonP ou nonQ ou nonR ou
19
Introduction
Variable

Elle peuvent stocker des chiffres, des nombres, des caractres des
chane de caractres..., dont la valeur peut tre modifie au cours de
lexcution de lalgorithme
Une variable est une entit qui contient une information, elle possde :
un nom ou identifiant, une valeur et un type qui caractrise
lensemble des valeurs que peut prendre la variable
Lensemble des variables est stock dans la mmoire de
lordinateur
Dclaration
Variable : <liste didentificateurs1> : typeVaraible1
<liste didentificateurs2> : typeVariable2
Exemple
Variable A, B : entier
d : rel
20
Elments de base
Entier

Cest le type qui reprsente des nombres entiers relatifs (int, integer)
Il peut tre cod en entier simple sur deux octets ou long sur quatre
octets
Il peut tre reprsent en dcimal (0, - 55), en hexadcimal (10h,
4Ah) ou en binaire (% 01001, % 1110)

Rel

Cest le type qui reprsente des nombres rels (float)
Il peut tre cod en rel simple sur 4 octets ou double sur 8 octets
Il peut tre reprsent en forme simple (2.5, -2.0) ou exponentielle (
2.1 e
4
, -6,98 E
-2
)


21
Elments de base
Caractre

Il est reprsent en code ASCII
Il permet davoir une relation dordre
Exemple A < a car en ASCII 65<97 et A<Z car en ASCII 65<90

Chane de caractre

Elle reprsente un tableau de caractres
Plusieurs fonctions prdfinies : Longueur(S) donne la longueur de S

Boolen

Il prsente les deux valeurs Vrai et Faux (True and False ou 1 et 0)


22
Elments de base
Constante

Elle peuvent stocker des chiffres, des nombres, des caractres des
chane de caractres..., dont la valeur ne peut tre modifie au cours de
lexcution de lalgorithme

Dclaration

Constante : <NomVariable> <ValeurVariable> : TypeVariable

Exemple

Constante A1 : entier
23
Elments de base
Oprateurs

Un oprateur est un symbole dopration qui permet dagir sur des
variables ou de faire des calculs

Une oprande est une entit (variable, constante ou expression) utilise
par un oprateur

Une expression est une combinaison doprateur(s) et doprande(s),
elle est value durant lexcution de lalgorithme, et possde une valeur
(son interprtation) et un type

Exemple
Dans lexpression a + b, a et b sont des oprandes et + loprateur
Dans lexpression c= a* b : c, a, b et a*b sont des oprandes et =
et * sont des oprateurs
Si par exemple a et b sont des entiers, lexpression a + b, a*b et c
sont aussi des entier
24
Elments de base
Types oprateurs

Un oprateur est unaire (non) ou
binaire (+)
Un oprateur est associ un type
et ne peut tre utilis quavec des
donnes de ce type



25
Elments de base
Arithmtiques
Addition : + (ou concatnation)
Soustraction : -
Multiplication : *
Division : /
Division entire : DIV
Puissance : |
Reste de DIV : MOD
Comparaisons
Infrieur : <
Infrieur ou gale : <=
Suprieur : >
Suprieur ou gale : >=
Diffrent : !=
Egale : =
Logiques
Conjonction : ET
Disjonction : OU
Disjonction exclusive : OUX
Ngation : NON
Dcalage droit : >>
Dcalage gauche : <<
Priorit des Oprateurs

En arithmtique les oprateurs * et / sont prioritaires sur + et -
Pour les boolens, la priorit des oprateurs est non, et, ouExclusif et
ou

Oprateur daffectation

Il permet daffecter une valeur de loprande droit une variable
(oprande gauche), il est reprsent par :

<Identificateur> <expression> || <constante> || <identificateur>

Exemple:
nom "Venus "
val1 val2
val val 2
26
Elments de base
Entre\Sortie

Un algorithme peut avoir des interactions avec lutilisateur et
communiquer avec lui dans les deux sens, les sorties sont des envois
de messages a l'utilisateur, les entres sont des informations fournies par
l'utilisateur.
Il peut demander lutilisateur de saisir une information afin de la
stocker dans une variable et peut afficher un rsultat (du texte ou le
contenu dune variable)

27
Elments de base
Instruction d'criture (Sortie)

Elle permet la restitution de rsultats sur le priphrique de sortie (en
gnral l'cran)

Syntaxe : crire(liste d'expressions)

Cette instruction ralise simplement l'affichage des valeurs des
expressions dcrites dans la liste.
Ces instructions peuvent tre simplement des variables ayant des
valeurs ou mme des nombres ou des commentaires crits sous forme de
chanes de caractres.

Exemple :
crire(x, y+2, "bonjour")
28
Elments de base
Instruction lecture (Entre)

L'instruction de prise de donnes sur le priphrique d'entre (en gnral
le clavier)

Syntaxe : lire(liste de variables)

L'excution de cette instruction consiste affecter une valeur la
variable en prenant cette valeur sur le priphrique d'entre

Exemple :
Lire(x, y, A)
29
Elments de base
Exemple

Cet algorithme demande a l'utilisateur de saisir une valeur numrique,
ensuite il affiche la valeur saisie, puis la mme valeur incrmente de 1.

Algorithme : Affichage incrment
variables :
a, b : entier
DEBUT
crire("Saisissez une valeur numrique")
lire(a)
b a + 1
crire("Vous avez saisi la valeur ", a, ". ")
crire(a, "+ 1 = ", b)
FIN
30
Elments de base
La structure Si

Linstruction si alors sinon permet de conditionner lexcution dun
algorithme la valeur dune expression boolenne.

Syntaxe :

si <expression boolenne> alors
<suite dinstructions excutes si lexpression est vrai>
sinon
<suite dinstructions excutes si lexpression est fausse>
finsi

La deuxime partie de linstruction est optionnelle, on peut avoir :

si <expression boolenne> alors
<suite dinstructions excutes si lexpression est vrai>
finsi
31
Structure conditionnelle
Structure Si

Exemple
Algorithme : Valeur Absolue
Donnes : La valeur calculer
Rsultat : La valeur Absolue

dbut
si valeur 0 alors
valeurabsolue valeur
sinon
valeurabsolue valeur * -1
finsi
fin

32
Structure conditionnelle
Structure de choix multiple

Lorsque lon doit comparer une mme variable avec plusieurs valeurs,
comme par exemple :

si abrviation = "M" alors
crire( "Monsieur" )
Sinon
si abrviation = "Mme" alors
crire("Madame")
sinon
si abrviation = "Mlle" alors
crire( "Mademoiselle" )
sinon
crire( "Monsieur, Madame " )
fsi
fsi
fsi
On peut remplacer cette suite de si par linstruction Selon
33
Structure conditionnelle
Structure de choix multiple

Syntaxe

selon <identificateur : V> faire
V1 : instructions 1
V2 : instructions 2

Vn : instructions n

[autres: instructions]
finSelon

V1,. . . ,Vn sont des constantes de type scalaire (entier, rel, caractre
)
instructions i est excute si V = Vi (on quitte ensuite le selon)
instruction autre est excute si quelque soit i, V Vi
34
Structure conditionnelle
Structure de choix multiple

Exemple


selon abrviation faire
"M" : crire( " Monsieur " )
"Mme" : crire( " Madame " )
"Mlle" : crire( " Mademoiselle " )
autres: crire( " Monsieur, Madame " )
finSelon
35
Structure conditionnelle

Un algorithme peut rpter le mme traitement plusieurs fois, avec
ventuellement quelques variantes.

Dans certain cas, Il est impossible de savoir l'avance combien de fois
la mme instruction doit tre dcrite.

Utilisation des instructions en boucle qui rptent plusieurs fois une
mme instruction.

Deux formes existent : la premire, si le nombre de rptitions est
connu avant l'excution de l'instruction de rptition ( Pour ), la seconde
s'il n'est pas connu ( Tant que et rpter jusqu). L'excution de la
liste des instructions se nomme itration.
36
Structure itratives
Rptition inconditionnelle

Il est frquent que le nombre de rptitions soit connu l'avance, et que
l'on ait besoin d'utiliser le numro de l'itration afin d'effectuer des
calculs ou des tests.

Syntaxe de Pour :

Pour <variable> de ValInit ValFin [par <pas>] faire
liste d'instructions
FinPour

La variable prend successivement toutes les valeurs entires entre
valeur initiale et valeur finale. Pour chaque valeur, la liste des instructions
est excute.
La valeur utilise pour numrer les itrations est appele valeur
d'itration, indice d'itration ou compteur. L'incrmentation par 1 de la
variable est implicite.
37
Structure itratives
Rptition conditionnelle

Dans beaucoup de cas, on souhaite rpter une instruction tant qu'une
certaine condition est remplie, alors qu'il est priori impossible de
savoir l'avance au bout de combien d'itrations cette condition cessera
d'tre satisfaite.

Dans ce cas, on a deux possibilits :
la boucle Tant que
la boucle Rpter jusqu'



38
Structure itratives
Boucle Tant que

Syntaxe :

tant que condition faire
liste d'instructions
FinTantQue

Cette instruction a une condition de poursuite dont la valeur est de type
boolen et une liste d'instructions qui est rpte si la valeur de la
condition de poursuite est vraie : la liste d'instructions est rpte autant
de fois que la condition de poursuite a la valeur est vraie.
Etant donn que la condition est value avant l'excution des
instructions rpter, il est possible que celles-ci ne soient jamais
excutes.
Il faut que la liste des instructions ait une incidence sur la condition
afin qu'elle puisse tre value faux et que la boucle se termine (Il faut
toujours s'assurer que la condition devient fausse au bout d'un temps fini.)
39
Structure itratives
Boucle Tant que

Exemple

Un utilisateur peut construire des rectangles de taille quelconque,
condition que les largeurs qu'il saisit soient suprieures 1 pixel.

Algorithme : saisirLargeurRectangle
Variable : largeur : entier
dbut
crire ("indiquez la largeur du rectangle :")
lire(largeur)
tant que largeur < 1 faire
crire ("erreur : indiquez une valeur > 0")
crire ("indiquez la largeur du rectangle :")
lire(largeur)
finTantQue
fin
40
Structure itratives
Boucle Rpter jusqu'

Syntaxe :

Rpter
liste d'instructions
jusqu' condition

La squence d'instructions est excute au moins une fois et jusqu' ce
que l'expression soit vraie. Ds que la condition est vrai, la rptitivit
s'arrte.
41
Structure itratives
Boucle Rpter jusqu'

Exemple

Algorithme : saisirLargeurRectangle
Variable : largeur : entier
dbut

rpter
crire ("indiquez la largeur du rectangle :")
lire(largeur)
si largeur < 1 alors
crire ("erreur : indiquez une valeur > 0")
finSi
jusqu' largeur >= 1
fin

42
Structure itratives
Comparaison Tant que e Rpter jusqu

La squence d'instructions est excuter au moins une fois dans la
boucle Rpter jusqu', alors qu'elle peut ne pas tre excuter
dans le cas du Tant que.

la squence d'instructions est excuter si la condition est vrai pour
le Tant que et si la condition est fausse pour le Rpter jusqu'.

Dans les deux cas, la squence d'instructions doit ncessairement
faire voluer la condition, faute de quoi on obtient une boucle
infinie.
43
Structure itratives
Conclusion
44
Structure itratives
Lorsque les donnes sont nombreuses et de mme type, afin d'viter de
multiplier le nombre des variables, on les regroupe dans un tableau

Le type d'un tableau prcise le type (commun) de tous les lments.

Syntaxe :
<nomTab> : tableau [borne_inf ... borne_sup] : <TypeTab>

En gnral, nous choisirons toujours la valeur 0 pour la borne infrieure
dans le but de faciliter la traduction de l'algorithme vers les autres
langages (C, Java, ...). Pour un tableau de 10 entiers, on aura :
Exemple
tabVal : tableau [0..9] : entier
45
Tableaux
Les tableaux une dimension (vecteurs)





Ce tableau est de longueur 10. Chacun des dix nombres du tableau est
repr par son rang, appel indice
Pour accder un lment du tableau, il suffit de prciser entre
crochets l'indice de la case contenant cet lment.
Pour accder au 5me lment (22), on crit : Tab[4]
Les instructions de lecture, criture et affectation s'appliquent aux
tableaux comme aux variables.
x Tab[0] (x=45)
Tab[6] 43
46
Tableaux
0 1 2 3 4 5 6 7 8 9
45 54 1 -56 22 134 49 12 90 -26
Les tableaux deux dimensions ( matrices)

Lorsque les donnes sont nombreuses et de mme nature, mais
dpendent de deux critres diffrents, elles sont ranges dans un tableau
deux entres.







Ce tableau a 3 lignes et 7 colonnes. Les lments du tableau sont
reprs par leur numro de ligne et leur numro de colonne.

Tab[1, 4] = 38
47
Tableaux
0 1 2 3 4
0 12 28 44 2 76
1 23 36 51 11 38
2 43 21 55 67 83

La variable Tab[i, j] s'appelle l'lment la ligne i et la colonne j (indice i et j
du tableau Tab).








Syntaxe

<nomTab> : tableau [binf1 ... Bsup1; binf2 ... Bsup2] : <TypeTab>


Les tableaux peuvent avoir n dimensions.
48
Tableaux
Tab[0, 0] Tab[0, 1] Tab[0, 2] Tab[0, 3] Tab[0, 4]
Tab[1, 0] Tab[1, 1] Tab[1, 2] Tab[1, 3] Tab[1, 4]
Tab[2, 0] Tab[2, 1] Tab[2, 2] Tab[2, 3] Tab[2, 4]
Traitements oprant sur des tableaux

Crer des tableaux
Ranger des valeurs dans un tableau
Rcuprer, consulter des valeurs ranges dans un tableau
Rechercher si une valeur est dans un tableau
Mettre jour des valeurs dans un tableau
Modifier la faon dont les valeurs sont ranges dans un tableau (par
exemple : les trier de diffrentes manires)
Effectuer des oprations entre tableaux : comparaison de tableaux,
multiplication,...
49
Tableaux
Parcours complet d'un tableau
.
Les rptitions inconditionnelles sont le moyen le plus simple de
parcourir compltement ou partiellement un tableau.
Syntaxe
Pour une dimension :
Pour cpte de 0 Taille(Tab)-1 [par 1] faire
Utiliser Tab[cpte] pour saisie, affichage, affectation, calcul
FinPour
Pour deux dimension :
Pour ligne de 0 nbLigne-1 [par 1] faire
Pour colonne de 0 nbColonne-1 [par 1] faire
Utiliser Tab[ligne,colonne] pour saisie, affichage,
FinPour
50
Tableaux
Exemple

Dans l'exemple suivant, le programme initialise un un tous les lments
de deux tableau diffrents:
Algorithme : initialisation tableaux
Variable : i , j :entier
Tab : tableau de [0n-1] :entier
Mat : tableau de [0n-1 ; 0n-1] :entier
Constante : n 20 : entier
dbut
pour i de 0 n-1 faire
tab[i] i
pour j de 0 n-1 faire
Mat[i , j] i*i
finpour
fin
51
Tableaux
Mthodologie de base:

1. Abstraire
Retarder le plus longtemps possible linstant du codage

2. Dcomposer
"...diviser chacune des difficults que jexaminerai en autant de
parties quil se pourrait et quil serait requis pour les mieux rsoudre."
Descartes

3. Combiner
Rsoudre le problme par combinaison dabstractions
52
Sous algorithmes
Exemple
rsoudre le problme suivant : Ecrire un programme qui affiche en
ordre croissant les notes dune promotion suivies de la note la plus
faible, de la note la plus leve et de la moyenne, revient rsoudre les
problmes suivants :
Remplir un tableau de naturels avec des notes saisies par
lutilisateur
Afficher un tableau de valeurs
Trier un tableau de valeurs en ordre croissant
Trouver la plus petite valeur dun tableau
Trouver la plus grande valeur dun tableau
Calculer la moyenne dun tableau de valeurs
Chacun de ces sous-problmes devient un nouveau problme
rsoudre.
Si on considre que l'on sait rsoudre ces sous-problmes, alors
on sait
.quasiment. rsoudre le problme initial
53
Sous algorithmes
Principe

Un algorithme appelle un sous-algorithme : cet algorithme passe
"momentanment" le contrle de l'excution du traitement au sous-
algorithme.
Un sous-algorithme est conu pour faire un traitement bien dfini, bien
dlimit, si possible indpendamment du contexte particulier de
lalgorithme appelant.
Remarque : un sous-algorithme peut en appeler un autre.
En algorithmique il existe deux types de sous-programmes :
Les fonctions
Les procdures
54
Sous algorithmes
Fonction

Une fonction est une suite ordonne dinstructions, ralisant une
certaine tche. Elle admet zro, un ou plusieurs paramtres et
retournant toujours une valeur
Une fonction joue le rle dune expression. Elle enrichit le jeu des
expressions possibles.
Exemple :
Y= sin (X)
Nom : sin
Arguments ou paramtres : X
55
Sous algorithmes
Procdure

Une procdure est une suite ordonne dinstructions ralisant une
certaine tche. Elle admet zro, un ou plusieurs paramtres et ne
renvoie pas de rsultat.
Une procdure joue le rle dune instruction. Elle enrichit le jeu des
instructions existantes.
Exemple :
print (X, Y, Z)
Nom : print
Arguments ou paramtres : X, Y et Z
56
Sous algorithmes
Caractristiques

Un programme est dit rcursif s'il s'appelle lui mme

Un programme rcursif est donc forcment une fonction ou une
procdure (il doit pouvoir s'appeler)

Il est impratif de prvoir une condition d'arrt la rcursion, sinon le
programme ne s'arrte jamais!

Il faut toujours tester en premier la condition d'arrt, et ensuite, si la
condition n'est pas vrifie lancer un appel rcursif
57
Fonction rcursive
Exemple : la factorielle
version itrative :
n ! = 1 x 2 x 3 x x n
Algorithme : Factorielle
Donnes : n : entier
Rsultat : le factoriel de n
Variable : i, r : entier
dbut
r 1
pour i de 2 n faire
r r*i
retourne r
fin
58
version rcursive:
1!=1 et pour n>1 n ! = n x (n-1)!
Algorithme : Factorielle
Donnes : n : entier
Rsultat : le factoriel de n
dbut
Si n=1 alors
retourne 1
Sinon
retourne n*Factorielle(n-1)
FinSi
fin
Fonction rcursive
Conclusion

La programmation rcursive, pour traiter certains problmes, peut tre
trs conomique, elle permet de faire les choses correctement, en trs
peu de lignes de programmation.

En revanche, elle est trs dispendieuse de ressources machine. Car il
faut crer autant de variable temporaires que de " tours " de fonction en
attente.

Toute fonction rcursives peut galement tre formule en termes
itratifs ! Donc, si elles facilitent la vie du programmeur, elle ne sont pas
indispensable.
59
Fonction rcursive
Besoin de fichiers

Jusqu' maintenant nous n'avions vu que des Entres/Sorties (E/S)
sous la forme d'entre standard (usuellement le clavier, lire) et de sortie
standard (usuellement l'cran, crire)

Ce type d'E/S atteint rapidement ses limites...
Utilisation des fichiers : sauvegarde/restitution des donnes
entre le programme et le disque dur.

60
Fichiers
Dfinition

Un fichier (file) est un ensemble structur de donnes stock en
gnral sur un support externe (disquette, disque dur ou optique, ...). Ils
servent stocker des informations de manire permanente, entre deux
excutions dun programme

Un fichier structur contient une suite d'enregistrements homognes,
qui regroupent le plus souvent plusieurs composantes (champs)

Un fichiers squentiel contient des enregistrements qui sont
mmoriss conscutivement dans l'ordre de leur entre et peuvent
seulement tre lus dans cet ordre. Si on a besoin d'un enregistrement
prcis dans un fichier squentiel, il faut lire tous les enregistrements qui le
prcdent, en commenant par le premier.

61
Fichiers
Types de fichiers

Les fichiers textes : sont les fichiers dont le contenu reprsente
uniquement une suite de caractres imprimables, d'espaces et de
retours la ligne (.txt,...). Ils peuvent tre lus directement par un diteur
de texte.

Les fichiers binaires : sont les fichiers qui ne sont pas assimilables
des fichiers textes (.exe, .mp3, .png,...). Ils ne peuvent pas tre lus
directement par un diteur de texte .
62
Fichiers
Structures de fichiers

Structure dlimite : Elle utilise un caractre spcial, appel
caractre de dlimitation, qui permet de reprer quand finit un champ et
quand commence le suivant. Il va de soi que ce caractre de dlimitation
doit tre strictement interdit lintrieur de chaque champ, faute de quoi
la structure devient proprement illisible.
"Fonfec";"Sophie";0142156487;"fonfec@yahoo.fr"

Structure champs de largeur fixe : les x premiers caractres de
chaque ligne stockent le premier champs, les y suivants le second
champs..Il faut faire attention aux longueurs des champs
Fonfec Sophie 0142156487 fonfec@yahoo.fr
63
Fichiers
Types daccs

Laccs squentiel : naccder une information qu'en ayant au
pralable examin celle qui la prcde. Accs un enregistrement par
enregistrement

Laccs direct (ou alatoire) : accder directement lenregistrement
de son choix, en prcisant le numro de cet enregistrement. Mais cela
veut souvent dire une gestion fastidieuse des dplacements dans le
fichier

Laccs index : combiner la rapidit de l'accs direct et la simplicit
de l'accs squentiel. Il est particulirement adapt au traitement des gros
fichiers, comme les bases de donnes importantes.
64
Fichiers
Proprits(fichier squentiel)

Un fichier est donn par son nom (et en cas de besoin le chemin
d'accs sur le mdium de stockage), il peut tre cr, lu ou modifi

Les fichiers se trouvent ou bien en tat d'criture (mettre dedans toutes
les informations que lon veut, mais les informations prcdentes, si elles
existent, seront intgralement crases), en tat de lecture (rcuprer
les informations quil contient, sans les modifier en aucune manire) ou
en ajout (ajouter de nouvelles lignes ou nouveaux enregistrement)

A un moment donn, on peut uniquement accder un seul
enregistrement; celui qui se trouve en face de la tte de lecture/criture.
Aprs chaque accs, la tte de lecture/criture est dplace derrire la
donne lue en dernier lieu.
65
Fichiers
Mcanisme

Dclarer un fichier : NomFichier : Fichier
Ouvrir le fichier en un mode spcifi : Ouvrir(NomFichier) en mode
Tester que le fichier est bien ouvert : Si NomFichier est Ouvert
Lire\ crire dans le fichier ouvert :
LireFichier(NomFichier, valeurEnregistrement)
EcrireFichier(NomFichier, valeurEnregistrement)
Fermer le fichier : Fermer(NomFichier)
66
Fichiers
Exemple
Variable Truc : chane Caractre
Fich : Fichier
Dbut
Fich "Exemple.txt"
Ouvrir(Fich) en Lecture
Tantque Non EOF(Fich)
LireFichier (Fich,Truc)
FinTantQue
Fermer(Fich)
Truc "Fonfec";"Sophie";0142156487;"fonfec@yahoo.fr"
Ouvrir(Fich) en Ajout
EcrireFichier (Fich, Truc)
Fermer(Fich)
Fin 67
Fichiers
Problmatique :

Mesurer l'efficacit d'un algorithme, ce qu'on appelle sa complexit
Prvoir son temps d'excution
Estimer les ressources qu'il va mobiliser dans une machine lors
de son excution (place occupe en mmoire en particulier)
Comparer avec un autre qui fait le mme traitement d'une autre
faon, de manire choisir le meilleur

L'valuation de la complexit peut se faire plusieurs niveaux
Niveau purement algorithmique, par l'analyse et le calcul
Niveau du programme, par l'analyse et le calcul
Niveau de l'excution du programme exprimentalement
68
Complexit
Complexit exprimentale

Jusqu'aux annes 70, seule la mesure exprimentale de la complexit
d'un algorithme tait (parfois) effectue

Cette valuation exprimentale dpendait normment des machines
mais permettait de comparer l'efficacit de diffrents algorithmes si on
les crivait dans un mme langage et qu'on les faisait tourner sur une
mme machine

Si on les faisait tourner sur des machines diffrentes, il fallait valuer la
puissance des machines qui dpend du matriel mais aussi du systme
d'exploitation et varie en fonction des traitements effectus (calculs
bruts, sur des entiers ou des rels, calculs lis l'affichage, ...)
69
Complexit
Complexit en temps et en espace

Plusieurs complexits peuvent tre values :
Complexit en temps : il s'agit de savoir combien de temps
prendra l'excution d'un algorithme
Complexit en espace : il s'agit de savoir combien d'espace
mmoire occupera l'excution de l'algorithme

Souvent, si un algorithme permet de gagner du temps de calcul, il
occupe davantage de place en mmoire (mais un peu d'astuce permet
parfois de gagner sur les deux tableaux)

Gnralement, on s'intresse essentiellement la complexit en temps
(ce qui n'tait pas forcment le cas quand les mmoires coutaient cher)
70
Complexit
Complexit au pire

La complexit n'est pas la mme selon les droulements du traitement
Complexit au pire : complexit maximum, dans le cas le plus
dfavorable ( borne suprieur du temps d'excution)
Complexit en moyenne : il s'agit de la moyenne des
complexits obtenues selon les issues du traitement
Complexit au mieux : complexit minimum, dans le cas le plus
favorable. En pratique, cette complexit n'est pas trs utile

Si on veut comparer les algorithmes indpendamment des
implmentations et des machines, on ne peut comparer que la forme
gnrale de la complexit, en particulier la faon dont elle volue selon
la taille des donnes
71
Complexit
Paramtre de la complexit

La complexit d'un algorithme est calcule en fonction d'un paramtre
par rapport auquel on veut calculer cette complexit

Pour un algorithme qui opre sur une structure de donnes (tableau),
la complexit est gnralement exprime en fonction d'une dimension de
la structure.

Si l'algorithme prend en entre une structure plusieurs dimensions il
faut prciser en fonction de quelle dimension on calcule la complexit
(l'algorithme peut avoir des complexits diffrentes)

Pour un algorithme qui opre sur un nombre, la complexit est
gnralement exprime en fonction de la valeur du nombre
72
Complexit
Complexit approche

Calculer la complexit de faon exacte n'est pas raisonnable (quantit
d'instructions ) et n'est pas utile (comparaison des algorithmes)

Premire approximation : considrer souvent que la complexit au
pire

Deuxime approximation : calculer la forme gnrale de la
complexit, qui indique la faon dont elle volue en fonction d'un
paramtre

Troisime approximation : tudier comportement asymptotique de la
complexit, quand la valeur du paramtre devient assez grande
73
Complexit
Notation Landau

g est domine asymptotiquement par f : f(n) = O(g(n)) si - c > 0 et
n
o
> 0 tels que n > n
o
f(n) s c. g(n)

f domine asymptotiquement g : f(n) = (g(n)) si - c > 0 et n
o
> 0 tels
que n > no f(n) > C. g(n)

f est asymptotiquement quivalente g : f(n) = (g(n)) si - c1 et
c2 > 0 et no > 0 tels que n > no c1.g(n) s f(n) s c2. g(n)
74
Complexit
Exemples
x = O(x
2
) car pour x>1, x<x
2
100*x = O(x
2
) car pour x>100, x<x
2
x
2
= O(x
3
) car pour x>1, x
2
<x
3
ln(x) = O(x) car pour x>0, ln(x)<x

i>0, x
i
= O(e
x
) car pour x tel que x/ln(x)>i, x
i
<e
x
O(x) = O(x2) mais O(x2) O(x)
Si f(x) = O(1) alors f est majore
Si f(x) = (1) f est minore
6*2
x
+ x
2
= O(2
x
)
10n
2
+4n+2= (n
2
)
6*2
n
+ n
2
= (n
2
) 75
Complexit
Types de complexit

Complexit constante en O(1)
Complexit logarithmique en O(log(n))
Complexit linaire en O(n)
Complexit quasi-linaire en O(nlog(n))
Complexit quadratique en O(n2) :
Complexit polynomiale en O(n
i
)
Complexit exponentielle en O(i
n
)
Complexit factorielle en O(n!)
76
Complexit
Exemple

Calcul de la valeur d'un polynme en un point
1. p a[0]
2. pour i 0 n-1 faire {puissance(a, n) retourne a
n
}
3. xpi puissance (x , i)
4. p p + a[i]* xpi
fpour
Nombre de multiplications
en 3 --> 1+2+3+...+ (n-1) = (n-l)n/2
en4 --> n
Nombre d'additions en 4 --> n
soit au total: n(n + 3)/2 < n2 pour n > 3.
77
Complexit
Les algorithmes de tri, sont utiliss principalement pour les tableaux (et
les listes), ils peuvent aller du plus simple au plus compliquer.

Donne : Un tableau de n lments (a
0
,a
1
, . . . ,a
n-1
)
Rsultat : Une permutation (a
0
,a
1
, . . . ,a
n-1
) du tableau dentre telle
a
0
a
1
. . . a
n-1
ou a
0
a
1
. . . a
n-1
Lopration de base pour les algorithmes de tri est la comparaison : A[i] :
A[j],
Une autre opration est lchange : on peut changer A[i] et A[j], ce que
lon note par A[i] A[j]. Le rsultat est alors le suivant :
k A[i]
A[i] A[j]
A[j] k
78
Algorithmes de tris
Le tri bulle

Cest un des algorithmes le plus connu moins efficace mais correcte.
Le principe consiste balayer tout le tableau, en comparant les
lments adjacents et en les changeant sils ne sont pas dans le bon
ordre. Ce processus est rpt chaque fin de tableau jusqu aucun
change ne sera effectu.
Ce tri va ncessiter un grand nombre de dplacements dlments, il est
donc inutilisable dans les cas o ces dplacements sont coteux en
temps.
Il peut tre intressant quand le tableau initial est pr-tri (classement
alphabtique)

79
Algorithmes de tris
Le tri bulle

Algorithme : TRI-BULLE
Donnes : A: tableau [0..n-1] : entier
Variable : i, x : entier
Echange : boolen
dbut
Rpter
Echange Faux
pour i de 1 n-2 faire
Si A[i-1]>A[i] alors
Echange Vrai
x A[j]
A[j] A[i]
A[i] x
finSi
jusqu non Echange
fin
80
Algorithmes de tris
Le tri bulle

Exemple

Donnes :
Itration 1 :
Itration 2 :
Itration 3 :
Itration 4 :
Itration 5 :
Itration 6 :
Rsultats :
81
Algorithmes de tris
101 115 30
101 115 30
101 30 115
101 115 30
101 115 30
101 30 115
30 101 115
30 101 115
30 101 115
30 101 115
30 101 115
Le tri par insertion

Prendre les lments du tableau lun aprs lautre dans lordre initial, et
les placer correctement dans les lments prcdents dj tris
(classement des cartes de jeux aprs une donne).

A litration k, le k
me
lment est insr dune manire squentielle
parmi les premiers (k 1) lments qui sont dj tris, cet lopration est
rpt n fois (n taille du tableau)

Le tri par insertion peut tre intressant pour des tableaux ayant dj t
tris, mais o lon doit rajouter quelques nouveaux lments.

Complexit : le nombre de comparaison litration k est au plus k, le
nombre total de comparaison est au plus (n(n+1)/2)-1 e O(n2)
82
Algorithmes de tris
Le tri par insertion

Algorithme : TRI-INSERTION
Donnes : A: tableau [0..n-1] : entier
Variable : i, x, k : entier
dbut
pour i de 1 n-1 faire
ki-1
x A[i]
Tant que A[k]>x faire
A[k+1] A[k]
k k-1
finTq
A[k+1] x
finPour
fin
83
Algorithmes de tris
Le tri par insertion

Exemple :

Donnes :
Itration 1 :
Itration 2 :
Itration 3 :
Itration 4 :
Itration 5 :
Itration 6 :
Rsultats :
84
Algorithmes de tris
101 115 30 63 47 20
101 115 30 63 47 20
30 101 115 63 47 20
30 63 101 115 47 20
101 115 30 63 47 20
30 47 63 101 115 20
20 30 47 63 101 115
20 30 47 63 101 115
Le tri par slection

Le but est dsormais de dplacer chaque lment sa position
dfinitive.

Rechercher de llment le plus petit (ou plus grand) et lchanger avec
llment de la premire position de la liste de recherche, lopration est
rpte n-1 fois

Aprs le k
me
placement, les k plus petits lments du tableau sont
leur place dfinitive, il faut recommencer avec la liste des lments
restants du tableau

Complexit : le nombre de comparaison litration k est n-k, le nombre
total de comparaison est n(n-1)/2 e O(n
2
)
85
Algorithmes de tris
Le tri par slection

Algorithme : TRI-INSERTION
Donnes : A: tableau [0..n-1] : entier
Variable : i, x, k,j : entier
Dbut
i0
Tant que i<n-1 faire { i
me
placement }
ji
pour k de i+1 n-1 faire
Si A[k]<A[j] faire
j k
finPour
x A[j]
A[j] A[i]
A[i] x
finTq
fin 86
Algorithmes de tris
Le tri par slection

Exemple :

Donnes :
Itration 1 :
Itration 2 :
Itration 3 :
Itration 4 :
Itration 5 :
Rsultats :
87
Algorithmes de tris
20 115 30 63 47 101
20 30 115 63 47 101
20 30 47 63 115 101
20 30 47 63 115 101
101 115 30 63 47 20
20 30 47 63 101 115
20 30 47 63 101 115
Le tri rapide (Quick Sort)

Ce tri est rcursif. On cherche trier une partie du tableau, dlimite
par les indices gauche et droite.

Un pivot est choisi alatoirement parmi les valeurs du tableau

Recherche de la position dfinitive de ce pivot de telle sorte que tous
les lments avant le pivot soient plus petit que lui et que tous ceux placs
aprs lui soient suprieurs (mais sans chercher les classer)

Rappelle rcursif du tri de la partie avant le pivot et de la partie aprs le
pivot jusqu que les parties ne contiennent quun seul lment

Complexit en pire cas : O(n
2
) et en meilleur cas : O(n log(n))

88
Algorithmes de tris
Le tri rapide (Quick Sort)

Algorithme : TRI-RAPIDE
Donnes : A: tableau [0..n-1] , gch, drt : entier
Variable : i, j, x, pivot : entier
dbut
i gch j drt pivot A[(i+j)/2]
rpter
tant que t[i]<pivot faire
i i+1
tant que t[j]> pivot faire
j j-1
si i<= j alors
echanger(A[i],A[j])
i i+1
j j-1
finsi
jusqu' ce que i>j 89
Algorithmes de tris
Le tri rapide (Quick Sort)

Algorithme : TRI-RAPIDE
Donnes : A: tableau [0..n-1] , gch, drt : entier
Variable : i, j, x, pivot : entier
Dbut (suite)
si gch < j alors
Tri-Rapide(A,gch,j)
finsi
si i < drt alors
Tri-Rapide(A,i,droit)
finsi
fin
90
Algorithmes de tris
Le tri rapide

Exemple :

Donnes :
Itration 1 :
Itration 2 :
Itration 3 :
Puis relancer le processus sur

Rsultats :
91
Algorithmes de tris
20 115(i) 30 63 47(j) 101
20 47 30(i) 63(j) 115 101
20 47
101(i) 115 30(p) 63 47 20 (j)
63 115 101
20 30 47 63 101 115
20 47(j) 30 63(i) 115 101
Le tri Fusion (mergesort)

Application de la mthode diviser pour rgner au problme du tri dun
tableau
Le principe est de diviser une table de longueur n en deux tables de
longueur n/2, de trier rcursivement ces deux tables, puis de fusionner
les tables tries.
Complexit en pire cas : O(n
2
) et en meilleur cas : O(n log(n))

92
Algorithmes de tris
Le tri Fusion (mergesort)

Premire phase : Dcoupe :
1. Dcouper le tableau en 2 sous-tableaux gaux ( 1 case prs)
2. Dcouper chaque sous-tableau en 2 sous-tableaux gaux
3. Ainsi de suite, jusqu obtenir des sous-tableaux de taille 1

Deuxime phase : Tri/fusion :
1. Fusionner les sous-tableaux 2 2 de faon obtenir des sous-
tableaux de taille 2 tris
2. Fusionner les sous-tableaux 2 2 de faon obtenir des sous-tableaux
de taille 4 tris
3. Ainsi de suite, jusqu obtenir le tableau entier
93
Algorithmes de tris
Le tri Fusion (mergesort)

Algorithme : FUSION
Donnes : A: tableau [0..n-1] , a, b,c : entier
Variable : i,j,k : entier
A1 : tableau[0b-a] , A2 :tableau [0c-b-1] :entier
dbut
pour i de 0 b-a faire
A1[i] A[a+i]
pour j de 0 c-b-1 faire
A2[j] A[b+1+j]
i 0
j 0
k a
94
Algorithmes de tris
Algorithme : FUSION(suite)
tant que (k <= c) faire
si (i >= b-a) alors
A[k] A2[j]
j j+1
sinon
si (j >= c-b-1) alors
A[k] A1[i] i i+1
sinon
si (A1[i] <= A2[j]) alors
A[k] A1[i] i i+1
sinon
A[k] A2[j] j j+1
finsi
finsi
finsi
k++
fintantque
fin
95
Algorithmes de tris
Le tri Fusion (mergesort)

Algorithme : TRI-FUSION
Donnes : A: tableau [0..n-1] , a, b : entier
dbut
si (b>a) alors
triFusion(A,a,(a+b)/2)
triFusion(A,((a+b)/2)+1,b)
fusion(A,a,(a+b)/2,b)
finsi
fin
96
Algorithmes de tris
Le tri Fusion

Exemple
97
Algorithmes de tris
101 115 30 63 47 20
101 115 30 63 47 20
101 115 30 47 20
63
115 30 20 47
20 47 30 115
20 47 63
30 101 115
20 30 47 63 101 115
La recherche squentielle
A partir dun tableau tri, on parcours ce tableau lment par lment
jusqu trouver le bon lment.

La recherche dichotomique
La recherche dichotomique recherche un lment dans un tableau tri et
retourne lindice dune occurrence de cet lment.
Le principe consiste compare llment cherch celui qui se trouve
au milieu du tableau. Si llment cherch est plus petit, alors continuer la
recherche dans la premire moiti du tableau, sinon dans la seconde
moiti.
Recommencer ce processus sur la moiti et sarrter lorsque lon a
trouv llment, ou lorsque lintervalle de recherche est nul.
98
Algorithmes de tris