UNIVERSITE de NICE SOPHIA ANTIPOLIS UFR SCIENCES L3 MASS P ESD

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

• Allumette

Informations

• Publié par: vehot
• Publié le: 01 décembre 2011
• Nombre de lectures: 29
• Langue: Français

Extrait

´ UNIVERSITE de NICE – SOPHIA ANTIPOLIS UFR SCIENCES L3 MASS P/ESD

ExamendeMath´ematiquesAppliqu´ees2011–2012

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.Choisirl’algorithmeapproprie´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:

6→5→1→2→6,6→5→9→10→6,7→3→4→8→7,7→11→12→8→7

2.2.De´terminersicegrapheestfortementconnexe.S’ilnel’estpas,de´terminer ses composantes fortement connexes. Onremarque,d’apr`eslaquestionpre´ce´dente,que6,1,2,5,9,1antdon0seˆemlsma-oocpm santefortementconnexeetqu’ilenestdemeˆmepour7,3,4,8,11,e`streIl2.1secisriova 2composantessontli´ees.Commeilyauneareˆte6→eaunetrˆ3eet7→2, les deux composantesconnexessontlesmˆemes,c’est-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 peutenlever1ou2allumettesdel’undes2tas.Lejoueurquiretireladernie`re allumette perd la partie. Onmode´lisecejeu`al’aided’ungrapheoriente´ayantpoursommetslespaires suivantes

(3,3),(3,2),(3,1),(3,0),(2,2),(2,1),(2,0),(1,1),(1,0),(0,0)

quirepre´sententlenombred’allumettesdansles2tas.Onmettraunearˆeteentre 2sommetssionpeutpasserdel’uneconfiguration`al’autreenuntourdejeu. Remarque:lestas´etantindiffe´renci´es,onconsid`ereraquelesconfigurations(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`l’undes2tasaupremiercoup,lepremierjoueurseretrouvedans la configuration (3,1).D’apr`esl,ilueurdeleopsneroja’tuesquleel´eartloioitseuqauq,.3.3n peuttoujoursarriver`alaconfiguration(1,0), ce qui lui assure de gagner. Ce n’est pas le cas silepremierjoueurenle`ve1allumetteaupremiercoup`al’undes2tasetseretrouvedans la configuration (3,2) (cf question 3.4).

Exercice4:Me´thodedelapuissance   −1 1 4.1. Calculer les valeurs propres et des vecteurs propresq 1 etq 2 deA=. −3 3 2 Lepolynˆomecaractr´eristiquedeAvaut (−1−λ)×(3−λ=) + 3 λ−2λ=λ(λ−2). Les valeurspropressontdonce´galesa`0et2.   x ∗ Lesvecteurspropresassoci´esa`0sontdelaforme,avecx∈R. On prend par exemple x   1 q 1 = . 1   x ∗ Lesvecteurspropresassocie´s`a2sontdelaforme,avecx∈R. On prend par exemple 3x   1 q 2 = . 3 t k 4.2. Exprimerx 0 = (1,0)en fonction deq 1 etq 2 erpxoissriude’le.E´endndeA x 0 , k A x 0 puis de . Conclure. k ||A x 0 || ∞ 3 1 t On trouve facilement quex 0 = (1,0) =q 1 −q 2 On a donc 2 2   k k −1 3 k k 1 k 2 −2 A x=A q− 0 1 A q 2 =−q 2 = k−1 . 2 2 2 −3×2

k k−1 La norme vaut alors||A x 0 || ∞ = 3×Donc2 .   k A x 0 1/3 → −, k 1 ||A x 0 || ∞

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.Choisirl’algorithmeapproprie´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:

5→2→1→4→5,5→2→3→6→5,8→7→10→11→8,8→9→12→11→8

2.2.De´terminersicegrapheestfortementconnexe.S’ilnel’estpas,de´terminer ses composantes fortement connexes. Onremarque,d’apre`slaquestionpr´ec´edente,que5,1,2,3,4,nteopascemoˆtnmmaed6snoasl fortementconnexeetqu’ilenestdemˆemepour7,8,9,10,11,ces2`avoirsiI.rlseet21

5