Examen IN102, 28 novembre 2023

Cet examen dure 2 heures.

Autorisations

Les documents (polys, transparents, TDs, livres…) sont autorisés.
Sont absolument interdits : le web, le courrier électronique, les messageries, les répertoires des camarades, le téléphone (même pour avoir l’heure puisque vous l’avez sur votre ordinateur).

Soumission

A la fin de l’examen, vous devrez créer une archive contenant tous les fichiers sources que vous avez écrits (.c, .h). Le nom de cette archive devra avoir la structure nom_prenom.zip (ou .tgz selon l’outil d’archivage que vous utilisez). Par exemple, Laura Croft nommera son archive laura_croft.zip. Avec l’outil zip, la commande serait

zip -r laura_croft.zip nom_du_dossier_a_zipper

Cette archive est à soumettre deux fois, comme suivant :

Vous le téléchargez en utilisant le formulaire à l’adresse https://forms.office.com/e/658GHp8HvS.
Vous l’envoyez par mail à votre chargé de TD (comme pour les copies des TDs).

Partie 1 : Questionnaire à choix multiples

(sur papier)

Partie 2: Ecrire des programmes en C

Question 2 : Un peu de chiffrement

L’objectif est de réussir à chiffrer et déchiffrer un message avec une méthode relativement simple appelée le code de César. L’idée est de décaler les lettres de l’alphabet. Imaginons que nous utilisions un décalage de 4 lettres, alors le a devient un e, le b un f, le c un g etc. et le z un d.

Question 2.1

Ecrivez une fonction encode qui encode une chaîne de caractères avec la méthode expliquée en introduction. Cette fonction prendra en argument :

une chaîne de caractères (en minuscule, sans caractères spéciaux, sans espaces),
un entier qui correspondra au décalage que l’on souhaite faire.

Exemple :

encode("bonjour", 4) renvoie "fsrnsyv"
encode("voiture", 6) renvoie "buozaxk"

Question 2.2

Ecrivez une fonction main qui permettra de récupérer 2 arguments qui seront passés en ligne de commande :

la chaîne de caractères à encoder (en minuscule, sans caractères spéciaux et sans espaces)
un entier, le décalage que l’on souhaite effectuer.

Votre programme devra afficher :

sur la première ligne, la chaîne de caractères et sa longueur
sur la deuxième ligne, la chaîne de caractères encodée.

Question 2.3

Ecrivez un fonction decode et qui permettra de déchiffrer un message codé. Cette fonction prendra en argument :

une chaîne de caractères, en minuscule, sans caractères spéciaux, sans espace
un entier qui correspondra au décalage qui a été fait, dans un premier temps on pourra supposer que cet entier est positif.

Question 2.4 :

Complétez votre fonction main pour qu’elle affiche également la chaîne décodée.
Profitez-en pour vérifier que votre algorithme fonctionne bien.

Question 3: Calculer avec des polynômes

On définit un polynôme comme une fonction de la forme : $P(X) = a_0 + a_1 X + a_2 X^2 + \ldots + a_n X^n = \sum_{i = 0}^n a_i X^i$ .

Nous souhaitons implémenter une bibliothèque de gestion de polynômes. Les polynômes sont à stocker dans la structure suivante :

struct polynom {
	int degree;
	float *coefficients;
};

Cette structure contient un pointeur vers un tableau de flottants pour stocker les coefficients du polynômes (i.e., les $a_i$ ) et un entier pour stocker le degré de $P$ (i.e., la valeur de $n$ ).

Question 3.1

Implémentez une fonction struct polynom* create_polynom(int degree, float *coefficients*) qui alloue de la mémoire pour stocker un polynôme de degré degree dont les coefficients sont ceux du tableau coefficients. Le premier élément de coefficients est le coefficient de degré 0 ( $a_0$ ), le deuxième élément est celui de degré 1 ( $a_1$ ), etc.
Cette fonction retourne un pointeur vers la zone mémoire allouée.

Question 3.2

Implémentez une fonction float random_float(float max) qui retourne un flottant aléatoire dans l’intervalle $[0, max]$ .

Astuce : générez un nombre aléatoire que vous divisez par RAND_MAX une valeur inclue dans stdlib.h qui est la valeur maximal d’un entier tiré aléatoirement : vous obtenez un nombre entre 0 et 1. Multipliez ensuite le résultat par max.

Question 3.3

Implémentez une fonction struct polynom create_random_polynom(int degree, float max) qui crée et retourne un polynome de degré degree et dont les coefficients sont choisi aléatoirement et inférieur à max.

Astuce : utilisez la fonction random_float de la question précédente. Si vous n’avez pas réussi à répondre à cette question, vous la simplifiez par une fonction qui donne toujours la valeur $0.33$ .

Question 3.4

Implémentez une fonction struct polynom create_custom_polynom(int degree) qui crée un polynome de degré degree et dont les coefficients sont saisis par l’utilisateur via l’utilisation de la fonction scanf.

Question 3.5

Implémentez une fonction void print_polynom(struct polynom *) qui affiche le polynôme dans l’ordre de degrés croissants, sans les coefficients qui valent zéro. Par exemple, au lieu d’afficher 0*X^0 + 1*X^1 + 0*X^2 + 3*X^3, on affichera X + 3*X^3. On évitera de faire suivre un +par un -, donc au lieu d’afficher X^2 + -3*X^3, on affichera X^2 - 3*X^3.

Question 3.6

Implémentez une fonction struct polynom sum_polynom(struct polynom p1, struct polynom p2) pour construire un nouveau polynome $R = \sum c_i X^i$ qui est la somme des deux polynômes donnés en paramètre, i.e., $P_1 = \sum a_i X^i$ et $P_2 = \sum b_i X^i$ tel que $c_i = a_i + b_i$ .

Question 3.7

Implémentez une fonction struct polynom prod_polynom(struct polynom p1, struct polynom p2) pour construire un nouveau polynôme $R = \sum c_i X^i$ qui est la multiplication des deux polynômes donnés en paramètre, i.e., $P_1 = \sum a_i X^i$ et $P_2 = \sum b_i X^i$ tel que $c_i = \sum _{k = 0}^i a_k b_{i-k}$ .

Question 3.8

Implémentez une fonction float eval_naive_polynom(float x, struct polynom *p) qui retourne l’évaluation naïve du polynôme p en x, c’est-à-dire sans aucune optimisations de calcul.

Astuce : utiliser la fonction powf de la librairie math.h. Par exemple, l’instruction powf(x,i) donne la valeur de $X^i$ .

Question 3.9

Les polynômes dorés (Golden polynomials) sont définis avec la suite $G_0(X)=-1$ , $G_1(X)=X-1$ et

G_{k} = X * G_{k - 1} + X * G_{k - 2} .

$G_k=X*G_{k-1} + X*G_{k-2}.$
Ecrivez une fonction struct polynom* golden_polynom(int k) qui retourne un tableau contenant les polynômes

G_{0}, G_{1}, . . ., G_{k}

$G_0,G_1,...,G_k$ . Utilisez obligatoirement les fonctions sum_polynom et prod_polynom (on ne cherche pas à trouver l’implémentation la plus rapide).

Dans votre main, appelez golden_polynom avec k=6 et affichez le tableau résultant en utilisant print_polynom.

Astuce: N’oubliez pas de libérer toute la mémoire réservée à la fin du programme.