CSC 3101 – Algorithmique et langage de programmation

Dans cet exercice, nous vous proposons de simuler l'univers. Un univers est constitué de corps célestes. Certains sont froids, comme les planètes, d'autres sont chauds, comme les étoiles. Dans cette première partie, nous commençons par construire les corps. Dans cette seconde partie, nous mettons en œuvre l'univers. Une instance de la classe univers possède un unique champ nommé carte de type java.util.Map<K, V> paramétré par des chaînes de caractères et des corps. On vous rappelle que la classe String définit déjà des méthodes equals et hashCode permettant d'utiliser une instance de String comme clé dans une table de hachage. Dans cette partie, nous souhaitons pouvoir effectuer des calculs sur l'ensemble de l'univers. Ce calcul pourrait, par exemple, déplacer les planètes en fonction du temps qui passe ou calculer la probabilité de trouver des ananas. Plus humblement, nous allons simplement calculer la masse de l'univers.

Comme nous souhaitons écrire du code générique permettant de spécifier facilement quel calcul nous souhaitons effectuer, nous allons écrire du code réutilisable. Pour rendre le code réutilisable, nous utilisons une interface nommée SkyWalker représentant un calcul quelconque. Cette interface définit une unique méthode compute permettant d'effectuer un calcul sur un corps de l'univers. Cette méthode prend en paramètre un corps et ne renvoie pas de valeur.

Pour effectuer un calcul sur tous les corps de l'univers, il suffit d'itérer sur les corps se trouvant dans l'univers, et, pour chacun des corps, d'appeler compute. Pour cela, nous ajoutons à la classe Univers une méthode d'instance apply prenant en argument un SkyWalker.

Par exemple, pour calculer la masse de l'univers, il faut écrire une classe CalculateurMasse mettant en œuvre SkyWalker. La méthode compute de CalculateurMasse doit alors simplement accumuler la masse de chacun des corps dans un champ de CalculateurMasse.

Répondez par vrai ou faux aux assertions suivantes (si vous doutez à cause d'une ambiguïté dans la formulation, c'est que le bonne réponse est probablement faux). Il n'est pas nécessaire de justifier. N'hésitez pas à mettre vos réponse directement sur cet énoncé et à glisser l'énoncé dans votre copie (en mettant, bien sûr, votre nom sur l'énoncé).

1. Un tableau extensible est inefficace lorsqu'on ajoute souvent de nouveaux éléments.
   Vrai. Il faut régulièrement copier le tableau lorsqu'on étend un tableau extensible.
2. Un tableau extensible est inefficace lorsqu'on le parcourt.
   Faux. Un tableau extensible est mise en œuvre avec un tableau, ce qui rend le parcours efficace.
3. Une liste chaînée est inefficace lorsqu'on ajoute souvent de nouveaux éléments.
   Faux. Ajouter un nœud au début d'une liste chaînée est toujours efficace et ne dépend pas de la taille du tableau.
4. Une liste doublement chaînée circulaire permet de simplifier le code de suppression d'un élément.
   Vrai. Il n'y a plus besoin de conserver une référence vers le nœud qui précède celui qu'on veut supprimer, et il n'y a plus besoin de gérer de façon particulière la suppression du premier nœud de la liste.
5. Une table de hachage permet toujours de retrouver une valeur en un temps constant (indépendant du nombre d'éléments).
   Faux. Ce serait vrai dans le cas d'une méthode de hash qui ne fait jamais de collision et si la table avait une taille infinie. En pratique, on retrouve un élément en un temps racine n^ième du nombre d'éléments, où n est une constante dépendant de la mise en œuvre.
6. main est un mot clé du langage Java.
   Faux. main est un symbole comme les autres. Il a role particulier : la machine virtuelle démarre par la méthode statique et publique main d'une classe.
7. Pour définir une méthode, il faut utiliser le mot clé static.
   Faux. static ne permet que de définir des méthodes de classe. L'absence de ce mot clé permet de définir des méthodes d'instances.
8. Le mot clé implements ne peut être utilisé que pour définir une classe qui met en œuvre une interface.
   Vrai. Il n'y a pas d'autres utilisations possible de ce mot clé.
9. Le mot clé extends ne peut être utilisé que pour définir une classe qui hérite d'une autre classe.
   Faux. extends est aussi utilisé pour déclarer un type générique qui hérite ou met en œuvre une classe particulière.
10. Quelque soit l'objet Java, il possède un méthode hashCode.
    Vrai. Object met en œuvre une méthode hashCode qui est donc héritée par toute classe Java.
11. Une classe ne peut mettre en œuvre qu'une unique interface.
    Faux. Une classe peut mettre en œuvre plusieurs interface mais ne peut hériter que d'une unique classe.
12. L'expression int[] tab; définit un tableau d'entiers.
    Faux. Cette expression définit une référence vers un tableau d'entiers.
13. La relation d'héritage construit un arbre dans lequel Object est la racine.
    Vrai. Toute classe hérite par transitivité de Object.
14. Le code int c = 'a'; System.out.println(c + 1); affiche b.
    Faux. Le calcul c + 1 promeut c en entier puisque 1 est un entier. Le résultat est un entier (98) et c'est cet entier qui est affiché.
15. Lorsqu'un paramètre d'une classe paramétrée n'est pas spécifié, le paramètre est de type Object.
    Vrai.

Le but de cet exercice est de concevoir une nouvelle structure de données. Cette structure de données, nommée une pile, possède deux méthodes :

• Une méthode push permettant de déposer un élément,
• Une méthode pop permettant de retirer le dernier élément déposé (dernier déposé, premier retiré). Par exemple, si une application dépose, dans l'ordre, les éléments "a", "b" puis "c" et retire ensuite trois éléments, elle retire, dans l'ordre, "c", "b" puis "a".

Pour mettre en œuvre une pile, vous disposez des classes suivantes :

Initialement, le champ head est initialisé à null, ce qui indique qu'aucun élément ne se trouve dans la pile. Pour déposer une valeur dans la pile (push), il faut allouer un nouveau StackNode et le placer en tête de pile (head). Pour retirer une valeur de la pile (pop), lorsque la pile n'est pas vide, il faut renvoyer l'élément en tête de pile (l'élément head) après avoir mis l'élément suivant (l'élément head.next) en tête de pile. Si la pile est vide, pop doit renvoyer la valeur null.