/home/scinfo/public_html/index.php:18:string 'ATTENTION: Ce site ne sera plus displonible à partir de Septembre 2017' (length=71)
Problème n°1, examen de juin 2010 :: Sciences Informatiques (ULg)
Nouveau sujet Répondre Imprimer Syndication RSS 2.0

Problème n°1, examen de juin 2010

Photo de Thomas D.

2ème Ms.
  • Age : 27 ans
  • Messages : 69
  Lien vers ce message 21 Aout 2012, 20:00
Bonjour http://www.scinfo.be/images/smileys/fsb2_smyle.gif ,


Préparant l'exam de seconde session prévu pour le 3 septembre, je refais quelques exercices issus des sessions précédents. Jusqu'ici ça semble aller (du moins mieux qu'en janvier) mais je ne parviens quand même pas à résoudre la deuxième partie du problème 1 présent dans l'examen de juin 2010.


L'énoncé de cet examen est disponible sur le site du cours (http://www.montefiore.ulg.ac.be/~geurts/iti.html) et l'auteur se nomme Liadan O'Callaghan. Malgré la référence précédente, je vous note l'énoncé de cette fameuse question au bas du post.


L'exercice est plutôt classique. Cependant j'ai dû interpréter la phrase " L'ordre des tâches a de l'importance car l'étudiant se fatigue au cours de la journée" d'une certaine manière. J'en ai en effet déduit qu'il n'existe pas de planning pour lequel l'étude et le projet sont adjacents. Donc par exemple, le planning (Videos, Projet, Etude) n'est pas valide.


Pour le point a) , j'ai déterminé que la relation était : f(n) = f(n-1) + 2*f(n-2) - 4 ; pour tout n > 3.
Les cas de bases étant f(0), f(1), f(2) et f(3), soit ceux de l'énoncé.


Par exemple, f(4) = 7 = 5 + 2*3 - 4 . L'ensemble des différents plannings de quatre heures est {(V, V, V, V), (V, V, P), (V, V, E), (E, V, V), (P, V, V), (V, P, V), (V, E, V) }, c'est à dire les plannings de f(3) auxquels on aurait ajouté une videos comme dernier élément + les plannings de f(2) pour lesquels on ajoute soit deux heures de projet, soit deux heures d'étude mais seulement si le planning concerné ne finit pas par deux heures d'étude ou de projet (Donc seul (Videos, Videos) est à prendre en compte dans les plannings de f(2)).


Par ailleurs, f(5) = 13 = 7 + 2*5 - 4

et f(6) = 23 = 13 + 2*7 - 4

http://www.scinfo.be/images/smileys/fsb2_clown.gif

Là où ça se complique c'est quand il faut déterminer une solution analytique, autrement dit lorsque l'on passe au point b) . J'ai d'abord estimé que les valeurs n'étaient pas assez explicites pour identifier un modèle tel quel et que donc il fallait s'en référer à la méthode de résolution de récurrences linéaires. On suit la recette et voici, étapes par étapes, les résultats obtenus (ainsi que le problème rencontré) :


1) Trouver les racines de l'équation caractéristique


L'équation caractéristique de f(n) = f(n-1) + 2*f(n-2) - 4 est x² = x + 2 <=> x² - x - 2 = 0
Les racines étant r1 = 2 et r2 = -1.


2) Déduire la solution homogène


Cette solution homogène équivaut simplement à f(n) = c1*(2)^n + c2 * (-1)^n . En effet, les deux racines ne sont pas répétées.


3) Déterminer la solution particulière


Ici, g(x) est une constante donc on doit résoudre l'équation d = d + 2*d - 4. La constante d vaut 2.


4) Former la solution générale par simple addition des solutions homogène et particulière


f(n) = c1*(2)^n + c2 * (-1)^n + 2


5) Trouver les valeurs de c1 et c2.

Ici, rien ne va plus... http://www.scinfo.be/images/smileys/fsb2_ice.gif
Ayant quatre cas de base (pour n = 0, 1, 2 et 3), je peux établir 6 systèmes distincts de deux équations à deux inconnues. Concrètement :


f(0) et f(1), (f0) et f(2), (f0) et f(3), f(1) et f(2), f(1) et f(3), (f2) et f(3).


Cependant, pour souligner le problème rencontré, je vais considérer les trois premiers systèmes de la liste ci-dessus et comparer leurs résultats.


f(0) = 1 => c1*(2)^0 + c2 * (-1)^0 + 2 = 1 <=> c1 + c2 = -1

et
f(1) = 1 => c1*(2)^1 + c2 * (-1)^1 + 2 = 1
f(2) = 3 => c1*(2)^2 + c2 * (-1)^2 + 2 = 3
f(3) = 5 => c1*(2)^3 + c2 * (-1)^3 + 2 = 5


Il s'en suit :



f(0) = 1 => c1 = -1 - c2

et donc
f(1) = 1 => 2*(-1 - c2) - c2 = -1 <=> c2 = - (1/3) et c1 = - (2/3)
f(2) = 3 => 4*(-1 - c2) + c2 = 3 <=> c2 = - (7/3) et c1 = 4/3
f(3) = 5 => 8*(-1 - c2) - c2 = 5 <=> c2 = - (13/9) et c1 = 22/9


Les différentes valeurs de c2 et c1 pour les trois premiers systèmes ont été trouvées. Malheureusement, aucunes des équations :


f(n) = - (2/3)*(2)^n - (1/3)*(-1)^n + 2 ,
f(n) = (4/3)*(2)^n - (7/3)*(-1)^n + 2 et
f(n) = (22/9)*(2)^n - (13/9)*(-1)^n + 2


ne fournissent les valeurs attendues.


J'ai également essayé avec les trois autres systèmes de deux équations à deux inconnues mais aucune solution ne semble convenir. Ca devrait pourtant être le cas même si l'équation de récurrence n'a rien avoir avec l'énoncé. Par conséquent, le soucis se situe dans l'usage de la recette de résolution elle même.

Vous comprendrez que ce problème est assez frustrant ( http://www.scinfo.be/images/smileys/fsb2_dead.gif ) et j'espère sincèrement que les bonnes âmes se manifesteront http://www.scinfo.be/images/smileys/fsb2_godgrace.gif


Merci d'avance,



Thomas Désir


Citation
" Un étudiant peut passer une heure à regarder des videos sur Youtube, deux heures à étudier ou deux heures à travailler sur un projet. Soit f(n) le nombre de plannings possibles de n heures. L'ordre des tâches a de l'importance car l'étudiant se fatigue au cours de la journée.


Par exemple:


f(0) = 1 . Il n'y a aucun planning de 0 heure, i.e. l'ensemble des plannings de zéro heure contient un élément qui est l'ensemble vide
f(1) = 1 . Un seul planning possible : (Videos)
f(2) = 3 . Pour { (Videos, Videos) , (Projet) , (Etude) }
f(3) = 5 . Pour { (Videos, Videos, Videos) , (Projet, Videos), (Etude, Videos), (Videos, Etude), (Videos, Projet) }


a) Exprimez f(n) en utilisant une relation de récurrence et un nombre suffisant de cas de base


b) Trouvez une expression réduite pour f(n) en résolvant la récurrence sans utiliser les fonctions génératrices "


Photo de Kowari

2ème Ms.
  • Age : 27 ans
  • Messages : 95
  Lien vers ce message 21 Aout 2012, 21:41
Citation
L'exercice est plutôt classique. Cependant j'ai dû interpréter la phrase " L'ordre des tâches a de l'importance car l'étudiant se fatigue au cours de la journée" d'une certaine manière. J'en ai en effet déduit qu'il n'existe pas de planning pour lequel l'étude et le projet sont adjacents. Donc par exemple, le planning (Videos, Projet, Etude) n'est pas valide.


Je pense que ça veut plutôt dire que le planning (Videos, Projet) n'est pas le même que (Projet, Video).

Je viens donc d'essayer sans exclure aucun cas de f(n-2), c'est à dire que f(n) sont les plannings de f(n-1) où on a rajouté 1h de vidéo et les plannings f(n-2) auxquels on a ajouté 2h d'études ou 2h de projet.

Ca me donne l'équation de récurrence : f(n) = f(n-1) + 2f(n-2) avec les cas de base f(0) = 1, f(1) = 1.

Pour résoudre il faut faire comme tu as fait aux 2 premiers points donc on se retrouve avec la solution homogène

f(n) = c1*(2)^n + c2 * (-1)^n (ce que tu as trouvé)

et ensuite trouver c1 et c2 à l'aide des cas de base et on trouve c1 = 2/3, c2 = 1/3 et ça a l'air de marcher pour f(2), f(3) (et f(4) = 11 d'après l'équation de récurrence).


Pour ce qui est du fait que ça ne marche pas avec ta solution, c'est bizarre en effet mais je suppose que c'est dut au trop grand nombre de cas de base ou alors il faudrait trouver une solution au système comprenant tout les cas en même temps (et donc un système de 4 équations à 2 inconnues possiblement impossible à résoudre...)

J'espère que je ne me suis pas trop gouré (ça fait quand même un ptit temps maintenant que j'ai plus fait ça :p)
Photo de Thomas D.

2ème Ms.
  • Age : 27 ans
  • Messages : 69
  Lien vers ce message 21 Aout 2012, 22:03
Ton interprétation donne effectivement lieu à une résolution plus proche de ce qui est généralement demandé aux examens. Donc oui, tu as certainement raison, le critère "l'ordre a de l'importance", signifie qu'il faut manipuler les plannings comme des séquences et non tel que des ensembles (et ce sans conditions supplémentaires).


Toutefois, je reste septique quant à la phrase "l'étudiant se fatigue en cours de journée"; cause de mon interprétation.


Pour quelle obscure raison l'auteur a-t-il pensé au critère "fatigue" ? Souhaitait-il, pour se divertir, diviser les étudiants en deux groupes afin que ceux-ci s'entretuent lors des concertations post exam ? Aux yeux des assistants, un étudiant peut-il supporter des plannings de 250 heures dont 50 d'affilées à regarder la même vidéo Youtube en boucle ?... Autant de questions qui resteront sans réponse... http://www.scinfo.be/images/smileys/fsb2_extraterre.gif


En tout cas, merci pour ton commentaire. Je ne m'attendais pas à ce que qqun réagisse aussi vite http://www.scinfo.be/images/smileys/fsb2_oui.gif !


Répondre


.