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. 1

• expression de akx0


• examen de mathematiques appliquees


• l3 mass


• court chemin


• tour de jeu


• chemin de longueur

Informations

• Publié par: vehot
• Publié le: 01 décembre 2011
• Nombre de lectures: 32
• 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.

1

Sujet A :

Exercice 1 :Graphes Legraphesuivantrepr´esenteunr´eseauroutier(avecdessensinterdits),ou`onaindique´les distancesenkilome`tres.Onpartdusommet0.

1.1. Y a t-il un circuit dans le graphe? 1.2.Choisirl’algorithmeapproprie´pourd´eterminerlecheminlepluscourtquirelie0aux autres sommets et l’appliquer. 1.3.Quelleestlavaleuretquelleestlacompositiondupluscourtcheminpourallerde0a` 7 ?

Exercice 2 :Graphes 2.1.Effectuerunparcoursenlargeurenpartantdusommet6dugraphesuivantetd´eterminer le plus de circuits possibles.

2.2.De´terminersicegrapheestfortementconnexe.S’ilnel’estpas,d´eterminersescompo- santes fortement connexes.

Exercice 3 :Graphes Deuxjoueursdisposentde2tasde3allumettes.Atourderoˆle,chaquejoueurpeutenlever 1ou2allumettesdel’undes2tas.Lejoueurquiretireladerni`ereallumetteperdlapartie. Onmod´elisecejeu`al’aided’ungrapheoirne´teayant pour sommets les paires suivantes

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

2

quirepre´sententlenombred’allumettesdansles2tas.Onmettraunearˆeteentre2sommets sionpeutpasserdel’uneconfiguration`al’autreenuntourdejeu. Remarque:lestase´tantindiffe´renci´es,onconside`reraquelesconfigurations(1,2) et (2,1) sontlesmeˆmes. 3.1. Expliquer pourquoi un sommet du graphe a au maximum 4 successeurs. 3.2.Comple´terlegraphesuivantentrac¸anttouteslesareˆtes.

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.4. Qu’en est-il pour les successeurs de (3,2) ? 3.5.Quedoitjouerlepremierjoueurpourgagnerlapartiea`coupsˆur?

Exercice4:M´ethodedelapuissance   −1 1 4.1. Calculer les valeurs propres et des vecteurs propresq 1 etq 2 deA= . −3 3 t k 4.2. Exprimerx 0 = (1,0) en fonction deq 1 etq 2 .iude´dnEseisnoeder’lxerpA x 0 , puis de k A x 0 . Conclure. k ||A x 0 || ∞

3

Sujet B :

Exercice 1 :Graphes Legraphesuivantrepr´esenteunre´seauroutier(avecdessensinterdits),ou`onaindiqu´eles distancesenkilom`etres.Onpartdusommet0.

1.1. Y a t-il un circuit dans le graphe? 1.2.Choisirl’algorithmeapproprie´pourd´eterminerlecheminlepluscourtquirelie0aux autres sommets et l’appliquer 1.3.Quelleestlavaleuretquelleestlacompositiondupluscourtcheminpourallerde0a` 4 ?

Exercice 2 :Graphes 2.1.Effectuerunparcoursenlargeurenpartantdusommet5dugraphesuivantetde´terminer le plus de circuits possibles.

2.2.De´terminersicegrapheestfortementconnexe.S’ilnel’estpas,d´eterminersescompo- santes fortement connexes.

Exercice 3 :Graphes Deuxjoueursdisposentde2tasde3allumettes.Atourderˆole,chaquejoueurpeutenlever 1ou2allumettesdel’undes2tas.Lejoueurquiretireladerni`ereallumetteperdlapartie. Onmod´elisecejeua`l’aided’ungrapheor´entieayant pour sommets les paires suivantes

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

4

quirepre´sententlenombred’allumettesdansles2tas.Onmettrauneareˆteentre2sommets sionpeutpasserdel’uneconfiguration`al’autreenuntourdejeu. Remarque:lestase´tantindiff´erenci´es,onconside`reraquelesconfigurations(1,2) et (2,1) sontlesmˆemes. 3.1. Expliquer pourquoi un sommet du graphe a au maximum 4 successeurs. 3.2.Compl´eterlegraphesuivantentrac¸anttouteslesareˆtes.

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,(11)`a,0) passant par ce successeur. 3.4. Qu’en est-il pour les successeurs de (3,2) ? 3.5.Quedoitjouerlepremierjoueurpourgagnerlapartie`acoupsˆur?

Exercice4:M´ethodedelapuissance   4−4 4.1. Calculer les valeurs propres et des vecteurs propresq 1 etq 2 deA= . 1−1 t k 4.2. Exprimerx 0 = (1,0) en fonction deq 1 etq 2 ondeessi.deiunE´dxerper’lA x 0 , puis de k A x 0 . Conclure. k ||A x 0 || ∞

5