Universite d'Orleans Avril

Publié par

Niveau: Supérieur, Master, Bac+5
Universite d'Orleans 2 Avril 2012 Departement de Mathematiques L4MA02 Feuille d'exercices n0 4 Exercice 1 Soit M ?Mn(R) symetrique. Montrer que Trace(M2 +M + 1) ≥ 3n 4 . Exercice 2 Soit A une matrice symetrique reelle satisfaisant Ak = Id pour un entier k ≥ 1. Montrer qu'alors A2 = Id. Que peut-on dire de plus si k est impair ? Exercice 3 Soit E = Mn(R) muni du produit scalaire defini par : < M,N >= Trace( tMN). Pour tout B ? E, on designe par LB l'operateur sur E de multiplication a gauche par B : LB(M) = BM pour tout M ? E. a) Determiner l'adjoint de LB . b) En deduire que LB ? O(E) si et seulement si B ? On(R). Exercice 4 Soient n ≥ 3 et A ?Mn(R) definie par aij = { 1 si i = n ou j = n 0 sinon a) Determiner le rang de A et son noyau. b) Determiner les elements propres de A. Exercice 5 Soit A ?M2n+1(R) definie par aij = { 1 si i = n+ 1 ou j = n+ 1 0 sinon Determiner le spectre de A (On pourra determiner rang(A) et calculer A2.

  • lb

  • adjoint de lb

  • base orthonormale

  • phisme orthogonal

  • feuille d'exercices n0

  • lb ?


Publié le : dimanche 1 avril 2012
Lecture(s) : 29
Source : univ-orleans.fr
Nombre de pages : 3
Voir plus Voir moins
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
Exercice 3:Chemins de longueur minimale Onutiliselesemi-anneaudesr´eelspourtraiterlescheminsdelongueurminimaldansungraphe. SoitAetBdeux matricesn×n[s0dsnaeitnœcc`a..M]∪ {∞}. On veut calculer la matriceCde cœfficients cik= min(aij+bjk). 1jn 3 1. Montrerque l’algorithme classique fonctionne enO(nlogM). 2.Onpeutame´liorerunpeucetalgorithmeenutilisantlefaitquepoura6=b, a bmin(a,b) lim (x+x)/x= 1 x0 a b et donc min(a, b) = log(x+x)/logxpourxpetit. P n b k (a) Soitb1, . . . , bn,nentiers positifs, et soitf(x) =xeta= min(b1, . . . , bn). Montrer k=1 m alors quea=d−(1/m) logf(2 )epour toutm >logn. (b)Soitunr´eel0< x <1 etzerideiobnabnmitneolezn´tearrr´eedseatrˆeeptoesdeelnx. Alors d−(1/m) logxe= 1 +bz/mc. (c) Donnerun algorithme qui calcule le (min,+)-produit de deux matricesAetBrate´sdecneevse log 7log 72 dans [0..M]∪ {∞}enO(niqetm´thleurssueare´po)irasnoitrse´leosuO(n(Mlogn) ) op´erationsbinaires. 3. Comparerles deux algorithmes et donner la valeur deMpour laquelle le premier algorithme est plus efficace. 4.Est-cequecetalgorithmeestplusrapidequandilsagitdematricesboole´ennes?
Exercice 4:2eS-`lmeobPrTA Soitx1, . . . , xnun ensemble denpsraelestneisriravelbaoobseel´esnndeineex´n.Unlitt´eral sur cet ensemble de variables est une variablexiintigaonsuo,e´na¬xi. Une 2-clause sur cet 0 ensembledevariableestunedisjonctiondedeuxlitt´eraux``. Une assignationτest une fonction de l’ensemblex1, . . . , xndans{0,1}itt´unleurdavalL.rela`ioatgnsiasneaut`menetavirlenτ, soit V(`, τatgsee´)a`elτ(xi) si`=xiea1t`τ(xi) si`=¬xi. La valeur d’une clauseca`tnemevrelati une assignationτ, soitV(c, τleuresvaesdesdestsel)e,umdmamixAS-2Tlboreme`uxraep.Lliux´ett s´enoncecommesuit: ´ Etantdonne´unentiernet une liste de 2-clauses sur l’ensemble de variablesx1, . . . , xne´ndtrerei,m s’il existe une assignationτennodiuqsetuota`uslascleliladeestslevalaue1rp(orbl`emeded´ecisio.)n Calculer une telle assignation si elle existe (calcul d’une solution).
1.Onassociea`unelistede2-clausessurlensembledevariablesx1, . . . , xnrieot´ennguphraeGdont 0 lessommetssontleslitte´rauxsurlensembledevariablesx1, . . . , xn. Pour chaque clause``, 0 0 onajoute`aGuarneteˆelaaltned¬`a``rˆeteallantdetenuae¬``a`eosnpuoo`(¬¬xi=xi). (a) Montrerque l’on peut calculerGen tempsO(n+m`u)onest le nombre de variables etm lenombredeclauses.Onexpliciteraunchoixdestructuresdedonn´eesetonproposeraune description de l’algorithme en terme de pseudo-code.
2
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.