7 jours d'essai offerts
Cet ouvrage et des milliers d'autres sont disponibles en abonnement pour 8,99€/mois
TD 4
Algorithmique
Exercice 1:Coupe minimale dans un graphe SoitGsegnuhparnecteconon-o´e,n´taeirneveneev´cmeleeltuieusplntteˆrasrulertnesensommets. UnecoupedansGestunensteˆruqselbmeadel`ene,evioisesnlGdevient non-connexe. Unecoupe minimaletedevuornureuocealimLee.obpreml`pemaximaleestdepuocenutseinemt´linadiarec NP-complet. Lide´edelalgorithmeestdechoisiruniform´ementuneareˆteetdefusionnerlesdeuxsommets enunseulsommetenmettantsurcesommetlesarˆetesquiarrivaientauxdeuxsommetsinitiauxet enenlevantlesboucles.Onappellecetteop´erationunecontractionilesemmˆephraegO.qteuvnio initialnavaitquuneseulearrˆeteentrechaquesommet,legrapheayantsubiunecontractionpeut encontenirauplusdeux.Ceprocessusdiminueduneunit´elenombredareˆte.Lalgorithmeeectue descontractionsjusqu`acequelenombredesommetssoite´gala`2etretournecommevaleurle nombredareˆtesentrecesdeuxpoints.
1.Montrerquunecontractiondarˆetenediminuepaslavaleurdunecoupeminimale. 2. Soitkla valeur d’une coupe minimale. Montrer queGa au moinskn/ra2teˆes. 3. SoitEirunearˆetaesdcehoisinedtnepee´´vnemelCa`ali-i`emeuo1re´atepp,in2. (a) Montrerque Pr[E1]12/n. i1 (b) Montrerque Pr[E2|E1]12/(nenemalern´´esglue)pt1[rPeuqtEi|∩ Ej]12/(ni+1). j=1 2 (c)Montrerquelaprobabilite´trouverunecoupeminimaleparceproce´d´eestaumoins. n(n1) 4.Montrercommentobtenirunalgorithmedontlaprobabilite´de´checsoit<1/eet donner sa complexit´e.
Exercice 2:nusnadevitisnartretuˆoClhegrap 3 1.RappelerlalgorithmedeFloyd-WarshallpourcalculerlaclˆoturetransitiveenΘ(n) en temps. 2.Montrerquesilexisteunalgorithmequicalculelacloˆturetransitivedunematricen×nenA(n) additions,multiplicationsde´l´ementsdunsemi-anneauetsiA(3n)cA(nnu´reel)opruc >0 et toutnentier positifs, alors il existe un algorithme de multiplication avecM(n) =O(A(n)) additions et multiplications. 3. Montrerque si le produit de deux matricesn×nutpentreˆeela´lceucM(n) additions et mul-tiplications et si 4M(n/2)M(n) etM(2n)cM(n) pour uncet toutncalstoˆl,rolaure transitive se calcule enA(n) =O(M(n)) additions et multiplications. 4.Montrerquelesemi-anneaubool´eenB= ({0,1},,,0,1) n’est pas un anneau. log 72 5. SoitAetBdeux matricesn×nptuestcelaucbeoloelr´eeennes.LeproduinO(n(logn=) ) 2.82 O(neualsnqiuterlcoˆsbintions,aiairepo)are´tisiantr.ve