Portail informatique Année 2018 – 2019

CSC 3101 – Algorithmique et langage de programmation

Durée: 2h, tout document papier autorisé
Lorsque vous écrivez du code, essayez d'avoir un indentation à peu près correcte (une indentation trop incorrecte vous ferait perdre des points). Sauf si explicitement demandé, il n'est pas nécessaire :
  • de gérer les cas d'erreurs,
  • d'expliciter la visibilité des champs, méthodes et constructeurs,
  • d'expliciter les packages et les imports,
  • d'indiquer quelles exceptions peuvent être levées par une méthode dans sa signature (c'est-à-dire sa déclaration).
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. Les corps (∼20mn – 7 points – facile) Dans cette première partie, nous commençons par construire les corps. Pour commencer, écrivez une classe abstraite nommée Corps et se trouvant dans le package univers (après cette question, vous pouvez omettre les packages). Une instance de la classe Corps représente n'importe quel corps et nous utiliserons l'héritage pour définir les corps chauds et les corps froids. Un corps possède :
  • Deux champs :
    • un nom de type chaîne de caractères (privé),
    • une masse de type entier (public).
  • Un constructeur avec deux paramètres permettant d'initialiser les deux champs de la classe (public).
  • Deux méthodes :
    • une méthode toString renvoyant le nom du corps (public),
    • une méthode abstraite String famille() (public). Cette méthode mise en œuvre dans les classes filles renverra la famille (corps froid ou corps chaud) à laquelle appartient le corps.
Écrivez une classe nommée CorpsFroid héritant de Corps. Cette classe ajoute un unique champ : estHabitable de type booléen. Cette classe définit aussi un constructeur permettant d'initialiser les champs d'un corps froid. CorpsFroid doit finalement mettre en œuvre la méthode famille. Cette méthode doit renvoyer la chaîne de caractères "Corps froid".

On ne vous demande pas de donner le code, mais à partir de cette question, vous pouvez supposer que vous disposez de façon similaire d'une classe CorpsChaud ajoutant le champ typeSpectral de type entier indiquant le type d'étoile (naine rouge, géante bleue etc...).

À titre d'information, voici aussi le code de la classe CorpsChaud qui n'était pas demandé :
Est-ce que le code suivant est correct et pour quelle raison ? Si ce code est correct, qu'affiche-t-il ? Corps corps = new CorpsFroid("Lune", 17, false); System.out.println(corps.famille()); Ce code est correct car CorpsFroid est une sorte de Corps. Ce code affiche "Corps froid" puisque le type effectif de corps est CorpsFroid (liaison tardive). Sachant que vous disposez d'une méthode Corps get(String name) renvoyant le corps de nom name, et sachant qu'un appelle à get("Lune") renvoie un corps nommé "Lune", est-ce que le code suivant est correct et pour quelle raison ? Si ce code est correct, qu'affiche-t-il ? CorpsFroid lune = get("Lune"); System.out.println(lune); Ce code n'est pas correct car get renvoie un objet de type Corps qui n'hérite pas de CorpsFroid. Sachant que ce code est correct, qu'affiche-t-il ? Le programme affiche 666 - 10 - 666. En effet, tab[0] et tab[2] référencent soleil qui a une masse de 666 suite à la modification effectuée à la ligne précédente. tab[1] référence terre qui a une masse initialisée à 10 lors de l'invocation du constructeur. L'univers (∼20mn – 4,5 points – facile) 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. Donnez la définition de la classe Univers avec son champ et un constructeur sans argument permettant d'initialiser le champ carte vers une instance de java.util.HashMap. Donnez le code de la méthode get se trouvant dans la classe Univers et renvoyant le corps associé au nom de type chaîne de caractères passé en paramètre. Si le corps n'existe pas, votre méthode doit renvoyer null.

On vous rappelle que l'interface Map<K, V> offre une méthode V get(K key) permettant de renvoyer la valeur associée à la clé key si la clé existe et null sinon.
Donnez le code de la méthode void put(Corps corps) throws CorpsExisteDeja se trouvant dans la classe Univers. Cette méthode doit :
  • Ajouter le corps à carte si aucun corps du même nom existe,
  • Ne pas modifier la carte de l'univers et lever une exception de type CorpsExisteDeja sinon.
Donnez aussi le code de la classe CorpsExisteDeja, sachant que cette exception ne définit ni champ, ni constructeur, ni méthode.

On vous rappelle que l'interface Map<K, V> offre une méthode boolean put(K key, V value) permettant d'associer la valeur value à la clé key.
Donnez le code d'une méthode permettant d'afficher dans le terminal les noms des corps se trouvant dans l'univers.

On vous rappelle que l'interface Map<K, V> offre une méthode Collection<V> values() renvoyant la collection des valeurs se trouvant dans la table d'association.
Simulons l'univers (∼ 30mn – 3,5 points – moyen) 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. Donnez la définition de l'interface SkyWalker. Écrivez la méthode void apply(SkyWalker luke) de la classe Univers permettant d'effectuer, de façon générique, le calcul.

On vous rappelle de nouveau que l'interface Map<K, V> offre une méthode Collection<V> values() renvoyant la collection des valeurs se trouvant dans la table d'association.
Écrivez la classe CalculateurMasse permettant de calculer la masse de l'univers. Sachant que la variable univers référence une instance de l'univers, écrivez le code permettant de calculer la masse de l'univers.
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 niè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. Écrivez la méthode push appartenant à la classe Stack permettant de déposer un élément. Écrivez la méthode pop appartenant à la classe Stack permettant de retirer le dernier élément déposé. Pensez à traiter le cas où la pile est vide.