TP3 - Manipulation de polynômes

Sommaire

Objectif

Dans ce troisième projet vous aurez l’occasion de pratiquer les concepts suivants:

  • Les routines et la décomposition fonctionnelle
  • Structures
  • Allocation dynamique
  • Pointeurs

Problématique

Le TP consiste à concevoir une librairie permettant d’effectuer plusieurs opérations sur des polynômes, dont les coefficients sont des entiers et les degrés sont positifs, modélisés par des listes doublement chaînées.

Exemple d’un polynôme de degré n : ax^n + bx^(n-1) + … + ux + z où les coefficients a, b, …, z sont des nombres entiers et les degrés n, n-1, … sont supérieurs ou égaux à 0.

Exemple avec des valeurs: 6x^3+2x^2+x

Note : pour faciliter l’affichage des polynômes, on va utiliser le symbole « ^ » pour désigner l’opérateur d’exponentiation.

La liste modélisant un polynôme est composée de nœuds qui représentent des termes du polynôme contenants l’information suivante :

  • Un entier a, coefficient (taille d’un mot)
  • Un entier n, degré de terme (taille d’un mot)
  • Lien vers le maillon précédant (taille d’un pointeur)
  • Lien vers le maillon suivant (taille d’un pointeur)

Les termes de chaque polynôme sont stockés dans un ordre décroissant de leur degré.

Votre programme devra être capable d’effectuer la création, la modification, la multiplication d’un terme et l’affichage d’un polynôme.

Routines à créer

Pour accomplir la tâche du TP, il sera nécessaire de créer au minimum les routines suivantes. Puisque votre bibliothèque sera utilisé avec un autre porgamme principale, n’oublier pas d’identifier vos routines de librairies comme .global pour que celles-ci soient visibles. Vous pouvez aussi faire les tests dans des fichiers séparé pour valider l’exportation des symboles de routines.

  • allocT
  • addT
  • printP
  • mulT
  • copy (extra)

Vous pouvez créer toutes les routines additionnelles que vous jugez utiles dans la réalisation de votre programme.

Routine allocT

La routine allocT alloue un maillon sur le tas composé de quatre champs et les initialise.

  • a0 : Le coefficient du nouveau terme.
  • a1 : le degré du nouveau terme.

Les quatre champs de chaque nœud sont les suivants :

  • Un entier représentant le coefficient du terme.
  • Un entier représentant le degré du terme.
  • Deux pointeurs initialisés à NULL (constante 0) pour les maillon précédent et suivant (dans cet ordre).
  • Résultat a0 : l’adresse du maillon créé.

Test - Création de maillon

    li a0, 5
    li a1, 7
    call allocT # Créé un maillon avec le coefficient 5 et le degré 7.

Routine addT

Cette routine doit insérer un maillon dans la liste à la bonne position. La liste doit être organisée en ordre décroissant des degrés des termes et est définie par le pointeur vers son premier élément.

  • a0 : l’adresse de la tête.

  • a1 : l’adresse du maillon à ajouté (on assume qu’il n’y à pas de lien vers d’autre maillon)

  • Résultat a0 : la tête

Test - Ajout d’un maillon

    li a0, 5
    li a1, 7
    call allocT # Premier maillon 5x^7

    mv s0, a0

    li a0, 2
    li a1, 6
    call allocT # Deuxième maillon 2x^6

    # Ajoute le maillon 2x^6 et 5x^7 ensemble
    mv a1, s0
    call addT # Retourne le maillon 5x^7 relié au maillon 2x^6

Routine printP

La routine printP affiche le contenu d’une liste polynôme.

L’affichage doit suivre la forme textuelle de polynôme suivante : -10x^4+10x^2+5x+20

  • a0 : L’adresse du maillon de tête du polynôme

Test - Affichage d’un polynôme

    li a0, 5
    li a1, 7
    call allocT

    mv s0, a0

    li a0, 2
    li a1, 6
    call allocT

    mv a1, s0
    call addT

    call printP # Affiche 5x^7+2x^6

Routine mulT

La routine mulT multiplie un terme d’un polynôme par une constante, si ce terme existe.

  • a0 : l’adresse du maillon de tête du polynôme

  • a1 : le degré du terme à multiplier

  • a2 : la valeur de multiplication du coefficient

  • Résultat a0: 0 si le maillon à été avec le bon degré trouvé et la modification réussi. -1 si le maillon avec le bon degré n’existe pas.

Test - Multiplication d’un polynôme

    li a0, 5
    li a1, 7
    call allocT

    mv s0, a0

    li a0, 2
    li a1, 6
    call allocT

    mv a1, s0
    call addT
    mv s0, a0
    
    li a1, 6
    li a2, 10
    call mulT
    
    mv a0,s0
    call printP ## Affiche 5x^7+20x^6

Test - Multiplication non trouvé

    li a0, 5
    li a1, 7
    call allocT

    mv s0, a0

    li a0, 2
    li a1, 6
    call allocT

    mv a1, s0
    call addT
    mv s0, a0
    
    li a1, 3
    li a2, 5
    call mulT
    
    li a7, 1 # PrintInt
    ecall # Affiche -1

Extra : Routine copy

Important : Cette partie est optionnelle et ne vaut que 2 points. Ne la faire que si tout le reste fonctionne et est d’excellente qualité.

La routine copy prend en paramètre une liste de polynôme (adresse de la tête) et retourne une copie profonde de cette liste.

  • a0 : l’adresse du maillon de tête du polynôme

  • Résultat a0 : l’adresse d’une copie du polynôme

Suggestion de développement

Pour vous aidez durant la réalisation de votre bibliothèque, il vous est suggéré de créé les éléments suivants. Ils ne seront pas évalué dans la remise.

Routine makeP

La routine makeP crée une liste représentant les termes d’un polynôme et retourne un pointeur vers son premier élément (tête). Elle permet la saisie des informations, la création des maillons de la liste doublement chaînée contenant ces informations, ainsi que l’enchaînement de ces maillons dans le bon ordre. Pour ce faire, elle utilise deux routines auxiliaires : allocT (allouer un terme) et addT (ajouter un terme).

La fin de la saisie des termes est définie par l’entrée d’une valeur négative pour le degré du terme.

Routine testMain

Une routine testMain (peux être renommer main et utilisé comme routine principale durant les test) permet de faire appel au fonctions du travail pour construire et tester l’affichage de polynômes.

  • call makeP # créer un polynôme
  • call printP # afficher le polynôme créé
  • call mulT # multiplier un terme du polynôme créé par une constante
  • call printP # afficher le polynôme

Exemples de création et d’affichage des différents polynômes.

Exemple 1

Entrée

Degré: 2

Coefficient: 10

Degré: 4

Coefficient: -10

Degré: 1

Coefficient: 5

Degré: 0

Coefficient: 20

Degré: -1

Sortie après l’appel de la routine printP

-10x^4+10x^2+5x+20

Exemple 2

Entrée

Degré: 2

Coefficient: -1

Degré: 0

Coefficient: -5

Degré: -1

Sortie après l’appel de la routine printP

-x^2-5

Exemple 3

Entrée

Degré: 0

Coefficient: 1

Degré: -1

Sortie après l’appel de la routine printP

1

Exemple 4

Entrée/Sortie

Degré: 2

Coefficient: -8

Degré: 6

Coefficient: 23

Degré: 4

Coefficient: -6

Degré: 0

Coefficient: -1

Degré: -1

23x^6-8x^2-6x^4-1
Sélectionner le degré du terme à multiplier: 6

Fournir la constante par laquelle multiplier le terme: -1

Polynôme avec un terme modifié par multiplication par une constante.
-23x^6-8x^2-6x^4-1

Exemple 5

Entrée/Sortie

Degré: 1

Coefficient: 1

Degré: 2

Coefficient: 2

Degré: 3

Coefficient: 3

Degré: 0

Coefficient: 5

Degré: -1

3x^3+2x^2+x+5
Sélectionner le degré du terme à multiplier: 0

Fournir la constante par laquelle multiplier le terme: 2

Polynôme avec un terme modifié par multiplication par une constante.
3x^3+2x^2+x+10

Exemple 6

Entrée/Sortie

Degré: 0

Coefficient: 1

Degré: -1

1
Sélectionner le degré du terme à multiplier: 0

Fournir la constante par laquelle multiplier le terme: 0

Polynôme avec un terme modifié par multiplication par une constante.
0

Exemple 7

Entrée/Sortie

Degré: 0

Coefficient: 5

Degré: -1

5
Sélectionner le degré du terme à multiplier: 0

Fournir la constante par laquelle multiplier le terme: 5

Polynôme avec un terme modifié par multiplication par une constante.
25

Exemple 8

Entrée/Sortie

Degré: 1

Coefficient: 1

Degré: 2

Coefficient: 2

Degré: 3

Coefficient: 3

Degré: 3

Coefficient: 3

Degré: -1

6x^3+2x^2+x
Sélectionner le degré du terme à multiplier: 2

Fournir la constante par laquelle multiplier le terme: 2

Polynôme avec un terme modifié par multiplication par une constante.
6x^3+4x^2+x

Réalisation

La réalisation de ce programme se fera par groupes, d’au plus, deux personnes. Chaque membre de l’équipe devra maîtriser tous les aspects du programme.

Contraintes d’implémentation:

  • Votre programme doit fonctionner avec RARS 1.7 en mode 64 bits (voir site du cours).
  • Il faudra respecter les conventions d’appel.

Évaluation

Aptitude fonctionnelle

  • 40%: tests publics (chaque test vaut 50*ceil(1/nombre de tests)).
    Les tests publics sont ceux présentés ci-dessus.

  • 60%: plusieurs tests privés évalués par le correcteur après la remise.
    Il est donc de votre responsabilité de vous assurer que votre programme fonctionne correctement au-delà des tests publics fournis.

Pour vous aider, le script de correction qui sera utilisé qui inclus tous les tests est disponible à https://gitlab.info.uqam.ca/inf2171/20243/tp3-corrige.

Important: si le programme remis ne s’assemble pas (erreur de syntaxe, fichier corrompu, etc.) ou si aucun test ne passe avec l’outil (échec systématique), la note zéro sera automatiquement attribuée au TP, et ce, indépendamment de la qualité du code, du temps de développement passé ou des affichages de RARS sur l’ordinateur de l’étudiant.

Qualité et lisibilité du code source

Des points bonus et malus seront attribués en fonction de la qualité du code.

  • Indentation et aération.
  • Nommage adéquat des symboles.
  • Présence et pertinence des commentaires.
  • Organisation du code, simplicité, modularité.

Les critères sont plus détaillés dans le guide de style.

Modalités de remise et dates

  • Date de remise: mercredi 13 décembre à 23h59.
  • La remise se fait via Moodle.
    • Remettez un seul fichier appelé polynomes.s (pas d’archive, juste ce fichier)
    • Mettez les noms, prénoms et codes permanents des étudiants du groupe en commentaire au début du fichier.
    • Dans un groupe de deux étudiants, un seul étudiant doit remettre.
    • Seule la remise la plus récente est considérée. Vous pouvez remettre autant de fois que vous le voulez avant l’échéance.
  • Si vous ne voulez pas perdre de points, assurez-vous de respecter le guide de style