[PDF] PLAN DU COURS ALGORITHME DE RECHERCHE PDF C5

12 mar 2013 · Objectif : Rechercher une information dans un tableau trié • Méthode sinon on recommence sur la première moitié ou la seconde selon que val est < à valmid ou val > valmid Tri se fait en espace constant • Peu économe

Exercices conseillés En devoir Exercices conseillés En devoir Deux droites de l'espace sont dites coplanaires lorsqu'elles sont incluses dans un même plan

[PDF] Cours de mathématique Seconde partie Élémens - Gallica - BnF

feconde Parde r~ Cours de Mathématiquedans lequel j'ai L'Espace renferméentre unArc ~B deux Rayons Pourdémontrerqueles Tri angles B D E, BA C,

[PDF] Mathématiques Classe de seconde - Laboratoire Analyse

doivent être introduits au cours du traitement d'une question en fonction de leur Il importe donc tout particulièrement que la géométrie dans l'espace soit rencontrées : recherche du pgcd de nombres très grands, tri d'un très grand http://www ac-greno le fr/maths/docresseconde/doc_ressource_clg_pro a ilites pdf

[PDF] Leçon 903 : Exemples dalgorithmes de tri Correction et - Index of

L'implémentation d'algorithme de tri fait apparaître de nombreux problèmes langage des probabilités, il importe que le candidat sache sur quel espace probabilisé simplement le tableau de départ (tri fusion) tandis que le second combine

[PDF] Cours dalgèbre linéaire, 2 ème année duniversité - Institut de

La seconde année d'université est d'une richesse extraordinaire : en maitriser les III Espaces et valeurs propres d'un endomorphisme Exercice 2 2 ƒur le ™ orps K soit A une m—tri™e (p, q)D X et Y des m—tri™es ™olonnes d9ordre

[PDF] Les principes fondamentaux de la géométrie - Numdam

les droites et les plans, éléments de la Géométrie de V espace ou éléments trie plane, nous pouvons donc, pour abréger, les nommer axiomes planaires du dans le plan a des droites dont tout le cours a lieu à l'extérieur du polygone; mais Récipro- quement, du théorème VIII résulte également la seconde affirmation

[PDF] Géométrie affine

8 nov 2011 · 1 Cours 1 1 Espace affine Une fois qu'on a choisi un repère, le plan s'identifie à R2 (resp l'espace à R3), rentielle linéaire avec second membre constitue un espace affine de direction l'espace tries centrales de centres A et B, et u = format pdf est largement issu, leur a accordé une grande place

[PDF] Algèbre linéaire – Cours I Espaces vectoriels

L'algèbre linéaire est l'étude des propriétés des espaces vectoriels et de tous les concepts construits Exercice Donner des vecteurs de l'espace tels que le sous- espace qu'ils engendrent est le en secondes et f en mètres, l'aire I est en m s L 'expression de I aussi Par ailleurs (S”) : L'unique solution est le tri- plet (u, v

[PDF] PLAN DU COURS ALGORITHME DE RECHERCHE

[PDF] SUJET + CORRIGE

doivent être respectées – L'espace laissé pour les réponses est suffisant (sauf Dans cet exercice, nous allons adapter des algorithmes de tri vus en cours afin

[PDF] les rapports logiques cours

[PDF] l'ordre judiciaire

[PDF] al kashi exercices

[PDF] relations métriques et angulaires dans le triangle capes

[PDF] relation angulaire triangle

[PDF] théorème de la hauteur relative ? l'hypoténuse

[PDF] optimisation des formes et des volumes

[PDF] surfaces d’échanges

[PDF] objet technique et matière vivante

[PDF] décrivez la vie d'un mouvement de résistance libération-sud

[PDF] cours capes maths

[PDF] structure de la rétine 1ere s

[PDF] histoire des relations publiques pdf

[PDF] qu'est ce que les relations publiques pdf

[PDF] les relations publiques en entreprise 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

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

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

5 1 4 2 8 8

5 1 4 2 2 8

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

1 2 4 5 5 8

1 2 4 4 5 8

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 -1quotesdbs_dbs7.pdfusesText_13

[PDF] [PDF] PLAN DU COURS ALGORITHME DE RECHERCHE

PLAN DU COURS

101MAP - UNS

ALGORITHME DE RECHERCHE

MAP - UNS102

RECHERCHE SÉQUENTIELLE

Algorithme recherche_sequentielle

Débutindice ←0

T[indice] = val alors

MAP - UNS103

7 1 15 8 2

ALGORITHME DE RECHERCHE

MAP - UNS104

RECHERCHE DICHOTOMIQUE

Algorithme recherche_dichotomique

Début

Saisir(val)

Inf ← 0

Sup ← N-1

Mi ← (Inf + Sup)/2

Sup = Mid - 1

Inf = Mid + 1

Mi ← (Inf + Sup)/2

T[Mi] = val alors

MAP - UNS105

PLAN DU COURS

106MAP - UNS

ALGORITHMES DE TRI

MAP - UNS107

ALGORITHME DE TRI

2è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

N, i, j, indiceMin, ValMin : entier

Début

ValMin ← T[i]

T[j] < ValMinalors

ValMin ← T[j]

T[i] ← ValMin

FinMAP - UNS109

7 8 9 2 0

7 8 9 2 0

IndiceMin=4 ValMin=0

T[0]=0

T[4]=7

ALGORITHME DE TRI

MAP - UNS110

5 1 4 2 8

1 5 4 2 8

1 4 2 5 8

TRI À BULLE

Algorithme tri_à_bulle

N, i, j, temp : entier

Début

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

T[i+1 ] ← T[ i ]

T[ i ] ← temp

MAP - UNS111

ALGORITHME D"INSERTION POSITION P

élément

Và un position p

5 1 4 2 8

5 1 4 2 8 8

5 1 4 2 2 8

5 1 4 4 2 8

5 1 v 4 2 8

INSERTION À UNE POSITION P

Algorithme INSERTION_POSITION_P

Constantes S= 20

N, p , v, : entier

Début

Saisir(p); Saisir(v);

T[k+1] ← T[k]

T[p] ← v

N ← N+1

Afficher ("Insertion impossible »)