Cherchez et vous trouverez car qui cherche trouve

pefav

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

16 pages

Français

Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

A propos
Informations
Extrait

Description

CHAPITRE V Recherche et tri Cherchez et vous trouverez, . . . car qui cherche trouve. Matthieu 7 7-8 et Luc 11 9-10 Objectif. Comprendre les techniques de base pour organiser des donnees ordonnees. Ce chapitre discute quelques methodes de recherche et de tri. Les applications sont abondantes ; imagi- nez par exemple a quel point un dictionnaire serait difficile a utiliser si les mots cles n'etaient pas ordonnes ! Ils le sont, heureusement, car l'editeur a pris le soin de les trier. Vous en profitez en appliquant une methode efficace de recherche. Le projet a la fin de ce chapitre illustre une application moins evidente : la recherche des solutions d'une equation diophantienne (par exemple x4 + y4 + z4 = w4 avec x,y,z,w ? Z+). Sommaire 1. Recherche lineaire vs recherche dichotomique. 1.1. Recherche lineaire. 1.2. Recherche di- chotomique. 1.3. Attention aux details ! 2. Trois methodes de tri elementaires. 2.1. Les plus petits exemples. 2.2. Tri par selection. 2.3. Tri par transposition. 2.4. Tri par insertion. 2.5. En sommes-nous contents ? 3. Diviser pour trier. 3.1. Le tri fusion. 3.2. Analyse de complexite. 3.3. Le tri rapide. 3.4. Ana- lyse de complexite.

methode de tri de complexite quadratique

ana- lyse de complexite

methodes

methodes optimales de tri

Sujets

Google

dictionnaire

exercice

mathe

exercices

Informations

Publié par	pefav
Nombre de lectures	70
Langue	Français

Extrait

CHAPITRE V

Recherche et tri

Cherchez et vous trouverez, . . . car qui cherche trouve. Matthieu 7 7-8 et Luc 11 9-10

Objectif. Comprendrelestechniquesdebasepourorganiserdesdonn´eesordonne´es. Cechapitrediscutequelquesm´ethodesderechercheetdetri.Lesapplicationssontabondantes;imagi-nezparexempleaquelpointundictionnaireseraitdifcielautilisersilesmotscle´sn'´etaientpasordonn´es! Ils le sont, heureusement, car l'e´diteur a pris le soin de le s trier .Vousenprotezenappliquantunem´ethode efcace de recherche .Leprojetalandecechapitreillustreuneapplicationmions´evidente:larecherche dessolutionsd'une´equationdiophantienne(parexemple x 4 + y 4 + z 4 = w 4 avec x  y  z  w ∈ Z + ). Sommaire 1.Recherchelin´eairevsrecherchedichotomique. 1.1.Recherchelin´eaire.1.2.Recherchedi-chotomique. 1.3. Attention aux de´tails ! 2.Troism´ethodesdetrie´l´ementaires. 2.1. Les plus petits exemples. 2.2. Tri par se´lection. 2.3. Tri par transposition. 2.4. Tri par insertion. 2.5. En sommes-nous contents ? 3. Diviser pour trier. 3.1. Le tri fusion. 3.2. Analyse de complexite. 3.3. Le tri rapide. 3.4. Ana-´ lyse de complexite´. 4.Fonctionsg´eneriques. 4.1.Lescalamit´esdelare´´ecritureinutile.4.2.L'usagedesfonctions ´ g´en´eriques.4.3.Imple´mentationderechercheettrienC++. 5. Solutions fournies par la STL. 5.1. Algorithmes de recherche et tri. 5.2. La classe ge´ne´rique set.5.3.Lesit´erateurs. Exemple 0.1. Lesdeuxproblemesfondamentaux,trietrecherche,peuvetnseformulerainsi: (1)Trierunelistedonn´eeand'´etablirl'ordre a 1 ≤ a 2 ≤    ≤ a n . (2)Chercherun´ele´ment b dans une liste ordonne´e ( a 1 ≤ a 2 ≤    ≤ a n ) . Ajoutonsqueletrir´esoutbiend'autresproblemesconcernantleslistes,apriorinontri´ees: (3)Trouverlese´l´ementsdoublesdansuneliste(problemedemultiplicite´). (4)Ve´riersideuxlistessontlesmˆemesapermutationpres(problemed'anagramme). (5)Trouverlam´edianed'unelonguelistedevaleursr´eelles(problemederang). Remarque 0.2 . D.E. Knuth dans The Art of Computer Programming discute diverses me´thodes de tri dans le tome 3, intitule´ Sorting and Searching . Tout au de´but il fait le constat suivant, toujours valable de nos jours : Computer manufacturers estimate that over 25% of the running time on their computers is cur-rently being spent on sorting (. . .) We may conclude that (i) there are many important applications of sorting, or (ii) many people sort when they shouldn't, or ( iii) inefcient sorting algorithms are in common use. The real truth probably involves some of all three alternatives. In any event we can see that sorting is worthy of serious study, as a practical matter. Cechapitretented'expliquerpuisdecomparerdiffe´rentesm´ethodesderecherche( § 1) et de tri ( § 2 § 3). Lesexercicesmath´ematiquespermettrontd'e´tablirlacorrectiondesme´thodespropose´esetdecomparer leurperformance.Cettepartiepeutsemblerunpeuthe´oriquemaiselleesttresb´en´equepourcomprendre cequ'estl'algorithmique.Lamoralearetenir:pr´ef´ererlesbonsalgorithmesauxsolutionsna¨ves! + Si vous ˆetes impatient ou insouciant, vous pouvez lire la recherche dichotomique (algorithme V.2) puis letrifusion(algorithmeV.6)etletrirapide(algorithmeV.7),andepasserdirectemental'impl´ementation ( § 4). En § 5 nous regardons brievement quelles solutions offre la STL. 83