Le but de cet exercice est de reprendre l'exemple du cours illustrant la gestion des structures.
Cliquez ici si vous souhaitez faire cet exercice.
Le but de ce programme est d'effectuer les manipulations élémentaires sur les nombres complexes : addition, soustraction, multiplication et division.
Dans le fichier complexes.cc, définissez une structure Complexe représentant un nombre complexe comme deux double (forme cartésienne).
Ensuite, prototypez puis définissez une procédure affiche qui prend un nombre complexe en argument et l'affiche.
Dans le main(), déclarez et initialisez un nombre complexe. Affichez-le. Compilez et exécutez votre programme pour vérifier que tout fonctionne comme prévu jusqu'ici.
Prototypez puis définissez une fonction addition qui prend deux nombres complexes en argument et retourne leur somme.
Testez votre fonction dans le main().
Terminez l'exercice en écrivant puis testant les fonctions soustraction, multiplication et division.
Rappel : la multiplication de z=(x,y) par z'=(x',y')
est le nombre complexe z*z'=(x*x'-y*y', x*y'+y*x').
la division de z=(x,y) par z'=(x',y')
est le nombre complexe z/z'=((x*x'+y*y')/(x'*x'+y'*y'),
(y*x'-x*y')/(x'*x'+y'*y')).
(1,0) + (0,1) = (1,1) (0,1) * (0,1) = (-1,0) (1,1) * (1,1) = (0,2) (0,2) / (0,1) = (2,0) (2,-3) / (1,1) = (-0.5,-2.5)
On cherche ici à faire un programme d'examen sous forme de questionnaire à choix multiple (QCM) où une question est posée et la réponse est à choisir parmi un ensemble de réponses proposées (une seule bonne réponse possible par question).
Dans un programme qcm.cc, définissez une structure QCM comprenant 3 champs :
Prototypez puis définissez une procédure affiche qui prend un QCM en argument et l'affiche. Par exemple :
Combien de dents possède un éléphant adulte ?
1- 32
2- de 6 à 10
3- beaucoup
4- 24
5- 2
Dans le main(), créez et initialisez le QCM ci-dessus, puis affichez le. Compilez et vérifiez que tout fonctionne correctement jusqu'ici.
Reprenez la fonction demander_nombre (avec 2 arguments, point 4 de l'exercice 2 de la série 5) définie dans ../serie05/proto.cc, et créez une fonction poser_question qui prend un QCM en argument, appelle successivement affiche et demander_nombre et retourne la réponse de l'utilisateur.
Avant de continuer, testez votre programme (affichage de la question et saisie de la réponse).
On cherche maintenant à faire un examen de plusieurs questions. Définissez le type Examen comme un tableau dynamique de QCM. Créez un Examen dans le main(), puis remplissez-le (dans une fonction creer_examen c'est mieux !) avec les questions suivantes (code partiel) :
// Question 1
{ "Combien de dents possède un éléphant adulte",
{ "32", "de 6 à 10", "beaucoup", "24", "2" },
2 // réponse
},
// Question 2
{ "Laquelle des instructions suivantes est un prototype de fonction",
{ "int f(0);" ,
"int f(int 0);" ,
"int f(int i);" ,
"int f(i);" },
3 // réponse
},
// Question 3
{ "Qui pose des questions stupides",
{ "le prof. de math",
"mon copain/ma copine",
"le prof. de physique",
"moi",
"le prof. d'info",
"personne, il n'y a pas de question stupide",
"les sondages" } ,
6 // réponse
}
q.question = "Combien de dents possède un éléphant adulte";
q.reponses.push_back("32");
q.reponses.push_back("de 6 à 10");
q.reponses.push_back("beaucoup");
q.reponses.push_back("24");
q.reponses.push_back("2");
q.solution=2;
q.question = "Laquelle des instructions suivantes est un prototype de fonction";
q.reponses.push_back("int f(0);");
q.reponses.push_back("int f(int 0);");
q.reponses.push_back("int f(int i);");
q.reponses.push_back("int f(i);");
q.solution=3;
q.question = "Qui pose des questions stupides";
q.reponses.push_back("le prof. de math");
q.reponses.push_back("mon copain/ma copine");
q.reponses.push_back("le prof. de physique");
q.reponses.push_back("moi");
q.reponses.push_back("le prof. d'info");
q.reponses.push_back("personne, il n'y a pas de question stupide");
q.reponses.push_back("les sondages");
q.solution=6;
Pour terminer :
Combien de dents possède un éléphant adulte ?
1- 32
2- de 6 à 10
3- beaucoup
4- 24
5- 2
Entrez un nombre entier compris entre 1 et 5 : 2
Laquelle des instructions suivantes est un prototype de fonction ?
1- int f(0);
2- int f(int 0);
3- int f(int i);
4- int f(i);
Entrez un nombre entier compris entre 1 et 4 : 3
Qui pose des questions stupides ?
1- le prof. de math
2- mon copain/ma copine
3- le prof. de physique
4- moi
5- le prof. d'info
6- personne, il n'y a pas de question stupide
7- les sondages
Entrez un nombre entier compris entre 1 et 7 : 5
Vous avez trouvé 2 bonnes réponses sur 3.
On s'intéresse ici à la résolution d'équations du second degré sur le corps des complexes.
Copiez le programme complexes.cc dans le programme complexes2.cc et éditez ce dernier.
Écrivez la fonction Complexe sqrt(Complexe); qui calcule la racine carrée de partie réelle positive d'un nombre complexe.
On peut montrer que la racine carrée z'=(x',y') de partie réelle positive d'un nombre complexe z=(x,y) est donnée par :
Testez avant de continuer. Calculez par exemple la racine carrée de -1.
Déclarez le type Solutions comme une structure à 2 champs Complexes : z1 et z2.
Pour finir prototypez puis définissez la fonction
resoudre_second_degre qui prend deux arguments
Complexe b et c et retourne, sous forme de
Solution, les solution de l'équation
z*z + b*z + c= 0
Avec b=0 et c=1 on a : z1=-i z2=i Avec b=3-2i et c=-5+i on a : z1=-4.11442+1.76499i z2=1.11442+0.235013i
Nous allons définir une structure Fraction, qui permettra de représenter des fractions, c'est-à-dire un numérateur et un dénominateur (entiers).
Nous voulons que les fractions soient toujours irréductibles, même après un calcul. Par exemple, le produit des fractions 4⁄25 et 15⁄2 devra donner la fraction 6⁄5, et non pas la fraction 60⁄50. Pour cela, on pourra utiliser la fonction pgcd de l'exercice 6 de la série 5.
Ainsi, la fonction init_frac s'écrit (par exemple, il y a d'autres solutions) :
Fraction init_frac(int num, int den)
{
const int div( pgcd( abs(num), abs(den) ) );
if (num < 0 and den < 0) {
num = -num;
den = -den;
}
return { num / div , den / div };
}
Ecrivez les fonctions afficher_frac, add_frac, mult_frac, mult_scal_frac, dont le but est, respectivement, d'afficher une fraction, d'additioner 2 fractions, de multiplier 2 fractions et de multiplier une fraction par un scalaire.
En utilisant la fonction init_frac, les fonctions add_frac, mult_frac, mult_scal_frac peuvent s'écrire très simplement, sur une seule ligne.
Testez vos fonctions sur des exemples numériques.
Je vous propose ici de coder l'échantillonnage d'un signal et sa reconstruction à partir des échantillons.
Pour commencer, définissez un type Sinuoide qui regroupe les trois caractéristique d'une sinusoide : amplitude, fréquence et déphasage.
Faites ensuite une fonction sin_pure qui calcule la valeur en un point x d'une sinusoide telle que définie ci-dessus ; par exemple :
double sin_pure(double x, Sinusoide const& s = { 1.0, 1.0, 0.0 });
Définissez ensuite un type Signal qui regroupe plusieurs sinusoïde pures et une fonction signal qui calcule la valeur en un point x d'un tel signal, somme de sinusoïde ; par exemple :
double signal(double x, Signal const& s);
Définissez maintenant un type Signal_Echant qui regroupe :
Définissez ensuite une fonction echantillonne qui à partir d'un signal, d'une fréquence d'échantillonnage, d'un temps initial et d'un temps final, construit (et retourne) le signal échantillonné. Son prototype pourrait par exemple être :
Signal_Echant echantillonne(Signal const& s, double freq,
double t_min = 0.0,
double t_max = 1.0);
Pour construire un tel signal échantillonné, il faut 1+size_t(freq * (t_max - t_min)) échantillons correspondant chacun au signal évalué au temps t_min + i / freq.
Comme nous ne pouvons pas faire une somme infinie, la formule de reconstruction implémentée ici ne sera qu'une approximation de la formule théorique : nous allons simplement sommer sur tous les échantillons (elle sera donc plus fausse aux bords) :
la valeur reconstruite en un points x est la somme sur tous les échantilllons, chacun multiplié par le sinus cardinal de la fréquence d'échantiollanage fois x moins le temps initial, le tout moins i, le numéro d'échantillon:
sinc(freq_ech * (x - t_initial) - i)
Nous vons conseillons pour cela, bien sûr, d'écrire une fonction auxiliaire « sinus cardinal ». Afin d'éviter le problème du calcul en 0 : retourner la valeur 1 si l'argument est plus petit que, disons, 1e-8.
Pour voir/expérimenter les effets du théorème d'échantillonnage, je vous propose dans le main() de :
0 0.189358 0.189358 0.189358 0.002 0.287194 0.23914 0.198669 0.004 0.383332 0.291892 0.208352 ... etc.
Si vous ne savez pas comment faire tout ça, voici un exemple de main() possible :
int main() { Signal s({ { 1.0 , 2.0, 0.0 }, // première composante { 0.5 , 4.0, 0.1 }, // ... { 0.33, 6.0, 0.2 }, // ... { 0.25, 8.0, 0.3 }, // ... }); constexpr double t_min(0.0); constexpr double t_max(2.0); Signal_Echant se1(echantillonne(s, 20.0, t_min, t_max)); Signal_Echant se2(echantillonne(s, 11.0, t_min, t_max)); // « dessin » des trois courbes constexpr size_t nb_points(1000); constexpr double dt((t_max-t_min) / nb_points); for (double t(t_min); t <= t_max; t += dt) { cout << t << " " << signal(t, s) << " " << reconstruction(t, se1) << " " << reconstruction(t, se2) << endl; } return 0; }
Pour vous aider, si nécessaire, à corriger votre programme, expliquons d'où vient la seconde ligne donnée ci-dessus :
0.002 0.287194 0.23914 0.198669
Ces quatre nombres représentent respectivement, le temps, le signal d'origine, le signal échantillonné à la première fréquence (20 Hz) puis reconstruit et le signal échantillonné à la seconde fréquence (11 Hz) puis reconstruit, provenant de la ligne du main() :
cout << t
<< " " << signal(t, s)
<< " " << reconstruction(t, se1)
<< " " << reconstruction(t, se2)
<< endl;
Le signal calculé ici est
sin(4πt)+0.5 sin(8πt+0.1)+0.33 sin(12πt+0.2)+0.25 sin(16πt+0.3),
ce qui, pour t=0.02 donne :
0.0251301 + 0.0748503 + 0.089737 + 0.0974768 = 0.287194.
Le signal échantilloné à 20 Hz puis reconstruit est calculé comme la somme des 41 termes suivants :
0.189358 * sinc(20 * (0.002 - 0) - 0 ) = 0.189358 * 0.99737 = 0.18886 1.44431 * sinc(20 * (0.002 - 0) - 1 ) = 1.44431 * 0.0415571 = 0.0600213 0.75564 * sinc(20 * (0.002 - 0) - 2 ) = 0.75564 * -0.0203545 = -0.0153807 0.731161 * sinc(20 * (0.002 - 0) - 3 ) = 0.731161 * 0.013478 = 0.00985457 0.257756 * sinc(20 * (0.002 - 0) - 4 ) = 0.257756 * -0.0100744 = -0.00259675 0.0582359 * sinc(20 * (0.002 - 0) - 5 ) = 0.0582359 * 0.00804331 = 0.000468409 -0.305928 * sinc(20 * (0.002 - 0) - 6 ) = -0.305928 * -0.00669376 = 0.00204781 -0.660188 * sinc(20 * (0.002 - 0) - 7 ) = -0.660188 * 0.00573201 = -0.0037842 -0.896827 * sinc(20 * (0.002 - 0) - 8 ) = -0.896827 * -0.00501191 = 0.00449481 -1.57352 * sinc(20 * (0.002 - 0) - 9 ) = -1.57352 * 0.00445255 = -0.00700616 0.189358 * sinc(20 * (0.002 - 0) - 10 ) = 0.189358 * -0.0040055 = -0.000758473 1.44431 * sinc(20 * (0.002 - 0) - 11 ) = 1.44431 * 0.00364004 = 0.00525734 0.75564 * sinc(20 * (0.002 - 0) - 12 ) = 0.75564 * -0.00333569 = -0.00252058 0.731161 * sinc(20 * (0.002 - 0) - 13 ) = 0.731161 * 0.0030783 = 0.00225073 0.257756 * sinc(20 * (0.002 - 0) - 14 ) = 0.257756 * -0.00285779 = -0.000736615 0.0582359 * sinc(20 * (0.002 - 0) - 15 ) = 0.0582359 * 0.00266677 = 0.000155301 -0.305928 * sinc(20 * (0.002 - 0) - 16 ) = -0.305928 * -0.00249967 = 0.00076472 -0.660188 * sinc(20 * (0.002 - 0) - 17 ) = -0.660188 * 0.00235229 = -0.00155295 -0.896827 * sinc(20 * (0.002 - 0) - 18 ) = -0.896827 * -0.00222131 = 0.00199213 -1.57352 * sinc(20 * (0.002 - 0) - 19 ) = -1.57352 * 0.00210416 = -0.00331093 0.189358 * sinc(20 * (0.002 - 0) - 20 ) = 0.189358 * -0.00199874 = -0.000378476 1.44431 * sinc(20 * (0.002 - 0) - 21 ) = 1.44431 * 0.00190338 = 0.00274907 0.75564 * sinc(20 * (0.002 - 0) - 22 ) = 0.75564 * -0.0018167 = -0.00137277 0.731161 * sinc(20 * (0.002 - 0) - 23 ) = 0.731161 * 0.00173758 = 0.00127045 0.257756 * sinc(20 * (0.002 - 0) - 24 ) = 0.257756 * -0.00166506 = -0.000429179 0.0582359 * sinc(20 * (0.002 - 0) - 25 ) = 0.0582359 * 0.00159835 = 9.30813e-05 -0.305928 * sinc(20 * (0.002 - 0) - 26 ) = -0.305928 * -0.00153678 = 0.000470144 -0.660188 * sinc(20 * (0.002 - 0) - 27 ) = -0.660188 * 0.00147978 = -0.000976931 -0.896827 * sinc(20 * (0.002 - 0) - 28 ) = -0.896827 * -0.00142685 = 0.00127964 -1.57352 * sinc(20 * (0.002 - 0) - 29 ) = -1.57352 * 0.00137758 = -0.00216765 0.189358 * sinc(20 * (0.002 - 0) - 30 ) = 0.189358 * -0.0013316 = -0.000252149 1.44431 * sinc(20 * (0.002 - 0) - 31 ) = 1.44431 * 0.00128859 = 0.00186113 0.75564 * sinc(20 * (0.002 - 0) - 32 ) = 0.75564 * -0.00124827 = -0.000943246 0.731161 * sinc(20 * (0.002 - 0) - 33 ) = 0.731161 * 0.0012104 = 0.000884998 0.257756 * sinc(20 * (0.002 - 0) - 34 ) = 0.257756 * -0.00117476 = -0.000302802 0.0582359 * sinc(20 * (0.002 - 0) - 35 ) = 0.0582359 * 0.00114116 = 6.64562e-05 -0.305928 * sinc(20 * (0.002 - 0) - 36 ) = -0.305928 * -0.00110942 = 0.000339403 -0.660188 * sinc(20 * (0.002 - 0) - 37 ) = -0.660188 * 0.0010794 = -0.00071261 -0.896827 * sinc(20 * (0.002 - 0) - 38 ) = -0.896827 * -0.00105097 = 0.000942538 -1.57352 * sinc(20 * (0.002 - 0) - 39 ) = -1.57352 * 0.00102399 = -0.00161127 0.189358 * sinc(20 * (0.002 - 0) - 40 ) = 0.189358 * -0.000998369 = -0.000189049
ce qui donne la valeur 0.23914.
Le signal échantilloné à 11 Hz puis reconstruit est calculé comme la somme des 23 termes suivants :
0.189358 * sinc(11 * (0.002 - 0) - 0 ) = 0.189358 * 0.999204 = 0.189207 0.851989 * sinc(11 * (0.002 - 0) - 1 ) = 0.851989 * 0.022477 = 0.0191502 0.482616 * sinc(11 * (0.002 - 0) - 2 ) = 0.482616 * -0.0111135 = -0.00536355 -0.0101872 * sinc(11 * (0.002 - 0) - 3 ) = -0.0101872 * 0.00738163 = -7.51984e-05 -0.643095 * sinc(11 * (0.002 - 0) - 4 ) = -0.643095 * -0.00552602 = 0.00355375 -1.53079 * sinc(11 * (0.002 - 0) - 5 ) = -1.53079 * 0.00441593 = -0.00675985 1.45684 * sinc(11 * (0.002 - 0) - 6 ) = 1.45684 * -0.00367723 = -0.00535713 0.72608 * sinc(11 * (0.002 - 0) - 7 ) = 0.72608 * 0.00315026 = 0.00228734 0.0696877 * sinc(11 * (0.002 - 0) - 8 ) = 0.0696877 * -0.00275539 = -0.000192017 -0.528292 * sinc(11 * (0.002 - 0) - 9 ) = -0.528292 * 0.00244848 = -0.00129351 -1.06421 * sinc(11 * (0.002 - 0) - 10 ) = -1.06421 * -0.0022031 = 0.00234455 0.189358 * sinc(11 * (0.002 - 0) - 11 ) = 0.189358 * 0.00200241 = 0.000379172 0.851989 * sinc(11 * (0.002 - 0) - 12 ) = 0.851989 * -0.00183524 = -0.0015636 0.482616 * sinc(11 * (0.002 - 0) - 13 ) = 0.482616 * 0.00169383 = 0.000817468 -0.0101872 * sinc(11 * (0.002 - 0) - 14 ) = -0.0101872 * -0.00157265 = 1.60209e-05 -0.643095 * sinc(11 * (0.002 - 0) - 15 ) = -0.643095 * 0.00146765 = -0.00094384 -1.53079 * sinc(11 * (0.002 - 0) - 16 ) = -1.53079 * -0.0013758 = 0.00210605 1.45684 * sinc(11 * (0.002 - 0) - 17 ) = 1.45684 * 0.00129476 = 0.00188626 0.72608 * sinc(11 * (0.002 - 0) - 18 ) = 0.72608 * -0.00122274 = -0.000887809 0.0696877 * sinc(11 * (0.002 - 0) - 19 ) = 0.0696877 * 0.00115831 = 8.07203e-05 -0.528292 * sinc(11 * (0.002 - 0) - 20 ) = -0.528292 * -0.00110033 = 0.000581298 -1.06421 * sinc(11 * (0.002 - 0) - 21 ) = -1.06421 * 0.00104788 = -0.00111516 0.189358 * sinc(11 * (0.002 - 0) - 22 ) = 0.189358 * -0.0010002 = -0.000189396
ce qui donne la valeur 0.198669.
Le plus simple pour visualiser ce que votre programme a sorti est d'utiliser un outil de dessin externe, comme par exemple gnuplot, qui est un programme (à lancer depuis la ligne de
commande) de dessin de données et de fonctions.
Vous pouvez aussi, naturellement, utiliser n'importe quel autre logiciel capable de dessiner des courbes à partir de points, comme des tableurs (LibreOffice, ou autres) ou Matplotlib, Octave, etc.
gnuplot lit des fichiers dont chaque ligne contient un point à dessiner, les coordonnées étant par colonnes, exactement comme le sort votre programme. Pour que la sortie de votre programme soit stockée dans un fichier, il suffit de le lancer depuis un terminal et « rediriger sa sortie » dans un fichier avec le signe >. Cela se fait simplement comme ceci:
./signal > data.txt
C'est aussi simple que cela ! Avec ça, vous devriez avoir, dans le répertoire courant, un fichier data.txt qui contient :
0 0.189358 0.189358 0.189358 0.002 0.287194 0.23914 0.198669 0.004 0.383332 0.291892 0.208352 0.006 0.477329 0.347325 0.218412 0.008 0.568761 0.405119 0.228854 0.01 0.657223 0.464923 0.23968 ... etc.
Une fois que vous avez un tel fichier (bon pour gnuplot), il suffit de lancer la commande gnuplot dans le terminal, puis, dans gnuplot, de taper
set style data line
plot "data.txt" u 1:2 t "signal", "data.txt" u 1:3 t "fe 20",
"data.txt" u 1:4 t "fe 10"
et vous devriez alors voir ceci (pour le main() donné plus haut) :
NOTE : les écarts aux bords (en début et fin) entre le signal d'origine et le premier signal reconstruit (correctement échantilloné) ne sont simplement du qu'au fait que nous ne faisons pas une somme infinie mais simplement une somme finie dans la formule de reconstruction. Il faut donc regarder « au milieu » pour voir que la reconstruction est assez bonne (parfaite en théorie avec sommes infinies).
Pour quitter gnuplot : simplement quit ou 'Control-D'.
Le « u 1:3 » signifie que l'on utilise la 1àre et la 3e colonne pour dessiner. Sinon gnuplot utilise les deux premières (i.e. il fait un « u 1:2 »).
Le « t "..." » est pour donner un titre à une courbe (légende sur le coté en haut à droite).
La commande « set style data line » demande à gnuplot d'utiliser simplement des lignes pour dessiner les données; sinon par défaut gnuplot utilise des « points » (petits symoles, en fait) pour dessiner les fichiers de données.
Le problème dit « du sac à dos » consiste à trouver, parmi un ensemble initial d'objets ayant chacun un poids et une valeur, quels objets mettre dans le sac de sorte que celui-ci ai une valeur maximale, mais ne pèse pas plus qu'un poids fixé au départ.
Par exemple, on chercher à remplir au mieux (valeur maximale) le sac à dos à partir des objets suivants, mais sans dépasser un poids total de 9 kg :
A noter que c'est bien la contrainte du poids maximal à ne pas dépasser qui rend ce problème « intéressant ». Sans une telle contrainte, il suffirait de tout mettre dans le sac pour maximiser sa valeur !
Ce problème « du sac à dos » est un problème NP-complet, c.-à-d. qu'à ce jour on ne connaît pas de meilleur algorithme pour le résoudre que celui qui consiste à essayer toutes les solutions.
Face à ce genre de problèmes, on peut alors chercher à ne pas le résoudre de façon optimale, mais utiliser un algorithme plus efficace que la recherche exhaustive, mais qui ne donnera qu'une solution approximative (une bonne solution mais qui n'est pas garantie pour être la meilleure).
Par exemple, un algorithme simple non optimal consiste à simplement remplir le sac avec les objets dans l'ordre dans lequel ils sont donnés/posés sur la table, si c'est possible (c.-à-d. ajouter l'objet ne fait pas dépasser le poids maximal autorisé).
Un autre algorithme simple non optimal consiste remplir le sac en mettant l'objet le plus lourd en premier si c'est possible, puis ensuite le 2e objet le plus lourd si c'est possible, etc. C'est le même algorithme que le précédent mais où l'on a au préalable trié les objets par poids décroissant. On appelle cet algorithme, un algorithme « glouton » car il « veut » consommer le plus en premier.
Si l'on applique le premier algorithme à l'exemple ci-dessus :
Au final, on arrive avec un poids total = 6 kg et une valeur totale de 11.
Si l'on applique l'algorithme glouton :
Au final, on arrive avec un poids total = 8 kg et une valeur totale de 13, ce qui est déjà mieux.
Mais la solution optimale consiste ici à prendre la boîte et le paquet. Le poids total est de 9 kg et la valeur totale de 15.
Le but est de programmer ces trois algorithmes. Commencez pour cela par représenter la liste des objets possibles, par exemple comme un ensemble de paires de valeurs.
Implémentez ensuite la recherche naïve (premier algorithme) dans une fonction qui prend en paramètres une liste d'objets et un poids maximal. Cette fonction affichera la valeur maximale trouvée et le poids restant libre dans le sac (avec notre exemple, elle afficherait : « valeur : 11, poids restant : 3 kg »).
Implémenez ensuite l'algorithme glouton en :
La partie la plus difficile est la recherche exacte. Celle-ci se fera de façon récursive en considérant le meilleur résultat des deux solutions consistant à prendre ou non le premier objet de la liste puis rechercher sur la suite de la liste des objets.
Plus précisément : écrire une fonction (récursive) qui prend une liste d'objets, un index de début et un poids maximum et qui
Le but de cet exercice est de réaliser des codes de Huffman de textes. Le principe du code de Huffman (binaire) est assez simple (cf cours ICC): il consiste à regrouper les deux « entités » les moins probables à chaque étape; une « entité » étant soit une lettre de départ, soit un groupe d'entités déjà traitées (une, deux, trois, ... lettres déjà traitées).
Le plus simple est peut être de commencer directement par l'algorithme lui-même à un niveau d'abstraction assez haut (approche descendante) :
à partir de la distribution de probabilité initiale des lettres (leur compte), on va, de proche en proche tant qu'il nous reste plus que deux « entités » à traiter
rechercher les deux entités les moins probables ;
ajouter le symbole '0' devant tous les codes déjà produits pour la première de ces deux entités ;
ajouter le symbole '1' devant tous les codes déjà produits pour la seconde de ces deux entités ;
fusionner ces deux entités en une nouvelle entité, dont on calcule la probabilité : somme des probabilités des deux entités fusionnées;
pour cela on écrasera une de ces deux entités par leur fusion et on supprimera l'autre.
Notez qu'on a donc une entité de moins à chaque fois (la fusion supprime les deux entités, mais n'en rajoute qu'une seule nouvelle).
Il nous faut donc représenter ces « entités » (et un ensemble d'entités). Je vous propose de le faire de la façon suivante :
une « entités » est simplement un groupe de lettres avec sa probabilité ;
le groupe de lettres peut simplement être représenté par la liste des positions de ces lettres (voir ci-dessous) ;
au départ, ces entités correspondent simplement aux lettres du mot avec leur probabilité.
Nous aurons aussi besoin de représenter le code lui-même. Un code est une bijection entre les mots à coder et leur code. La bonne structure de données pour représenter cela est ce que l'on appelle des « tables associatives », que nous n'avons pas encore vues (2e semestre). A ce stade du cours, nous vous proposons donc simplement de représenter le code comme un tableau dynamique de structures contenant:
Prenons un exemple (cf cours ICC) :
supposons que l'on veuille coder la phrase « JE PARS A PARIS »
On commencera par créer un « code » (il n'est pas complet à ce stade, tous ses mots sont vides) contenant par exemple (ordre de lecture ici, mais vous pouvez changer cet ordre, bien sûr):
Une fois ce « code » (mots vides) créé, on pourra créer la version initiale de la liste d'« entités » nécessaires pour l'algorithme décrit plus haut (ordonnée à nouveau ici dans l'ordre de lecture, mais vous pouvez choisir un autre ordre):
Pour l'instant cette liste d'« entités » ne semble pas très intéressante et semble faire double emploi avec le code : c'est normal : le code de Huffman commence par les lettres seules.
Mais dès la première étape de codage, cela va changer : on commence par regrouper les deux moins probables, disons par exemple le "J" et le "E" (les deux premiers moins probables dans l'ordre de lecture, là encore votre choix peut être différent suivant comment vous écrivez l'algorithme, cela ne change rien au final sur la longueur moyenne du code). On aura alors une nouvelle entité :
indices: 0, 1, probabilité : 2./12.;
et la liste d'« entités » devient (elle ne contient plus que 7 éléments):
Et comme dit au départ de cet exercice : une fois la fusion ci-dessus effectuée (ou même avant), on ajoutera respectivement '0' et '1' à chacun des mots de code correspondants. Dans cet exemple précis, cela à revient à les ajouter à chacun des deux mots de code, vides, de "J" et "E".
Voilà pour les structures de données proposées pour cet algorithme.
Pour l'algorithme lui-même : adoptez (bien sûr !) une démarche très modulaire en introduisant des fonctions pour chacune des tâches élémentaires ; par exemple : compter les lettres, normaliser les probabilités, fusionner 2 entités, rechercher les deux entités les moins probables, ajouter un symbole à un mot de code, construire les entités initiales à partir d'un « code » (mots vides), etc. etc.
Le but est d'écrire un programme turing.cc permettant de simuler une machine de Turing.
Si vous n'avez aucune idée sur la manière de procéder, vous pouvez utiliser la modélisation proposée ci-dessous, sinon allez y puis reprenez l'exercice ici.
Proposition de méthode :
Notez que, dans l'implémentation proposée, lecture et ecriture peuvent changer la valeur de tete : comme indiqué au point 1. ci-dessus, l'aspect infini de la bande est simulé en insérant le bon nombre d'epsilons en début de bande lorsque la position de la tête devient négative. Il faut alors naturellement repositionner la tête à la valeur zéro lorsque cela a été fait, et donc modifier sa valeur. On aurait également pu choisir d'effectuer ces opérations (simuler une bande infinie) lors des déplacements de la tête plutôt que lors de la lecture/écriture...(libre à vous)
struct Transition
{
Etat etat;
char caractere;
int deplacement;
}
typedef array Ligne; // 3 : caractères 0 , 1 , epsilon
Avec une telle représentation, une table de transitions sera simplement un tableau de Lignes.
Écrivez une structure TMachine, simulant une machine de Turing.
Vous aurez besoin des champs suivants :
Testez votre machine avec l'exemple du cours testant la parité de l'entrée.
Avec la modélisation proposée, utilisez la syntaxe suivante pour
définir une table de transition (dans la fonction cree :
TableTransition table = {
{ { 1, '0', +1}, { 1, '1', +1}, { 2, EPSILON, -1} },
{ { 3, EPSILON, -1}, { 4, EPSILON, -1}, {UNDEF, EPSILON, -1} },
{ { 3, EPSILON, -1}, { 3, EPSILON, -1}, { 5, '1', +1} },
{ { 4, EPSILON, -1}, { 4, EPSILON, -1}, { 5, '0', +1} },
{ {UNDEF, EPSILON, -1}, {UNDEF, EPSILON, -1}, {UNDEF, EPSILON, -1} }
};
Note : il se peut qu'avec la version actuelle (4.6) du compilateur C++11 vous ayez à écrire :
TableTransition table = {
{{ { 1, '0', +1}, { 1, '1', +1}, { 2, EPSILON, -1} }},
{{ { 3, EPSILON, -1}, { 4, EPSILON, -1}, {UNDEF, EPSILON, -1} }},
{{ { 3, EPSILON, -1}, { 3, EPSILON, -1}, { 5, '1', +1} }},
{{ { 4, EPSILON, -1}, { 4, EPSILON, -1}, { 5, '0', +1} }},
{{ {UNDEF, EPSILON, -1}, {UNDEF, EPSILON, -1}, {UNDEF, EPSILON, -1} }}
};
là où l'écriture précédente aurait du fonctionner...
La constante UNDEF représente un état non défini également utilisé pour "l'ordre de fin d'exécution".
Dans cet exemple, on suppose que le déplacement vers l'avant est représenté par la valeur +1, et le déplacement vers l'arrière par -1.
Exemple (détaillé) d'execution :
Lancement de la machine de Turing
--------------------------------
Etat actuel : 1
Bande :
10
^ (Tete : 0)
--------------------------------
lu : 1, nouvel état : 1, écrit : 1, avance
--------------------------------
Etat actuel : 1
Bande :
10
^ (Tete : 1)
--------------------------------
lu : 0, nouvel état : 1, écrit : 0, avance
--------------------------------
Etat actuel : 1
Bande :
10
^ (Tete : 2)
--------------------------------
lu : e, nouvel état : 2, écrit : e, recule
--------------------------------
Etat actuel : 2
Bande :
10e
^ (Tete : 1)
--------------------------------
lu : 0, nouvel état : 3, écrit : e, recule
--------------------------------
Etat actuel : 3
Bande :
1ee
^ (Tete : 0)
--------------------------------
lu : 1, nouvel état : 3, écrit : e, recule
--------------------------------
Etat actuel : 3
Bande :
eee
^ (Tete : -1)
--------------------------------
lu : e, nouvel état : 5, écrit : 1, avance
--------------------------------
Etat actuel : 5
Bande :
1eee
^ (Tete : 1)
--------------------------------
lu : e, nouvel état : 0, écrit : e, recule
--------------------------------
Etat actuel : 0
Bande :
1eee
^ (Tete : 0)
--------------------------------
Arrêt de la machine de Turing.
Écrivez (sur papier) la table de transition d'une machine de Turing réalisant l'inversion d'une séquence de bits.
Par exemple, si l'on a 1101 en entrée, on devra avoir 1011 en sortie.
On supposera que:
Indications: si vous êtes en panne d'inspiration, vous pouvez essayer l'algorithme proposé ci-après.