I. 163. Un des plus célèbres codes utilisés à corriger les erreurs survenues au cours des transmissions de données digitales est lié au nom de Richard Wesley Hamming. Une des versions de ce code est capable de corriger au plus une erreur sur 7 bits (la valeur d’un seul bit est transmise erronée).

Le processus d’encodage est le suivant. Les données à transmettre sont décomposées en paquets de 4 bits; ces paquets sont ensuite complétés par 3 bits de contrôle comme illustré par la figure:

(Où est l’addition modulo 2, l’opération ,,ou exclusif'' : si et seulement si parmi les bits x₁,x₂,...,x_n  il y a un nombre impaire de 1.)

On transmet ensuite les 7 bits ainsi obtenus et notés par k₇...k_1. Soit le code (éventuellement erroné) perçu par le récepteur f₇...f₁.

Le décodage se fait de la manière suivante. On calcul de nouveau, à partir des f _j  correspondants, les sommes de contrôle et on compare le résultat avec les bits de contrôle f₄, f₂  et f₁. (par exemple f₂  avec la somme  .) On additionne les indices i  pour lesquels la valeur du bit de contrôle f_i  est incorrecte. Si la somme ainsi obtenue est égale à 0, alors il n’y a pas d’erreur, sinon, et c’est là qu’on voit vraiment la beauté du code, la somme donne le lieu de l’erreur qui peut être tout de suite corrigée par inversion. Ensuite, par la lecture des bits correspondants du mot de code (déjà) correcte, on obtient les données transmises.

Ecrire un programme qui encode ou décode, suivant son premier paramètre ,,en''  ou ,,de'', le fichier donné par son deuxième paramètre dans le fichier dont le nom est précisé par le troisième paramètre. Dans les fichiers, les mots de données et de codes doivent être des séries de 0-1 séparées par des caractères d’espacement. L’ordre des bits de code à l’intérieur du mot de code est quelconque.

(Dans le premier code, le bit de contrôle f₄ signale une erreur, donc on corrige le 4^ème bit, f₄. Le deuxième code est correcte, dans le troisième, f₄ et f₂ signalent une erreur, donc on doit corriger le 6^ème bit, f ₆.)

Envoyer le code source du programme (i163.pas, i163.cpp, ...), ainsi que sa documentation brève (i163.txt, i163.pdf, ...) qui contient la description de la solution et donne le nom de l’environnement de développement dans lequel le code source peut être compilé.

(10 points)

I. 164. Dans une version du jeux de l’automate de cellules, l’univers est considéré comme une grille à carreaux de 27×27. Sur les cases de la grille vivent des cellules, deux au plus sur une case. La particularité des cellules situées au bord de la grille est qu’elles ont elles aussi quatre voisines: les cellules de la rangée supérieure sont voisines des cellules de la rangée inférieure et inversement, de même les cellules de la colonne de gauche sont voisines des cellules de la colonne de droite.

De nouvelles générations se créent à intervalles réguliers. Chaque cellule se divise en quatre et elle-même elle meurt (une cellule se crée dans chacune des cases voisines). Si, dans une case, il y a plusieurs cellules, elles se suppriment par groupe de trois jusqu’à ce qu’ il n’en reste plus qu’une ou deux.

Ecrire un programme qui, en se basant sur la position actuelle des cellules, détermine l’image de l’univers dans N  générations.

Le programme doit lire les données nécessaires à partir de l’entrée standard. La première ligne de l’entrée contient le nombre de générations N (), les 27  lignes suivantes contiennent chacune 27 chiffres, le nombre de cellules vivantes dans les cases correspondantes (0, 1 ou 2). Le programme doit écrire le résultat sur la sortie standard, au format identique à celui de l’entrée.

La rapidité du programme sera appréciée même pour des valeurs élevées de N. Rechercher une règle de fonctionnement.

Faute de place, voici un exemple à dimensions réduites (mais qui fonctionne de la même manière):

Un exemple de 27×27 peut être téléchargé sur Internet.

Envoyer le code source du programme (i164.pas, i164.cpp, ...), ainsi que sa documentation brève (i164.txt, i164.pdf, ...) qui contient la description de la solution et donne le nom de l’environnement de développement dans lequel le code source peut être compilé.

exemple d’entrée de 27×27

exemple de sortie de 27×27

(10 points)

I. 165. La colonne ,,A''  de la première feuille de calcul d’un classeur Excel contient des chiffres 0 et 1. Les quelques premiers éléments de la série sont des 0. Ensuite, 8 chiffres de 1 signalent le début des données importantes. Les groupes de 8 chiffres suivants contiennent chacun les bits d’un byte. Les données sont issues d’un fichier de texte, chaque byte correspond à un caractère ASCII. Les cellules situées après la dernière donnée sont vides.

Ecrire dans la cellule B1 la formule qui donnera le texte d’origine. Le texte contient quelques centaines de caractères au plus. Les autres formules et calculs nécessaires doivent être placés dans la deuxième feuille de calcul du classeur.

Exemple: si le contenu de la colonne ,,A'' est:

La valeur de la sortie (cellule B1): 6aA.

Envoyer le classeur (i165.xls, i165.ods, ...) ainsi qu’une documentation brève (i165.txt, i165.pdf, ...) qui contient le nom du tableur utilisé, sa version et la description brève de la solution.

(10 points)

S. 28. Une certaines version du jeu de cartes Rami est jouée avec deux paquets de cartes françaises. Le gagnant est celui qui arrive à poser toutes ses cartes sur la table, selon les règles. Les règles sont les suivantes:

1. Les cartes peuvent être posées sur la table par groupe d’au moins trois cartes de telle façon qu’elles constituent ou une série de cartes de même couleur ou bien un groupe de cartes de même chiffre ou figure. Exemple pour le premier cas: le quadruple de 3 de cœur, 4 de cœur, 5 de cœur et de 6 de cœur, un exemple pour le deuxième cas: le triplet de roi de cœur, roi de carreau, roi de pique. Des groupes incorrects: le triplet de 4 de cœur, 5 de cœur, 6 de carreau, ou encore le triplet de l’as de pique, as de pique, as de trèfle.

2. Les séries doivent contenir des cartes de même couleur, l’ordre des cartes doit être 2, 3, ..., 9, 10, valet, dame, roi, as, ou bien as, 2, 3, ..., 9, 10, valet, dame, roi. La carte as doit être donc ou le premier ou le dernier membre d’une série. Une série correcte par exemple: 10 de trèfle, valet de trèfle, dame de trèfle, ou bien as de cœur, 2 de cœur, 3 de cœur, 4 de cœur; une série incorrecte: roi de pique, as de pique, 2 de pique.

3. A la constitution d’un groupe, une carte quelconque peut être remplacée par un Joker  mais le nombre de cartes non Joker doit être supérieur à celui des cartes Joker. Exemple pour un groupe correcte: 9 de cœur, 10 de cœur, Joker, Joker, roi de cœur ; groupe incorrecte: Joker, pique 4, Joker, ou encore 5 de cœur, Joker, Joker, 8 de cœur.

Les joueurs peuvent poser sur la table les cartes q’ils ont dans leurs mains, mais ils peuvent aussi réordonner les cartes qui se trouvent déjà sur la table selon les règles décrites ci-dessus. Si un joueur a par exemple sur la table le quadruple 5 de cœur, 5 de carreau, 5 de trèfle, 5 de pique et dans sa main le 4 de trèfle et le 6 de trèfle, il peut créer un groupe avec 5 de cœur, 5 de carreau, 5 de pique et une série contenant 4 de trèfle, 5 de trèfle et 6 de trèfle – et peut donc poser sur la table les deux cartes qu’il avait en main, en regroupant les cartes qui se trouvaient déjà sur la table.

Les joueurs n’ont pas le droit de reprendre des cartes déjà posées sur la table et s’ils ne peuvent pas en poser, ils doivent piocher une carte du paquet de cartes non encore distribuées. Ecrire un programme nommé s28 qui permet la pose du plus grand nombre de cartes en fonction des cartes se trouvant déjà sur la table et dans les mains du joueur. Le programme doit lire les cartes se trouvant sur la table à partir du premier fichier donné dans la ligne de commande et les cartes se trouvant dans les mains du joueur à partir du deuxième fichier. Il doit ensuite écrire sur la sortie standard la situation sur la table, après regroupement des groupes et pose des cartes, ainsi que les cartes restantes dans les mains du joueur.

Dans les fichiers en entrée et à la sortie, les cartes de cœur, carreau, trèfle et pique sont signalées par les lettres C, R, T, P, la valeur des cartes par les chiffres 2, 3, ..., 9, 0 et par les lettres J, Q, K, A. Ainsi C4 signifie 4 de cœur et R A  désigne la carte as de carreau, T0  le 10 de trèfle,  PJ le valet de pique, PQ la dame de pique. Les Joker n’ont pas de couleur, leur signe est JJ.

Le fichier en entrée contient les groupes posés sur la table, un groupe par ligne, les cartes de la série étant séparées par des caractères d’espacement et présentées en ordre croissant. Le fichier en entrée peut être vide, ce qui signifie qu’il n'y a aucune carte posée sur la table. Le deuxième fichier en entrée contient les cartes se trouvant dans les mains du joueurs, en une seule lignes,  séparées par des caractères d’espacement. Ce fichier ne peut pas être vide, il doit contenir au moins une carte. La sortie doit donner d’abord les cartes se trouvant sur la table, un groupe par ligne, les cartes séparées par des caractères d’espacement et triées en ordre croissant; ensuite les cartes se trouvant dans les mains du joueurs, en une seule lignes,  séparées par des caractères d’espacement.

Exemple: Soit le contenu du fichier donnant les cartes se trouvant sur la table (a.txt):

C4 JJ K6 C7
PQ CQ TQ
TA T2 T3 T4 T5

Le contenu du fichier donnant les cartes se trouvant dans les mains du joueur (b.txt):

C5 C5 JJ TK T0

Le programme écrira alors à la sortie, après avoir entrée la ligne de commande s28 a.txt b.txt :

C4 C5 C6 C7
TQ TK TA
PQ CQ JJ
T2 T3 T4
C5 T5 JJ
T0

Envoyer le code source du programme (s28.pas, s28.cpp, ...), ainsi que sa documentation brève (s28.txt, s28.pdf, ...) qui contient la description de la solution et donne le nom de l’environnement de développement dans lequel le code source peut être compilé.

(10 points)