Graphes d'objets

Section 2.3: graphes d’objets #

Dans le cas général, des données orientées-objet forme un graphe.

2.3.1 Graphe film/personnage #

On peut compléter ainsi la modélisation des films et celle des personnages présentées aux chapitres précédents.

  • Un Personnage apparaît dans plusieurs Film.
  • Un Film contient plusieurs Personnage.

Voici un exemple de données se conformant à cette modélisation.

  • Le Personnage James Bond apparaît dans deux films : Dr. No et Bon Baisers de Russie.
  • Le Film Dr. No contient deux personnages : James Bond et Dr. No.

2.3.2 Exemple : Fibonacci #

Dans le cas général, il n’est pas facile de visualiser un graphe d’objet avec des cartes. Dans notre approche, il est donc nécessaire de s’en tenir à des cas particuliers. Comme exemple, nous développons une modélisation de la séquence de Fibonacci.

2.3.3 Définition #

Voici le début de la suite de Fibonacci :

0 1 1 2 3 5 8 13 21 34 55 89 144 ...

La définition mathématique est récursive :





  \(    F_0 = 0\\~\\

    F_1 = 1\\~\\

    F_n = F_{n-1} + F_{n-2}\\~\\
    \)

Autrement dit :

  • 0 et 1 sont deux cas spéciaux.

  • Sinon le prochain nombre de la suite est toujours l’addition deux nombres précédents

2.3.4 Nombre d’or #

  1. La suite de Fibonacci est utilisée pour calculer le nombre d’or, soit environ 1.618

    • Le nombre d’or est reconnu, entre autres choses, comme une proportion hauteur/largeur agréable à l’oeil.

  2. Comme pour π, on peut calculer le nombre d’or avec autant de précision que désirée, c.-à-d. avec autant de chiffres après le point que désiré.

  3. Pour calculer une approximation du nombre d’or, on fait tout simplement :

    \( \text{nombre d'or} \approx \dfrac{F_{n}}{F_{n-1}} \text{~~~pour~~~} n\geq 2 \)

  4. Plus on prend un n élevé, plus la précision est bonne.

  5. Autrement dit, le nombre d’or est à peu près égal à un nombre de la suite de Fibonacci, divisé par le nombre qui le précède.

    • Plus on prend un nombre loin dans la suite, plus l’approximation est bonne

2.3.5 Modéliser la suite de Fibonacci #

  1. Pour modéliser la suite en Java, on va créer une structure de données récursive :

  1. Pour n = 0, on a le graphe d’objets suivant :

  2. Pour n = 1, on a le graphe d’objets suivant :

  3. Pour n = 2, on a le graphe d’objets suivant :

    • NOTE : la suite se lit de droite à gauche.

  4. Pour n = 3, on a le graphe d’objets suivant :

  5. Et ainsi de suite.

2.3.6 Pour calculer la réponse et le nombre d’or #

  1. Calculer la réponse pour n >= 2 est simple :

    reponse = moinsUn.getReponse() + moinsDeux.getReponse();

  2. Même chose pour le nombre d’or :

    nombreOr = Double.valueOf(reponse) / Double.valueOf(moinsUn.getReponse());

  3. Le défi est qu’il faut d’abord construire le graphe d’objet.

2.3.7 Construire le graphe d’objets récursivement #

  1. Avec des appels récursifs, on va construire d’abord, puis calculer :

    • On crée d’abord l’objet n, puis n-1, et ainsi de suite jusqu’à l’objet 0

  2. Pour le cas n >= 2, voici comment procéder :

    1. Créer un nouvel objet MonFibonacci et le mémoriser dans moinsUn

    2. Enregistrer que le n de ce moinsUn est n-1 (le n courant moins 1).

    3. Créer le reste du graphe récursivement en appelant moinsUn.construireGrapheRecursivement()

    4. Enregister que le moinsDeux courant est moinsUn.getMoinsUn() (le moinsUn du moinsUn courant).

    5. Calculer la réponse courante à partir des réponses de moinsUn et moinsDeux

  3. L’appel récursif est plus proche de la définition mathématique :

    • Pour calculer la réponse en n, il faut d’abord calculer la réponse en n-1

  4. L’inconvénient est qu’on peut déborder la pile d’appel :

    Exception in thread "main" java.lang.StackOverflowError
    at ca.ntro.cards.fibonacci.solution.MonFibonacci.construireGrapheRecursivement(MonFibonacci.java:31)
    at ca.ntro.cards.fibonacci.solution.MonFibonacci.construireGrapheRecursivement(MonFibonacci.java:31)
    at ca.ntro.cards.fibonacci.solution.MonFibonacci.construireGrapheRecursivement(MonFibonacci.java:31)
    at ca.ntro.cards.fibonacci.solution.MonFibonacci.construireGrapheRecursivement(MonFibonacci.java:31)
    at ca.ntro.cards.fibonacci.solution.MonFibonacci.construireGrapheRecursivement(MonFibonacci.java:31)
    at ca.ntro.cards.fibonacci.solution.MonFibonacci.construireGrapheRecursivement(MonFibonacci.java:31)
    at ca.ntro.cards.fibonacci.solution.MonFibonacci.construireGrapheRecursivement(MonFibonacci.java:31)
    at ca.ntro.cards.fibonacci.solution.MonFibonacci.construireGrapheRecursivement(MonFibonacci.java:31)
    at ca.ntro.cards.fibonacci.solution.MonFibonacci.construireGrapheRecursivement(MonFibonacci.java:31)
    at ca.ntro.cards.fibonacci.solution.MonFibonacci.construireGrapheRecursivement(MonFibonacci.java:31)
    at ca.ntro.cards.fibonacci.solution.MonFibonacci.construireGrapheRecursivement(MonFibonacci.java:31)
    at ca.ntro.cards.fibonacci.solution.MonFibonacci.construireGrapheRecursivement(MonFibonacci.java:31)
    ...
    • RAPPEL : le code n’est pas bogué, mais limité par la mémoire attribuée à la pile d’appel.

2.3.8 Construire le graphe d’objets dynamiquement #

  1. En programmation dynamique, on calcule en même temps qu’on construit :

    • On crée d’abord l’objet 0, puis 1, et ainsi de suite jusqu’à l’objet n

  2. L’idée est qu’on fait une boucle pour créer le graphe d’objets.

    • On crée une nouvelleTete

    • Le moinsUn de la nouvelleTete est l’ancienne tete

    • Le moinsDeux de la nouvelleTete est le moinsUn de l’ancienne tete

      • c.-à-d. on insère la nouvelleTete à gauche, et on « pousse » les objets existants vers la droite.

  3. Pour le cas n >= 2, voici comment procéder :

    • Pour chaque i allant de 2 à n (inclusivement) :

      1. Créer un nouvel objet MonFibonacci pour représenter la nouvelleTete

      2. Enregistrer que le n de la nouvelleTete est i

      3. Enregistrer que le moinsUn de la nouvelleTete est la tete courante.

      4. Enregistrer que le moinsDeux de la nouvelleTete est le moinsUn de la tete courante.

      5. Enregistrer que tete pointe maintenant vers la nouvelleTete

      6. Calculer la réponse pour tete

  4. Le calcul dynamique est moins intuitif (et moins proche de la définition mathématique), mais on a éliminé l’appel récursif, alors on ne peut plus déborder la pile d’appel.



↪ Chapitre 3:  qu'est-ce que l'efficacité?
FabriqueREL
Creative Commons License
Collège Montmorency