MAT432 Corrige du controle Classant du Novembre

Description

MAT432 : Corrige du controle Classant du 4 Novembre 2004 Exercice I Les hypotheses sur n et ? montrent aisement que l'integrale converge. On choisit la determination principale du loga- rithme c'est-a-dire definie surC\]0,?∞[ et dont l'argument varie entre ?pi et pi. On en deduit la determination de la puissance ?. La fonction f(z) = z ? 1+zn est holomorphe sur C\]0,?∞[ prive de ses poles e(2k+1) ipi n . Soit ? > 0 et ?? l'arc de cercle de rayon ? et d'angle compris entre 0 et 2pi/n, ? ? ? ∫ ?? z? 1 + zn dz ? ? ? ≤ 2pi? n ?? |1? ?n| . Les hypotheses sur ? montrent que cette integrale tend vers 0 lorsque ? tend vers 0 ou bien vers +∞. Le theoreme des residus applique au contour decrit lorsque r tend vers 0 et R tend vers +∞ donne alors, ∫ +∞ 0 x? 1 + xn dx? ∫ +∞ 0 (xe2ipi/n)? 1 + (xe2ipi/n)n e2ipi/ndx = 2ipiRes(f ; eipi/n) c'est-a-dire, (1? e 2ipi n (?+1)) ∫ +∞ 0 x? 1 + xn dx = 2ipiRes(f ; eipi/n

• courbes ?


• hypotheses sur ?


• arc de cercle de rayon ? et d'angle


• nom- bre de solutions de l'equation


• hu ?

Informations

• Publié par: pefav
• Publié le: 01 novembre 2004
• Nombre de lectures: 90
• Langue: Français

Extrait

Epreuve d’informatique

sujet 2004 – Solution

Presentation du sujet ´ L’objetdelapremi`erepartieestdetrouverunalgorithmeline´airepourleproble`me d’accessibilit´edanslesgraphesET/OU.Ceproble`meseretrouvesousdiversesformesdans lalitte´rature,parexempleleproble`meduvidepourlesautomatesd’arbres,leprobl`emede satisfaisabilite´d’unensembledeclausesdeHornpropositionnellesouencore(danssaversion accessibilite´re´pe´te´e)leprobl`emeduvidepourlesautomatesdeB¨uchialternants.Ceproble`me d’accessibilit´estaussiunprototypedeprobl`emePTIME-complet.Lapremie`repartiepeut e eˆtrecomple´t´eepardesproble`mesd’accessibilit´ere´p´ete´edediversesformes,correspondant auxconditionsd’acceptancepardesautomatesdemotsinfinis.Cesquestionsn’ontpase´t´e inclusespourgarderun´enoncecourt. ´ Ladeuxi`emepartieestconsacr´eeauxautomatesalternantsdemots,dansuneversion tressimple.Uned´efinitionplusjolie(etaussipluspratique)desautomatesalternantspermet ` destransitionsversdescombinaisonsboole´ennespositives(oumemearbitraires)d’´etats. ˆ Nousavonspre´f´ere´icinouslimiteradesconjonctionsoudesdisjonctionsd’e´tatspour´eviter ` d’avoira`utiliserlarelationdesatisfactionencalculpropositionnel.Laquestion10montre quelecompl´ementairepeutˆetrecalcule´entempsline´aire.L’intersectionetl’unionpeuvent aussiˆetrecalcule´sentempslin´eaire,maiscen’´etaitpasdemand´eicicarlaquestion,dansle formalismedel’´enonc´e,estdifficile.Laquestion11faitlelienaveclapremi`erepartie:dans lecasd’unalphabeta`unelettre,leproble`meduvideestunprobl`emed’accessibilite´dansun grapheET/OU.Cettecorrespondanceestutilise´enotammentenv´erificationdemode`le,mais avec des automates d’arbres ou des automates de mots infinis. Ici, on pouvait aussi donner unepreuvedirecte,lesgraphes´etantacycliques.Laquestion12montrequelesautomates alternantsontmˆemepouvoird’expressionquelesautomatesnon-de´terministes(etaussiles automatesd´eterministesdanslecasdesmotsfinisquiestceluidel’e´nonc´e).Cependant, commelemontrelaquestion13,ilspeuventpermettreunerepre´sentationexponentiellement plussuccincte.Enfait,ler´esultatdelaquestion13seg´en´eralise`adesautomatesd´eterministes arbitraires,maislaquestionn’estpaspos´eeparsoucidesimplicite´.(Onpeutsereporter`a l’articledesynthe`sesuivantetauxr´efe´rencesquiysontmentionne´es:ShengYu, Regular Languages in Handbook of formal languages, Rozenberg and Salomaa eds, Springer Verlag, 1997).

1Accessibilite´danslesgraphesET/OU Lestroispremi`eresquestionsavaientpourobjetdemontrerl’existencedel’application A G compatible avec G et telle que, pour toute application g compatible avec G et tout sommet

1