L'Algorithmique

7/31/2019 L'Algorithmique

1/120

ABDELKADER BENHARIABDELKADER BENHARIABDELKADER BENHARIABDELKADER BENHARI

LALGORITHMIQUELALGORITHMIQUELALGORITHMIQUELALGORITHMIQUE

The algorithm is the set of rules and techniques that are involved in the definition and design of algorithms,that is to say, systematic process of problem solving to describe the steps to the result. In other words, an

algorithm is a finite and unambiguous instructions to give the answer to a problem.

If the instructions of an algorithm executed one after the other, the algorithm is called sequential if they run

at the same time, it is parallel. If the algorithm operates tasks running on a processor network is calleddistributed algorithm, or distributed.

The word "algorithm" comes from the name of the mathematician Al Khawarizmi (Latinized Algoritmi in the

Middle Ages), which, in the ninth century wrote the first systematic work on the solution of linear andquadratic equations.


2/120

A.BENHARI 2

Table des matires

INTRODUCTION A LALGORITHMIQUE........................................................................................................ 4

- Analyse- Algorithme-

Squelette dun algorithme- Elment de base- Schmas algorithmique

APPLICATION............................................................................................................................................... 13

DEFINITION DES VARIABLES ....................................................................................................................... 14

- Variable destine au calcul- Variable non destine au calcul

ENTREE DE DONNEES DANS LA MACHINE................................................................................................ 15

AFFICHAGE DE RESULTATS ......................................................................................................................... 15

CALCULS........................................................................................................................................................ 15

CONDITIONS................................................................................................................................................. 15

LES STRUCTURES REPETITIVES ................................................................................................................... 16

LES PROCEDURES ET LES FONCTIONS (SOUS-PROGRAMME).................................................................. 19

- Procdure- Fonction

LES CHAINES DE CARACTERES .................................................................................................................... 22

- Dfinition- Concatnation- Conversions- Longueur dune chane- Sous chane dune chane

NOTION DE TABLEAU (OU TABLE OU VECTEUR OU MATRICEARRAY)............................................. 24

- Dfinition- Dclaration du tableau- Mise ltat initial- Recherche de donne dans un tableau

LES METHODES DE TRI USUELLES .............................................................................................................. 28

-

Tri par insertion- Tri par slection- Le tri bulle- Le tri de shell- Tri de shell-Metzner- Tri par vecteur dindice- Tri par monotonie

LA RECURSIVITE........................................................................................................................................... 35

- Dfinition- Principe

LES FICHIERS................................................................................................................................................. 37

- Dfinition


3/120

A.BENHARI 3

- du fichier- Notion denregistrement- Dclaration des fichiers en algorithme- Instruction de manipulation des fichiers- Application sur les fichiers squentiels- Les fichiers accs direct- Les fichiers texte

ALGORITHMES ET STRUCTURE DE DONNEES ........................................................................................... 44

- Les structures arborescentes- Graphes- Problme de la recherche- Problme du tri- Quicksort- Heapsort

ALGORITHMES NUMERIQUES .................................................................................................................... 58

-

Gnralits- Systmes linaires Ax=b : mthodes directes- Factorisation A=LU- Factorisation PA=LU- Factorisation A=BBt: Cholesky- Factorisation A=LDLt: Crout

SYSTEMES LINEAIRES AX=B : METHODES ITERATIVES ............................................................................. 73

- Principe- Mthode Jacobi- Mthode Gauss-Seidel- Mthode de relaxation- Mthodes du gradient

PROBLEMES AU MOINDRES CARRES (LINEAIRE)...................................................................................... 79

- Rgression linaire- Mthode des quations normales

RESOLUTION DES EQUATIONS NON LINEAIRES ....................................................................................... 81

- Mthode de dichotomie- Gnralits- Valeurs propres et vecteurs propres

APPROXIMATION POLYNOMIALE & INTEGRATION NUMERIQUE.......................................................... 85

- Approximations polynomialesQUATIONS DIFFERENTIELLES.................................................................................................................... 89

- Gnralits- Mthode de rsolution numrique- Mthode de Euler- Mthode du dveloppement de Taylor- Mthode de Runge - Kutta

EXERCICES CORRIGES .................................................................................................................................. 92

BIBLIOGRAPHIE......................................................................................................................................... 120


4/120

A.BENHARI 4

LALGORITHMIQUELALGORITHMIQUELALGORITHMIQUELALGORITHMIQUE

I.INTRODUCTION A LALGORITHMIQUE

Quest ce quun algorithme ?"Une suite finie de rgles appliquer dans un ordre dtermin un nombre fini de donnespour arriver, en un nombre fini d'tapes, un certain rsultat, et cela indpendamment desdonnes".Encyclopaedia universalis

I.1. Analyse

DfinitionLa dcomposition dun problme en sous problmes, ensuite des sous problmes en sousproblmes, on arrive ainsi des problmes non dcomposables, ou des tches lmentaires.Ces tches lmentaires ordonnes forment la succession des tapes qui permettent partirdune situation initiale daboutir une situation finale qui reprsente la solution du problmede dpart. Une premire solution peut tre rdige dans un langage non formel (en franaispar exemple), ensuite traduite dans un langage formel (algorithme), partir duquel il est

possible dcrire un programme dans un langage de programmation et de lexcuter sur unemachine.

Dmarche de dcompositionNous allons dtailler un exemple qui montre la dmarche de dcomposition et commentarriver rsoudre un problme sans faire autre chose que de lexprimer par des problmesplus petits.Le problme initial : un individu se trouve devant une voiture et doit la faire dmarrer.

Entrer dans la voiture

Dmarrer la voitureOuvrir la portireMonterFermer la portire

Faire fonctionner la voitureDmarrer la voiture

Mettre la cl dans le contactFaire un quart de tour, les voyants doivent sactiver

Continuer tourner la cl jusqu ce que la voiture mette un bruit indiquantltat de marche normal


5/120

A.BENHARI 5

Appuyer sur la pdale dembrayageEnclencher la premire vitesseDsactiver le frein mainActionner doucement le dmarreur et relcher progressivement lembrayage.

La solution finale est exprime par les tches se trouvant en bas du schma. Cette successionde tches sappelle un algorithme mais il est ici exprim dans un langage non formel.La situation initiale : individu, et voiture ouverte (non verrouille).La situation finale : individu dans la voiture et voiture en tat de marche.

Lalgorithme a besoin de certains renseignements externes pour pouvoir fonctionnercorrectement (voyants, bruit que fait la voitureetc.)La solution est donne dans le cas o il ny a aucun problme, supposons maintenant que lavoiture ne veut pas dmarrer o quune fois dmarre, le conducteur cale ! Que faire ? Il estclair que notre algorithme ne rpond plus la question, et quil faut lamliorer pour quil

marche dans toutes les situations possibles.Nous allons rcrire notre algorithme.Entrer dans la voitureDmarrer la voiture

Ouvrir la portireMonterFermer la portire

Faire fonctionner la voitureDmarrer la voiture

Si le conducteur a la cl alorsTant que la voiture nest pas en tat de fonctionnement normal il fautDbut

Mettre la cl dans le contactFaire un quart de tour, les voyants doivent sactiverContinuer tourner la cl jusqu ce que la voiture mette unbruit indiquant ltat de marche normalSi la voiture ne dmarre pas alorsRetourner la cl dans le sens contraire

Reprendre : Mettre cl dans contactFinAppuyer sur la pdale dembrayageEnclencher la premire vitesseDsactiver le frein mainActionner doucement le dmarreur et relcher progressivementlembrayage.Si la voiture cale alors

Retourner la cl dans le sens contraireReprendre : Mettre cl dans contact

Fin si

Sinon Retourner chercher la cl.


6/120

A.BENHARI 6

Reprendre : Mettre cl dans contactFin si.

Ce nouvel algorithme permet de refaire certaines actions si elles ne fonctionnent pascorrectement.

I.2. Algorithme

DfinitionUn algorithme est rdig dans un pseudo-langage et destin une machine abstraite(virtuelle). Il permet de dcrire formellement toutes les tapes ncessaires qui partir dunesituation initiale, permettent daboutir une situation finale. Cette dernire constitue lasolution qui rsout un problme donn.Le langage algorithmique est prcis, et suit des rgles qui seront dcrites tout au long de cedocument.

Dmarche : Problme, analyse, algorithmePour illustrer la dmarche qui permet dcrire un algorithme nous allons traiter des exemplesconcrets1er exemple : Somme de deux entiersSoit le problme formul dans les termes suivants : crire un algorithme qui calcule la sommede deux entiers, et affiche le rsultat lcran.Le problme ici est simple, il sagit de calculer la somme de 2 entiers. Le problme ne prcisepas o trouver les deux entiers, il est alors possible de supposer que les deux entiers serontdonns par lutilisateur, ce dernier dialogue avec la machine par lintermdiaire du clavier.On dit alors que les deux entiers seront saisis au clavier. Lnonc ne prcise pas non plus que

faire du rsultat, on suppose alors que ce dernier sera affich sur lcran.

Voici le schma qui rsume notre problme.

Figure Erreur ! Il n'y a pas de texte rpondant ce style dans ce document. -1

Deux donnes seront lentre dune bote qui ralise le calcul et fournit en sortie la sommede ces deux donnes.En algorithmique, il est frquent de parler dentre et de sortie.

o Les donnes dun algorithme sont appeles entres : elles sont la base du traitementdes algorithmes.

o Les rsultats dun algorithme sont appels sorties : elles sont le fruit des traitementsfaits par les algorithmes et fournissent une rponse au problme pos.

Donne 2

RsultatCalcul de Somme

Donne 1


7/120

A.BENHARI 7

La bote de la figure Figure Erreur ! Il n'y a pas de texte rpondant ce style dans ce document. -1reprsente ce que nous allons appeler par la suite un processus de calcul. Ce processus raliseun traitement simple, qui est le calcul de Donne 1 + Donne 2. Une fois le rsultat obtenu ilsera affich sur lcran.La totalit du schma est le processus gnral et cest ce quil faut concrtiser par un

algorithme.Pour crire cet algorithme nous avons besoin de :1. Accepter Donne 1 et la stocker,2. Accepter Donne 2 et la stocker,3. Calculer Donne 1 + Donne 2,4. Stocker le rsultat,5. Afficher le rsultat sur lcran.

Nous avons ainsi dcompos le problme comme expliqu dans la section 0, les tchesnumrotes de 1 5 sont en fait lalgorithme crit en langage non formel. Il est possible denoter ici, que chaque problme possde la solution dans sa dcomposition.Nous allons le traduire dans un langage algorithmique formel, et nous expliquerons les

diffrents mots-cls utiliss au fur et mesure.Algorithme SommeVariablesDonne1, Donne2, Rsultat : entierDbut

Ecrire (Donner la donne numro 1 )Lire Donne1Ecrire (Donner la donne numro 2 )Lire Donne2Rsultat = Donne1+Donne2Ecrire (La somme est : Rsultat)

Fin

I.3. Squelette dun algorithmeAlgorithmeNomDeLAlgorithmeVAR//Dclaration de variables manipuls par lalgorithmeDonne1, Donne2, Rsultat : entierDbut

//Corps de lalgorithme constitu par les expressionsFin

Un algorithme est dfini par un entte donnant le nom de lalgorithme, gnralementexplicite. Lentte est suivie par une partie dclarative permettant de dfinir toutes les

donnes qui seront utilises par lalgorithme. Par la suite entre deux mots-cl Dbut et Fin,nous retrouvons le corps de lalgorithme qui sera constitu par les diffrentes expressionspermettant de rsoudre le problme.

I.4. Elments de base

TypesLes types permettent de donner un domaine de dfinition aux objets manipuls par unalgorithme, par exemple des donnes ncessaires pour un calcul seront dfinies dans ledomaine des rels ou des entiers, un message affich sera dfini dans le domaine des

caractres alphanumriquesetc.


8/120

A.BENHARI 8

Il existe 5 types de base en langage algorithmique de programmation :Les entiers : dfinis dans le domaine des entiers naturels et les entiers relatifs.Les relsLes caractres : dfinit tout ce qui est caractre alphanumrique, a .. z , 1 .. 9 ainsi que les caractres spciaux, caractres de ponctuation, etc

Les chanes de caractres : un assemblage de caractres forme une chane.Les boolens : un boolen permet de dfinir une donne qui ne peut prendre quun avaleurentre deux : vrai ou faux, ou bien 0 ou 1.

VariablesLes variables servent dclarer des objets ncessaires au bon fonctionnement dunalgorithme. Les variables doivent tre dfinies avant leur utilisation, en gnral en dessous delentte de lalgorithme dans une partie qui peut tre distingue par le mot cl VAR. Elles sontdfinies grce lun des cinq types de base et peuvent accepter une valeur de dbut appelevaleur initiale.Exemple :

Algorithme Exemple

VARDonne1 : entierDonne2 : entierCar : caractreMessage : Chane de caractresVraiOuFaux : boolen

Dbut// Initialisation des diffrentes variablesCar A

VraiOuFaux

FauxDonne1 10Donne220...Fin

Linitialisation des variables permet de donner ces dernires une premire valeur. Il nestpas interdit de changer cette valeur par la suite que ce soit par lintermdiaire :

o dune autre affectation,o dune expression de calcul,o

dune lecture au clavier.Constantes

Les constantes sont des donnes initialises qui ne changent jamais de valeur pendant toute ladure de lalgorithme. Elles peuvent seulement tre lues, utilises pour un traitement,affiches mais jamais modifies

AlgorithmeCirconfrenceConstantesPI = 3,14VARCirconfrence : rel

Rayon : rel


9/120

A.BENHARI 9

DbutEcrire (Donner le rayon du cercle)Lire RayonCirconfrencePI * (Rayon)Ecrire (La circonfrence de votre cercle est : Circonfrence)

Fin.

Dans cet algorithme PI ne peut qutre utilise telle quelle, elle ne peut pas tre modifiedune faon quelconque.

DclarationLa dclaration sert introduire la donne (variable ou constante)qui sera utilise parlalgorithme. Lors de la dclaration dune donne il est ncessaire de lui donner un type, et ilest parfois possible de lui affecter une valeur de dpart. Pour les constantes, la valeur dedpart est obligatoire.Il existe deux manires de dclarer une variable en pseudo-langage.NomDeLaVariable [: type de la variable]

Ou bien[Type de la variable] NomDeLaVariable Remarque : Il est conseill de garder le mme type de dclaration dans le mme algorithme.Exemples :V1 : entier //Dclaration de V1 de type entierEntier V2 0 //Dclaration de V2 de type entier avec une valeur initiale gale 0Entier V3 //Dclaration de V3 de type entier sans valeur initialeIl est aussi possible de faire des dclarations groupes .Entier V1, V2, V3 // Dclaration de trois variables de type entier par le biais dune mmeinstruction.

InitialisationLinitialisation dune variable revient une affectation dune premire valeur avant touteautre utilisation de cette variable. Les instructions dinitialisation peuvent figurer nimporteo dans lalgorithme, et pas ncessairement au dbut.

OprateursLes oprateurs permettent de modifier des valeurs de donnes lintrieur des expressions.Nous allons distinguer entre trois types doprateurs en algorithmique. Le type dune donnedtermine le type des oprateurs qui peuvent lui tre appliqus.Remarque : certains langages de programmation possdent des oprateurs spciaux.

Oprateurs arithmtiquesLes oprateurs arithmtiques sont tous utiliss en algorithmique pour crire des expressionsarithmtiques pouvant tre affectes des variables numriques. Par exemple pour modifiercertaines valeurs il est ncessaire dutiliser des oprateurs.Remarque : Il est aussi possible dutiliser loprateur + pour modifier des chanes decaractres.+ : permet les additions- : permet les soustractions.* : permet la multiplication

/ : permet la division% ou modulo : le reste de la division entire


10/120

A.BENHARI 10

Oprateurs logiquesLes oprateurs logiques sont utiliss pour affecter ou modifier les valeurs des donnes de typeboolen. Il en existe trois :

o NON : appel Non logique, cest un oprateur unaire,o OU : oprateur binaire appel Ou logique,o ET : oprateur binaire appel Et logique.

Les trois tableaux ci-dessous rsument les tables de vrit des oprateurs logiques :

Et Vrai FauxVrai Vrai FauxFaux Faux Faux

Ou Vrai FauxVrai Vrai VraiFaux Vrai Faux

Non Vrai FauxFaux Vrai

Oprateurs relationnelsLes oprateurs relationnels permettent de comparer des expressions entre elles, le rsultat seraune expression logique : vraie ou fausse. Ces oprateurs peuvent comparer entre les typesnumriques, les types caractres et les types chanes de caractres.=Oprateur Type numrique Type alphanumrique Type chane


11/120

A.BENHARI 11

Les expressions comme nous le verrons plus loin peuvent aussi contenir des appels defonctions, ou constituer des appels de procdure.Les expressions constituent les instructions algorithmiques.

I.5. Schmas algorithmiquesSchma algorithmique simple

AffectationLaffectation est lexpression de base en algorithmique, elle permet dassocier une valeurquelconque une variable de lalgorithme. Il est clair que la valeur doit tre du mme typeque la variable.Laffectation comprend 2 parties spares par le symbole daffectation :

o une partie gauche appele aussi valeur de gauche et constitue par une variable, c'est--dire un objet qui peut prendre une valeur,

o une partie droite ou valeur droite constitue par une expression pouvant trevalue.

VARV1 : entierV2 : relDbut

V1 10.5 // Affectation erroneV1 10 // Affectation correcte, on dit que V1 reoitla valeur 10V232.5 // Affectation correcte, V2 reoit 32.5V210 // Affectation correcte, les rels englobent les entiers naturels

V2

25/2 // Affectation correcte, V2 recevra le rsultat du calcul de 25 divis par 2Fin

Lecture de donnesUne autre manire daccorder des valeurs des variables est de faire ce quon appelle unelecture de donnes. La lecture se fait partir dun dispositif dentre, en loccurrence unclavier. On lappelle aussi saisie ou entre de donnes. Ce procd est utilis chaque foisquune valeur est requise par lalgorithme et que cette valeur ne peut tre donne que parlutilisateur, c'est--dire la personne qui utilise le programme. Bien sr dans un algorithme ilny aura pas de vritable saisie partir du clavier mais seulement une simulation de la saisie.Lalgorithme simule une demande de donne lutilisateur et laccepte pour la stocker dans

une variable.Plus tard, lalgorithme sera traduit par un programme, le programme sera compil et lesinstructions qui seront excutables par une machine demanderont une saisie relle de la partde lutilisateur. Ce dernier devra taper une donne du type requis au clavier et valider sarponse par un retour chariot.La syntaxe permettant de lire une donne est la suivante :Lire NomDeLaVariable

Ecriture de donnesLcriture de donnes permet un autre type dinteraction avec lutilisateur : la sortie de

messages ou de rsultats lattention de ce dernier. Lcriture se fait sur un dispositif de sortietel que lcran ou limprimante par exemple.


12/120

A.BENHARI 12

La syntaxe communment adopte est la suivante :Ecrire Message Ecrire Valeur

Incrmentation

Lincrmentation est une expression particulire qui permet daugmenter la valeur dunevariable dune certaine quantit la fois.V1 V1 + 1V2V2 + 2

DcrmentationLa dcrmentation permet de rduire la valeur dune variable.V1 V1 - 1V2V2 - 2

Schma algorithmique conditionnel

Un schma algorithmique conditionnel donne lalgorithme la possibilit daller dans un sensplutt que dans un autre. Une condition est value, et partir du rsultat de cette valuationun choix est fait.


13/120

A.BENHARI 13

II. Application

Ennonc de EXAM1 : on fait passer un examen des tudiant et lon veut dterminer ceux quisont admis . Il y a 3 matires : math (coef 3), franais (coef 2) et informatique (coef 5).Les notes peuvent aller de 0 20. Il y a admission la condition dobtenir la moyennec'est--dire 10 sur 20.

Ralisation des spcifications :3 matires :

maths 3franais 2informatique 5

notes 0 20

admis = moyenne de 10/20 minimumc'est--dire ajourn pour un total de point = 100

Ralisation dun organigramme de programmation ou ordinogramme

Ralisation de lalgorithmealgo exam1 ()

Dbut

Entre des notes

Calcul le total

Si total >= 100

AdmisAjourn

FIN

Non Oui


14/120

A.BENHARI 14

/* dterminer admis ajourn*//* 0


15/120

A.BENHARI 15

ex :chane (15) phrase.Phrase il y a des nuages

IV. Entre de donnes dans la machinesaisir (nom_variable)

V. Affichage de rsultatsafficher ( libell1 , var1, libell2 , var2, )

VI. CalculsSymbole daffectation

total

math*3 Rgle hirarchique des oprateurs :- puissance : **- multiplication et division : * et /- addition et soustraction : + et

Les parenthse peuvent changer la hirarchie des oprations. Ralisation des oprations dansla parenthse la plus interne.

VII.ConditionsExcution squentielle des instructions des programmes

Attention au parenthsesi (a=8 et b=3 ou (c=5) ou non d


16/120

A.BENHARI 16

VIII. Les structures rptitives

Pour que le programme ne boucle pas indfiniment, il faut continuellement inclure lintrieur de la boucle une instruction capable de modifier la valeur de lexpression test.

Diffrentes faon de programmer une boucle :Lors dun dialogue clavier/cran = question pos loprateurAutres traitement ? (oui/non)

Rponse de loprateur variable = rponse

Analyse du problme : faire n addition de 2 nombrec a + b

tant que rponse = oui si nonfaire

calculer 1 additionautre calcul ? (oui/non)saisir la rponse

fin tant que

prog

Dbut

Calculer 1 addition

(c fois)

fin

Saisie de a et b

Addition

Affichage du rsultat

question


17/120

A.BENHARI 17

Entrez imprativement dans la boucle : rponse oui Entrez conditionnelle dans la boucle suivant oprateur :Afficher (calcul ? (oui/non))

algo rep1()var locales

entier a, b, cchane (3) reponse

dbutafficher ( Voulez-vous faire un calcul ? (oui/non) )saisir (rponse)c a + btant que rponse = oui faire

afficher ( entrez a et b )saisir (a, b)c a + bafficher ( rsultat= , c)afficher ( autre addition ? (oui/non) )saisir (rponse)

fin tant quefin

A laide dune marque de fin de travailalgo rep2()var locales

entier a, b, cdbut

afficher ( Entrez une valeur pour a ou -1 pour terminer.)saisir (a)tant que a -1faire

afficher ( entrez b )saisir (b)c a + b

afficher ( rsultat= , c)afficher ( Entrez a ou -1 pour terminer.)saisir (a)

fin tant quefin


18/120

A.BENHARI 18

a.A laide dun compteurPar incrmentation ou dcrmentation

i.Par dcrmentationalgo rep3()var locales

entier a, b, c, idbut

afficher ( Entrez le nombre daddition faire.)saisir (i)tant que i > 0faire

afficher ( entrez a et b )saisir (a, b)c a + b

afficher ( rsultat= , c)ii-1fin tant que

fin

ii.Par incrmentationalgo rep4()var locales

entier a, b, c, I, cptdbut

afficher ( Nombre daddition.)

saisir (i)cpt0tant que i > 0faire

afficher ( entrez a et b )saisir (a, b)c a + bafficher ( rsultat= , c)cptcpt+1

fin tant quefin


19/120

A.BENHARI 19

IX. Les procdures et les fonctions (sous-programme)

Raison des sous programmes :- rutilisabilit- lisibilit du programme- facilit de maintenance- facilit de mise au point

P1 : entreP2 : entre-sortieP3 : sortie


20/120

A.BENHARI 20

Une fonction ne retourne quune valeur, ses paramtres doivent tre exclusivement dentre(passage par valeur uniquement)

Entre = passage de paramtre par valeurEntre-sortie et sortie : passage par rfrence

Passage par une valeur : on donne au programme une valeur donn


21/120

A.BENHARI 21

a.ProcdureEst un sous ensemble indpendant o faisant partie dun programme principale. Ellecommunique avec des paramtres entre-sortie, sorties.Exemple : soit calcul de la somme de 2 nombres : c a + b

procdure somme (a, b, c)val entier a

val entier bref entier c

dbutca+b

fin

programme principalalgo pp ()var locales

entier x, y, z

dbutafficher ( Entrez une valeur pour x )saisir (x)afficher ( Entrez une valeur pour y )saisir (y)somme (x, y, z)afficher ( Le rsultat est , z)

fin

b.FonctionUne fonction est une sous partie dun programme qui retourne 1 valeur donc une fonctionpossde un type.Elle ne doit possder que des entrs.

Doit contenir la commande retourne (constante, variable, expression arithmtique)

fonction entier fsomme (a,b)


22/120

A.BENHARI 22

val entier aval entier b

var localesentier c

dbut

ca+bretourne (c)fin

dbutretourne (a+b)

fin

programme principalalgo fpp()var locales

entier a, bdbut

afficher ( entrez a et b )

saisir (a,b)afficher ( Rsultat , fsomme (a,b))

fin

X. Les chanes de caractresa.Dfinition

Cest un ensemble de caractres affichable. On utilise un code ISO (ASCII) codant 0 127caractre texte et 128 255 caractres graphiques

- 0 31 caractre de contrle du terminal- 48 57 chiffre- 65 A, B- 97 a, b

caractre alphabtique numrique spciaux

Une chane de caractre = caractre concatn

b.ConcatnationMise bout bout de caractre pour former une chaneMise bout bout de plusieurs chanes

Oprateur de concatnation = +y = il fait chaud // pas de smantiquez = xyaZb2 a = il b = fait c = froid d = chaud e = humide

y = a + b + d


23/120

A.BENHARI 23

c.Conversionsi.Conversions dune chane en entier

Fonction chanant

c 2003 z chainant (c)

d 128 y c + d

y = 2003128

r chainant (d)r = 128

w = z + v

w = 2131a chainant (y)a = 2003128

Si erreurchainant = Za34 retourne 0chainant = 34Za retourne 34

ii.Conversion dun entier en chaneEnt chaine (entier) retourne une chane

d.Longueur dune chaneDfinition de la chanevar locales

chaine (12) a

Longueur effective de la chane= Longueur de lespace utilis

longueur (chaine) retourne un entier

ex : l

longueur (a)

e.Sous chane dune chanez = Il fait chaud temperature milieu (z, 9, 5)temprature = froid

milieu (chaine, num dpart, nombre partir de dpart)


24/120

A.BENHARI 24

XI. Notion de tableau (ou table ou vecteur oumatrice array)a.Dfinition

Un tableau est un ensemble de valeurs de mme type

Types :- prdfinis = entier, rel, logique, caractre, chane- construits = structur, numr

Ex dun tableau dentier1, 3, 5, 2, 8, 7

en variable1 3 5 2 8 7A B C D E F

Tableau t11 3 5 2 8 7 Valeur

Rang dans tableau

t1[3] = 55 est la valeur de llment de rang 3 du tableau t1

1 2

1 1 32 5 23 8 7t1[2ligne,1colone] = 5rang = 2,1

b.Dclaration du tableauvar locales

type nom_tableau [taille] taille = 1er valeur valeur max

Ex : soit un tableau de 50 entiers appel t1entier t1 [1 50]

Soit un tableau de 50 chanes de caractres de 22 caractreschaine (22) t2 [1 50]

i.Tableau 1 dimensionOn peut le considrer comme linaireOn le remplie avec 1 et 1 seul indice(vecteur)Chaque lment est identique

ii.Tableau 2 dimensions, 3, n


25/120

A.BENHARI 25

On peut considrer quil sagit dune nature contenant l lignes et c colones

var localestype nom_tableau [ [1l], [1 c] ]

exemple 3 dimensionsentier t1 [ [1 m], [1l], [1 c] ]ensemble de matrice

Du plus haut niveau au plus bas niveau

c.Mise ltat initialMettre les donnes dans un tableau correspond au chargement des donnes dans le tableau.RAZ, RAB, VRAI / FAUX

- Transfert de variables- Transfert dautre tableau- Saisie- Donns de fichiers

Exemple de saisiealgo saisie ()var locales

entier t1 [[1..5], [1..3]], l, c

dbut /* -1 pour fin*/afficher ( entrez un numro de ligne )

saisir (l)tant que l -1faire

afficher ( entrez un numro de colone )saisir (c)afficher ( entrez une valeur pour , l, c)saisir (t1[l,c])afficher ( Entrez un numro de ligne ou -1 pour quitter

fin tant quefin

Exemple de fonction avec passage de tableaufonction entier TOTO (t1[], n)ref entier t1 [1..n]val entier n

d.Recherche de donne dans un tableaui.Recherche par le rang

Ex : afficher (t1 [3])

ii.Recherche squentielle1.Sans erreur possible


26/120

A.BENHARI 26

C'est--dire lment cherch se trouve toujours dans le tableau

2.Avec erreur possibleEn italique dans sch prcdent.t1 (0,1)t1 (0,1)

procdure rechseq (t1 [], n atrouve)ref entier t1[1..n]val entier nval entier atrouvervar locales

entier ilogique trouve

dbut

trouve

fauxi1tant que (i


27/120

A.BENHARI 27

PrincipeSoit un tableau dune suite de 8 nombres.3 5 8 12 15 27 43 751 2 3 4 5 6 7 8

Chercher 15indice mini = 1indice maxi = 8indice mil = (mini + maxi) /2 =4

trouve = 12indice mini mil +1indice mil 6

trouve = 27indice maximil - 1

indice mil (5+5) / 2 = 5

procdure dichotomie (t1[], n, cherche, trouve, rang)ref entier t1[1..n]val entier nval entier chercheref logique trouveref entier rang

var localesentier mini, maxi, mil

dbutmini 1maxi nmil (mini + maxi) / 2tant que mini


28/120

A.BENHARI 28

sinonmini mil + 1

finsimil (mini + maxi) / 2fin tant que

si t1[mil] = cherchealorstrouve vrairang milsinontrouve fauxfinsi

fin

XII.Les mthodes de tri usuellesa.Tri par insertion

i.Principe18 5 12 17 14 31 81 2 3 4 5 6 7

Comparer un lment au suivant de la liste si cet lment une valeur infrieur, il reste enplace sinon il est chang avec celui qui est de valeur infrieur, il sagit donc pour chaquelment du tableau de lui mnager une petite place parmi ceux qui sont dj tri en dcalantvers le haut ceux qui sont plus grand que tri.

ii.Algorithmeprocdure tri insre (tab [], n)rf TIND tab [1..n] TIND correspond un type indterminvaleur entier nvar locales

entier i,jTIND temp

logique fin

dbuti 2tant que i


29/120

A.BENHARI 29

tant que (j > 0) et (fin = faux)faire

si temp < tab [j]alors

tab [j+1] tab [j]

j j 1sinonfin vrai

finfin tant quetab [j+1] tempi i+1

fin tant quefin

b.Tri par slectioni.Principe

A chaque itration, on choisi le plue petit lment parmi ceux quil reste trier et on le met sa place.

ii.Algorithmeprocdure trislection (tab [], n)ref TIND tab [1..n]val entier n

var localesTIND petitentier i, ipetit, j

dbuti 1tant que i < nfaire

ipetit ipetit tab [ipetit]

j i+1tant que j


30/120

A.BENHARI 30

iii.RemarqueCette mthode conduit peu de dcalage. Elle est pourtant moins rapide que la prcdente.

c.Le tribullei.Principe

On parcoure le tableau autant de fois quil le faut en comparant les lments qui se suivent eten les changeant sils ne sont pas dans le bonne ordre. A chaque passage, on peut enlever 1 n puisque lon trouve le dernier du tableau trier.

ii.Algorithmeprocdure triballe (tab [], n)ref TIND tab [1..n]val entier nvar locales

logique finentier iTIND petit

dbutfin fauxtant que fin = fauxfaire

fin vraii1tant que i < nfaire

si tab [i] > tab [i+1]alors

petit tab [i+1]tab [i+1] tab [i]tab [i] petitfin faux

finsii i+1

fin tant quen n 1

fin tant quefin

iii.CommentaireLun des plus mauvais trie si les donnes sont trs disperses par contre, il peut trs bienconvenir pour remettre en ordre des donnes peu tris.

d.Le tri de shelli.Principe


31/120

A.BENHARI 31

Pour limiter les dplacements , on choisi de comparer des lments du tableau dans desparties de tableau. On choisi au dpart des parties dun pas gale la moiti de la taille dutableau, chaque lments de la premire moiti est compar un lment de la seconde. Silne sont pas dans le bonne ordre, ils sont chang puis on diminue le pas en continuant comparer des lments dont la distance est gale au pas. De cette faon, les lments traits

sont dabord des sauts important puis de plus en plus petit jusqu ce que le pas soit gale 1.

ii.Algorithmeh n/2tant que h >=1faire

fin vraii1tant que i tab [i+h]alors

petit tab [i+h]tab [i+h] tab [i]tab [i] petitfin faux

finsii i+1

fin tant quesi fin = vraialors

h h/2fin si

fintantque

iii.RemarqueMthode plus efficace que la prcdente dans les cas dune grande dispersion.

e.Tri de shell-Metzneri.Principe

Mme principe que pour le shell, au lieu d utiliser , le triballe, on choisi le tri par insertion( i+1 chang par i +h).

ii.Algorithmehn/2tant que h>=1faire

ih+1tant que i= 1


32/120

A.BENHARI 32

fairea[j+h]a[j]

jj-hfin tantii+1

fin tanthh/2fin tant

iii.RemarqueTri rput plus rapide que tous les prcdant

f.Tri par vecteur dindicei.Principe

Mthode ne manipulant pas directement les lments du tableau mais utilisation dun vecteurdindice qui joue le rle de pointeur

Ex :Avant triTab50 2 25 -30 45 11 2 3 4 5 6

Indice1 2 3 4 5 61 2 3 4 5 6

Aprs tri

Tab50 2 25 -30 45 11 2 3 4 5 6

Indice4 6 2 3 5 11 2 3 4 5 6

Rsultat : -30, 1, 2, 25, 45, 50

ii.Algorithme(Avec tri par slection)

ideb1tant que ieb


33/120

A.BENHARI 33

aux indice [min]indice [imin] indice [ideb]indice [ideb] aux

finsik k+1

fin tantideb ideb +1fin tant

iii.RemarqueCette mthode est trs intressante pour manipuler des fichiers de grande taille, on peut doncles trier sans dplacer lordonne.

g.Tri par monotoniei.Principe

On part du constat que dans toute suite de nombre entier tri au hasard, on a toujours un

certain nombre dentre eux tri naturellement.

On appelle monotonie, une suite de nombre naturellement tri ?Exemple :

ii.Algorithmeprocedure separation (tab1[], tab2[], tab3[], i1,i2, i3)ref TIND tab1 [1..i1], tab2 [1..i2], tab3 [1..i3]ref entier i2, i3val entier i1

var localesentier ecrit, i

dbutecrit 2i 1i2 1


34/120

A.BENHARI 34

i3 0tab2[i2] tab1[1]

tant que i


35/120

A.BENHARI 35

si k


36/120

A.BENHARI 36

1 instant tn ! = (n-1) ! * n0 !=1

fonction entier facto (n)val entier ndbut

si n=0alors

retoune (1)sinon

retourne (facto(n-1)*n)finsi

fin

algo factorielle ()var locales

entier ndbut

afficher ( Quelle factorielle ? )saisir (n)afficher ( La valeur est ,facto(n))

fin

En C++

int facto (int n){

if (n==0)return (1)

elsereturn (facto (n-1)*n)

endif}

Ex 2: soit la somme des n premiers nombres entiersfonction entier somme (n)val entier ndbut

si n = 0alors

retoune0sinon

retourne (somme (n-1) +n)finsi

fin


37/120

A.BENHARI 37

Ex 3 : crire une procdure rcursive qui affiche tous les lments dun tableau dentier danslordre croissant de leur indice.

procedure ecrivect (V[], n, i)val entier V[i..n]val entier i,n

dbutsi i


38/120

A.BENHARI 38

Transfert logique

En mmoire centrale, 3 zones de travail ou BUFFERS qui ralise les entre, sortie et travail.

c.Dclaration des fichiers en algorithmePour viter les problmes de recopie, nous dclarons les types de fichiers au niveau globalEX : Soit dclarer un fichier client qui contient un numclient 1 nom, 1 adresse, 1 solde decompte.

typestypes struct

entier numroclientchaine (30) nomchaine (80) adressereel solde

fstruct CLIENT

Aprs dclaration des bibliothque (#iostream.h)

var globaleCLIENT ennrcli /*dclaration dun buffer*/FICHIER (client) ficli /*dclaration dun fichier construit sur la structure CLIENT*/

ficli est un nom logique


39/120

A.BENHARI 39

d.Instruction de manipulation des fichiers- Ouverture- Lecture/ criture/ suppression

i.Ouverture, fermeture1.Ouverture

OUVRE (nom_fichier_logique, nom-fichier_physique , mode_douverture)

nom_fichier_logique : nom pour le programme.

nom-fichier_physique : nom connu pour le systme dexploitation.mode_douverture :- lecture- criture- Mise Jour (MAJ) {lecture/criture}- Extension {aprs fin de fichier}

Fonction :- En ouverture : vrifier que le fichier existe, rserver ensuite un buffer.- Ouverture en criture : cr le fichier ou lcraser sil existe dj- En MAJ : modifier directement chaque enregistrement- En extension : on efface la fin de fichier actuelle pour enregistrer des donnes lasuite de celle qui existe dj.

En algo, on peut utiliser une primitive (fonction) systme qui est fdef (fin de fichier ;fdef(nom de fichier))

2.Fermeturefermer (nom de fichier logique)Libre le buffer cr louverture en criture, enregistrer sur le disque le dernier contenu du

tampon.

ii.Lecture, criture, suppressionLecture lire (nom fichier logique, nom du buffer)Ecriture ecrire (nom fichier logique, nom du buffer)

Remarque :Encli.nom donne du buffer toujours nomm par le prsence du nom du buffer avant lenom de la donne spar dun point.


40/120

A.BENHARI 40

e.Application sur les fichiers squentielsi.Soit imprimer le contenu dun fichier sur

imprimanteFichier physique : FiphyFichier logique : fientr

typestype struct

chaine (25) nomentier nucli

fstruct CLIENT

var globalesCLIENT enrcliFICHIER (CLIENT) fientrchaine (25) snomentier snucli

algo lecseq ()dbut

ouvre (fientr, Fiphy , lecture)

lire (fientr, enrcli)tant que non fdef (fientr)faire

snom enrcli.nomsnucli enrcli.nucliimprimer ( , snom , , snucli)

fintantferme (fientr)

fin

ii.RemarqueLe fichier dentr ne doit pas tre cr partir de lditeur de texte mais laide dunprogramme de cration.


41/120

A.BENHARI 41

iii.Cration dun fichier squentieltypes

type structchaine (25) nomentier nucli

fstruct CLIENT

var globalesCLIENT enrcliFICHIER (CLIENT) fisor

chaine (25) tnomentier tnucli

algo ecriseq ()dbut

ouvre (fisor, Fiphy , ecriture)afficher ( entrez un nom ou fin )saisir (tnom)tant que tnom fin faire

enrcli.nom tnomafficher ( entrez un numro )saisir (tnucli)enrcli.nucli tnuclicrire (fisor, enrcli)afficher ( entrez un nom ou fin )saisir (tnom)

fintantferme (fisor)

fin

f.Les fichiers accs directSachant que les supports externes tel que les disques magntiques sont adressable, on va lesutiliser pour retrouver directement des donnes

Remarque : random (ang) = alatoire ou au hasard

Dans tous les cas il faut crer une correspondance entre une des informations delenregistrement et le rang de stockage de lenregistrement sur le support externe.

Algorithme de gnration automatique dadresse ou correspondance direct.

Ex : Correspondance direct, rang identifiant externe


42/120

A.BENHARI 42

Exemple = numro tudiant = rang de stockage sur le disque

i.Lecture accs directetypes


fstruct CLIENT

var globalesCLIENT enrcliFICHIER (CLIENT) filogcli

chaine (25) snomentier snucli, rang

algo lecdir ()dbut

ouvre (filogcli, Fiphy , lecture)afficher ( entrez un numro de client ou 0 pour fin )saisir (rang)tant que rang 0faire

positionner (filogcli, rang)lire (filogcli, eurcli)snom enrcli.nomstnucli enrcli.nucliafficher ( Nom du client : , snom)afficher ( Numro du client : snucli)afficher ( entrez un numro de client ou 0 pour fin )saisir (rang)

fintantferme (filogcli)

fin

ii.Cration a accs directtypes


fstruct CLIENT

var globalesCLIENT enrcliFICHIER (CLIENT) filogcli

chaine (25) tnomentier tnucli, rang


43/120

A.BENHARI 43

algo ecridir ()dbut

ouvre (filogcli, Fiphy , ecriture)afficher ( entrez un numro de client ou 0 pour fin )

saisir (rang)tant que rang 0faire

afficher ( Entrez nom du client )saisir (tnom)enrcli.nom tnomenrcli.nucli rangpositionner (filogcli, rang)ecrire (filogcli, enrcliafficher ( entrez un numro de client ou 0 pour fin )saisir (rang)

fintantferme (filogcli)

fin

g.Les fichiers textei.Dfinition

Fichier dont les composantes sont des caractresTEXTE fitext

On la particularit dtre divis en ligne dont la fin est indiquer par un caractre spciale en

gnral ce caractre et le caractre CR (caracter return).Un fichier texte fait les conversions de formats de donnes. Les transferts se fond par lesnoms de variables et non pas par structure complte. Les entres sorties standards sontgnralement de ce type (saisir, afficher, imprimer).

Remarque : un fichier texte peut tre cr partir de lditeur de texte

ii.Dclaration dun fichier textevarTEXTE nom_du_fichier_texte (logique)

iii.Action sur un fichier texte1.Ouverture de fichier

ouvre_text (nom_logique, nom_physique , mode douverture)

2.Transfert de donnesa.Lecture

lire_text (nom_logique, arg1, arg2 )

b.Ecriture


44/120

A.BENHARI 44

ecrire_text (nom_logique, arg1, arg2 )

3.Fermetureferme_text (nom_logique)

XV.Algorithmes et structure de donnes

a. Les structures arborescentesUn arbre est un ensemble dlments appels nuds ou sommets organiss de manire hirarchique partir dunnud distingu appel racine. On repre les nuds de larbre en leur donnant des noms diffrents.

i. Arbres binairesUn arbre binaire est soit vide, not , soit de la forme < r, B1, B2 > o r est la racine et o B1 et B2 sont desarbres binaires.

On dfinit intuitivement les notions de sous-arbre, de sous-arbre gauche, de fils gauche, de lien gauche et

rciproquement droite. On dfinit encore les notions depre, defrre, dascendantet de descendant. Lesnuds dun arbre binaire ont au plus deux fils. Un nud interne ou double a 2 fils. Unpoint simple gauche aseulement un fils gauche, et rciproquement droite. Un nud externe ou feuille na pas de fils. De faongnralise, on qualifie de nud interne, tout nud qui nest pas externe. On appelle les branches de larbre toutchemin (suite conscutive de nuds) allant de la racine une feuille. Il y a autant de branches que de feuilles. Lebord gauche est le chemin issu de la racine en suivant les liens gauches, et rciproquement droite.

Les caractristiques dun arbre sont :- la taille de larbre est le nombre total de nuds. - la hauteur ou niveau dun nud x est le nombre de lien sur lunique chemin allant de la racine x,

note h(x).

- la hauteur ou profondeur de larbre A, ( ) ( ){ }xhAhx

max= .

- la longueur de cheminement de larbre A, ( ) ( ) ( ) ( )ALCIALCExhALCx

+== avecLCE

la longueur de cheminement extrieure ( )feuillex

xh etLCI la longueur de cheminement intrieure

( )internenoeudx

xh .

- la profondeur moyenne externe deA est ( ) ( )feuillesdenombre

ALCEAPE = .

On donne la signature du type abstrait arbre binaire :

sorte arbreutilise nudoprations

r

B1 B2


45/120

A.BENHARI 45

: arbre< , , > : nud x arbre x arbre arbreracine : arbre nudgauche : arbre arbredroit : arbre arbre.

Proposition : Soit un arbre binaire de taille n, de profondeurp et possdantf feuilles. Si on examine les casextrmes, on obtient que ( ) 1log2 npn ; par ailleurs

pf 2 do ( ) fp 2log .

Reprsentation des arbres en machines : On utilise la structure rcursive des arbres.1) Dans cette premire reprsentation, le chanage est symbolis par des pointeurs.type arbre = adresse de nud ;type nud = structure

val : lment ;g, d : arbre ;fin ;

1.2. Larbre est dtermin par ladresse de la racine. On gre la mmoire dynamiquement pour les oprations desuppression / insertion.

2) Dans la reprsentation contigu, on simule les chanages par des indices dans un tableau.type arbre = tableau de 1 N de

structureval : lment ;g, d : entier ;fin ;

3.4. On utilise lindice 0 pour indiquer quil ny a pas de fils. Larbre est dtermin par une variable entirecontenant lindice de la racine. On va grer les cases libres pour des insertions / suppressions. On chane les

cases libres comme une pile, en utilisant le chanage g et on utilise une variable entire libre pour indiquerlindice du sommet de pile .

ii. Arbres binaires completsUn arbre binaire est completsi tous les nuds qui ne sont pas des feuilles ont 2 fils.

Propositions : Un arbre binaire complet ayant n nuds internes possde en tout n+1 feuilles. La dmonstrationse fait simplement par rcurrence. Par ailleurs, on montre quil existe une bijection entre lensemble des arbresbinaires de tailles n,Bn, et lensemble des arbres binaires complets de taille 2n+1,BC2n+1. Principe : on ajoute

des feuilles de sorte que tout nud de larbre ait deux fils. De plus on tablit quen

nnn Cn

BCB 212 1

1

+== + .

iii. Arbres binaires parfaits, ordre hirarchiqueOn dit quun arbre binaire estparfaitsi toutes ses feuilles sont situes sur les deux derniers niveau, lavantdernier tant complet, et les feuilles du dernier sont le plus gauche possible. Attention ! un arbre binaire parfaitnest pas forcment complet, mais il a toujours au plus un nud simple (le pre de la feuille la plus droite).

On peut reprsenter un arbre binaire parfait de taille n de manire compacte par un tableau n cases. Ceci se faiten numrotant les nuds de 1 n en partant de la racine, niveau par niveau de gauche droite (ordrehirarchique). On a les relation gnrales suivantes :

- le pre du nud dindice i est lindice i / 2 (division entire) ;- le fils gauche dun nud i est, sil existe, lindice 2i ;- le fils droit dun nud i est, sil existe, lindice 2i+1 ;- les feuilles sont aux indices > n / 2.


46/120

A.BENHARI 46

iv. Parcours en profondeur dun arbre binaireOn considre lopration deparcours qui consiste examiner systmatiquement dans un certain ordre tous lesnuds de larbres pour effectuer un traitement de donnes. Le parcours en profondeur gauche consiste partirde la racine et tourner autour de larbre en allant toujours le plus gauche possible.

Procdure Parcours(A : arbre) ;

dbutSi A =

Alors T0Sinondbut

T1 ;Parcours(g(A)) ;

T2 ;Parcours(d(A)) ;T3 ;

fin ;fin ;

Chaque nud est visit trois fois. A chaque visite correspond un traitement Ti et un ordre de parcours. T1seffectue avant la descente gauche et dcrit lordre prfixe oupr-ordre. T2 seffectue aprs la remonte gaucheet avant la remonte droite, lordre associ est lordre infixe ou symtrique. Le traitement T3 est ralis aprs laremonte droite ; les nuds sont parcourus dans lordre suffixe oupost-fixe.On ajoute un traitement particulierT0 pour les nuds vides.

v. Arbres gnrauxUn arbre gnral, ou simplement arbre, est une structure arborescente o le nombre de fils nest plus limit 2.Un arbre A = < r, A1, A2, , An > est la donne dune racine r et dune suite ventuellement vide de sous-arbresdisjoints. Cette suite est unefort. Un arbre est obtenu en rajoutant un nud racine la fort.

On donne la signature des arbres gnraux :

sorte arbre, fortutilise nudoprations

cons : nud x fortarbreracine : arbre nudsous-arbre : arbre fort : fortime : fort x entierarbrelongueur : fortentierinsrer : fort x entier x arbre fort

Il ny a plus de notion de fils gauche ou de fils droit. On parle du ime fils dun nud.

Dans un parcours gauche, chaque nud est rencontr une fois de plus que son nombre de fils.

Procdure Parcours(A : arbre) ;dbutSi sous-arbre(A) =

Alors T0Sinon

dbuti 1 ;Rpter

Ti ;Parcours(ime(sous-arbre(A), i)) ;i++ ;

Jusqu ce que i > longueur(sous-arbre(A)) ;


47/120

A.BENHARI 47

Ti ;fin ;

fin ;

Lordreprfixe sur les nuds est obtenu en ne faisant quintervenir que T 1. Lordre suffixe est obtenu en nefaisant intervenir que Ti lextrieur de la boucle. Il ny a pas dordre infixe.

Reprsentation des arbres : On reprsente un arbre gnral par des listes chanes dynamiques.

type arbre = adresse de nud ;type nud = structure

val : lment ;premier_fils, frre : arbre ;fin ;

Propositions : Le nombre darbres gnraux de taille n+1 estn

nCn

21

1

+. Par ailleurs, il existe des bijections

entre les forts de taille n, les arbres gnraux de taille n+1, et les arbres binaires de taille n, avec des propritsintressantes sur les parcours.

b. Graphes

i. DfinitionUn graphe est un ensemble dobjets modliss par des sommets, et mis en relation (binaire). Ces relations sont

modliss par des arcs ou des artes. Un graphe orient[non orient] est un couple ASG ,= o S est unensemble fini de sommets, et A un ensemble de paire ordonnes [couple] de sommets appels arcs [artes].

ii. TerminologieUn graphe simple est sans boucle1, et sans liens multiples. Dans un graphe orient, on dit quey est le successeurdex sil existe un arc qui mne dex versy ; on dit en outre quey est adjacentx. Pour un graphe orient, on ditsimplement quex ety sont adjacents. Un graphe est dit completsi pour tout couple de sommet il existe un arc(ou une arte) les joignant. Dans un graphe orient, le demi-degr extrieur[intrieur] dun sommetx, que lon

note ( )xd+ [ ( )xd ], est le nombre darcs ayantx comme extrmit initiale (finale). Le degrdex est

( ) ( ) ( )xdxdxd + += . Pour un graphe non orient, on dfinit uniquement le degrdun sommetx ( )xd .

Dans un graphe orient, on appelle chemin de longueurL une suite deL+1 sommets ( )Lsss L10 , telles que

( )1, +ii ss forme un arc. Pour un graphe non orient, on parle de chane. Dans un graphe orient [non orient],un chemin [une chane] dont tous les arcs [artes] sont distincts et tels que les sommets aux extrmits concidentest un circuit[un cycle]. Un graphe orient estfortement connexe si pour toute paire de sommets distincts s et s,il existe un chemin de s vers s et un chemin de s vers s. Un graphe non orient est connexe, si pour toute pairede sommets distincts, il existe une chane les joignant. Une composante fortement connexe [connexe] est un

sous-graphe fortement connexe [connexe] maximal.

iii. Graphe et ArbreEn thorie des graphes, un arbre est un graphe non orient, connexe et sans cycle. Soit G un graphe orient, onappelle racine de G un sommet rtel que, pour tous sommetsx distincts de r, il existe un chemin de rversx. Unearborescence est un graphe orient G admettant une racine et tel que le graphe obtenu partir de G en enlevantlorientation soit un arbre.

iv. Signature graphe orient

sorte sommetutilise boolen, entier

1 lien dun sommet sur lui-mme


48/120

A.BENHARI 48

oprationss : entiersommetn : sommetentier arc : sommet x sommetboolend+ : sommetentierime_succ : sommet x entiersommet

prem_succ : sommetsommetsucc_suivant : sommet x sommetsommet

Pour les graphes non orients, on dispose de la mme signature en remplaant arc par arte et d+ par d.

v. Reprsentation des graphesOn aura deux possibilits classiques de gestion de la mmoire : contiguet chane.

Reprsentation contigu: Soit n le nombre de sommet dun graphe ; on dfinit la matrice dincidence de

dimension n x n not G et tel que [ ] vraijiG =, ssi il existe un arc de i versj. Si le graphe est non orient lamatrice dincidence est symtrique.

type graphe = tableau[1 n, 1 n] de boolen.

La complexit en espace est en O(n), parcourir les successeurs dun sommet se fait en O(n), savoir siy est lesuccesseur dex se fait en O(1).

Reprsentation chane : Pour chaque sommet si, on forme la liste dadjacence, qui est la liste chane de tous lesuccesseur de si.

type graphe = tableau[1 n] dadresse de cellule;cellule = structurenumro : entier de 1 n;

suivant : adresse de cellule;fin;

Soit ( ) +=x

xdA . La complexit en espace est en n + 2p. Le parcours des successeurs dun sommet

seffectue en ( )( )xdO + . La consultation complte est en ( )AO . Savoir siy est le successeur dex se fait en( )( )xdO + , dans le pire des cas.

Remarque. Le chanage peut tre simul dans un tableau. Pour un graphe non orient, il y a redondance 2dinformation.

vi. Parcours en profondeur dun graphe orientLe parcours en profondeurun parcours rcursif, simulable par unepile.Principe : On utilise une marque (vecteur de n boolens) pour marquer les sommets au fur et mesure quon lesrencontre. A partir dunx de dpart, non marqu, on avance dans le graphe en allant toujours vers un nouveausuccesseur non marqu ; les sommets retenus chaque fois sont marqus. Quand on ne peut plus avancer, onrevient au choix prcdent, et on itre la mthode.

Procdure Profondeur(x : sommet) ;dbuti n(x) ;marque[i]vrai ;pour j de 1 d+(x) faire

dbuty ime_succ(x, j) ;

k

n(y) ;

2 y est le successeur de x et rciproquement


49/120

A.BENHARI 49

si non marque[k] alors Profondeur(y) ;fin ;

fin_Profondeur ;

Programme principaldbut

pour i de 1 n faire marque[i] faux ;pour i de 1 n fairesi non marque[i] alors profondeur(s(i)) ;

fin.

5. Pour les graphes non orients, on dispose du mme algorithme en remplaant d+(x) par d.Les sommets ne sont marqus quune seule fois et lalgorithme parcourt un fois et une seule les listes

dadjacence : complexit en ( ) +x

xd , ce qui donne ( )AO pour les listes dadjacence et ( )nO pour les

matrices dadjacence.

On considre les arcsx y tels que Profondeur(x) appelle Profondeur(y). Ces arcs couvrants constituent unefort couvrante constitue darborescences disjointes et dont les racines sont les sommets de dpart. Les graphesobtenu sans orientation sont des arbres (graphe non orient, connexe et sans cycle). Lafort couvrante a autantdarbres recouvrants quil y a de composantes connexes dans le graphe. Ainsi le parcours en profondeur rsoutle test de connexit en temps linaire.

vii. Parcours en largeurLeparcours par largeur ou par niveau est un parcours itratif qui fonctionne avec unefile.Principe : On part dun sommetx et on visite tous les successeursy dex ; on ritre lalgorithme sur les sommetsy dans lordre o on les a rencontrs partir de x. On utilise toujours une marque de sommets. On utilise une filepour grer ce parcours par niveaux.

Procdure Largeur(x :sommet)

dbutfile_vide(file) ;i n(x) ;marque[i] vraie ;ajouter(file, x) ;tant que non est_vide(file) faire

dbuty premier(file) ;

retirer(file) ;pour i de 1 d+(y) faire

dbutz ime_succ(y,i) ;j n(z);

si non marque[j] alorsdbutmarque[j] vraie;ajouter(file,z);fin;

fin ;fin ;

fin ;

Programme principaldbutpour i de 1 n faire marque[i] faux ;

pour i de 1 n fairesi non marque[i] alors Largeur(s(i)) ;


50/120

A.BENHARI 50

fin.

On a la mme complexit que pour le parcours en profondeur. Lalgorithme pour un graphe non orient sobtientsimplement en remplaant d+ par d. On a la mme proprit sur la fort couvrante et les composantes connexesque pour le parcours en profondeur.

c. Problme de la recherchei. Introduction

Considrons un ensemble de grande taille ayant des caractristiques communes. On veut faire de manireoptimise des oprations de recherche, dadjonction et de suppression. A chaque lment, on associe une clsimple (critre unique) : recherche associative. Les bases de donnes traitent des critres plus gnraux et descls multiples.

Signature

sorte ensembleutilise lment, clefoprations

cl : lmentclefvide : ensembleajouter : lment x ensemble ensemblesupprimer : clef x ensemble ensemble_ _ : clef x ensemble boolen

Remarques :- Si plusieurs lments ont la mme cl, la recherche fournit une solution quelconque parmi les

possibilits ; sil ny a pas de solutions (chec), on fournit une valeur spciale.- La suppression commence par une recherche, en cas dchec de la recherche, la suppression laisse

lensemble inchang.

-

En gnral, et sil ny a pas ambigut, on confond llment et sa cl.La complexit fondamentale est celle de la comparaison entre deux cls. Si lensemble des cls est muni dunerelation dordre, on peut les trieravec des algorithmes efficaces. On distingue les mthodes de recherchesquentielle, les mthodes de recherche dichotomique, de hachage, et les mthodes arborescentes.

ii. Arbres binaires de rechercheOn reprsente un ensemble ordonn n lments par un arbre binaire n nuds (les nuds sont les lments), etcest la comparaison avec la valeur dun nud qui va orienter la suite de la recherche.Un arbre binaire de recherche est un arbre binaire tel que pour tout nud x , les nuds de son sous arbre-gauchesils en existent ont des valeurs infrieures ou gales celle de x, et les nuds de son sous arbre-droit des valeursstrictement suprieures ;

6.

ce que lon traduit par g(A) racine(A) < d(A).

On obtient toujours lensemble ordonn par un parcours rcursif gauche symtrique. Il ny a pas unicit de lareprsentation.

x

x >x


51/120

A.BENHARI 51

iii. Recherche dun lment

rechercher : valeurarbreboolen

On compare llment la valeur de la racine :

- galit succsx = r rechercher (x , < r , g , d > ) = vraie7.- si le sous-arbre slectionn est vide, llment est absent checrechercher ( x , ) = faux

- si la valeur est plus petite, on recommence rcurcivement dans le sous-arbre gauche ; etrciproquement si la valeur est plus grande dans le sous-arbre droit

x < r rechercher (x , < r , g , d > ) = rechercher (x , g )

x > r

rechercher (x , < r , g , d > ) = rechercher (x , d )

Complexit: La complexit au pire est en O ( hauteur de larbre ).

iv. Adjonction dun lment aux feuilles

ajout_feuille : arbre valeurarbre

Ladjonction aux feuilles dun lment se ralise en deux tapes :- tape de recherche pour savoir o insrer le nouvel lment ;- adjonction elle-mme.

On compare la valeur de llment ajouter celle de la racine pour dterminer si on lajoute sur le sous-arbregauche ou droit.

x r ajout_feuille ( < r , g , d > , x ) = < r , ajout_feuille ( g , x ) , d >x > r ajout_feuille ( < r , g , d > , x ) = < r , g , ajout_feuille ( d , x ) >

Le dernier appel rcursif se fait sur un arbre vide ; on cre un nouveau nud cette place pour le nouvel lmentqui devient donc une feuille.

ajout_feuille ( , x ) = < x , , >

8. On peut construire un arbre binaire de recherche par adjonctions successives aux feuilles.9.On donne lalgorithme dadjonction aux feuilles (rcursif) en LDA :

Fonction adjonction_feuille (A : arbre , e : entier ) : arbredbutsi est_vide(A)

alors retourner < e , , >

sinon si ( e racine(A) )retourner < racine(A) , ajout_feuille( g(A) , e ) , d(A) >

sinonretourner < racine(A) ,g(A) , ajout_feuille( d(A) , e ) >

fin10.11. On donne galement une version itrative de lalgorithme ( voire td).12.13. La complexitdun adjonction est O ( hauteur de larbre ).


52/120

A.BENHARI 52

v. Adjonction dun lment la racineSoit A un arbre binaire de recherche, on veut ajouterx la racine.

On procde en deux tapes :- on coupe A en deux arbres binaires de recherche G et D contenant respectivement tous leslments x et tous ceux > x.

- construire larbre < x , G , D > voire cours

vi. Suppression dun lment

supprimer : arbre valeurarbre

- recherche de llment supprimer-

suppression qui dpend de la place de llment, selon que le nud est sans fils, avec un seul fils,ou avec deux fils. La suppression dun nud sans fils est immdiate. Pour la suppression un nud avec unseul fils, on remplace ce nud par son fils. Pour un nud, avec deux fils, on dispose de deux solutions : soiton remplace le nud supprimer par le plus grand lment de son sous-arbre gauche, soit on le remplacepar le plus petit lment de son sous-arbre droit.

On donne lalgorithme de suppression en LDA :14.

Fonction suppression ( A : arbre , e : entier ) : arbredbut% recherche de llment supprimer %si est_vide(A)

alors retourner erreur

si ( e < racine(A) )alors retourner < racine(A), suppression( g(A) , e ) , d(A) )sinon si ( e > racine(A) )

retourner < racine(A), g(A) , suppression( d(A) , e ) )% suppression %sinon

si est_feuille(A)

alors retournersinon si est_vide(g(A))

retourner d(A)sinon si est_vide(d(A))

retourner g(A)sinon

% on ajoute llment le plus droite du sous-arbre gauche %retourner < max_noeud(g(A)) , retire_max(g(A)), d(A) >

fin

Fonction max_noeud ( A : arbre ) : entier% retourne le plus grand lment de larbre A, le plus droite %dbutsi est_vide(d(A))

alors retourner racine(A)sinon

retourner max(d(A))fin

Fonction retire_max ( A : arbre ) : arbre% retourne larbre priv de son plus grand lment %


53/120

A.BENHARI 53

dbutsi est_vide(d(A))

alors retourner g(A)sinon

retourner < racine(A) , g(A) , retire_ max(d(A)) >fin

La complexit est O ( hauteur de larbre ).

Conclusion, Tri par arbre binaire de rechercheToutes les oprations ont une complexit dpendant de la hauteur de larbre binaire de recherche. Elle varieentre O (log n ) pour des arbres quilibrs et O ( n ) pour des arbres dgnrs.

Par consquent, le tri par arbre binaire de recherche, obtenu par un parcours symtrique de larbre, a unecomplexit en comparaison dans le pire des cas variant entre O ( n log n ) et O ( n ).

d. Problme du tri

i. IntroductionLe problme du tri est quasiment le plus important en informatique.

Spcification du tri : La donne est une liste n lments ; chaque lment est associe une cl dont la valeurappartient un ensemble totalement ordonn ; le rsultat est une liste dont les lments sont une permutation dela liste dorigine, et telle que les valeurs des cls soient croissantes quand on parcourt la liste squentiellement.

Un tri est stable, sil conserve lordre de dpart des lments dont les cls sont gales.

En fonction de la capacit mmoire, on distingue le tri interne (tout en mmoire centrale) et le tri externe(mmoire centrale + disque). Pour le tri interne, on a des algorithmes qui travaillent sur place, cest--dire sur laliste de dpart et des algorithmes qui manipulent physiquement une copie. On a des algorithmes diffrents et plus

compliqus quand ils se font sur place.On compte le nombre de variables auxiliaires pour valuer la complexit en mmoire. Le tri interne, sur place,avec un nombre constant de variables auxiliaires possde une bonne complexit en espace. On compte le nombrede comparaisons entre cls et de transferts dlments pour valuer la complexit en temps.

On distingue les mthodes simples et les mthodes plus complexes.

ii. Tri par arbre binaire de rechercheCest une mthode plus complexe, qui consiste crer larbre binaire de recherche, puis faire un parcourssymtrique, pour obtenir la liste trie.

voire partie sur les arbres binaires de recherche

e. Quicksort

i. PrincipeOn choisit une des cls de la liste (par exemple, celle du premier lment), et on lutilise comme pivot. Onconstruit sur place une sous-liste dont les cls sont infrieures ou gales au pivot et une sous-liste dont les clssont strictement suprieurs au pivot.

p > pivotpivot


54/120

A.BENHARI 54

Le pivotp a alors sa place dfinitive. Et on recommence rcursivement sur chacune des deux sous-listes. A lafin, la liste est trie par ordre croissant. Remarquons que le choix du pivot est dlicat ; de lui dpendlquilibrage des deux sous listes.

On suppose donne une procdure

Placer (e/s t : tableau de 1 n entiers , e/ i : entier , e/ j : entier , /s k : entier)

qui effectue le traitement de tentre les indices i etj en fonction du pivot t[i], et qui rend comme rsultat lindicek o le pivot a t plac et le tableau tragenc.

La procdure gnrique du quicksortscrit :

Procdure Quicksort (e/s t : tableau de 1 n entiers , e/ i : entier , e/ j : entier)utilise localement k : entierdbutsi i < jalors dbutPlacer (t , i , j , k)

Quicksort (t , i , k - 1)Quicksort (t , k + 1 , j)fin

fin

Le tri de la liste complte est obtenu par Quicksort (t , 1 , n).

La procdure Placer : La partition et le placement du pivot ne ncessite quun parcours.

On utilise deux compteurs l et kqui partent des extrmits du sous-tableau, et qui vont lun vers lautre :- l part de i+1 et avance tant que lon rencontre un lment a.- kpart dej et recule tant que lon rencontre un lment > a.

On change les deux lments et on recommence la progression jusqu ce que les deux compteurs se croisent :la place dfinitive du pivot est en k, et on y place le pivot a par change avec un lment a.

Si on utilise la procdure Placersur un sous-tableau qui nest pas la fin de ( x =t[j+1] existe ), alors

llmentx est un pivot plac antrieurement. Donc, on a [ ] ][,, stxjis . Par consquent, cet lmentxva arrter la progression du compteur l. Pour utiliser cette proprit (effet de bord) lors de tous les appels, on

rajoute un terme en t[n+1] qui contiendra un lment plus grand que tous les autres.15. Procdure Placer (e/s t : tableau de 1 n entiers , e/ i : entier , e/ j : entier , /s k : entier)16. utilise localement l : entier17. dbut18. l i +119. k j20. % boucle : tant que les compteurs ne se croisent pas %

21. tant que l k faire22. dbut23. tant que t[k] > t[i] faire k--

24. tant que t[l] t[i] faire l++

25. % on a t[k] t[i] et t[l] > t[i] %

26. si l < k alors dbut27. changer t[l] et t[k]28. l++

a > > > > x

i l k j j+


55/120

A.BENHARI 55

29. k--30. fin31.32. fin33. % on met le pivot sa place dfinitive %34. changer t[i] et t[k]

35. finii. Complexit

36. Complexit de Placer : Considrons un sous-vecteur p lments, on la pivot aux p - 1 autres lments. Oneffectue en toutp + 1 comparaisons.37.38. Complexit du Quicksort, au pire: Le graphe des appels du Quicksort est un arbre binaire. La complexit aupire en nombre de comparaisons est obtenu pour tdj tri est en prenant chaque fois le 1er lment commepivot. Le graphe des appels sera dgnr (peigne) et va induire une complexit au pire en O ( n ).39.40. Complexit du Quicksort, en moyenne : On suppose que les n nombres sont distincts, et que le pivot vaoccuper la pime place de la liste trier. On suppose que toutes les places sont quiprobables ; on a la probabilit

1/ndavoir le pivot la place

pet donc davoir deux sous-listes de taille

p - 1et

n - p. On dmontre ( voire

cours + td ) que la complexit en moyenne est en O (2n log n).

iii. Taille de la pile de rcursivit41. Dans la procdure Quicksort, le 2me appel est terminal, ce qui veut dire quon peut le supprimer, et doncviter des empilements. Comme un seul appel va tre conserv, on leffectuera systmatiquement sur la pluspetite des deux sous-listes. La taille de rcursion sera en O (log2 n), car on divisera par 2 la taille de la listedappel.42.Procdure Quicksort (e/s t : tableau de 1 n+1 entiers , e/ i : entier , e/ j : entier)utilise localement k : entierdbuttant que i < j

alors dbutPlacer (t , i , j , k)% on choisit le plus petit %

si (j - k) > (k - i)alors dbut

Quicksort (t , i , k - 1)i k + 1fin

sinon dbutQuicksort (t , k + 1 , j)j k - 1fin

43. fin

fin

f. Heapsort3Cest un tri par slection des minimums successifs bas sur une structure de tas. On va obtenir un tri O (n log n)comparaisons au pire, sans mmoire auxiliaire.

3 Tri par tas


56/120

A.BENHARI 56

i. Arbres partiellement ordonnsUn tri par slection ncessite de savoir localiser et rcuprer efficacement ( en O (1), si possible ) le minimumparmi les lments non encore placs.On considre le cas particulier du type abstrait ensemble o les seules oprations sont :

- laccs un lment minimum- la suppression du minimum- ladjonction dun nouvel lment

On reprsente cette ensemble par un arbre binaire parfait partiellement ordonn.44.Un arbre partiellement ordonnest un arbre tiquet par les valeurs dun ensemble muni dun ordre total, telque la valeur associe tout nud soit aux valeurs associes aux fils. La racine contient toujours un lmentminimum, accs en O (1).45.1) Adjonction dun lment xOn ajoute dabordx comme une feuille en conservant la structure darbre binaire parfait. Puis, on reconstruitlordre partiel :

y x

tant que ( y racine ) et ( y < pre(y) ) fairechanger y et pre(y)46.2) Suppression du minUne fois la racine enleve, on place la dernire feuille la racine, pour conserver la structure darbre binaireparfait. Puis, on reconstruit lordre partiel :

y racine

tant que ( y nest pas une feuille ) et ( y nest pas aux deux fils ) fairechanger y et son fils de valeur minimum

47.48.La complexiten nombre de comparaisons de ladjonction et de la suppression du minimum est au pire enO (hauteur de larbre). Par ailleurs, la hauteurdun arbre binaire parfait ayant n nuds est de n2log .

On utilise la reprsentation en tableau (ordre hirarchique) des arbres binaires parfaits. ( voire partie sur lesstructures arborescentes) Le tableau forme le tas.

On donne les algorithmes crits en LDA des procdure dadjonction et de suppression du minimum :

Procdure ajouter ( e/s t : tableau de 1 N entiers , e/s n : entier , e/ x : entier )% ajoute llment x t ayant n lments au moment de lappel %utilise localement i : entierdbutsi n < Nalors dbutn++t[n] xi ntant que ( i > 1 ) et ( t[i] < t[i div 2] ) faire

dbutchanger t[i] et t[i div 2]i i div 2fin

finsinon crire dbordement du tas

fin

Procdure suppress_min ( e/s t : tableau de 1 N entiers , e/s n : entier , /s min : entier )% fournit dans min le minimum pour t ayant n > 0 lments %utilise localement i, j : entiers


57/120

A.BENHARI 57

dbutmin t[1]

t[1] t[n]n--i 1% tant que lon est pas sur une feuille %

tant que ( i n div 2) fairedbutsi ( n = 2i ) ou ( t[2i] < t[2i+1])

alors j 2isinon j 2i +1

si ( t[i] > t[j])alors dbut

changer t[i] et t[j]i jfinsinon exit

finfin

ii. Tri par tasPrincipe :

- Construire un tas contenant les n lments par adjonction successives ; en O (n log n).- Tant que le tas nest pas vide, faire supprimer le minimum du tas avec rorganisation, mettre ce

minimum sa place dfinitive ; en O (n log n).

La complexit en comparaison est au pire en O(n log n).

On utilise un seul tableau pour le tas et les valeurs des minimums successifs. Le minimum rcuprer esttoujours dans t[1]. On mettra les minimums successifs la droite du tableau, de la droite vers la gauche. A la fin,

on obtient lensemble dans lordre dcroissant.

49.50.51.

52.53. Procdure heapsort (e/s t : tableau de 1 n entiers)54. utilise localement p, min : entiers55. dbut56. % construction du tas %57. p 058. tant que p < n faire

59. ajouter( t , p , t[p+1] )60. % tri %61. tant que p > 1 faire62. suppress_min ( t , p , min )t[p+1] min63. fin

64.65.Remarque : lincrmentation et la dcrmentation de p est gnr par les procdures en e/s.

tas traiter minimums bien plasmin t[n]


58/120

A.BENHARI 58

XVI. Algorithmes numriques

a. Gnralitsi.Normes et rayon spectral

Dfinition norme vectorielle :

+RRxxn,a vrifiant :

- 00et0 == xxx - xx .. = - yxyx ++

Exemple de norme vectorielle :

- Norme 1 : =i

ixX 1

- Norme 2 : XXxXi

i ,2

2==

- Norme : ii

xSupX =

Proposition : En dimension finie, toutes ces normes sont quivalentes ; en pratique, on choisit celle qui nousarrange.

Dfinition norme matricielle :

C'est une norme dans l'espace vectorielleMn(R), avec en plus BABA . .

ii.Norme matricielle induite :A partir d'une norme vectorielle, on construit une norme matricielle induite :

( )AXSupX

AXSupA

XouXX 110 ==

= .

Notons de plus que1=I

.

En particulier pour la norme 2, on a la relation : ( )AAI t=2

avec le rayon spectral.

Proprits :

- XAAX . et BAAB . - Cas de A symtrique : ( ) i

iAA max

2==

- Dans le cas gnral, max2 =A , maximum des valeurs singulires ii = avec i les valeurspropres (positives) de la matrice symtrique AAt . (?)

- Soit A une matrice carr quelconque n x n. Pour toutes normes de matrice induite, on a ( ) AA .


59/120

A.BENHARI 59

iii.Conditionnement dune matrice inversible :Considrons un systme linaire AX=b. L'exprience de Wilson met un vidence une instabilit des calculs danscertains cas. Si l'on modifie sensiblement les paramtres de la matrice A, ou du second membre b, on peuttrouver des rsultats compltement diffrends !

- ( ) 1. = AAACond - ( ) ( )ACondACond = - ( ) 1ACond avec ( ) 1=IdCond - Soit une matrice Q orthogonale :

22XQX = et ( ) 1=QCond

- Les bons conditionnements sont les petits conditionnements (au mieux 1 pour les matrices orthogonales).- Pour A symtrique : ( )

min

max2

=ACond ; dans la cas gnral : ( )

min

max2

=ACond

Thormes sur le conditionnement :

Thorme : ( ) bbXXABAX +=+= et . On a ( )b

bACond

X

X

.

Thorme : ( )( ) bXXAABAX =++= et . On a ( )A

AACond

XX

X

+

.

Remarque : Le conditionnement traduit l'amplification des grandeurs relatives.

iv.Inverse numrique dune matrice :

Soit A une matrice inversible et A-1 son inverse thorique.M est un inverse de A du point de vue numrique si :

-1

1

A

AMest petit, ce qui correspond M=A-1

-A

AM 1

est petit, ce qui correspond A=M-1

- IdMAIdAM et sont petits, ce qui correspond 0Id-MAet0 ==IdAM On s'adapte au calcul que l'on veut faire. Notons que l'on rsout rarement un systme linaire en calculantl'inverse bAX 1=


60/120

A.BENHARI 60

b. Systmes linaires Ax=b : mthodesdirectes

i. Formules de CrammerCette mthode ncessite le calcul d'un dterminant, dont la complexit est en n!. La complxit de la formule deCramer est en n 2 n!. Par consquent, cette mthode n'est pas utilisable en informatique.

ii. Mthode du pivot de Gauss

la kme tape : pour ,ki > kLigneiLigne,

,

kk

ki

a

a. On pose

kk

ki

kia

al

,

,, = .

L'algorithme une complexit en3

3n.

Le problme des coefficients diagonaux nuls : il faut permuter les lignes lorsque apparat un zro sur ladiagonale.

Stratgie du pivot maximum partiel :

On permute la kme ligne et la ime ligne avec i tel que klkl

ki aSupa ,,

= . Pour des raisons de stabilit

numrique, on divise par le terme de la colonne k, qui a la plus grande valeur absolue.

Stratgie du pivot avec seuil :

On effectue une permutation uniquement des


61/120

A.BENHARI 61

En rsum, on a leAx = et MAUeMxU l == avec.. une matrice triangulaire suprieure.On veut traiter tous les seconds membres en une seule passe ; pour cela on considre la matrice n x 2n suivante :

qui aprs calculs donne

.

On donne ici un exemple dcriture en langage de description algorithmique :

- Procdure pivot ( k , l : entiers ; OK : boolens )- Dbut- Max := ( )kkA , ;- l := k ;- Pour i := k+1 n faire- Si max < ( )kiA , - Alors- Dbut- Max := ( )kiA , ;- l := i ;- Fin ;- OK := Max > ;- Fin ;- Procdure permuter ( k , l : entiers )- Dbut- Si lk - Alors- Pour j := k 2n faire- Dbut- c := ( )jkA , ;- ( )jkA , : = ( )jlA , ;- ( )jlA , := c ;- Fin ;- Fin ;

On donne maintenant le programme principal, ralisant le calcul de linverse.

- Dbut- Initialiser A et lire ;-- /* triangularisation */- Pour k := 1 n faire- Dbut- Pivot (k , l , OK ) ;- Si non(OK)- Alors- Dbut- Ecrire matrice non inversible ;- Exit echec ;- Fin ;- Permuter ( k , l ) ;- Pour j := k+1 2n faire- ( ) ( ) ( )kkAjkAjkA ,/,:, = ;


62/120

A.BENHARI 62

- Pour i := k+1 n faire- Pour j := k+1 2n faire- ( ) ( ) ( ) ( )jkAkiAkiAjiA ,*,,:, = ;

Fin ;-- /* n remontes */- Pour k := 1 n faire- Pour i := n-1 1 par pas de -1 faire- Dbut- s := 0 ;- Pour j := i+1 n faire- ( ) ( )knjAjiAss ++= ,*,: ;- ( ) ( ) skniAkniA +=+ ,:, ;- Fin ;- Fin ;

Remarques :- Choix du pivot : pour des raisons de stabilit numrique, on divise toujours par le terme de la colonne k qui

a la plus grande valeur absolue (Cf. Pivot partiel maximum).- Recherche du pivot : si la plus grande valeur absolue est infrieure la prcision machine , alors on arrte

en disant que la matrice nest pas inversible prs (test dinversibilit informatique). Cependant, elle peuttrs bien tre inversible du point de vue mathmatique !

c. Factorisation A=LUSoit A une matrice rgulire, de dimension n.

Lien avec la mthode de Gauss

On applique la mthode de Gauss sans pivoter. U est une matrice triangulaire suprieure relle, telle que

UAJnk

k == ,1

.

On donne la dfinition des matrices

= +

1

1

1

1

,

,1

kn

kkkJ

OM

aveckk

kl

kla

a

,

,, = pour kl > .

On dmontre que linverse des Jk existe et que =

=

nk

kJL,1

1est une matrice triangulaire infrieure, avec des 1

sur la diagonale. En fait, on a

= +

1

1

1

1

,

,11

kn

kkkJ

OM

.

Calcul algorithmique des coefficients de L et de U

On procde par identification en utilisant les proprits de L (triangulaire infrieure avec une diagonale de 1) etde U (triangulaire suprieure). On cherche un algorithme par ligne donnant les

njuijl jiji 1pourleset11pour ,, .

-Pour i := 1 n faire- Dbut


63/120

A.BENHARI 63

- Pour j := 1 i-1 faire- jj

j

k

jkkijiji aulal ,

1

1,,,, .:

=

=

;

- /* avec 1, =iil */-

- Pour j := i n faire-

=

=1

1,,,, .:

i

k

jkkijiji ulau ;

- Fin ;Remarque : L et U crasent la matrice A.

Cas particulier des matrices structure bande

OO

OO

OOO

OOO

OOO

OO

OO

- La largeur de la bande est W = P+Q+1- On ne stocke dans une structure de donne approprie que la bande, soit un O(W.N), ce qui est intressant si

W


64/120

A.BENHARI 64

Matrice de permutation lmentaire i j :

jligne

iligne

1

1

01

1

1

10

1

1

,

=

O

O

O

jiP

Le produit PA permute les lignes i et j de la matrice A. Le produit AP permute les colonnes i et j de la matrice A.

( complter avec le cours : obtention de la factorisation et utilisation de la factorisation )


65/120

A.BENHARI 65

e. Factorisation A=BBt: CholeskyCette factorisation s'applique pour des matrices A symtriques et positives.Thorme : Soit A une matrice SDP de dimension n. Il existe une et une seule matrice B triangulaire infrieure,telle que A=BBt.

f. Factorisation A=LDLt: CroutThorme : Soit A une matrice SDP de dimension n. Il existe une et une seule matrice L triangulaire infrieure etD diagonale positive, telles que A=LDLt.Remarque : Crout a le mme comportement numrique que Cholesky. Cependant, il est plus utilis cargnralisable au cas complexe.

Soit A une matrice symtrique dfinie positive (quelconque ?).L est une matrice triangulaire infrieure de dimension n dont la diagonale se compose de 1.D est une matrice diagonale de dimension n.

L est en fait la matrice B pour laquelle les termes d'une colonne sont diviss par les coefficients bii. D est lamatrice dont les coefficients diagonaux sont les bii.

i.Algorithme par ligne pour lobtention de lafactorisation

On crit

=

1

0

001

,jil

L O et

=

nd

d

D O

1

.

Il s'agit de calculer les li,j et les di. On a jij

j

k

jkkikji dlldla +=

=

1

0

, .

On tablit un algorithme par ligne : Pour la 1re ligne, on crit 1,11 ad = . Supposons maintenant le calcul

effectu jusqu' la ligne i-1 ; le calcul de la ligne i est donn par

( )

j

j

kjkkik

jijid

ldl

al

==

1

1,, pour 1 ij et

par ( )

=

=1

1

2,

j

k

kikiii dlad . Ainsi une CNS pour cette factorisation est que les di ne soient pas nuls.

On donne lalgorithme correspondant :

-Pour i de 1 n faire- Dbut- Pour j de 1 i-1 faire- ( ) j

j

k

jkkikjiji dldlal /:1

1,,

=

= ;

- /* 1:, =iil */- ( )

=

=1

1

2,:

j

k

kikiii dlad ;

- Fin ;


66/120

A.BENHARI 66

Remarque : L et D crase la partie triangulaire infrieure de A.

On veut maintenant apporter une amlioration cet algorithme en diminuant les nombres de calcul ; on

conomise les produits kki dl ., , que lon stocke pour un i fix dans le vecteur C[k].

On donne lalgorithme modifi :

-Pour i de 1 n faire- Dbut- Pour j de 1 i-1 faire- Dbut- C[ j] :=

=

1

1, ][.

j

k

jkji kCla ;

-j

jid

jCl

][:, = ;

- Fin ;-

=

=1

1, ][.:

j

k

ikiii kClad ;

- Fin ;

ii.Algorithme par colonne pour lobtention de lafactorisation

Principe : On construit L et D, en procdant par dcomposition successives. On ralise le dcoupage suivant :

==1

1

1

1

11

1

Bd

v

dv

d

AA

t

, avec v1 un vecteur colonne de dimension n-1, et B1 une matrice carr de dim

n-1.

On pose

=

11

1

1

1

nIdv

O

L ,

=

1

1

2

BO

Od

A , avec1

1111

.

d

vvBB

t

= .

Ainsi, on a :t

LALAA 1211 == . Puis, en ritrant n-1 fois, il vient : ( ){

( )43421

L43421

Lt

L

t

n

D

n

L

n LLALLAA 11111 == .


67/120

A.BENHARI 67

Le produit des matrices

=

1

1

1

k

k

k

dv

LO

O

donnent la matrice finale

=

1

1

1

2

2

1

1 L

O

dv

dv

L .

Ce qui correspond en effet une factorisation de Crout, car la matrice ( )idD = est bien diagonale et la matriceL est bien triangulaire infrieure, par construction.

On donne lalgorithme de calcul de L et de D par colonne, qui procde en crasant la partie triangulaireinfrieure de A, (les 1 de la diagonale de L ne sont pas stocks, car on prfre y stocker D) :

-Dbut-Pour k de 1 n-1 faire- Pour j de k+1 n faire- Dbut- kkkj aad ,,:= ;- Pour i de j n faire daaa kijiji .: ,,, = ;- da kj =:, ;- Fin ;-Fin ;

La structure donne dimplmentation serait un vecteur une dimension stockant conscutivement les colonnesde la partie triangulaire infrieure de A.

Remarque fondamentale : jia , est modifi par kia , et kja , .

iii.Etude du remplissage lors de la factorisation dematrices SDP creuses

Considrons une matrice A symtrique creuse. On utilise une structure de donne type profil, il est important desavoir o se trouvent les termes priori non nuls de L.

Une matrice est dite creuse si elle contient un grand nombre de termes nuls. Plus prcisment, on considreque la matrice est creuse partir du moment, o son pourcentage de termes nuls permet un gain informatique parrapport un traitement classique qui la considrerait pleine.

Dfinitions :

- Un terme de remplissage apparat en (i,j) au cours de la factorisation si et seulement si 0, =jia et0, jil . On reformule le problme comme la conservation du creux initial de la matrice.

- li,j est logiquement non nul si 0quetel11,ou0 ,,, kjkiji lljkka . Cest dire, la kmeitration ( )11 nk un terme jia , de la matrice A qui est nul, devient non nul ssi


68/120

A.BENHARI 68

0et0 ,, kikj aa avec 1 jk . Preuve (algorithme par colonne):{ {

kk

kjki

jijia

aaaa

,

0

,,

0

,

0

,

.:

48476

=

= .

- Les li,j logiquement non nuls

Documents

L'Algorithmique