Examen final
6
pages
Français
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
6
pages
Français
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
TP, Supérieur, TP
Voir
- redaction
- mémoire
- chaîne de caractères correspondant au polynôme
- instance représentant le polynôme nul
- arbres binaires
- arbre binaire
- public noeud
- polynômes
- polynôme
- chaîne
- chaînes
- codes
- code
- classes
- classe
- correspondant
- correspondants
Programmation orientée objet L2 — Info 211A
Examen final L2 Maths-Info
10 janvier 2011 — 2h
Tous les documents de cours/TP/TD sont autorisés. Le barème (sur 25 points!) est donné à titre indicatif. La notation tiendra compte du respect des conventions de code Java ainsi que de la rédaction et du soin(3 points). Le sujet comporte 14 questions réparties en 2 parties indépen-dantes (une partie algorithmique et une partie POO). La partie algorithmique est composée de deux exercices indépendants. Des exemples d’utilisation des différentes classes à programmer sont généralement données. Il est donc (très) fortement conseillé de lire l’ensemble d’un exercice avant de commencer à le traiter. 1 Algorithmique(10 points) 1.1 Arbresbinaires (6 points) L’annexe 3 donne l’implémentation d’un arbre binaire de recherche permet-tant de représenter une collection d’entiers. Cette implémentation doit être utilisée pour répondre aux questions de cet exercice. 1. Qu’est-cequ’un arbre binaire de recherche? Quelles sont ses principales utilisations ?(1 point) 2. Donnezle code de la méthodecherchequi renvoietruesi l’élément est présent dans la collection représentée par l’arbre etfalsesinon.(2 points) On souhaite ajouter une méthodeprofondeurMaxqui renvoie la profondeur maximale de l’arbre. La profondeur maximale est définie comme la taille du plus grand chemin entre la racine et une feuille. Par convention, une feuille a une pro-fondeur de 0. 3. Onsouhaite trouver une formulation récursive de la définition de la pro-fondeur maximale. Quelle relation existe-t-il, dans un arbre binaire, entre la 1
profondeur maximal d’un nœud et la profondeur maximale de ses fils.(0,5 point) 4. Donnezle code d’une méthoderécursivequi permet de déterminer la pro-fondeur maximale d’un arbre binaire.(2,5 points)
1.2 Rechercheunimodale (4 points) Remarque: attention cet exercice est le plus difficile du sujet. N’oubliez pas qu’il y a une seconde partie ! Un tableauA[0..n−1] estunimodals’il est composé d’une série d’éléments croissants suivie d’une série d’éléments décroissants. Formellement, il existe un indicemde0,n−1tel que : –A[i]<A[i+1] pour toutitel que 0≤i<m; –A[i]>A[i+1] pour toutitel quem≤i<n−1. En particulierA[m] est le plus grand élément et c’est le seul élément entouré d’éléments plus petits (A[m−1] etA[m+1]). Par exemple,[1,4,5,3,2,1,0]et[4,6,7]sont deux tableaux unimodaux dont les éléments maximaux sont, respectivement, 5 et 7. 5. Donnezle code en java d’un algorithme permettant de trouver le plus grand élément d’un tableau unimodal enOlogn.(4 points) 2 Remarque :vous pouvez vous inspirez d’un algorithme dont la complexité est en O(logn) vu en cours. 2
2 ProgrammationOrientée Objet (12 points) 2.1 Présentationdu problème (1 point) On souhaite définir, en java, une classe représentant un polynôme à coefficients 2n entiers de la formec0+c1∙x+c2∙x+...+cn∙x. Différentes structures de données sont envisageables pour représenter un polynôme en fonction des caractéristiques de celui-ci (degré, nombres de coefficients nuls, ...). C’est pourquoi on décide de définir une interfacePolynome etune classe abstraiteAbstractPolynome . La première partie du sujet porte sur la définition de la classe abstraite, la se-conde partie sur deux implémentations de celle-ci,DensePolynome etSparsePolynome. 6. Quelest l’intérêt de l’architecture proposée (séparation en interface, classe abstraite et classe concrète) ?(1 point)
2
2.2 InterfacePolynome(1,5 point) Voici l’interfacePolynome etla documentation qui lui est associée : importjava.lang.Iterable;
// Implémenteun polynôme dont les coefficients sont des entiers public interfacePolynomeextendsIterable<Integer> {
// Renvoie true si et seulement si tous les coefficients de ce // polynôme sont nuls. publicbooleanestZero();
// Renvoie le coefficient du terme de ce polynôme dont l’exposant // est l’entier spécifié. // // Par exemple, si le polynôme est x^2 + 3 * x + x^25, // this.coefficient(3) = 0 et this.coefficient(2) = 1 publicintcoefficient(intexposant);
// Renvoie la valeur de ce polynôme pour la valeur du paramètre // spécifié // // Par exemple, si le polynôme est x^2 + 3 * x + x^25, // this.valeur(0) = 0 et this.valeur(1) = 5 publicdoublevaleur(doublex);
// Renvoie un nouveau polynôme correspondant à l’addition du // polynôme spécifié avec un ce polynôme publicPolynomeadditionner(Polynome p); // Renvoie une chaîne de caractères correspondant au polynôme. // Cette chaîne est de la forme c1 * x^e1 + c2 * x^e2 + ... // // les exposants sont classés par ordre croissant, les termes de // coefficients nuls ne sont pas affichés et on ne prend pas en // compte le fait que certains termes peuvent être négatifs. // // Par exemple : 2 * x^0 + 3 * x^2 + -7 * x^23 publicStringtoString(); } 3
L’interface Polynome héritede l’interfaceIterable . Il est donc possible d’ob-tenir un itérateur retournant la valeur des coefficients des termes de ce polynôme (y compris les coefficients nuls). Les coefficients sont renvoyés par ordre croissant de leur degré. Le dernier élément renvoyé correspond au coefficient non nul de de-gré le plus élevé. L’itérateur renvoie desInteger . Par exemple, pour le polynôme 2 0 3+x, l’itérateur renverra successivement, 3 (coefficient dex), 0 (coefficient de 1 2 x) et 1 (coefficient dex). Pour mémoire : – lesinterface Iterable et Iterator sontrappelées en annexes; y – enjava la fonction (x,y)→xcorrespond àpow(x,y); 7. Onconsidère le morceau de code suivant : for(Integer c:p) { System.out.println(c); } oùpest une variable de typePolynomeinitialisée de manière à représenter 3 le polynômex−x+3. Pourquoi l’utilisation d’une boucle « foreach » est possible ? Quelle est la sortie du programme précédent ?(1 point) 8. Quellessont les méthodes qui devront être présentes dans les classes concrètes implémentant cette interface ?(0,5 point)
2.3 Définitionde la classeAbstractPolynome(2,5 points) Pour la classeAbstractPolynome proposezune implémentation des mé-thodes : 9.booleanestZero()(0,5 point) 10.doublevaleur(doublex)(1 point) 11. StringtoString()(1 point) On veillera à donner le code source complet (avec les entêtes) de la classe.
2.4 Définitionde la classeDensePolynome(4 points) La classeDensePolynome estune implémentation d’ AbstractPolynomeuti-lisant un tableau pour représenter tous les coefficients d’un polynôme des termes d’exposants inférieurs ou égaux à son degré (y compris les coefficients nuls). Avec une telle représentation, les indices du tableau représentent les exposants des termes alors que les valeurs du tableau contiennent les coefficients correspon-2 5 dant aux exposants. Par exemple, le polynôme 2+3∙x+12∙xsera représenté par
4
un tableau de six éléments contenant 2 à l’indice 0, 3 à l’indice 2 et 12 à l’indice 5. Tous les autres éléments du tableau sont nuls. Ce type de représentation est destinée à représenter les polynômes de petit degré ou les polynômes de degré élevé mais dont très peu de termes ont des coef-72 ficients nuls. Elle est par contre très peu adaptée pour stocker le polynôme 21+x. On appelle un tel polynôme (dont la majorité des coefficients est nulle) un poly-nôme creux (sparseen anglais). La classe possède également deux constructeurs permettant : – d’initialiserune instance représentant le polynôme nul; – d’initialiserun polynôme à partir d’une chaîne de caractères du type"3x0+2x2+4x4" 0 2 4 (cette chaîne décrit naturellement le polynôme 3∙x+2∙x+4∙x). On sup-posera que toutes les chaînes sont bien formées (c.-à-d. qu’elles seront tou-jours de la forme"t+t+t+t..."«t s’écrit, où chaquenombrexnombre»), que tous les nombres sont positifs et que les termes sont rangés par ordre croissant (plus grand exposant en dernier). 12. Enutilisant la classeAbstractPolynome donnezle code source complet de la classeDensePolynome .(4 points) RemarqueArrayList plutôt: il est conseillé d’utiliser unqu’un tableau.
2.5 Implémentationde la classeSparsePolynome(3 points) On souhaite maintenant définir une autre classe implémentant la classe abs-traite AbstractPolynome, qui serait plus adaptée aux polynômes creux.La struc-ture de données utilisée ne mémorise que les termes de coefficient non nul. Dans ce but, on définit une classeSparsePolynome quiutilisent un tableau asso-ciatif pour stocker un polynôme : – lesclés correspondent aux exposants de coefficient non nul ; – lavaleur associée à une clé correspond au coefficient associé à cette expo-sant. 72 Par exemple, le polynôme 21+xsera représenté par le tableau associatif suivant : clé 072 valeur 211 On vous demande : 13. d’implémenterun constructeur permettant d’initialiser unSparsePolynome à partir d’un tableau d’exposants et d’un tableau de coefficients. Par exemple : 9 2 le polynômex+3×x+SparsePolynome2 sera initialisé par({9, 2, 0}, {1, 3, 2}). On supposera que les tableaux passés en paramètre sont bien construits.(1,5 points)
5
14. d’implémenterla méthodeadditionner . On supposera que le résultat de l’addition sera également un polynôme creux. Par contre, le polynôme passé en paramètre peut aussi bien être un polynôme dense qu’un polynôme creux (il est de typePolynome).(1,5 points) On supposera que le code de toutes les autres méthodes est donné.
3 Annexes Classe pour représenter les nœuds d’un arbre binaire : public classNoeud{ privateNoeud filsGauche; privateNoeud filsDroit; privateintcontenu; publicNoeud(intc) { this.contenu=c; this.filsDroit=null; this.filsGauche=null; }
publicNoeud(intc,Noeud filsGauche,Noeud filsDroit) { this.contenu=c; this.filsDroit=filsDroit; this.filsGauche=filsGauche; }
public staticvoidmain(String[]s) {
Noeud Noeud Noeud Noeud
a=newNoeud(2); b=newNoeud(3,a,null); c=newNoeud(5,null,null); racine=newNoeud(4,c,b);
System.out.println(racine.profondeurMax()); } }
6
