UNIVERSITE de NICE SOPHIA ANTIPOLIS UFR SCIENCES L3 MASS P ESD

UNIVERSITE de NICE SOPHIA ANTIPOLIS UFR SCIENCES L3 MASS P ESD

Documents
9 pages
Lire
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

Description

Niveau: Supérieur, Licence, Bac+3
UNIVERSITE de NICE – SOPHIA ANTIPOLIS UFR SCIENCES L3 MASS P/ESD Examen de Mathematiques Appliquees 2011–2012 Examen du Mardi 13 Decembre 2011 Duree : 2h Les documents, calculatrices,... ne sont pas autorises. Sujet A : Exercice 1 : Graphes Le graphe suivant represente un reseau routier (avec des sens interdits), ou on a indique les distances en kilometres. On part du sommet 0. 1 3 5 6 72 83 7 4 2 8 4 0 0 2 3 6 3 2 2 2 5 7 1 1 1 1.1. Y a t-il un circuit dans le graphe ? Oui, par exemple le circuit 1-5-2-1. 1.2. Choisir l'algorithme approprie pour determiner le chemin le plus court qui relie 0 aux autres sommets et l'appliquer. On ne peut pas appliquer l'algorithme pour les graphes sans circuits, on utilise donc l'algo- rithme de Dijkstra. On obtient alors le tableau suivant : 1 pred 2 pred 3 pred 4 pred 5 pred 6 pred 7 pred 8 pred 0 7 0 3 0 4 0 2 5 2 5 2 11 2 3 1 6 1 4 11 4 5 8 5 9 5 6 7 1.3. Quelle est la valeur et quelle est la composition du plus court chemin pour aller de 0 a 7 ? 1

  • algorithme pour les graphes sans circuits

  • tas etant

  • algo- rithme de dijkstra

  • tas

  • derniere allumette

  • allumette

  • akq1 ?


Sujets

Informations

Publié par
Publié le 01 décembre 2011
Nombre de visites sur la page 29
Langue Français
Signaler un problème
´ UNIVERSITE de NICE – SOPHIA ANTIPOLIS UFR SCIENCES L3 MASS P/ESD
ExamendeMath´ematiquesAppliqu´ees20112012
ExamenduMardi13De´cembre2011
Dur´ee:2h Lesdocuments,calculatrices,...nesontpasautorise´s.
Sujet A :
Exercice 1 : Graphes Legraphesuivantrepre´senteunre´seauroutier(avecdessensinterdits),o`uon aindique´lesdistancesenkilom`etres.Onpartdusommet0.
1.1. Y a t-il un circuit dans le graphe ? Oui, par exemple le circuit 1-5-2-1. 1.2.Choisirlalgorithmeapproprie´pourde´terminerlecheminlepluscourtqui relie0aux autres sommets et l’appliquer. On ne peut pas appliquer l’algorithme pour les graphes sans circuits, on utilise donc l’algo-rithme de Dijkstra. On obtient alors le tableau suivant : 1 pred 2 pred 3 pred 4 pred 5 pred 6 pred 7 pred 8 pred 0 7 0 3 0 4 0 2 5 2 5 2 11 2 3 1 6 1 4 11 4 5 8 5 9 5 6 7 1.3. Quelle est la valeur et quelle est la composition du plus court chemin pour aller de0`a7?
1
Lepluscourtcheminpourallerde0`a7vaut9etuncheminpossibleest0-2-1-5-7.
Exercice 2 : Graphes 2.1. Effectuer un parcours en largeur en partant du sommet6du graphe suivant etde´terminerleplusdecircuitspossibles.On trouve le parcours en largeur suivant :
Onende´duitlescircuitssuivants:
65126,659106,73487,7111287
2.2.De´terminersicegrapheestfortementconnexe.Silnelestpas,de´terminer ses composantes fortement connexes. Onremarque,dapr`eslaquestionpre´ce´dente,que6,1,2,5,9,1antdon0seˆemlsma-oocpm santefortementconnexeetquilenestdemeˆmepour7,3,4,8,11,e`streIl2.1secisriova 2composantessontli´ees.Commeilyauneareˆte6eaunetrˆ3eet72, les deux composantesconnexessontlesmˆemes,cest-a`-direquelegrapheestfortementconnexe. Autrepossibilit´e:faireunparcoursenlargeurinverse´`apartirde6commeci-dessousOn ende´duitquelacomposanteconnexede6este´gale`a{1,2,3,4,5,6,7,8,9,10,11,12} ∩ {1,2,3,4,5,6,7,8,9,10,11,12}={1,2,3,4,5,6,7,8,9,10,11,12}, le graphe est donc forte-ment connexe.
2
Exercice 3 : Graphes Deuxjoueursdisposentde2tasde3allumettes.Atourderoˆle,chaquejoueur peutenlever1ou2allumettesdelundes2tas.Lejoueurquiretireladernie`re allumette perd la partie. Onmode´lisecejeu`alaidedungrapheoriente´ayantpoursommetslespaires suivantes
(3,3),(3,2),(3,1),(3,0),(2,2),(2,1),(2,0),(1,1),(1,0),(0,0)
quirepre´sententlenombredallumettesdansles2tas.Onmettraunearˆeteentre 2sommetssionpeutpasserdeluneconguration`alautreenuntourdejeu. Remarque:lestas´etantindie´renci´es,onconsid`ereraquelescongurations(1,2) et(2,1)mˆemes.sontles 3.1. Expliquer pourquoi un sommet du graphe a au maximum 4 successeurs. A chaque coup, on peut choisir d’enlever, si c’est possible, 1 ou 2 allumettes, soit 2 choix pour chacun des 2 tas. Il y a donc au maximum 2×4p2=ibilsois.´tse 3.2.Compl´eterlegraphesuivantentrac¸anttouteslesarˆetes.
3
3.3. Lister les successeurs de(3,1)et montrer que quel que soit le successeur choisi, il existe toujours un chemin de longueur 2 de(3,1)`a(1,0)passant par ce successeur. (3,1) a 3 successeurs possibles : (3,0),(2,1),(1,1). A partir de (3,1), on a les chemins suivants : (3,1)(3,0)(1,0) (en enlevant 2 allumettes au tas qui en compte 3) et (3,1)(2,1)(1,0) (en enlevant 2 allumettes au tas qui en compte 2) et (3,1)(1,1)(1,nenlevan0)(ett`euadn1tlaulem.)sat2se 3.4. Qu’en est-il pour les successeurs de(3,2)? Les successeurs de (3,2) sont (3,1),(3,0),(2,2),(2,.)eDˆmmeqeeuoprulaquestionpr´ec´deneet,1 les chemins (3,2)(2,1)(1,0) et (3,2)(3,0)(1,0) sont de longueur 2. En revanche, les chemins (3,2)(2,2)(2,0)(1,0) et (3,2)(3,1)(1,1)(1,0) sont de longueur 3. 3.5.Quedoitjouerlepremierjoueurpourgagnerlapartiea`coupsuˆr? Enenlevant2allumettesa`lundes2tasaupremiercoup,lepremierjoueurseretrouvedans la configuration (3,1).Dapr`esl,ilueurdeleopsnerojatuesquleel´eartloioitseuqauq,.3.3n peuttoujoursarriver`alaconguration(1,0), ce qui lui assure de gagner. Ce n’est pas le cas silepremierjoueurenle`ve1allumetteaupremiercoup`alundes2tasetseretrouvedans la configuration (3,2) (cf question 3.4).
Exercice4:Me´thodedelapuissance   1 1 4.1. Calculer les valeurs propres et des vecteurs propresq1etq2deA=. 3 3 2 Lepolynˆomecaractr´eristiquedeAvaut (1λ)×(3λ=) + 3 λ2λ=λ(λ2). Les valeurspropressontdonce´galesa`0et2.   x Lesvecteurspropresassoci´esa`0sontdelaforme,avecxR. On prend par exemple x   1 q1= . 1   x Lesvecteurspropresassocie´s`a2sontdelaforme,avecxR. On prend par exemple 3x   1 q2= . 3 t k 4.2. Exprimerx0= (1,0)en fonction deq1etq2erpxoissriudele.E´endndeA x0, k A x0 puis de . Conclure. k ||A x0||3 1 t On trouve facilement quex0= (1,0) =q1q2On a donc 2 2   k k1 3 k k1k22 A x=A q0 1A q2=q2=k1. 2 2 23×2
k k1 La norme vaut alors||A x0||= 3×Donc2 .   k A x01/3 → −, k 1 ||A x0||
cequiestbienunvecteurpropreassocie´`alavaleurpropredeplusgrandmodule2.
4
Sujet B :
Exercice 1 : Graphes Legraphesuivantrepre´senteunr´eseauroutier(avecdessensinterdits),o`uon aindiqu´elesdistancesenkilom`etres.Onpartdusommet0.
1.1. Y a t-il un circuit dans le graphe ? Oui, par exemple le circuit 5-6-3-5. 1.2.Choisirlalgorithmeapproprie´pourde´terminerlecheminlepluscourtqui relie0aux autres sommets et l’appliquer. On ne peut pas appliquer l’algorithme pour les graphes sans circuits, on utilise donc l’algo-rithme de Dijkstra. On obtient alors le tableau suivant :
0 1 3 5 2 6 4 7
1 4
pred 0
2
9 7
pred
1 3
3 5
pred 0
4
13
11
pred
3
6
5 8
7
pred 0
3
6
9
pred
5
7
12
pred
6
8
14
pred
2
1.3. Quelle est la valeur et quelle est la composition du plus court chemin pour aller de0a`4? Lepluscourtcheminpourallerde0a`4vaut11etuncheminpossibleest0-3-5-6-4.
Exercice 2 : Graphes 2.1. Effectuer un parcours en largeur en partant du sommet5du graphe suivant etd´eterminerleplusdecircuitspossibles. Ontrouveleparcoursenlargeursuivant:Onend´eduitlescircuitssuivants:
52145,52365,8710118,8912118
2.2.De´terminersicegrapheestfortementconnexe.Silnelestpas,de´terminer ses composantes fortement connexes. Onremarque,dapre`slaquestionpr´ec´edente,que5,1,2,3,4,nteopascemoˆtnmmaed6snoasl fortementconnexeetquilenestdemˆemepour7,8,9,10,11,ces2`avoirsiI.rlseet21
5