[PDF] [PDF] Recherche dichotomique - Unisciel

[PDF] Lalgorithme de dichotomie - IREM dAix-Marseille

L'algorithme de dichotomie Henri ROLAND On obtient ainsi l'algorithme suivant N←− Nombre Programmation sur TI 82 Programmation en Python 2 6

[PDF] Zéros de fonctions - Exo7 - Cours de mathématiques

Voici comment implémenter la dichotomie dans le langage Python Tout d'abord on return a,b Enfin, voici la version récursive de l'algorithme de dichotomie

[PDF] TP : algorithme de dichotomie

Vous pouvez utiliser GEOGEBRA pour vérifier vos résultats Utiliser la console PYTHON pour trouver un encadrement de 0,0001 Modifier la fonction utilisée dans 

[PDF] Informatique en CPGE (2018-2019) Résolution dune équation

méthodes de dichotomie et de Newton Algorithme : les variables sont a et b, les bornes de l'intervalle, f la fonction (qui change Un programme en Python :

[PDF] [TP5] Python Algorithmiquepdf

RECHERCHE PAR DICHOTOMIE DANS UN TABL ▫ PRINCIPE : Lors du précédent TP, nous avons mis en œuvre un algorithme d Dans le pire des cas, pour 

[PDF] Algorithme de dichotomie permettant dencadrer une solution dune

L'algorithme suivant permet d'afficher un encadrement à e près de la solution de l 'équation f(x) = 0 dans l'intervalle [a,b], a, b et e étant saisis par l'utilisateur et 

[PDF] Recherche dichotomique - Unisciel

Python - Recherche dichotomique (Solution) Mots-Clés Cet exercice réalise l' algorithme de la recherche dichotomique, prouve l'algorithme et calcule sa 

[PDF] Recherche de racine par dichotomie

Programmer en Python Exercice 2 - Recherche de racine par dichotomie Implémenter l'algorithme de Newton pour trouver la racine d'une fonction réelle

[PDF] algorithm better than k means

[PDF] algorithm lecture

[PDF] algorithme d'euclide bezout

[PDF] algorithme d'euclide casio

[PDF] algorithme d'euclide étendu python

[PDF] algorithme d'euclide pgcd

[PDF] algorithme d'euclide pgcd python

[PDF] algorithme d'euclide polynome

[PDF] algorithme d'euclide python

[PDF] algorithme de dijkstra arduino

[PDF] algorithme de dijkstra c++

[PDF] algorithme de dijkstra en ligne

[PDF] algorithme de dijkstra java

[PDF] algorithme de dijkstra javascript

[PDF] algorithme dichotomie python

Recherche dichotomique [re04] - Exercice

Karine Zampieri, Stephane Riviere

UniscielalgoprogVersion 21 mai 2018

Table des matieres

1 Algorithme de la recherche dichotomique

2

2 Algorithmique, Programmation

2

2.1 Rappel : Representation et operations

2

2.2 Sequence d'elements

3

3 Preuve et complexite

4

4 References generales

6 Python - Recherche dichotomique (Solution)Mots-ClesAlgorithmes de recherche RequisAxiomatique imperative sauf Fichiers, Preuve et Notations asymptotiques

FichiersUtilsRech

Diculte• ◦ ◦Objectif

Cet exercice realise l'algorithme de la recherche dichotomique, prouve l'algorithme et calcule sa complexite. Dans le m^eme ordre d'idees, l'exercice @[Recherche sequentielle] construit un algorithme dans le cas ou le multi-ensemble n'est pas trie. 1 Unisciel algoprog { Recherche dichotomique [re04]2

1 Algorithme de la recherche dichotomique

Soit une structure tabulaireA[1..n]triee en ordre croissant. On eectue une recherche dichotomique d'une valeurxcomme suit.

Soient :

•gl'indice de gauche initialise a 1. •hl'indice de droite initialise an. •trouvele booleen de la recherche initialise aFaux. •ml'indice milieu de l'intervalle[g..h].

Alors :

1.

S iA[m]=xalors on xetrouveaVrai.

2. S inonsi A[m]Dans le cas contraire, on xehenm-1(carA[m]>x). 3. O nr epetel eso perations( 1)et ( 2)ju squ'ac eq uetrouvesoitVraiou quegsoit plus grand queh.2 Algorithmique, Programmation

2.1 Rappel : Representation et operationsSoientla denition et les operations de base sur uneSequence:Soientla denition et les operations denies sur uneSequence:MAXELEMS= ... # Taille maximale de la Sequence

classSequence:self.taille= ... # nombre d "élémentsdans la Sequence

defieme(self,k):# Valeur du k -ièmeé lémentde la Sequence A deffixerIeme(self,k,valeur):# Fixe la valeur du k -ièmeé lémentde A à valeur defafficherSeq(self):# Affiche la Sequence A defsaisirSeq(self):# Saisie une Sequence dans A defpermuterSeq(self,j,k):# Permute les é lémentsen position j et k de A Telechargezle chier suivant et mettez-le dans votre dossier.

Python@[Sequence.py]

Unisciel algoprog { Recherche dichotomique [re04]3Copiez/collezensuite la ligne suivante :

Python

Au d ebutde votre programme :fromSequenceimportSequence

2.2 Sequence d'elements

On considere un multi-ensemble represente par le typeSequence(structure tabulaire) sur lequel est deni une relation d'ordreUnisciel algoprog { Recherche dichotomique [re04]4initialisationn iteration 1n iteration 2n iteration 3

g1166 h1010107 m-586

A[m]-122215

trouveFFFV Comment faut-il modier l'algorithme si l'on n'est pas s^ur quexappartienne a la se- quence?Aide simple Il faut ajouter la possibilite de terminer la boucle quandg>hce qui signie quexn'est

pas dans la sequence.Copiez/collez la fonctionrechDicho1en la fonctionrechDicho2(A,x)puis modiez-la de

sorte que la fonction renvoie-1en cas de recherche infructueuse.Validez votre fonction avec la solution.

Solution Python@[pgdichoseq.py]defrechDicho2(A,x):trouve= False g h = 0, A taille -1 m = -1 while(g<= h andnot trouve):m= ( g+h)//2 if(A.ieme(m) ==x ):trouve= True elif(A.ieme(m) 3 Preuve et complexite On considere une structure tabulaireAtrie.Indiquez un invariant de boucle pour cet algorithme. Unisciel algoprog { Recherche dichotomique [re04]5Solution simple Considerons l'invariant de boucle suivant :.

L'invariant precedent s'ecrit :

soit :A[mk] =xettrouvek=V rai Cet invariant n'est vrai que si le tableauAest trie et sixest bien un element du tableau. Il permet de prouver a la fois la terminaison et la validite de l'algorithme. En eet, a chaque iteration : •Soit on a trouve la valeurx. •Soit on obtient un intervalle strictement plus petit que celui de l'iteration prece- dente, dont on est s^ur qu'il contient la valeurx. Au pire, l'algorithme se terminera

sur un sous-tableauA[gk..hk]reduit a un seul element avecA[gk] =A[hk] =x.On suppose que le tableau contientn= 2kelements (oukest un entier positif).

Combien d'iterations l'algorithme eectuera-t-il au maximum?Solution simple A chaque iteration, l'algorithme compare la valeurxavec l'element central du tableau A g h ]. Si ces deux elements sont dierents, a l'iteration suivante le tableau de travail est de taille inferieure a la moitie de celle de l'iteration courante. Exemple : pourk=3et x =8avecA=[1,2,3,4,5,6,7,8], l'execution de l'algorithme passera par les sous-tableaux : [...,5,6,7,8]puis[ ...,7,8]puis[...,8]et eectuera donckboucles avant de tomber sur un sous-tableau de longueur 1 contenant forcement la valeurx=8. Dans le cas general, on peut facilement prouver que l'algorithme eectuera au maximum

k= log2n= lgniterations pour arriver a un tableau de taille 1.Deduisez la complexite enOde l'algorithme.Solution simple

D'apres la question precedente l'algorithme est donc en

O(k) =O(lgn)?O(logn)

La complexite de la recherche dichotomique d'existence dexdansAest donc logarithmique si les comparaisons entreElements s'eectuent en temps constant. Si ces comparaisons sont eectuees en temps lineaire, la complexite de la recherche dichotomique est presque

lineaire,O(klog2n), oukest la complexite de la comparaison dexavec unElements.Comparez les complexites des algorithmes de recherche sequentielle et dichotomique pour

k= 100. Calculez les temps d'execution pour une machine capable d'eectuer 1 million de boucles en 1 seconde. Unisciel algoprog { Recherche dichotomique [re04]6Solution simple Pourk= 100(et dans le pire des cas) l'algorithme sequentiel eectuera2100≈1030 iterations alors que l'algorithme dichotomique n'en eectuera que100. Si l'on considere une machine capable d'eectuer 1 million de boucles en 1 seconde, l'algorithme sequentiel prendra3×1016annees de calcul alors que l'algorithme dichotomique fournira le resultat en moins d'une milliseconde.

4 References generales

Comprend[Felea-PG1 :c3 :ex77]

quotesdbs_dbs7.pdfusesText_13