Corrigé du TD 4 : recherche de l'élément majoritaire Écrivez un algorithme qui calcule le nombre d'occurrences d'une valeur x présentes entre les indices i
| Previous PDF | Next PDF |
[PDF] Algorithmique avancée Corrigé de lexamen du 29 janvier 2002
1 – Algorithme glouton de remplissage des faces d'une cassette Note sur la correction Toutes les questions suivantes dépendent de la formule établie `a cette
[PDF] TD dalgorithmique avancée Corrigé du TD 2 : récursivité
TD d'algorithmique avancée Corrigé du TD 2 : récursivité Jean-Michel Montrez que la complexité (en nombre d'additions) de cet algorithme est en Ω(2 n 2 )
[PDF] SUJET + CORRIGE
UE J1BS7202 : Algorithmique et Programmation Épreuve : Examen Date : Jeudi 19 Écrire un algorithme sontInvOuOpp(a,b) o`u a et b sont deux nombres,
[PDF] Algorithmique Avancée et Complexité Fiche TD correction
Algorithmique Avancée et Complexité 2010–2011 Master 1 d'Informatique S Tison Fiche TD correction : Algorithmes gloutons Exercice 1 : Optimal ? Q 1
[PDF] Corrigé de lexamen de rattrapage
Module ''Algorithmique Avancée et Complexité'' Date : 30/01/2012 Corrigé de l' examen de rattrapage
[PDF] Algorithmique avancée 2017 - Département Informatique
Matière 1 : Algorithmique avancée et complexité, écrire un algorithme non naïf de complexité minimale pour trouver dans Corrigé Exercice 1 :
[PDF] exercices corrigés algorithmepdf
Ecrire un algorithme qui demande à l'utilisateur un nombre compris entre 1 et 3 Réécrire l'algorithme précédent, mais cette fois-ci on ne connaît pas d'avance
[PDF] Exercices avec Solutions
En fait, le chargé du TD Exercices Corrigés d'Algorithmique – 1ére Année MI 5 Solution 3 : en utilisant une boucle Tantque + Lecture avant la boucle
[PDF] TD dalgorithmique avancée Corrigé du TD 4 : recherche de l
Corrigé du TD 4 : recherche de l'élément majoritaire Écrivez un algorithme qui calcule le nombre d'occurrences d'une valeur x présentes entre les indices i
[PDF] Algorithmique – Travaux Dirigés - AAATE
Corrigé Exercice 1 – Affectations 1 Considérons les algorithmes ci-dessous (a) Quel Algo – Corrigé TD – 1 il faut forcer la conversion en réel avant la divi-
[PDF] sujet d'examen de biologie animale
[PDF] qcm biologie animale s2
[PDF] examen biologie animale l1
[PDF] oscillateur harmonique quantique correction
[PDF] oscillateur harmonique quantique exercices corrigés pdf
[PDF] exercices corrigés mécanique quantique oscillateur harmonique pdf
[PDF] mécanique quantique solutions des examens corrigés
[PDF] examen corrige de mecanique quantique s5
[PDF] mecanique quantique exercices corrigés pdf s4
[PDF] examen pharmacologie générale
[PDF] exercices corrigés de pharmacologie générale
[PDF] qcm pharmacologie generale corrigé
[PDF] exercice pharmacologie infirmier
[PDF] qcm pharmacologie speciale pdf
TD d'algorithmique avancee
Corrige du TD 4 : recherche de l'element majoritaireJean-Michel Dischler et Frederic Vivien
Nous nous interessons a un tableauAdenelements,netant suppose ^etre une puissance de deux. Noussupposons egalement que la seule operation a notre disposition nous permet de verier si deux elements sont
ou non egaux. Un elementxdeAest dit majoritaire si et seulement siAcontient strictement plus den=2 occurrences dex. Nous nous interesserons a la complexite au pire.Algorithme naf1.Ecrivez un algorithme qui calcule le nombre d'occurrences d'une valeurxpresentes entre les indicesi
etjd'un tableauA.Occurrences(x,A,i,j) compteur 0 pourk iajfaire siA[k] =xalorscompteur compteur+ 1 renvoyercompteur2.Quelle est la complexite de cet algorithme?La boucle executeji+ 1iterations. La complexite de cet algorithme est donc en(ji).3.Au moyen de l'algorithme precedent, ecrivez un algorithmeMajoritairequi verie si un tableauA
contient un element majoritaire.Majoritaire(A) pouri 1alongueur(A)=2faire siOccurrences(A[i],A,i,longueur(A))>longueur(A)=2alors renvoyerVrai renvoyerFaux4.Quelle est la complexite de cet algorithme? Dans le pire cas, la boucle eectuen=2iterations, chacune de ces iterations eectuant un appel a Occurrencessur un tableau de tailleni(ivariant de 1 an) donc de co^ut(ni). Le co^ut total de l'algorithme est donc en(n2).Premier algorithme
Justications
Les deux seuls cas qui ne sont peut-^etre pas immediats sont les suivants :(a)rx=Fauxetry=Faux: dans ce cas il n'y a pas d'element qui soit majoritaire dans la premiere
moitie du tableau, ni d'element qui soit majoritaire dans la deuxieme moitie du tableau. Si le table contientnelements, le nombre d'occurrences d'un element quelconque dans la premiere moitie du tableau est donc inferieur ou egal a n22|la premiere moitie ayantn2elements| et il en va de m^eme pour le deuxieme moitie. Donc le nombre d'occurences d'un element quelconque dans le tableau est inferieur an2et le tableau ne contient pas d'element majoritaire.(b)rx=Vraietry=Vraiavecx=y: dans ce casxest present au moins1+n4fois dans chacune
des deux parties |qui sont de taille n2| et donc au moins2 +n2fois dans le tableau.2.Quelle est la complexite de cet algorithme? La complexite de cet algorithme est denie par la relation de recurrence :T(n) = 2Tn2
+ (n): En eet, la phase de combinaison necessite, dans le pire des cas, la recherche du nombre d'occurences de deux elements dans le tableau, ce qui a un co^ut den, toutes les autres operations etant de co^ut constant ((1)). Nous avons donc ici :a= 2,b= 2etf(n) = (n) == (nlog22). Nous sommes donc dans le cas 2 du theoreme et donc :T(n) = (nlogn):
Deuxieme algorithme
tableauA|qu'il divisera en deux| et possedant la propriete suivante :{soit cet algorithme nous garantit que le tableauAne contient pas d'element majoritaire;{soit cet algorithme nous renvoie un elementxet un entiercx> n=2 tels quexapparaisseau pluscx
fois dansAet que tout autre element deAapparaisseau plusncxfois dansA.PseudoMajoritaire(A,i,j) sii=jalors renvoyer(Vrai,A[i], 1)2 (rx,x,cx) Majoritaire(A,i,i+j12) (ry,y,cy) Majoritaire(A,i+j+12,j) sirx=Fauxetry=Fauxalors renvoyer(Faux, 0, 0) sirx=Vraietry=Fauxalors renvoyer(Vrai,x,cx+ji+14) sirx=Fauxetry=Vraialors renvoyer(Vrai,y,cy+ji+14) sirx=Vraietry=Vrai alors six=y alors renvoyer(Vrai,x,cx+cy) sinon sicx=cy alors renvoyer(Faux, 0, 0) sinon sicx> cy alors renvoyer(Vrai,x,ji+12+cxcy) sinon renvoyer(Vrai,y,ji+12+cycx)Justications
Nous considerons un par un les dierents cas de gure :{rx=Fauxetry=Faux. Aucun element n'appara^t strictement plus den4fois dans la premiere
(resp. la deuxieme) moitie du tableauA. Donc un element quelconque deAappara^t au plusn4fois dans chacune des deux moities, et donc n2fois en tout dansA. DoncAne contient pas d'element majoritaire.{rx=Vraietry=Faux. Un element quelconque deAappara^t doncau plusn4fois dans la deuxiememoitie deA. Nous avons deux cas a considerer :{xappara^t donc au pluscx+n4fois dansA.{Un element autre quexappara^tau plusn2cxfois dans la premiere moitie deA. Par consequent
un tel element appara^t au plusn2cx+n4=3n4cx=ncx+n4fois dansA.D'ou le resultat.{ry=Vraietrx=Faux: ce cas est symetrique du precedent.{rx=Vraietry=Vrai:{x=y.xest presentau pluscx+cyfois dansA. De plus, tout autre element est presentau plus
n2cxfois dans la premiere moitie deAetn2cyfois dans la deuxieme moitie, soit en toutau plusn(cx+cy)fois dansA.{x6=yetcx=cy.xest presentau pluscxfois dans la premiere moitie etn2cy=n2cx fois dans la deuxieme moitie, soitn2fois en tout etxn'est pas un element majoritaire deA. Symetriquement, il en va de m^eme dey. Tout autre element ne peut ^etre un element majoritairequotesdbs_dbs3.pdfusesText_6