Description du Cours
FST - Universit Hassan 1er
LICENCE UNIVERSITAIRE SPECIALISEE
Description du Cours
Algorithmique & Structures de Donnes
Droulement du Cours
Cours + TD + (TP)
Comptences Attendues
Connaissance des algorithmes classiques (Recherche, parcours, tris, )
Concevoir, dfinir et utiliser une structure de donnes.
Etablir et implmenter des algorithmes de traitement des structures de donnes (listes chanes, piles, files, arbres,..)
Contenu du cours Introduction lAlgorithmique Les Objets et structures Algorithmiques
Les fonctions et les procdures
La rcursivit La complexit dun algorithme Les types complexes (Tableaux ou vecteurs, matrices, les chanes) Les algorithmes de Tri
Les pointeurs Les listes simple chanage
Les listes double chanage
Les piles
Les files
Les arbres
Pr requis du CoursNotions de logique binaire
Evaluation du Cours Contrles crits et oraux
Travaux pratiques.
Support - polycopies
Chapitre 1: Introduction lalgorithmique1. Dfinitions :
Un Algorithme est une spcification d'un schma de calcul, sous forme d'une suite finie d'oprations lmentaires obissant un enchanement dtermin. Un Algorithme est un ensemble de rgles opratoires dont l'application permet de rsoudre un problme donn au moyen d'un nombre fini d'oprations.2. Proprits d'un algorithme:
Un algorithme doit tre:
PRECIS:
Il doit indiquer:
- l'ordre des tapes qui le constituent
- quel moment il faut cesser une action
- quel moment il faut en commencer une autre
- comment choisir entre diffrentes possibilits
DETERMINISTE
- Une suite d'excutions partir des mmes donnes doit produire des rsultats identiques.
FINI DANS LE TEMPS
Cest--dire s'arrter au bout d'un temps fini.
3. Les Phases de rsolution d'un problme informatique
La rsolution d'un problme informatique se dcompose en quatre phases: Phase d'tude
Inventorier les paramtres connus ou observables et dfinir les objectifs raliser.
Phase de ralisation du modle
Dterminer l'enchanement des oprations. Cette phase aboutit l'laboration d'un schma de rsolution.
Phase de spcification
Exprimer le schma de rsolution de manire plus prcise en utilisant ventuellement un pseudo-langage. Cette phase dbouche sur des algorithmes.
Phase de traduction
Mettre en uvre les algorithmes en les traduisant en un langage de programmation.
4. Le Pseudo langage. Il permet d'crire tout algorithme de faon formelle, c'est--dire suffisamment prcise, tout en restant comprhensible pour l'ensemble des informaticiens.
La phase de programmation se trouvera ncessairement allge, puisqu'elle se rsumera adapter l'ensemble des oprations dcrites aux spcificits du langage utilis.
Il est bas sur les instructions disponibles dans la plupart des langages.
Exemple:
Calculer la factorielle de N (version itrative)
VAR
N, F: Entier
DEBUT
ECRIRE (Entrer un entier N=)
LIRE (N)
F ( 1
POUR I allant de 1 N FAIRE
F ( F* I
FIN POUR
ECRIRE (la Factorielle de N est :, F)
FIN5. Les Structures lmentaires: Entres/Sorties: LIRE, ECRIREExemple:ECRIRE (Entrer un entier N=)
LIRE (N)
Affectation: Exemple:X ( YX ( x+1 Instruction conditionnelle: SI (Expression Vraie) ALORS instructions
SINON instructions FINSIExemple:Si (Somme 0
n! = 1
( La Solution itrative Classique
FONCTION Fact( n: ENTIER): ENTIER
VAR
F: ENTIER
DEBUT
F( 1
TANT QUE n > 1
F( F*n
n ( n-1
FINTANTQUE
FIN
Connaissant la relation mathmatique: N!=n*(n-1)!On peut en dduire :
( La Solution Rcursive :FONCTION Fact(n : ENTIER):ENTIER
DEBUT
SI n=1 ALORS RETOURNER (1)
SINON RETOURNER (n*Fact(n-1))
FINSI
FINLexistence dune partie auto imbrique conduit la ncessit de grer une pile destine emmagasiner temporairement les informations relatives lexcution de la fonction un certain niveau dimbrication.
Ainsi, le calcul de Fact(3), par exemple, s'effectue de la manire suivante:Fact(3)=3*Fact(2)=3*2*Fact(1)=3*2*1=6
4. Transformation de boucle en fonction rcursive:
On peut transformer en une fonction rcursive, nimporte quelles instructions de type :Pour x allant de val1 val2 faire
instructions x ( val1; Tant que x< val2 faire
instructionsx ( val1; faire instructions Tant que x< val2
Exemple: a et b tant deux entiers positifs ou nuls ,
On peut Calculer la somme a+b suivant le principe : a+b=a+ (b-1) +1 FONCTION Somme(a,b : entiers) : retourne un entier
DEBUT
si b=0 alors retourner (a)
sinon retourner (1+Somme(a,b-1))
finsi
FINAinsi:
Somme(4,3)=1+ Somme(4,2)= 1+(1+ Somme(4,1))=1+(1+(1+ Somme(4,0)))= 1+(1+(1+ Somme(4,0)))=7Cet exemple montre que le choix d'une solution rcursive n'est pas toujours pertinent, cependant ils existent des types de problmes o la rcursivit est la bonne solution. 5. Quelques algorithmes rcursifs:
Calcul des lments de la suite Fibonacci:
- Les deux premiers lments sont gaux 0 et 1
- Chaque lment de la suite est gal a la somme de ses deux prdcesseurs.
F(0) = 0; F(1) = 1
(n > 1; F(n) = F(n-1)+ F(n-2) FONCTION Fibo(n : entiers) : retourne un entier
DEBUT
si (n=0 ou n=1) alors retourner (1)
sinon retourner (Fibo(n-1)+Fibo(n-2));
finsi
FINExercice: Calculer les lments de cette suite de Fibonacci par une mthode itrative. Faites la comparaison avec la solution itrative. Recherche du Plus Grand Diviseur Commun par l'Algorithme dEuclide:Calcul du pgcd de deux nombres par soustractions successives :pgcd(a; b) = pgcd(a - b; b) si a > b
pgcd(a; b) = pgcd(a; b- a) si b > a
pgcd(a; b) = a si a = bOn suppose que les oprandes sont des entiers positifs.
Algo pgcd(a,b:entier) : retourne un entier
DEBUT
si a=b alors
retourner a
sinon si a>b alors retourner pgcd(a-b,b)
sinon retourner pgcd(b-a,a)
finsi
finsi
FINExemple :
pgcd(114,42)=pgcd(72,42)=pgcd(30,42)=pgcd(12,30)=pgcd(18,12)=pgcd(6,12) = pgcd(6,6)=6 Problme de Tours de Hanoi: Il sagit de dplacer les disques dun pilier un autre en utilisant un pilier intermdiaire et en respectant une simple rgle: un disque d'un certain diamtre ne peut pas tre plac au dessus d'un disque de diamtre infrieur.
La rsolution dun tel problme est un algorithme rcursif:
ALGORITHME Hanoi(Nb_disque:entier, Depart:entier, Destination:entier)Var: intermdiaire:entier
Debut
Si (Nb_disque=1) Afficher (On dplace de, Depart,a, Destination)
Sinon
intermdiaire=6-(Depart+Destination)
Hanoi(Nb_disque -1, Depart, intermdiaire)
Hanoi(1, Depart, Destination)
Hanoi(Nb_disque -1, intermdiaire, Destination)
Finsi
Fin
Exemple: Dplacer 3 Disques du pilier 1 vers le pilier 3.
Ce Traitement ncessite ( 2nb_Disque 1) dplacements, soit 23 1 pour cet exemple.Rsum:
La rcursivit est lgrement moins rapide quun algorithme itratif quivalent cause du temps ncessaire lempilage et au dpilage des donnes
La rcursivit utilise plus de ressources mmoire pour empiler les contextes
La rcursivit est plus lgante
Les algorithmes rcursifs sont souvent plus faciles crire
Chapitre 4:
La complexit dun algorithme1) Introduction:
Pour rsoudre un problme la question du choix de lalgorithme se pose souvent. Lalgorithme choisi doit satisfaire un compromis entre deux besoins souvent contradictoires:
Simplicit comprendre et facilit de mise en uvre.
Exploitation optimale des ressources de lordinateur (mmoire) et plus prcisment sexcuter le plus rapidement possible (vitesse dhorloge).
2) Le Temps dexcution du programme :
Il dpend des facteurs suivants:
Le type et la taille des donnes entrants
La qualit du code gnr par le compilateur.
La vitesse dexcution des instructions du P utilis.
La complexit algorithmique.
3) La Notation en O:
Pour comparer les performances dalgorithmes, on peut considrer une mesure base sur leur temps dexcution. On utilise la notion dite de Landau qui traite de lordre de grandeur du nombre doprations effectues par un algorithme donn. Cest la notation O qui donne une majoration de lordre de grandeur du nombre doprations.
Pour dterminer cette majoration, il faut:
Connatre la taille n de la donne en entre du problme (ex. nombre de donnes traiter, le degr dun polynme, taille dun fichier, le codage dun entier, etc.) Dterminer les oprations fondamentales qui interviennent dans ces algorithmes et qui sont telles que les temps d'excution seront directement proportionnels au nombre de ces oprations.Dfinition de la O-notation
Une fonction f(n) est O(g(n)) s'il existe deux constantes positives K et n0 tel que |f(n)| K|g(n)| pour tout nn0
En dautres termes, f(n) est O(g(n)) si partir dune certaine valeur n0 de n tous les f(n) sont infrieurs g(n) en valeur absolue.
Le O(g(n)) reprsente le cot de lexcution de la fonction f(n). Il permet de classer la complexit de la fonction f parmi les classes de complexit connues. Le but de cette classification est danticiper le comportement de la fonction en prsence de grande quantit de donnes.4) Exemple:On dsire calculer Exp(x) par lapproximation suivante:
S=Exp(x) 1+x/1! + x/2! + x^3/3! + + x^n/n!
Algorithme 1:
Dbut
S(1
I( 1
Tant que I Y
Ecrire (Entrer deux Entiers)
Lire(X, Y)
Ecrire (X)
Ecrire (Y)
FIN
FIN
Ecrire (P)
P ( P+A
B ( B-1
Lire (A, B)
Ecrire (Entrer deux Entiers Positifs)
B0
DEBUT
P ( 0
2
1
3
3
2
1
3
2
1
3
2
1
3
2
1
3
2
1
3
2
1
PAGE 20Algorithmique & Structures de Donnes
A.RADOUANE