Support de Cours - Structures de Données PDF

Système dExploitation I

SMI – S3. El Mostafa DAOUDI. Université Mohammed Premier. Faculté des Sciences Pour accéder au sous-répertoire « smi » du répertoire « cours » à.

Filière : SMI Semestre 3 Module 18 Cours de Statistique Descriptive

Deux groupes de S3 Statistique comparent leurs résultats du Contrôle final et déclarent : “nos classes ont le même profil puisque dans les deux cas la médiane

SMI - S3

8h. 9h. 10h. 11h. 12h. 13h. 14h. 15h. 16h. 17h. 18h. Y. ZAZ. A. ENAANAI. A. ENAANAI. O. EL M'RABET. O. EL M'RABET. L. BENAMEUR. L. BENAMEUR. Cours -

Support de Cours - Structures de Données

Support de Cours. Structures de Données. Filière: SMI- S4. Réalisé par: Pr. Mohamed Bellouki N={S1S2

EMPLOIS DU TEMPS SEMESTRE DAUTOMNE 2019 (S1 S3 et S5)

19 sept. 2019 (S1 S3 et S5). Cours magistraux. &. Travaux dirigés ... SMI : 1 section et 1 groupe de TD;. ? SMC : 1 section et 3 groupes de TD;.

Module par filière Sciences Mathématiques et Informatiques

S3. M18. PROBABILITES -STATISTIQUES. M16. ALGORITHMIQUE II. M17. SYSTEME D'EXPLOITATION I. M20. ELECTRONIQUE. M15. PROGRAMMATION I. M19. TECHNOLOGIE DU WEB.

Filière : SMI Semestre 3 Module 18 Cours calcul des probabilités et

Filière : SMI Cours calcul des probabilités et variables aléatoires ... Ce cours a pour but de familiariser l'étudiant avec le raisonnement probabiliste ...

Flyer SMI

Le volume horaire de chaque Module est de 48H de cours TD et Evaluation. S1. S2. S3. S4. S5. • Analyse 1. • Algèbre 1. • Algèbre 2. • Physique 1.

Cours de probabilités et statistiques

On se limite dans ce cours `a étudier les univers dénombrables. La probabilité d'un événement est une valeur numérique qui représente la proportion de fois o`u

Cours de Programmation linéaire et Recherche Opérationnelle

Pr. Abdelghni LAKEHAL. SMI S5. Cours de la. Recherche. Opérationnelle Donc on a 4 stables S1 = {BF}

UUnniivveerrssiittéé MMoohhaammeedd PPrreemmiieerr FFaaccuullttéé PPlluurriiddiisscciipplliinnaaiirree DDééppaarrtteemmeenntt ddee MMaatthhéémmaattiiqquueess && IInnffoorrmmaattiiqquuee ""NNaaddoorr""

SSuuppppoorrtt ddee CCoouurrss

SSttrruuccttuurreess ddee DDoonnnnééeess

FFiilliièèrree:: SSMMII-- SS44

Réalisé par:

Pr. Mohamed Bellouki

"Année Universitaire 2019-2020

Pr. Mohamed Bellouki 2

SSoommmmaaiirree

CChhaappiittrree 11 RRaappppeell ssuurr lleess AAllggoorriitthhmmeess ddee TTrrii eett ddee RReecchheerrcchhee

CChhaappiittrree 22 SSttrruuccttuurreess LLiinnééaaiirreess :: LLiissttee,, FFiilleess,, PPiilleess

CChhaappiittrree 33 SSttrruuccttuurreess AArrbboorreesscceenntteess :: AArrbbrreess bbiinnaaiirreess eett AArrbbrreess BBRR

CChhaappiittrree 44 AArrbbrreess BBiinnaaiirreess CCoolloorrééss CChhaappiittrree 55 AArrbbrreess MMuullttiipplleess eett GGrraapphheess

Pr. Mohamed Bellouki 3

CChhaappiittrree 11 RRaappppeell ssuurr lleess AAllggoorriitthhmmeess ddee TTrrii eett ddee RReecchheerrcchhee

11..11 IInnttrroodduuccttiioonn

Un algorithme de Tri est, en informatique ou en mathématique, un algorithme qui permet

11..22 CCllaassssiiffiiccaattiioonn ddeess aallggoorriitthhmmeess ddee TTrrii

La classification des algorithmes de tri est très importante, car elle permet de choisir

de contraintes imposées

par celui-ci. Les principales caractéristiques qui permet de différencier les algorithmes sont :

la complexité des algorithmes, les ressources nécessaires (espace mémoire utilisé). 9 :

Tri par sélection :

Principe : On cherche le premier minimum de {t0, . . ., tn-1}, puis on le place à la position 0,

ensuite on cherche le deuxième élément parmi {t1, . . ., tn-1} est on le place à la position 1, ce processus est répété jusqu'à ce qun-1. Rq : Le tri par selection effectue n-1 échanges dans le pire des cas

Exercice 1-1 :

stockés dans un tableau T. Le programme doit trier le tableau par ordre croissant et doit afficher le tableau. Algorithme suggéré (Tri par Selection).

Tri à bulles :

Principe

trié.

Pr. Mohamed Bellouki 4

Tri par insertion :

Principe : On parcourt le tableau à trier du début à la fin. Au moment où on considère le i

ème élément, les éléments qui le précéd insérer le i eme élément , ceux à sa place parmi ceux qui précédent. Il faut élément doit être inséré en le comparant aux autres, puis décaler les éléments afin de pouvoir effectuer l, ces deux actions sont fréquemment effectuées en une passe, qui consiste à faire remonter

Exercice 1-2 :

stockés dans un tableau T. Le programme doit trier le tableau par ordre croissant et doit afficher le tableau. Algorithme suggéré (Tri par Insertion).

9 Tri plus rapide :

Tri par fusion :

Principe : Le tri par fusion est construit suivant la stratégie " diviser pour régner ». Il est

souvent plus facile de diviser un gros problème en petits problèmes élémentaires,

érentes solutions de ces derniers. Il est

préférable de trier deux sous tableaux, puis de combiner les résultats. Etapes de

Trier chacun des deux ensembles,

Fusionner les deux ensembles.

Exemple du tableau.

Tableau

6 3 0 9 1 7 8 2 5 4

6 3 0 9 1 7 8 2 5 4 Division du tableau en deux parties

0 1 3 6 9 2 4 5 7 8 Trier chaque tableau et les Fusionner

0 1 2 3 4 5 6 7 8 9 Le tableau est trié,

Exercice 1-3 : Tri par fusion (voir TD)

Pr. Mohamed Bellouki 5

11..33 AAllggoorriitthhmmeess ddee rreecchheerrcchhee

99 Recherche Dichotomique

La recherche dichotomique, ou recherche par dichotomie), est un algorithme de recherche pour trouver la position d'un élément dans un tableau trié. Principe: Comparer l'élément avec la valeur de la case au milieu du tableau ; si les valeurs sont égales, la tâche est accomplie, sinon on recommence dans la moitié du sous tableau. La recherche dichotomique s'applique à plus de problème.

4 < milieu

1 3 4 6 7 8 10 13 14

Visualisation d'une recherche dichotomique, où 4 est la valeur recherchée.

L'algorithme est le suivant :

Trouver la position la plus centrale du tableau (si le tableau est vide, sortir). Comparer la valeur de cette case à l'élément recherché.

Si la valeur est égale à l'élément, alors retourner la position, sinon reprendre la procédure

dans la moitié du sous tableau.

On peut toujours se ramener à une moitié de tableau sur un tableau trié en ordre croissant. Si

la valeur de la case est plus petite que l'élément, on continuera sur la moitié droite, c'est-à-dire

sur la partie du tableau qui contient des nombres plus grands que la valeur de la case. Sinon, on continuera sur la moitié gauche.

Exercice 1-4 : (voir TD)

99 Recherche Séquentielle

La méthode de recherche la plus simple est la recherche séquentielle qui s'effectue en temps

linéaire : étudier les éléments les uns après les autres. Elle ne nécessite pas d'avoir une

structure de données triée. De plus elle peut être pratiquée non seulement sur un tableau, mais

aussi sur une liste chaînée, qui est parfois une structure plus adaptée. Sur des tableaux

ordonnés, la recherche dichotomique est plus rapide asymptotiquement, mais pas forcément sur des tableaux de petite taille.

Exercice 1-5 : (voir TD)

Pr. Mohamed Bellouki 6

11..44 CCoommpplleexxiittéé ddeess AAllggoorriitthhmmeess

La classification des algorithmes de tri est très importante, car elle permet de choisir

par celui-ci. Les principales caractéristiques qui permet de différencier les algorithmes sont :

la complexité des algorithmes, les ressources nécessaires (espace mémoire utilisé).

11 ..44..11 NNoottiioonn ddee ccoommpplleexxiittéé

un algorithme en fonction de ses paramètres

représentant la taille du problème à résoudre. Le calcul de la complexité permet de comparer

évaluation compte de la machine sur laquelle nous allons exécuter algorithme. Quand on veut comparer deux algorithmes qui exécutent différemment la même tache, on va comparer principalement :

Le temps mis pour faire le calcu.

11..44..33 IImmppoorrttaannccee pprraattiiqquuee ddee llaa ccoommpplleexxiittéé

Un algorithme qui traite 100 données en 1 seconde. Le temps de calcul pour 1000 données. complexité (n) (n2) (n4) (2n) Temps approximatif 10sec 1min 40 sec 2h 46mn 40 sec 10270 > 10260 an

11..44..44 EEffffiiccaacciittéé ddeess aallggoorriitthhmmeess vvuuss lleess tteecchhnnoollooggiieess mmooddeerrnneess

Exemple 1 : un ordinateur A : très rapide un ordinateur B : très lent Pour trier un million de valeurs : Tri par sélection avec A et Tri par fusion par B.

A exécution : 2000 sec

B exécution : 100 sec

Pour trier 10 million de valeurs : Tri par sélection avec A et Tri par fusion par B.

A exécution : 20 mn

A exécution : 2 jours 8h

Pr. Mohamed Bellouki 7

11..44..55 PPrriinncciippaauuxx ttyyppeess ddee ccoommpplleexxiittéé

(c) : temps constant (n) : complexité linéaire (log(n)) : complexité logarithmique (n2) , (n3) , (n4), (np) : complexités polynomiales (pn) : complexité exponentielle

11..44..55 QQuueellqquueess MMéétthhooddeess dduu ccaallccuull ddee ccoommpplleexxiittéé ddeess aallggoorriitthhmmeess

9 Exemple 1

Calculer

entiers de 1 à n, avec n un entier saisi au clavier.

9 Exemple 2 (Voir TD - Série 1)

Pr. Mohamed Bellouki 8

CChhaappiittrree 22 SSttrruuccttuurreess LLiinnééaaiirreess :: LLiisstteess,, FFiilleess,, PPiilleess

Une structure de données est un moyen de stocker et organiser les données pour faciliter dices (tableau) ou par des pointeurs (listes chainées).

22..11 LLiisstteess

quotesdbs_dbs50.pdfusesText_50

[PDF] Support de Cours - Structures de Données