TD 1 : Codes et Codage de caractères PDF

Codes et codages 1 Exercices

Exercice 1-1 Avec le codage ASCII. Pour cet exercice utilisez la table ASCII de la page 6. Question 1 Codez votre nom en hexadécimal avec le codage ASCII.

Travaux dirigés (D ) Le codage des caractères

- Exercices d'entraînement Un switch sur ce codage permet de conclure plus facilement. void typeCarac ( char car) { int code = (int) car; // Code ASCII du ...

Langage C : énoncé et corrigé des exercices IUP GéniE

apr è s l'échange. Exercice 3 Ecrire un progra mm e q ui a ffi che l es code ASCII des l ettres et des chiff res sous l a l'erreur ) . Exercice 27 Ecrire une ...

Code gray / Code bcd ---exercices

Convertissez les nombres décimaux suivants en code ASCII referez-vous au tableau : Exercice PDS (corrigé). Exercice 1 : a) b).

Corrigé du BTS Métropole septembre 2020 Services informatiques

2 sept. 2020 C = N ×S =.. 200. 100. 60.. donc R = 200 G = 100 et B = 60. Exercice 3. 7 points. En informatique

TP CODAGE DE LINFORMATION 1 – CODAGE DUN NOMBRE

Dans le texte présenté le problème concerne les lettres accentuées. 2.2 – LE CODE ASCII. Exercice n°11. 1. L a c o m p a g n i e d e. 0x4C 0x61 0x20 0x63 0x6F

TP – Codage numérique des caractères Un ordinateur ne manipule

Chaque lettre ainsi que l'espace est codée par un nombre selon le code ASCII. Taille d'un texte. Exercice : Quelle est la taille en octet de la phrase ...

Exercice 1 Exercice 2

18 oct. 2021 On veut coder le mot ≪ HELLO ≫ et enregistrer son codage ASCII en syst`eme binaire sur un fichier chaque lettre tenant sur 8 bits

Programmation en C – Exercices

leur code ASCII. Ecrire un programme code-ascii qui. 1. affiche le code ASCII /* Regarder sorties dans formats-sorties.pdf */. /* TODO: trouver solution ...

Langage C : énoncé et corrigé des exercices IUP GéniE

Exercice 3 Ecrire un progra mm e q ui a ffi che l es code ASCII des l ettres et des chiff res sous l a f or m e suivante : caract're = A code = 65 code hexa

TP CODAGE DE LINFORMATION 1 – CODAGE DUN NOMBRE

Dans le texte présenté le problème concerne les lettres accentuées. 2.2 – LE CODE ASCII. Exercice n°11.

TD 1 : Codes et Codage de caractères

Exercice 2 Quelle partie de l'espace de code est utilisée par UTF-32 ? est la taille (en octets) d'un texte avec n caractères ASCII codé en format.

Numération et codage

Ce code est composé de points et de tirets (une sorte de codage binaire). SOS : Le jeu de caractères codés ASCII3 (American Standard Code for Information

Corrigé Exercice 1 : NUMERATION. Corrigé Exercice 2 : CODAGE.

1 juin 2010 En revanche en utilisant un codeur en Binaire Réfléchi

Corrigé Exercice 1: 1.a : P X = = C p 1 ? p = 0

Chapitre 3 Codage de linformation

Écrivez les nombres en base 2 de l'exercice 3.8a sur 32 bits en respectant la norme IEEE 754. ASCII : American. Standard. Code for. Information. Interchange.

Programmation en C – Exercices

III Exemples de corrections des exercices 1. affiche le code ASCII d'un caractère entré au clavier ... Regarder sorties dans formats-sorties.pdf */.

TP – Codage numérique des caractères Un ordinateur ne manipule

Pour ce qui est de l'informatique c'est le code ASCII dont les premières versions datent du début des années 1960. ASCII signifie American Standard Code for

Représenter les images

4 déc. 2012 Les corrigés des exercices qui ne sont pas à rendre seront déposés dans ... Le format PGM (codé en ascii) est construit sur le même modèle :.

Théorie de l"Information

Année 2016 - 2017

L1 Semestre 2TD 1 : Codes et Codage de caractères

1 Codage de caractères

Exercice 1Convertissez

les nom bres(17)10,(42)10,(555)10en base 16 et 2 les nom bres(3A)16et(DEC)16en base 10 et 2BEGIN SOLUTION les nom bres(17)10= (11)16,(42)10= (2A)16,(555)10= (22B)16en base 16 et 2 les nom bres(3A)16= 58et(DEC)16= 3564END SOLUTION Exercice 2Quelle partie de l"espace de code est utilisée par UTF-32?BEGIN SOLUTION L"espace de alphabet représentable en Unicode est U+0 ...U+(10FFFF)16, il y a donc(11:0000)16

caractères dans l"alphabet. Un mot 32 bit permet de représenter(1:0000:0000)16valeurs. La fraction

utilisée est donc(1110000 )16(13855 )10.END SOLUTION Exercice 3Quelle est la taille (en octets) d"un texte avecncaractères ASCII codé en format 1. UTF-8 2.

UTF-16

UTF-32 BEGIN SOLUTION

1.n 2.2n

3.4nEND SOLUTION

Exercice 4Voici des extraits de la table de codage Unicode pour l"alphabet hébreu, japonais et phéni-

cien.(a)Hebrew (b)Kat akana(c)Pho enician

Codez les caractères Alef, Bet et Nun (05D0, 05D1, 05E0), les caractères Gu et We (30B0, 30F1) et

Alf, Bet (10900, 10901) en UTF-8, UTF-16, UTF-32.

Théorie de l"Information 2016 - 2017 1 TD 1

BEGIN SOLUTION

-unicode 0x5D0: U+05D0 HEBREW LETTER ALEF, UTF-8 : d7 90 UTF-16BE : 05d0 -unicode 0x5D1: U+05D1 HEBREW LETTER BET, UTF-8 : d7 91 UTF-16BE : 05d1 -unicode 0x5E0: U+05E0 HEBREW LETTER NUN, UTF-8 : d7 a0 UTF-16BE : 05e0 -unicode 0x30B0: U+30B0 KATAKANA LETTER GU, UTF-8 : e3 82 b0 UTF-16BE : 30b0 -unicode 0x30F1: U+30F1 KATAKANA LETTER WE, UTF-8 : e3 83 b1 UTF-16BE : 30f1 -unicode 0x10900: U+10900 PHOENICIAN LETTER ALF, UTF-8 : f0 90 a4 80 UTF-16BE : d802dd00 -unicode 0x10901: U+10901 PHOENICIAN LETTER BET, UTF-8 : f0 90 a4 81 UTF-16BE : d802dd01END SOLUTION

2 Codes et codages

Exercice 5Cochez les cases oùm1m2:m

1/m201010110

01 101
10 11 Exercice 6On dit qu"une relationRest un ordre si elle est réflexiv e: 8x:R(x;x) an tisymétrique: 8xy:R(x;y)^R(y;x)!x=y transitiv e: 8xy:R(x;y)^R(y;z)!R(x;z) Pour la relation, on utilise une notationinfixe, c.à.d. on écritxyau lieu de(x;y). Montrez que la relationdéfinie parmm0=def9r:m0=mrest un ordre. Exercice 7On définit trois codesc1;c2;c3pour un alphabetA=fa;b;c;dgselon le tableau suivant :xc 1(x)c 2(x)c

3(x)a0100

b0100010 c0111110 d10110111

Montrez que :

-c1est injectif, mais son extension homomorphec1n"est pas unique -c2n"est pas un code préfixe, mais son extension homomorphec2est unique -c3est un code préfixeBEGIN SOLUTION

Non-unicité de c1:c1(ca) =c1(b)

Unicité de c2: Uniquementc2(c)etc2(d)n"ont pas la propriété préfixe. Pour toute chaîne110:::,

on a besoin d"un lookahead arbitrairement long. Si11est suivi d"un nombre pair de0, on a la séquencecb:::. Si11est suivi d"un nombre impair de0, on a la séquencedb:::.END SOLUTION Exercice 8Montrez formellement que tout codage unique est un codage injectif. Remarque :L"exercice7 mon treque cette inclusion est s tricte.

Théorie de l"Information 2016 - 2017 2 TD 1

BEGIN SOLUTION

Soitcun codage unique. Il existe donc undtel que pour tout messagem,d(c(m)) =m. Soientm1;m2 messages avecm16=m2. Supposonsc(m1) =c(m2). Par unicité dec, on am1=d(c(m1)) =d(c(m2)) = m

2, une contradiction.END SOLUTION

Exercice 9Montrez formellement que tout codagecqui est l"extension homomorphe d"un code préfixe cest injectif.BEGIN SOLUTION Soitcun code préfixe homomorphe. On montre qu"il est injectif : Sic(m1) =c(m2), alorsm1=m2. Par induction sur la taille (= nombre de caractères) dem1. Si jm1j= 0, doncm1= [], alorsc(m1) =c(m2) = [], donc forcémentm2= []. Soit jm1j=n+1, doncm1=am01. On voit quem2ne peut pas être vide. Il est donc de la forme bm02. Alors,c(m1) =c(am01) =c(a)c(m01) =c(m2) =c(b)c(m02). On voitc(a)c(b), donca=bà cause deccode préfixe, doncc(a) =c(b), doncc(m01) =c(m02), doncm01=m02par hypothèse d"induction.END SOLUTION Exercice 10Est-ce que le code Morse est unique / injectif / un code préfixe?BEGIN SOLUTION

Réponse : il n"est pas injectif (par example code(ATT) = code(J)) et par conséquent pas unique.

END SOLUTION

Exercice 11Appliquez l"algorithmearbre_decaux codagesc1etc2de la table suivante.xc 1(x)c 2(x)c

3(x)a00010

b011110 c1000110 d110011110

Si la construction de l"arbre échoue, identifiez les causes. Est-ce que vous pouvez proposer des codages

qui évitent le problème?BEGIN SOLUTION

1.c2est "l"inverse" du codec2de l"exercice7 , donc pas un code préfixe. Irréparable.

2.c3ne permet pas la construction d"un arbre binaire complet (voir exercice14 ). On peut trouver le

code plus court0, 10, 110, 111END SOLUTION

Exercice 12Appliquez l"algorithmetab_codaux arbres de décodage obtenus dans l"exercice11 et v é-

rifiez que vous obtenez bien les tables d"origine. Exercice 13Pourquoi est-ce que l"algorithmetab_codtermine?

Théorie de l"Information 2016 - 2017 3 TD 1

BEGIN SOLUTION

Récursion structurelle sur l"arbre.

END SOLUTION

Exercice 14(Devoir maison)

Analyse de l"algorithmearbre_dec:

Quels problèmes se p oseraientp ourun algorithme de déco dagesi l"arbre n"était pas un arbre

binaire (mais si un noeud intérieur pouvait avoir un seul successeur)? 2. Un in variantde arbre_decest qu"il prend la représentation d"une tabletabd"un codage préfixe. Démontrez que cet invariant est maintenu par les appels récursifs, donc, que f(c;m)j(c;0m)2tabg représente bien une table d"un codage préfixe (et pareil pour1m). 3. Démon trezque si (c;[])2tab, alors il n"est pas possible d"avoir un(d;m)2tab, pour unc6=d. 4. Démon trezque l"algorithme termine. BEGIN SOLUTION 1. Arbre binaire incomplet : certains co desne seraien tpas un co dagecorrect d"un co desource, par exemple1111. Mais c"est aussi un problème pour des arbres complets, si le message est tronqué. 2. Supp osonsqu"il existen tm1;m2avec(c;0m1)2tabet(c;0m2)2tabetm1m2. Alors, aussi

0m10m2. Contradiction avec codage préfixe detab.

3. Si (c;[])2tabet(d;m)2tab, puisque[]m, on a une contradiction avec codage préfixe detab. 4.

T erminaison: dans c haqueapp elrécursiv, p ourc haque(c;m), la taille demdécroit, jusqu"à ce

quetabcontient uniquement des éléments avecm= []. Selon (3), il peut seulement y avoir un seul (c;[])2tab, on termine donc avec la clause (2).END SOLUTION

Exercice 15

Utilisez l"inégalité de Kr aftp ourdéterminer s"il es tp ossiblede construire un co depréfixe p ourles

caractèresa:::davec les longueurs de code suivants :caractèreabcd longueur1223 2. Quelle serait v otrerép onsesi on admet un co dede longueur 3 p ourle caractère b? Proposez effectivement un code.BEGIN SOLUTION

1.21+ 222+ 23=98

>1, un code n"est pas possible.

2.21+ 22+ 223= 1, un code est possible, par exemplea7!0;c7!10;b7!110;d7!111END SOLUTION

Exercice 16

Une en treprisev eutinstaller un système téléphonique in terneoù les 5 mem bresdu directoire on t

un numéro à un seul chiffre (de 0 à 9) et les 80 autres employés un nombre à deux chiffres. Est-ce

possible? 2.

Serait-il p ossibled"a voirdes n umérosà deux c hiffresp ourles mem bresdu directoire et de trois

chiffres pour les autres employés? Faites une proposition concrète.

Théorie de l"Information 2016 - 2017 4 TD 1

A noter :L"inégalité de Kraft se généralise d"un code binaire à un coden-aire (alphabet ànchiffres)

comme suit : Il existe un code préfixen-aire aveckcodesu1:::uksi et seulement si k X i=1n juij1 oùjuijest la longeur du codeui.BEGIN SOLUTION

1.5101+ 80102=50100

+80100
= 1:3>1, un tel système ne peut donc pas exister.

2.5102+ 801031. On peut attribuer des codes01...05au directeurs et101...180aux

autres employés.END SOLUTION

Théorie de l"Information 2016 - 2017 5 TD 1

quotesdbs_dbs6.pdfusesText_11

[PDF] TD 1 : Codes et Codage de caractères

Théorie de l"Information

Année 2016 - 2017

1 Codage de caractères

Exercice 1Convertissez

UTF-16

UTF-32 BEGIN SOLUTION

3.4nEND SOLUTION

Alf, Bet (10900, 10901) en UTF-8, UTF-16, UTF-32.

Théorie de l"Information 2016 - 2017 1 TD 1

BEGIN SOLUTION

2 Codes et codages

Exercice 5Cochez les cases oùm1m2:m

1/m201010110

3(x)a0100

Montrez que :

Non-unicité de c1:c1(ca) =c1(b)

Théorie de l"Information 2016 - 2017 2 TD 1

BEGIN SOLUTION

2, une contradiction.END SOLUTION

END SOLUTION

3(x)a00010

1.c2est "l"inverse" du codec2de l"exercice7 , donc pas un code préfixe. Irréparable.

2.c3ne permet pas la construction d"un arbre binaire complet (voir exercice14 ). On peut trouver le

Théorie de l"Information 2016 - 2017 3 TD 1

BEGIN SOLUTION

Récursion structurelle sur l"arbre.

END SOLUTION

Exercice 14(Devoir maison)

Analyse de l"algorithmearbre_dec:

0m10m2. Contradiction avec codage préfixe detab.

Exercice 15

1.21+ 222+ 23=98

2.21+ 22+ 223= 1, un code est possible, par exemplea7!0;c7!10;b7!110;d7!111END SOLUTION

Exercice 16

Théorie de l"Information 2016 - 2017 4 TD 1

1.5101+ 80102=50100

2.5102+ 801031. On peut attribuer des codes01...05au directeurs et101...180aux

Théorie de l"Information 2016 - 2017 5 TD 1