END SOLUTION Exercice 3 Quelle est la taille (en octets) d'un texte avec n caractères ASCII codé en format 1 UTF-8 2 UTF-16 3 UTF-32 BEGIN SOLUTION
| Previous PDF | Next PDF |
[PDF] Codes et codages 1 Exercices - Formations en Informatique de Lille
Codage de l'information Codes et codages 1 Exercices 1 1 Première série Exercice 1-1 Avec le codage ASCII Pour cet exercice, utilisez la table ASCII de la
[PDF] Informatique et sciences du numérique - Unithequecom
Exercice 8 1 (avec corrigé) Trouver la représentation binaire en ASCII du texte « Je pense, donc je suis » On cherche la table des codes ASCII sur le Web de
[PDF] TD 1 — Codage de linformation — Correction - LIPN
On travaille dans cet exercice sur des entiers naturels codés sur un octet Donner, à l'aide de la table ASCII donnée dans le cours, la séquence binaire corres-
[PDF] 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
[PDF] Travaux Dirigés (partie 1/2) Objectifs du TD : - Robert cireddu
décimale vers Décimale Codé Binaire (DCB) Exercices d'application Le code ASCII est un code sur 8 bits (valeurs 0 à 255), il permet de définir :
[PDF] Chapitre 3 Codage de linformation - Apprendre-en-lignenet
Exercice 3 1 Donnez la méthode pour passer de la base décimale à Le code ASCII de base représentait les caractères sur 7 bits (c'est-
[PDF] TD 1 : Codes et Codage de caractères
END SOLUTION Exercice 3 Quelle est la taille (en octets) d'un texte avec n caractères ASCII codé en format 1 UTF-8 2 UTF-16 3 UTF-32 BEGIN SOLUTION
[PDF] Tronc Commun
Codage (binaire, hexadécimal, ASCII) et transcodage de l'information, Chaque caractère est représenté par un code sur 8 bits (code ASCII étendu) Pour la compression sans perte, on peut montrer par un exercice simple, le principe du
[PDF] exercices corrigés codes linéaires
[PDF] exercices corrigés comportement consommateur
[PDF] exercices corrigés composantes symetriques
[PDF] exercices corrigés composés organiques oxygénés
[PDF] exercices corrigés congruences divisibilité
[PDF] exercices corrigés consolidation comptes pdf
[PDF] exercices corrigés contraintes mmc
[PDF] exercices corrigés convergence en probabilité
[PDF] exercices corrigés d amélioration génétique des animaux
[PDF] exercices corrigés d'algorithmique sur les tableaux
[PDF] exercices corrigés d'automatique pdf
[PDF] exercices corrigés d'économétrie des variables qualitatives pdf
[PDF] exercices corrigés d'économie des transports
[PDF] exercices corrigés d'électricité pdf
Théorie de l"Information
Année 2016 - 2017
L1 Semestre 2TD 1 : Codes et Codage de caractères1 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)16caractè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
3.UTF-32 BEGIN SOLUTION
1.n 2.2n3.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 enicianCodez 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 SOLUTION2 Codes et codages
Exercice 5Cochez les cases oùm1m2:m
1/m201010110
01 10110 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 d10110111Montrez 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 SOLUTIONNon-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)) = m2, 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 SOLUTIONRé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)c3(x)a00010
b011110 c1000110 d110011110Si la construction de l"arbre échoue, identifiez les causes. Est-ce que vous pouvez proposer des codages
qui évitent le problème?BEGIN SOLUTION1.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 SOLUTIONExercice 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:
1.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, aussi0m10m2. 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 SOLUTIONExercice 15
1.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 SOLUTION1.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
1.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 SOLUTION1.5101+ 80102=50100
+80100= 1:3>1, un tel système ne peut donc pas exister.