[PDF] PLAN DU COURS ALGORITHME DE RECHERCHE

View - Download PLAN DU COURS ALGORITHME DE RECHERCHE

Previous PDF

Next PDF

PLAN DU COURS

•Introduction au langage C •Notions de compilation •Variables, types, constantes, •Tableaux, opérateurs •Entrées sorties de base •Structures de contrôle •Algorithmes de recherche •Algorithmes de Tri -Insertion-Fusion •Les pointeurs •Procédures et fonctions •les types composés •Allocation dynamique •Listes Chaînées

101MAP - UNS

ALGORITHME DE RECHERCHE

•Objectif : Rechercher une information dans un tableau •Méthode : séquentielle •Soit Tun tableau de N éléments et val l"élément cherché •parcours du tableau à partir du premier élément (T[0]) •Arrêt quand élément trouvé ou si fin de tableau (T[n-1]) •Complexité : •linéaire de l"ordre de n. •Pire cas : parcourt de tout le tableau

MAP - UNS102

RECHERCHE SÉQUENTIELLE

Algorithme recherche_sequentielle

{Recherche le premier indice où se trouve la valeur val parmi les N données du tableau tab; affiche l'indicesi la valeur est trouvée. }

variables : T [0, N-1], val entier n, val, indice : entier

Débutindice ←0

tant que ( val <> T[indice] && indice < N-1) faire indice ←indice + 1 ftq si

T[indice] = val alors

afficher( "l"élément se trouve en : » indice); sinon afficher( " Elément non présent " ); fsi Fin

MAP - UNS103

7 1 15 8 2

ALGORITHME DE RECHERCHE

•Objectif : Rechercher une information dans un tableau trié •Méthode : dichotomique ou " diviser pour régner » •Soit Tun tableau de N éléments et val l"élément cherché •T est trié •Sinon effectuer un prétraitement de tri. •Comparer valavec l"élément u milieu du tableau T. •Si c"est le même => trouvé •sinon on recommence sur la première moitié ou la seconde selon que val est valmidou val > valmid •Arrêt quand élément trouvé ou si fin de tableau (T[indice-1]) •Complexité : •T(n) nombre d"opérations sur un tableau de taille n •T(n) satisfait l"équation de récurrence T(n) = T(n/2)+1

MAP - UNS104

RECHERCHE DICHOTOMIQUE

Algorithme recherche_dichotomique

{Recherche le premier indice où se trouve la valeur val en utilisant la stratégie diviser pour régner }

variables T [0, N-1] , val entier lnf, Sup, N, Mi : entier

Début

Saisir(val)

Inf ← 0

Sup ← N-1

Mi ← (Inf + Sup)/2

tant que ( val <> T[Mi] && Inf <= Sup) faire si val < T[Mi] alors

Sup = Mid - 1

sinon

Inf = Mid + 1

fsi

Mi ← (Inf + Sup)/2

ftq si

T[Mi] = val alors

afficher( " l"élément se trouve en : » Mi); sinon afficher( " Elément non présent " ); fsi Fin

MAP - UNS105

PLAN DU COURS

•Introduction au langage C •Notions de compilation •Variables, types, constantes, •Tableaux, opérateurs •Entrées sorties de base •Structures de contrôle •Algorithmes de recherche •Algorithmes de Tri -Insertion-Fusion •Les pointeurs •Procédures et fonctions •les types composés •Allocation dynamique •Listes Chaînées

106MAP - UNS

ALGORITHMES DE TRI

•Objectif : Etant donné une suite de Nnombres de la ranger par ordre croissant (ou décroissant) •Différents algorithmes •Tri par sélection •Tri se fait en espace constant •Peu économe en temps (2 boucles for imbriquées ) •Boucle interne fait N-1 opérations •Boucle externe fait N-1 à itération 1, N-2 (itération 2) ... •Complexité 2*(N-1)+(N-2) +(N-3) ...+ 1 = (N+1)*N+N! ≈ N2 •Tri à bulles •Peu économe en temps (2 boucles for imbriquées ) •Complexité ≈ N2 •Tri rapide •Econome en temps •Complexité ≈ N*Log(N) •Algorithme récursif

MAP - UNS107

ALGORITHME DE TRI

•Objectif : Etant donné une suite de Nnombres de la ranger par ordre croissant (ou décroissant) •Méthode : Tri par sélection •Soit Tun tableau de N éléments •Rechercher le plus petit élément parmi les Net on l"échange à la fin avec le 1er •Puis recherche du plus petit parmi les N-1éléments restant et échange avec le

2ème

•... parmi N-k+1éléments restants échange avec le Kième

MAP - UNS108

7 8 9 2 0

0 8 9 2 7

0 2 9 8 70 2 7 8 9

TRI PAR SELECTION

Algorithme tri_selection

{ Ranger par ordre croissant(ou décroissant) une suite de Nnombres rangés dans un tableau T. } variables tab : tableau [0, N-1] de entier

N, i, j, indiceMin, ValMin : entier

Début

pour i = 0 àN-2 faire indiceMin ← i

ValMin ← T[i]

pourj = i +1 àN-1 faire si

T[j] < ValMinalors

indiceMin ← j

ValMin ← T[j]

fsi fpour T[indiceMin] ← T[i] { Echange des deux valeurs }

T[i] ← ValMin

fpour

FinMAP - UNS109

7 8 9 2 0

7 8 9 2 0

i=0 j=1j=2j=3j=4 indiceMin=0 ValMin=7 indiceMin=3 ValMin=2

IndiceMin=4 ValMin=0

T[0]=0

T[4]=7

i=1

ALGORITHME DE TRI

•Objectif : faire remonter les plus grandes valeurs en haut de tableau •Méthode : Tri à bulle •Soit Tun tableau de N éléments •Comparer 1erélément avec 2ème. Si 1er>2ème, échanger les deux éléments

•Comparer 2èmeélément avec 3ème. Si 2er>3ème, échanger les deux éléments

•... comparer N-2ièmeavec N-1 ième. Si N-2 ième> N-1ième,échanger les deux éléments.

•Recommencer à partir du début tant que vous avez opéré au moins à un échange

MAP - UNS110

5 1 4 2 8

1 5 4 2 8

1 4 2 5 8

TRI À BULLE

Algorithme tri_à_bulle

{ faire remonter les plus grandes valeurs en haut d"un tableau T de Néléments. } variables tab : tableau [0, N-1] de entier

N, i, j, temp : entier

nouvel_echange : booleen

Début

répéter nouvel_echange ←faux pouri = 0 àN-1 faire si

T[ i ] > T[i+1] alors

temp ← T[ i +1]

T[i+1 ] ← T[ i ]

T[ i ] ← temp

nouvel_echange ← vrai fsi fpour tant que nouvel_echange ==vrai Fin

MAP - UNS111

ALGORITHME D"INSERTION POSITION P

•Objectif : Ajouter un élément dans un tableau trié ou pas. Insertion n"est possible que si il reste de la place dans le tableau. L"Insertion est un décalage à droite des éléments du tableau •Méthode : Insertion Soit Tun tableau de taille de N éléments, On insère un

élément

Và un position p

•Variable k positionnée en fin de tableau •Copie de T[k] dans T[k+1] tant que k>=P •Qdk=pranger la valeur ven T[k] •Incrémenter N

5 1 4 2 8

pk

5 1 4 2 8 8

pk

5 1 4 2 2 8

pk

5 1 4 4 2 8

p k

5 1 v 4 2 8

p112MAP - UNS

INSERTION À UNE POSITION P

Algorithme INSERTION_POSITION_P

{ Insérer une valeur và une position pdans un tableau T de Néléments et de taille S}

Constantes S= 20

variables T : tableau [0, S-1] de entier

N, p , v, : entier

Début

{ Code d'initialisation des N éléments du tableau } Afficher(" entrez val à insérer et position p}

Saisir(p); Saisir(v);

si N < S alors pour k= N-1 àp pas-1 faire

T[k+1] ← T[k]

fpour

T[p] ← v

N ← N+1

sinon

Afficher ("Insertion impossible »)

fsi

FinMAP - UNS113

ALGORITHME D"INSERTION DANS

TABLEAU TRIÉ

•Objectif: Ajouter un élément dans un tableau trié ou pas. Insertion n"est possible que si il reste de la place dans le tableau. L"Insertion est un décalage à droite des éléments du tableau

•Méthode : Insertion Soit Tun tableau de taille de N éléments triés , On insère un élément V

•Variable k positionnée en fin de tableau •Copie de T[k] dans T[k+1] •tant que k>=0 && V>T[k] •QdT[k]1 2 4 5 8 k

1 2 4 5 8 8

k

1 2 4 5 5 8

k

1 2 4 4 5 8

k

1 2 v 4 5 8

114MAP - UNSk

INSERTION DANS UN TABLEAU TRIÉ

Algorithme INSERTION_V_dans_Tableau-Trié

{ Insérer une valeur và une position pdans un tableau T de Néléments et de taille Srangé

par ordre croissant}

Constantes S= 20

variables T : tableau [0, S-1] de entier

N, p , v, : entier

Début

{ Code d'initialisation des N éléments du tableau } Afficher(" entrez val à insérer} Saisir(v); si N < S alors tant que k>= 0 && T[k] > val faire

T[k+1] ← T[k]

k ← k -1 fpour

T[k+1] ← v

N ← N+1

sinon

Afficher ("Insertion impossible »)

fsi Fin

MAP - UNS115

ALGORITHME DE SUPPRESSION

POSITION P

•Objectif : Supprimer un élément dans un tableau trié ou pas. La suppression est un décalage à gauche des éléments du tableau •Méthode : Suppression Soit Tun tableau de taille de N éléments, On supprime un élément

Và un position p

•Variable kpositionnée à p+1 •Copie de T[k] dans T[k-1] tant que k5 1 4 2 8 pk

5 1 2 2 8

pk

5 1 2 8 8

pk

MAP - UNS

SUPPRESSION À UNE POSITION P

Algorithme SUPPRESSION_POSITION_P

{ Supprimer l"élément à une position pdans un tableau T de Néléments et de taille S}

Constantes S= 20

variables T : tableau [0, S-1] de entier

N, p , v, : entier

Début

{ Code d'initialisation des N éléments du tableau } Afficher(" entrez position p de l'élément à supprimer »)

Saisir(p);

pour k= p+1 àN - 1 faire

T[k-1] ← T[k]

fpour

N ← N-1

Fin

MAP - UNS117

SUPPRESSION D"UNE VALEUR V

Algorithme SUPPRESSION_VALEUR_V

{ Supprimer une valeur vdans un tableau T de Néléments et de taille S} variables T : tableau [0, S-1] de entier

N, p=0 , v, k : entier

Début

{ Code d'initialisation des N éléments du tableau }

Afficher(" entrez la valeur à supprimer »)

Saisir(v);

tant que T[p] <> val && p < N-1 faire p ← p +1 ftq si

T[p] == val alors

pour k= p+1 àN -1 faire

T[k-1] ← T[k]

fpour

N ← N-1

sinon

Afficher

(" valeur non trouvée ») fsi Fin

MAP - UNS118

quotesdbs_dbs31.pdfusesText_37

[PDF] recherche dichotomique recursive langage c

[PDF] exemple de manuel de procedure informatique

[PDF] organisation d une dsi type

[PDF] manuel de procédures informatiques

[PDF] cyberlux 8

[PDF] organisation dun service informatique dans une entreprise

[PDF] cyberlux 8 crack

[PDF] exemple dossier exploitation informatique

[PDF] cyberlux 8 full

[PDF] bibliographie de max weber

[PDF] max weber pdf

[PDF] max weber économie et société tome 2 pdf

[PDF] max weber le savant et le politique pdf

[PDF] max weber économie et société fiche de lecture

[PDF] max weber économie et société tome 1 résumé