Solution à la tâche 5 de l'examen d'État unifié en informatique

La leçon est consacrée à la façon de résoudre la tâche 5 de l'examen d'État unifié en informatique

Le 5ème sujet est caractérisé par des tâches d'un niveau de complexité de base, temps d'exécution - environ 2 minutes, score maximum - 1

• Codage- est la présentation d'informations sous une forme pratique pour leur stockage, leur transmission et leur traitement. La règle pour convertir les informations en une telle représentation s'appelle code.
• Le codage se produit uniforme Et inégal:
• avec un codage uniforme, tous les symboles correspondent à des codes de même longueur ;
• Avec un codage inégal, différents symboles correspondent à des codes de longueurs différentes, ce qui rend le décodage difficile.

Exemple: Chiffrons les lettres A, B, C, D en utilisant un codage binaire avec un code uniforme et comptons le nombre de messages possibles :

Nous avons donc code uniforme, parce que la longueur de chaque mot de code est la même pour tous les codes (2).

Encodage et décryptage des messages

Décodage (décodage)- c'est la restauration d'un message à partir d'une séquence de codes.

Pour résoudre les problèmes de décodage, vous devez connaître la condition de Fano :

Etat Fano : aucun mot de code ne doit être le début d'un autre mot de code (ce qui garantit que les messages sont décodés sans ambiguïté depuis le début)

Code préfixe est un code dans lequel aucun mot de code ne coïncide avec le début d'un autre mot de code. Les messages utilisant ce code sont décodés sans ambiguïté.

Un décodage sans ambiguïté est fourni :

Résoudre 5 tâches d'examen d'État unifié

Examen d'État unifié 5.1 : Pour coder les lettres O, B, D, P, A, nous avons décidé d'utiliser la représentation binaire des nombres 0, 1, 2, 3 et 4, respectivement (avec conservation d'un zéro insignifiant dans le cas d'un simple- représentation numérique).

Encodez ainsi la séquence de lettres CASCADE et écrivez le résultat en code octal.

✍Solution :

• Convertissons les nombres en codes binaires et associons-les à nos lettres :

O -> 0 -> 00 V -> 1 -> 01 D -> 2 -> 10 P -> 3 -> 11 A -> 4 -> 100

Codons maintenant la séquence de lettres du mot WATERFALL :

010010001110010

Divisons le résultat en groupes de trois caractères de droite à gauche pour les convertir au système numérique octal :

010 010 001 110 010 ↓ ↓ ↓ ↓ ↓ 2 2 1 6 2

Résultat: 22162

Solution d'examen d'État unifié pour cette tâche informatique, vidéo :

Regardons l'analyse de la tâche 5 de l'examen d'État unifié :

Examen d'État unifié 5.2 : Pour 5 lettres de l'alphabet latin, leurs codes binaires sont précisés (pour certaines lettres - à partir de deux bits, pour certaines - à partir de trois). Ces codes sont présentés dans le tableau :

un	b	c	d	e
000	110	01	001	10

Quel ensemble de lettres est codé par la chaîne binaire 1100000100110 ?

✍Solution :

• Tout d’abord, nous vérifions la condition de Fano : aucun mot de code n’est le début d’un autre mot de code. La condition est vraie.

✎ 1ère solution :

• On casse le code de gauche à droite selon les données présentées dans le tableau. Traduisons-le ensuite en lettres :

110 000 01 001 10 ↓ ↓ ↓ ↓ ↓ b a c d e

Résultat: b a c d e.

✎ 2ème solution :

110 000 01 001 10

Résultat: b a c d e.

De plus, vous pouvez regarder une vidéo de la solution à ce devoir d'examen d'État unifié en informatique :

Résolvons la 5ème tâche suivante :

Examen d'État unifié 5.3 :
Pour transmettre des numéros sur un canal bruyant, un code de contrôle de parité est utilisé. Chacun de ses chiffres est écrit en représentation binaire, avec des zéros non significatifs ajoutés sur une longueur de 4, et la somme de ses éléments modulo 2 est ajoutée à la séquence résultante (par exemple, si nous transmettons 23, nous obtenons la séquence 0010100110).

Déterminez quel numéro a été transmis sur le canal sous la forme 01100010100100100110.

✍Solution :

• Considérons exemple de l'énoncé du problème :

Il avait 23 ans 10 Maintenant 0010100110 2

Où sont les chiffres du numéro d'origine (surlignez-les en rouge) :

0010 10011 0 (0010 - 2, 0011 - 3)

Premier chiffre ajouté 1 après le deux binaire se trouve un contrôle de parité (1 unité dans 0010 - signifie étrange) 0 après le triple binaire, il y a aussi un contrôle de parité impaire (2 uns dans 0011 , ce qui signifie même).

Sur la base de l'analyse de l'exemple, nous résolvons notre problème de cette façon : puisque les nombres dont nous avons « besoin » sont formés de groupes de 4 nombres chacun plus un nombre pour le contrôle de parité, nous diviserons le message codé en groupes de 5 et rejetterons le dernier personnage de chaque groupe :

Décomposez-le en 5 :

01100 01010 01001 00110

supprimez le dernier personnage de chaque groupe :

0110 0101 0100 0011

Résultat convertir en système décimal :

0110 0101 0100 0011 ↓ ↓ ↓ ↓ 6 5 4 3

Répondre: 6 5 4 3

Vous pouvez regarder une vidéo de la solution à ce devoir d'examen d'État unifié en informatique :

Examen d'État unifié 5.4 :
Pour coder une certaine séquence composée des lettres K, L, M, N, ils ont décidé d'utiliser un code binaire non uniforme qui satisfait à la condition de Fano. Le mot de code 0 a été utilisé pour la lettre H et le mot de code 10 pour la lettre K.

Quelle est la longueur totale la plus courte possible des quatre mots de code ?

✍Solution :

✎ 1 solution possible basé sur des conclusions logiques :

• Trouvons les mots de passe les plus courts possibles pour toutes les lettres.
• Mots de code 01 Et 00 ne peut pas être utilisé, car alors la condition de Fano est violée (ils partent de 0, et 0 - Ce N).
• Commençons par des mots de passe à deux chiffres. Prenons pour la lettre L mot de code 11 . Ensuite, il est impossible de sélectionner un mot de code pour la quatrième lettre sans violer la condition de Fano (si vous prenez ensuite 110 ou 111, alors ils commencent par 11).
• Cela signifie que des mots de code à trois chiffres doivent être utilisés. Encodons les lettres L Et M mots de code 110 Et 111 . La condition de Fano est satisfaite.

(N)1 + (K)2 + (L)3 + (M)3 = 9

✎ Option 2:

(N) -> 0 -> 1 caractère (K) -> 10 -> 2 caractères (L) -> 110 -> 3 caractères (M) -> 111 -> 3 caractères

La longueur totale des quatre mots de passe est :

(N)1 + (K)2 + (L)3 + (M)3 = 9

Répondre: 9

Examen d'État unifié en informatique 5 tâche 2017 FIPI option 2 (édité par Krylov S.S., Churkina T.E.) :

Les messages contenant seulement 4 lettres sont transmis via le canal de communication : A, B, C, D ; Pour la transmission, un code binaire est utilisé qui permet un décodage sans ambiguïté. Pour les lettres A, B, C, les mots de code suivants sont utilisés : A : 101010, B : 011011, C : 01000.

Г, auquel le code permettra un décodage sans ambiguïté. le plus petit valeur numérique.

✍Solution :

• Les plus petits codes pourraient ressembler à 0 Et 1 (un seul chiffre). Mais cela ne satisferait pas la condition de Fano ( UN commence par un - 101010 , B commence à zéro - 011011 ).
• Le prochain plus petit code serait un mot de deux lettres 00 . Puisqu'il ne s'agit d'un préfixe d'aucun des mots de passe présentés, alors G = 00.

Résultat: 00

Examen d'État unifié en informatique 5 tâche 2017 FIPI option 16 (édité par Krylov S.S., Churkina T.E.) :

Pour coder une certaine séquence composée des lettres A, B, C, D et D, nous avons décidé d'utiliser un code binaire non uniforme, qui nous permet de décoder sans ambiguïté la séquence binaire apparaissant du côté réception du canal de communication. Le code utilisé était : A - 01, B - 00, C - 11, D - 100.

Indiquez avec quel mot de code la lettre D doit être codée. Longueur ce mot de code devrait être moins de tous les possibles. Le code doit satisfaire à la propriété de décodage sans ambiguïté. S'il existe plusieurs de ces codes, indiquez celui ayant la valeur numérique la plus faible.

✍Solution :

Résultat: 101

Une analyse plus détaillée de la leçon peut être vue dans la vidéo de l'examen d'État unifié en informatique 2017 :

Examen d'État unifié en informatique 5 tâche 2017 FIPI option 17 (Krylov S.S., Churkina T.E.) :

Pour coder une certaine séquence composée des lettres A, B, C, D, D et E, nous avons décidé d'utiliser un code binaire non uniforme, qui nous permet de décoder sans ambiguïté la séquence binaire apparaissant du côté réception du canal de communication. . Le code utilisé était : A - 0, B - 111, C - 11001, D - 11000, D - 10.

Indiquez avec quel mot de code la lettre E doit être codée. La longueur de ce mot de code doit être la plus courte possible. Le code doit satisfaire à la propriété de décodage sans ambiguïté. S'il existe plusieurs de ces codes, indiquez celui ayant la valeur numérique la plus faible.

✍Solution :

1 - ne convient pas (toutes les lettres sauf A commencent par 1) 10 - ne convient pas (correspond au code D) 11 - ne convient pas (le début des codes B, C et D) 100 - ne convient pas (le code D - 10 - est le début de ce code) 101 - ne convient pas (le code D - 10 - est le début de ce code) 110 - ne convient pas (le début des codes B et D) 111 - ne convient pas (correspond au code B) 1000 - ne convient pas ( le code D - 10 - est le début de ce code) 1001 - ne convient pas (le code D - 10 - est le début de ce code) 1010 - ne convient pas (le code D - 10 - est le début de ce code) 1011 - ne convient pas (le code D - 10 - est le début de ce code) 1100 - ne convient pas (début des codes B et D) 1101 - convient

Résultat: 1101

Une solution plus détaillée à cette tâche est présentée dans le didacticiel vidéo :

Tâche 5. Version démo de l'examen d'État unifié 2018 en informatique (FIPI) :

Des messages cryptés contenant seulement dix lettres sont transmis sur le canal de communication : A, B, E, I, K, L, R, S, T, U. Un code binaire impair est utilisé pour la transmission. Les mots de code sont utilisés pour neuf lettres.

Spécifiez le mot de code le plus court pour la lettre B, sous lequel le code satisfera la condition de Fano. S'il existe plusieurs de ces codes, indiquez le code avec le plus petit valeur numérique.

✍Solution :

Résultat: 1100

Pour une solution détaillée à cette 5ème tâche de la version démo de l'examen d'État unifié 2018, regardez la vidéo :

Tâche 5_9. Options d'examen modèle 2017. Option 4 (Krylov S.S., Churkina T.E.) :

Des messages cryptés contenant seulement quatre lettres sont transmis sur le canal de communication : A, B, C, D ; Pour la transmission, un code binaire est utilisé qui permet un décodage sans ambiguïté. Pour les lettres UN, B, DANS mots de code utilisés :

A : 00011 B : 111 C : 1010

Spécifiez le mot de code le plus court pour la lettre G, dans lequel le code permettra un décodage sans ambiguïté. S'il existe plusieurs de ces codes, indiquez le code avec le plus petit valeur numérique.

✍Solution :

Résultat: 00

Tâche 5_10. Option de formation n°3 du 10/01/2018 (FIPI) :

Les messages contenant uniquement des lettres sont transmis sur le canal de communication : A, E, D, K, M, R; Pour la transmission, un code binaire satisfaisant la condition de Fano est utilisé. Les codes suivants sont connus pour être utilisés :

E – 000 D – 10 K – 111

Spécifiez la longueur de message codé la plus courte possible DEDMAKAR.
Dans votre réponse, écrivez un nombre – le nombre de bits.

✍Solution :

D E D M A K A R 10 000 10 001 01 111 01 110

Comptons le nombre de chiffres dans le code final et obtenons 20 .

Résultat: 20

Voir la solution à la tâche :

5ème tâche : « Encodage et décodage des messages »
Niveau de difficulté - basique,
Note maximale - 1,
Le temps d'exécution approximatif est de 2 minutes.

Examen d'État unifié 5.1 : Pour coder les lettres O, B, D, P, A, nous avons décidé d'utiliser la représentation binaire des nombres 0, 1, 2, 3 et 4, respectivement (avec conservation d'un zéro insignifiant dans le cas d'un simple- représentation numérique).

Encodez ainsi la séquence de lettres CASCADE et écrivez le résultat en code octal.

Répondre: 22162

✍ Afficher la solution :

• Convertissons les nombres en codes binaires et associons-les à nos lettres :

O -> 0 -> 00 V -> 1 -> 01 D -> 2 -> 10 P -> 3 -> 11 A -> 4 -> 100

Codons maintenant la séquence de lettres du mot WATERFALL :

010010001110010

Divisons le résultat en groupes de trois caractères de droite à gauche pour les convertir au système numérique octal :

010 010 001 110 010 ↓ ↓ ↓ ↓ ↓ 2 2 1 6 2

Examen d'État unifié 5.2 : Pour 5 lettres de l'alphabet latin, leurs codes binaires sont précisés (pour certaines lettres - à partir de deux bits, pour certaines - à partir de trois). Ces codes sont présentés dans le tableau :

un	b	c	d	e
000	110	01	001	10

Quel ensemble de lettres est codé par la chaîne binaire 1100000100110 ?

Répondre: b a c d e

✍ Afficher la solution :

• Tout d’abord, nous vérifions la condition de Fano : aucun mot de code n’est le début d’un autre mot de code. La condition est vraie.

✎ 1ère solution :

• On casse le code de gauche à droite selon les données présentées dans le tableau. Traduisons-le ensuite en lettres :

110 000 01 001 10 ↓ ↓ ↓ ↓ ↓ b a c d e

Résultat: b a c d e.

✎ 2ème solution :

110 000 01 001 10

Examen d'État unifié 5.3 :
Pour transmettre des numéros sur un canal bruyant, un code de contrôle de parité est utilisé. Chacun de ses chiffres est écrit en représentation binaire, avec des zéros non significatifs ajoutés sur une longueur de 4, et la somme de ses éléments modulo 2 est ajoutée à la séquence résultante (par exemple, si nous transmettons 23, nous obtenons la séquence 0010100110).

Déterminez quel numéro a été transmis sur le canal sous la forme 01100010100100100110.

Répondre: 6 5 4 3

✍ Afficher la solution :

• Considérons exemple de l'énoncé du problème :

Il avait 23 ans 10 Maintenant 0010100110 2

Où sont les chiffres du numéro d'origine (surlignez-les en rouge) :

0010 10011 0 (0010 - 2, 0011 - 3)

Premier chiffre ajouté 1 après le deux binaire se trouve un contrôle de parité (1 unité dans 0010 - signifie étrange) 0 après le triple binaire, il y a aussi un contrôle de parité impaire (2 uns dans 0011 , ce qui signifie même).

Sur la base de l'analyse de l'exemple, nous résolvons notre problème de cette façon : puisque les nombres dont nous avons « besoin » sont formés de groupes de 4 nombres chacun plus un nombre pour le contrôle de parité, nous diviserons le message codé en groupes de 5 et rejetterons le dernier personnage de chaque groupe :

Décomposez-le en 5 :

01100 01010 01001 00110

supprimez le dernier personnage de chaque groupe :

0110 0101 0100 0011

Résultat convertir en système décimal :

0110 0101 0100 0011 ↓ ↓ ↓ ↓ 6 5 4 3

Examen d'État unifié 5.4 :
Pour coder une certaine séquence composée des lettres K, L, M, N, ils ont décidé d'utiliser un code binaire non uniforme qui satisfait à la condition de Fano. Le mot de code 0 a été utilisé pour la lettre H et le mot de code 10 pour la lettre K.

Quelle est la longueur totale la plus courte possible des quatre mots de code ?

Répondre: 9

✍ Afficher la solution :

✎ 1 solution possible basé sur des conclusions logiques :

• Trouvons les mots de passe les plus courts possibles pour toutes les lettres.
• Mots de code 01 Et 00 ne peut pas être utilisé, car alors la condition de Fano est violée (ils partent de 0, et 0 - Ce N).
• Commençons par des mots de passe à deux chiffres. Prenons pour la lettre L mot de code 11 . Ensuite, il est impossible de sélectionner un mot de code pour la quatrième lettre sans violer la condition de Fano (si vous prenez ensuite 110 ou 111, alors ils commencent par 11).
• Cela signifie que des mots de code à trois chiffres doivent être utilisés. Encodons les lettres L Et M mots de code 110 Et 111 . La condition de Fano est satisfaite.

(N)1 + (K)2 + (L)3 + (M)3 = 9

✎ Option 2:

(N) -> 0 -> 1 caractère (K) -> 10 -> 2 caractères (L) -> 110 -> 3 caractères (M) -> 111 -> 3 caractères

La longueur totale des quatre mots de passe est :

(N)1 + (K)2 + (L)3 + (M)3 = 9

Examen d'État unifié en informatique 5 tâche 2017 FIPI option 2 (édité par Krylov S.S., Churkina T.E.) :

Les messages contenant seulement 4 lettres sont transmis via le canal de communication : A, B, C, D ; Pour la transmission, un code binaire est utilisé qui permet un décodage sans ambiguïté. Pour les lettres A, B, C, les mots de code suivants sont utilisés : A : 101010, B : 011011, C : 01000.

Spécifiez le mot de code le plus court pour la lettre G, auquel le code permettra un décodage sans ambiguïté. le plus petit valeur numérique.

Répondre: 00

✍ Afficher la solution :

• Les plus petits codes pourraient ressembler à 0 Et 1 (un seul chiffre). Mais cela ne satisferait pas la condition de Fano ( UN commence par un - 101010 , B commence à zéro - 011011 ).
• Le prochain plus petit code serait un mot de deux lettres 00 . Puisqu'il ne s'agit d'un préfixe d'aucun des mots de passe présentés, alors G = 00.

Examen d'État unifié en informatique 5 tâche 2017 FIPI option 16 (édité par Krylov S.S., Churkina T.E.) :

Pour coder une certaine séquence composée des lettres A, B, C, D et D, nous avons décidé d'utiliser un code binaire non uniforme, qui nous permet de décoder sans ambiguïté la séquence binaire apparaissant du côté réception du canal de communication. Le code utilisé était : A - 01, B - 00, C - 11, D - 100.

Indiquez avec quel mot de code la lettre D doit être codée. Longueur ce mot de code devrait être moins de tous les possibles. Le code doit satisfaire à la propriété de décodage sans ambiguïté. S'il existe plusieurs de ces codes, indiquez celui ayant la valeur numérique la plus faible.

Répondre: 101

✍ Afficher la solution :

Examen d'État unifié en informatique 5 tâche 2017 FIPI option 17 (Krylov S.S., Churkina T.E.) :

Pour coder une certaine séquence composée des lettres A, B, C, D, D et E, nous avons décidé d'utiliser un code binaire non uniforme, qui nous permet de décoder sans ambiguïté la séquence binaire apparaissant du côté réception du canal de communication. . Le code utilisé était : A - 0, B - 111, C - 11001, D - 11000, D - 10.

Indiquez avec quel mot de code la lettre E doit être codée. La longueur de ce mot de code doit être la plus courte possible. Le code doit satisfaire à la propriété de décodage sans ambiguïté. S'il existe plusieurs de ces codes, indiquez celui ayant la valeur numérique la plus faible.

Répondre: 1101

✍ Afficher la solution :

1 - ne convient pas (toutes les lettres sauf A commencent par 1) 10 - ne convient pas (correspond au code D) 11 - ne convient pas (le début des codes B, C et D) 100 - ne convient pas (le code D - 10 - est le début de ce code) 101 - ne convient pas (le code D - 10 - est le début de ce code) 110 - ne convient pas (le début des codes B et D) 111 - ne convient pas (correspond au code B) 1000 - ne convient pas ( le code D - 10 - est le début de ce code) 1001 - ne convient pas (le code D - 10 - est le début de ce code) 1010 - ne convient pas (le code D - 10 - est le début de ce code) 1011 - ne convient pas (le code D - 10 - est le début de ce code) 1100 - ne convient pas (début des codes B et D) 1101 - convient

Tâche 5. Version démo de l'examen d'État unifié 2018 en informatique (FIPI) :

Des messages cryptés contenant seulement dix lettres sont transmis sur le canal de communication : A, B, E, I, K, L, R, S, T, U. Un code binaire impair est utilisé pour la transmission. Les mots de code sont utilisés pour neuf lettres.

Spécifiez le mot de code le plus court pour la lettre B, sous lequel le code satisfera la condition de Fano. S'il existe plusieurs de ces codes, indiquez le code avec le plus petit valeur numérique.

L'examen d'État unifié en informatique comprend 27 tâches. La tâche 5 teste les compétences en matière d'encodage et de décodage des informations. L'étudiant doit être capable de coder et de décoder des informations dans différents systèmes numériques, ainsi que de déchiffrer les messages et de choisir le code optimal. Ici, vous pouvez apprendre à résoudre la tâche 5 de l'examen d'État unifié en informatique, ainsi qu'étudier des exemples et des solutions basés sur des tâches détaillées.

Toutes les tâches USE toutes les tâches (107) Tâche USE 1 (19) Tâche USE 3 (2) Tâche USE 4 (11) Tâche USE 5 (10) Tâche USE 6 (7) Tâche USE 7 (3) Tâche USE 9 (5) Tâche d'examen d'État unifié 10 (7) Tâche d'examen d'État unifié 11 (1) Tâche d'examen d'État unifié 12 (3) Tâche d'examen d'État unifié 13 (7) Tâche d'examen d'État unifié 16 (19) Tâche d'examen d'État unifié 17 (4) État unifié Examen sans numéro (9)

Pour coder les lettres, nous avons décidé d'utiliser une représentation binaire

Pour coder les lettres, nous avons décidé d'utiliser la représentation binaire des nombres respectivement 0, 1, 2, 3 et 4 (avec conservation d'un zéro insignifiant dans le cas d'une représentation à un chiffre). Si vous codez une séquence de lettres de cette manière et écrivez le résultat en code octal, vous obtenez...

Pour transmettre un message composé uniquement de caractères sur un canal de communication

Pour transmettre un message sur un canal de communication composé uniquement des caractères A, B, C et D, un codage caractère par caractère est utilisé. Un message est transmis via un canal de communication. Encodez le message avec ce code. Convertissez le nombre binaire obtenu sous forme hexadécimale.

La tâche est incluse dans l'examen d'État unifié en informatique pour la 11e année sous le numéro 5.

Pour coder les lettres A, B, C, D, nous avons décidé d'utiliser des lettres à deux chiffres

Pour coder les lettres A, B, C, D, ils ont décidé d'utiliser des nombres binaires séquentiels à deux chiffres (respectivement de 00 à 11). Si vous codez une séquence de caractères de cette manière et écrivez le nombre binaire résultant dans le système de numérotation hexadécimal, vous obtenez...

La tâche est incluse dans l'examen d'État unifié en informatique pour la 11e année sous le numéro 5.

Les messages contenant seulement 5 lettres sont transmis sur le canal de communication

Les messages contenant seulement 5 lettres sont transmis sur le canal de communication. Un code binaire non uniforme est utilisé pour coder les lettres. Parmi les mots ci-dessous, indiquez celui dont le code ne peut être décodé que d'une seule manière. S'il existe plusieurs mots de ce type, indiquez le premier par ordre alphabétique.

La tâche est incluse dans l'examen d'État unifié en informatique pour la 11e année sous le numéro 5.

Pour transmettre des messages, vous devez utiliser un code binaire non uniforme

Les messages contenant seulement 4 lettres sont transmis sur le canal de communication. Pour transmettre des messages, vous devez utiliser un code binaire non uniforme qui permet un décodage sans ambiguïté ; les messages doivent être aussi courts que possible. Le cryptographe peut utiliser l’un des codes listés ci-dessous. Quel code choisir ?

La tâche est incluse dans l'examen d'État unifié en informatique pour la 11e année sous le numéro 5.

Pour encoder un message composé uniquement des lettres A, B, C et D

Pour coder un message composé uniquement des lettres A, B, C et D, un code binaire de longueur inégale est utilisé. Si vous encodez une séquence de caractères de cette manière et écrivez le résultat en code hexadécimal, vous obtenez...

La tâche est incluse dans l'examen d'État unifié en informatique pour la 11e année sous le numéro 5.

Pour 5 lettres de l'alphabet latin leurs codes binaires sont donnés

Pour 5 lettres de l'alphabet latin, leurs codes binaires sont précisés (pour certaines lettres - à partir de deux bits, pour certaines - à partir de trois). Ces codes sont présentés dans le tableau. Déterminer quel ensemble de lettres est codé dans une chaîne binaire ?

La tâche est incluse dans l'examen d'État unifié en informatique pour la 11e année sous le numéro 5.

Un code de parité est utilisé pour transmettre des numéros sur un canal bruyant.

Pour transmettre des numéros sur un canal bruyant, un code de contrôle de parité est utilisé. Chacun de ses chiffres est écrit en représentation binaire, avec des zéros non significatifs ajoutés sur une longueur de 4, et la somme de ses éléments modulo 2 est ajoutée à la séquence résultante. Déterminer quel nombre a été transmis sur le canal ?

La tâche est incluse dans l'examen d'État unifié en informatique pour la 11e année sous le numéro 5.

Un code à 5 bits est utilisé pour transmettre des données sur le canal de communication

Un code à 5 bits est utilisé pour transmettre des données sur un canal de communication. Le message contient uniquement les lettres A, B et C, qui sont codées avec des mots de code. Il peut y avoir des interférences pendant la transmission. Vous pouvez néanmoins tenter de corriger certaines erreurs. Deux de ces trois mots de code diffèrent l'un de l'autre sur au moins trois positions. Par conséquent, si une erreur s’est produite dans au plus une position lors de la transmission d’un mot, il est alors possible de deviner quelle lettre a été transmise. Si le mot de code reçu diffère des mots de code des lettres A, B, C sur plus d'une position, alors une erreur est considérée comme s'est produite (elle est désignée par « x »). Message reçu. Décodez ce message - choisissez la bonne option.

La tâche est incluse dans l'examen d'État unifié en informatique pour la 11e année sous le numéro 5.

Pour coder une séquence composée de lettres

Pour coder une certaine séquence de lettres, un code de préfixe binaire non uniforme est utilisé. Est-il possible de raccourcir la longueur du mot de passe pour l'une des lettres afin que le code reste toujours un préfixe ? Les codes des lettres restantes ne doivent pas changer. Choisissez la bonne réponse. Note. Un code préfixe est un code dans lequel aucun mot de code n’est le début d’un autre ; De tels codes permettent de décoder sans ambiguïté la séquence binaire résultante.

La tâche est incluse dans l'examen d'État unifié en informatique pour la 11e année sous le numéro 5.

Pour visualiser la présentation avec des images, un design et des diapositives, téléchargez son fichier et ouvrez-le dans PowerPoint sur votre ordinateur.
Contenu textuel des diapositives de présentation : Préparation à l'examen d'État unifié Professeur d'informatique MBOU École secondaire n° 1, Azova Balamutova Irina Aleksandrovna 2015 Encodage et décodage des informations. (Tâches 5) Codage des données, combinatoire, systèmes numériques (Tâches 10) Contenu du sujet « Encodage et décodage des informations. » ThéorieTâche 1Tâche 2Tâche 3Tâche 4Tâches pour la formationThème : Codage des données, combinatoire, systèmes numériquesThéorieTâche 1Tâche 2Tâche 3Tâche 4Tâche 5Tâches pour la formationRéférences SITES UTILES FOR PREPARATIONS FOR USE2 est décodé depuis le début si la condition de Fano est satisfaite : aucun mot de code n'est le début d'un autre mot de code ; un message codé peut être décodé sans ambiguïté depuis la fin si la condition de Fano inverse est satisfaite : aucun mot de code n'est le début d'un autre mot de code ; fin d'un autre mot de code ; la condition de Fano est suffisante, mais n'est pas une condition nécessaire pour une théorie de décodage sans ambiguïté3. Le codage est la traduction d'informations d'une langue à une autre. Le codage peut être uniforme ou inégal. Avec un codage uniforme, tous les caractères sont codés avec des codes de longueur égale. Avec un codage inégal, différents caractères peuvent être codés avec des codes de longueurs différentes. 4 théories sont transmises sur un canal de communication, dont chacun contient. 16 lettres A, 8 lettres B, 4 lettres C et 4 lettres G (il n'y a pas d'autres lettres dans les messages). Chaque lettre est codée sous forme de séquence binaire. Lors du choix d'un code, deux exigences ont été prises en compte : a) aucun mot de code n'est le début d'un autre (cela est nécessaire pour que le code permette un décodage sans ambiguïté) ; b) la longueur totale du message codé doit être aussi petite que possible. Quel code parmi les suivants doit être choisi pour coder les lettres A, B, C et D 555551) A : 0, B : 10, C : 110, D: 1112) A: 0, B:10, C:01, D:113) A:1, B:01, C:011, D:0014) A:00, B:01, C:10, D: 11Tâche 15, sélectionnez d'abord les codes dans lesquels pas un seul mot de code ne coïncide avec le début d'un autre (j'appelle de tels codes préfixe) ; pour le code 2, la condition « a » n'est pas remplie, puisque le mot de code de la lettre B ; (01) commence par le mot de code de la lettre A (0) ; pour le code 3, la condition « a" n'est pas remplie, puisque le mot de code de la lettre B (011) commence par le mot de code de la lettre B ( 01) pour les codes 1 et 4 la condition est remplie, on les considère plus loin, on calcule le nombre total de bits dans le message pour le code 1 : 16∙1 + 8 2 + 4∙3 + 4∙3 = 56 bits compter le nombre total de bits dans le message pour le code 4 : 16∙2 + 8 2 + 4∙2 + 4∙2 = 64 bits le code 1 donne la longueur de message la plus courte, alors choisissez-leRéponse : 1.6 Solution Problème 1 Pour coder une certaine séquence composée des lettres A, B, C, D, nous avons décidé d'utiliser un code binaire non uniforme qui satisfait la condition de Fano. Pour la lettre A, nous avons utilisé le mot de code 0, pour la lettre B, nous avons utilisé le mot de code 110. Quelle est la plus petite longueur totale possible des quatre mots de code 1) 7 2) 8 3) 9 4) 107 Problème 2 Solution (méthode 1) ? , élimination des options) : La condition Fano signifie qu'aucun mot de code ne correspond au début d'un autre mot de code, puisqu'il existe déjà un mot de code 0, aucun autre mot de code ne peut commencer par 0, puisqu'il existe un code 110, les mots de code 1, 11 sont interdits ; de plus, aucun autre mot de code ne peut commencer par 110, vous devez donc choisir deux autres mots de code pour lesquels ces restrictions sont remplies. Il existe un mot de code valide de deux caractères : 10 si vous choisissez le mot de code 10 pour la lettre B, alors il y en a un. à gauche, le mot de code à trois caractères autorisé est 111, qui peut être sélectionné pour la lettre G8. Solution au problème 2. En choisissant les mots de code A – 0, B – 110, C – 10, D – 111, nous obtenons la longueur totale. des mots de code 9 caractères Si vous ne sélectionnez pas B – 10, soit trois mots de code valides à trois caractères : 100, 101 et 110 ; en choisissant deux d'entre eux pour les lettres B et G, nous obtenons la longueur totale des mots de code 10, qui est supérieure à 9 ; par conséquent, nous choisissons l'option 3 (9 caractères) Réponse : 3. Solution au problème 2 (suite) 9 AB10100 Solution (méthode 2, construction d'arbre) : La condition de Fano signifie qu'aucun mot de code ne coïncide avec le début d'un autre mot de code ; en même temps, dans l'arbre de codes, tous les mots de code doivent être situés dans les feuilles de l'arbre qui n'ont pas de descendants ; construisons un arbre pour les mots de code donnés A - 0 et B - 110 :10 Tâche 2, lignes pointillées marquer deux branches « vides » auxquelles des feuilles peuvent être « attachées » pour les mots-codes des lettres B (10) et G (111)AB10100VG, en choisissant les mots-codes A – 0, B – 110, C – 10, D – 111, on obtient la longueur totale des mots de code 9 caractères Réponse : 3. Problème 2 méthode 2, construction de l'arbre suite 11 Les messages contenant seulement 4 lettres P, O, S, T sont transmis via le canal de communication ; Pour la transmission, un code binaire est utilisé qui permet un décodage sans ambiguïté. Pour les lettres T, O, P, les mots de code suivants sont utilisés : T : 111, O : 0, P : 100. Précisez le mot de code le plus court pour la lettre C, auquel le code permettra un décodage sans ambiguïté. S'il existe plusieurs de ces codes, indiquez le code avec la valeur numérique la plus basse. 12Tâche 3 OT101000P1Solution (méthode 2, construction d'arbre) : La condition de Fano signifie qu'aucun mot de code ne coïncide avec le début d'un autre mot de code ; en même temps, dans l'arbre de codes, tous les mots de code doivent être situés dans les feuilles de l'arbre, c'est-à-dire dans des nœuds qui n'ont pas de descendants ; construisons un arbre pour les mots de code donnés O - 0, T - 111 et P - 100:13 Solution du problème 3 Les lignes pointillées marquent deux branches « vides » sur lesquelles vous pouvez « attacher » une feuille pour le mot de code de la lettre C : 101 ou 110 ; parmi celles-ci, la valeur minimale est le code 101 Solution du problème 3 (suite) 14 15 Les lignes pointillées marquent deux branches « vides » auxquelles vous pouvez « attacher » une feuille pour le mot de code de la lettre C : 101 ou 110 ; parmi ceux-ci, la valeur minimale est le code 101. OT101000P1S Après avoir choisi les mots de code A – 0, B – 110, C – 10, D – 111, nous obtenons la longueur totale des mots de code 9 caractères Réponse : 101. Solution au problème 3 (suite) 15 Une image tramée en noir et blanc est codé ligne par ligne, en commençant par le coin supérieur gauche et en se terminant dans le coin inférieur droit. Lors de l'encodage, 1 représente le noir et 0 représente le blanc. BD9AA5 2) BDA9B5 3) BDA9D5 4)DB9DAB 16Tâche 4 « étendre » l'image raster en chaîne : d'abord la première ligne (du haut), puis la seconde, etc. : il y a 24 cellules dans cette bande, remplissez les noires avec uns, et remplissez les blancs avec des zéros : puisque chaque chiffre du système hexadécimal est décomposé en exactement 4 chiffres binaires, nous diviserons la bande en tétrades - groupes de quatre cellules (dans ce cas, peu importe où commencer la division, puisqu'il y a un nombre entier de tétrades dans la bande - 6) : en convertissant les tétrades en système hexadécimal , on obtient séquentiellement les nombres B (11), D (13), A (10), 9, D (13) et 5, c'est-à-dire la chaîne BDA9D5, donc la bonne réponse est de 3,17 Solution au problème 4 1 ligne 2 ligne 3 ligne 4 ligne 1011110110101001110101011 Ligne 2 ligne 3 ligne 4 ligne 1011110110100 11101010118 Résoudre le problème 4 (suite) Tâche 5 Tâche 5 N° 7746. Pour coder une certaine séquence composée des lettres A, B, C, D et D, un code binaire non uniforme est utilisé, ce qui permet de décoder sans ambiguïté la séquence binaire résultante. Voici le code : A - 1 ; B-0100 ; B-000 ; G-011 ; D - 0101. Il est nécessaire de réduire la longueur du mot de code pour l'une des lettres afin que le code puisse toujours être décodé sans ambiguïté. Les codes des lettres restantes ne doivent pas changer. Parmi les méthodes suivantes, laquelle peut-on procéder ? 1) pour la lettre G - 112) pour la lettre B - 003) pour la lettre G - 014) c'est impossible Réponse : 19 problèmes pour une solution indépendante2
Tâche 5 n° 1104. Pour coder les lettres X, E, L, O, D, nous avons décidé d'utiliser la représentation binaire des nombres 0, 1, 2, 3 et 4, respectivement (avec la préservation d'un zéro insignifiant dans le cas d'une représentation à un chiffre). Si vous codez la séquence de lettres ICE DRIVE de cette manière et écrivez le résultat en code hexadécimal, vous obtiendrez 1) 999С2) 32541453) 123F 4) 2143034 Réponse : 20 réponses Tâche 5 n° 1104 HELOD0123400011011100 Tout d'abord, vous devez présenter les données dans la condition numérique en code binaire : encodez la séquence de lettres : OD - 1001100110011100 Divisons maintenant cette représentation en quatre de droite à gauche et convertissons l'ensemble de nombres résultant d'abord en code décimal, puis en hexadécimal. 1001 1001 1001 1100 - 9 9 9 12 - 999C. La bonne réponse est indiquée sous le numéro 1.21 Tâche 5 n° 7193 Transmettre un message sur un canal de communication composé uniquement des caractères A, B, C et D, un impair (en longueur) le code est utilisé : A – 0 ; B-100 ; Q – 101. Quel mot de code doit être utilisé pour coder le symbole G afin que sa longueur soit minimale et que le code permette une division sans ambiguïté du message codé en symboles ? 1) 12) 113) 01 Solution4) 010 http://inf.reshuege.ru/test?theme=232 Réponse :222
Tâche 5 n° 9293.23 Pour coder une certaine séquence composée des lettres I, K, L, M, N, nous avons décidé d'utiliser un code binaire non uniforme qui satisfait à la condition de Fano. Pour la lettre L, nous avons utilisé le mot de code 1, pour la lettre M, nous avons utilisé le mot de code 01. Quelle est la longueur totale la plus courte possible des cinq mots de code Remarque. La condition de Fano signifie qu’aucun mot de code n’est le début d’un autre mot de code. Cela permet de déchiffrer sans ambiguïté les messages cryptés Réponse : 4 Solution http://inf.reshuege.ru/test?theme=23123.
24Tâches pour le lien de la leçon vidéo de formationhttps://www.youtube.com/watch?v=BoBnzjwLsnU Sujet : Codage des données, combinatoire, systèmes numériques (Tâches 10) 25 Ce que vous devez savoir : Principes de l'alphabet russe pour travailler avec des nombres écrits en position systèmes numériques si le mot est composé de L lettres et qu'il existe n1 options pour choisir la première lettre, n2 options pour choisir la deuxième lettre, etc., alors le nombre de mots possibles est calculé comme le produit N = n1 · n2 · … · nL si le mot est constitué de L lettres et que chaque lettre peut être choisie de n manières, alors le nombre de mots possibles est calculé comme suit : N = nL26 théorie Vasya compose des mots de 5 lettres qui contiennent uniquement les lettres S, L, O , N et la lettre S est utilisée exactement 1 fois dans chaque mot. Chacune des autres lettres valides peut apparaître dans un mot un certain nombre de fois ou pas du tout. Un mot est une séquence valide de lettres, pas nécessairement significative. Combien de mots Vasya peut-il écrire ?27Tâche 1 La lettre C peut apparaître à l'un des cinq endroits suivants : С****, *С***, **С**, ***С* et *** * C, où * désigne l'un des trois caractères restants dans chaque cas, dans les quatre positions restantes, il peut y avoir l'une des trois lettres L, O, N, donc, avec un arrangement donné de la lettre C, nous avons 34 = 81 options , un total de 5 81 = 405 options. Réponse : 405.28solution Combien de séquences de caractères différentes de longueur 5 y a-t-il dans un alphabet de quatre lettres (A, C, G, T), qui contiennent exactement deux lettres A ?29 Problème 2 Solution. (option 1, recherche) : considérez différentes versions de mots de 5 lettres contenant deux lettres A et commençant par A:AA*** A*A** A**A* A***AZIci, l'astérisque désigne tout caractère de l'ensemble (C, G, T), c'est-à-dire l'un des trois caractères. Ainsi, dans chaque modèle, il y a 3 positions, chacune pouvant être remplie de trois manières, donc le nombre total de combinaisons (pour chaque modèle !) est de 33 = 27 au total 4 modèles, ils donnent 4 27 = 108 combinaisons30solution Maintenant, nous considérons les modèles où le premier à compter, la lettre A est en deuxième position, il n'y en a que trois : *AA** *A*A* *A**Ails donnent 3 · 27 = 81 combinaisons de deux motifs, où la première lettre A est en troisième position : **AA* **A*Et ils donnent 2 · 27 = 54 combinaisons et un motif, où la combinaison AA est à la fin ***AA ils donnent 27 combinaisons, au total on obtient (4 + 3 + 2 + 1) · 27 = 270 combinaisons Réponse : 270 .Solution (suite)31 Tous les mots de 4 lettres composés des lettres K, L, R, T sont écrits par ordre alphabétique et numérotés. Voici le début de la liste : KKKK2. KKKL3. KKKR4. KKKT......Écrivez le mot qui se trouve à la 67ème place depuis le début de la liste. 32Tâche 3 La solution la plus simple à ce problème consiste à utiliser des systèmes numériques ; en effet, ici la disposition des mots par ordre alphabétique équivaut à la disposition par ordre croissant des nombres écrits dans la numération quaternaire (la base de la numération est égale au nombre de lettres utilisées). Faisons le remplacement K. 0, L1, P2, T3 ; puisque la numérotation des mots commence par un et que le premier nombre КККК0000 est 0, le nombre 67 sera le nombre 66, qu'il faudra convertir dans le système quaternaire : 66 = 10024 Après avoir effectué le remplacement inverse (des nombres par des lettres ), nous obtenons le mot LKKR Réponse : LKKR .33Solution 34Tâche 4 Tâche 10 n° 6777. Combien de mots de longueur 5 peuvent être formés à partir des lettres E, G, E ? Chaque lettre peut apparaître plusieurs fois dans un mot. 35SolutionS'il y a M caractères dans l'alphabet, alors le nombre de tous les « mots » (messages) possibles de longueur N est égal à Q = MN. Dans notre cas, N = 5, M = 3. Donc Q = 35 = 243. Réponse : 243. 36Tâche 5 Tâche 10 n° 4797. Il y a 32 crayons dans une boîte fermée, certains d'entre eux sont bleus. Un crayon est sorti au hasard. Le message « ce crayon n’est PAS bleu » véhicule 4 bits d’information. Combien y a-t-il de crayons bleus dans la boîte ? 37 Formule de Shannon : où x est la quantité d'informations contenues dans le message sur l'événement P, p est la probabilité qu'ils n'aient PAS reçu de bleu où est le nombre de crayons bleus. En utilisant la formule de Shannon, nous trouvons que Y =. 30 Solution 38 Tâches de formation lien vers le didacticiel vidéo d'auto-préparation https:/ /www.youtube.com/watch?v=BoBnzjwLsnU RÉFÉRENCEShttp://kpolyakov.narod.ru/ Krylov S.S., Churkina T.E. Examen d'État unifié 2015. Informatique et TIC. Options d'examen typiques. - M. : « Éducation nationale », 2015. Leshchiner V.R. Examen d'État unifié 2015. Informatique. Tâches de test typiques. - M. : Examen, 2015. Evich L.N., Kulabukhov S.Yu. Informatique et TIC. Préparation à l'examen d'État unifié 2015. - Rostov-sur-le-Don : Légion, 2014. Ouchakov D.M., Yakushkin P.A. Informatique. L'édition la plus complète des versions standard des tâches de l'examen d'État unifié 2014 - M. : Astrel, 2014. Evich L.N., Kulabukhov S.Yu. Informatique et TIC. Préparation à l'examen d'État unifié 2015. - Rostov-sur-le-Don : Légion, 2014. Ostrovskaya E.M., Samylkina N.N. Examen d'État unifié 2015. Informatique. Nous louons sans aucun problème ! - M. : Eksmo, 2014. Samylkina N.N., Ostrovskaya E.M. Examen d'État unifié 2015. Informatique. Tâches de formation thématiques. - M. : Eksmo, 2014. Zorina E.M., Zorin M.V. Examen d'État unifié 2015. Informatique. Collection de tâches. - M. : « Eksmo », 2015.39 Sites utiles pour la PRÉPARATION À l'examen d'État unifié !40 L'informatique est facile http://easyinformatics.ru/Analyse vidéo de la tâche Examen d'État unifié-2013 http://www.ageychev. rf/ege.htmlPortail pédagogique pour la préparation aux examens http://inf.reshuege.ru/?redir=1USE en informatique 2013 http://infoegehelp.ru/40

Pour une préparation efficace en informatique, un bref matériel théorique pour accomplir la tâche est fourni pour chaque tâche. Plus de 10 tâches de formation avec analyse et réponses ont été sélectionnées, développées sur la base de la version démo des années précédentes.

Il n'y a aucun changement par rapport à l'examen d'État unifié KIM 2019 en informatique et TIC.

Domaines dans lesquels les connaissances seront testées :

• Programmation;
• Algorithmisation ;
• Outils TIC ;
• Activités d'information ;
• Processus d'information.

Actions nécessaires lorsque préparation:

• Répétition du cours théorique ;
• Solution essais en informatique en ligne;
• Connaissance des langages de programmation;
• Améliorer les mathématiques et la logique mathématique ;
• Utiliser un éventail plus large de littérature - le programme scolaire pour réussir à l'examen d'État unifié - ne suffit pas.

Structure de l'examen

La durée de l'examen est de 3 heures 55 minutes (255 minutes), dont il est recommandé de consacrer une heure et demie à la réalisation des tâches de la première partie des KIM.

Les tâches contenues dans les tickets sont divisées en blocs :

• Partie 1- 23 tâches avec réponse courte.
• Partie 2- 4 tâches avec des réponses détaillées.

Sur les 23 tâches proposées pour la première partie de l'épreuve d'examen, 12 se situent au niveau de base du test de connaissances, 10 sont d'une complexité accrue, 1 est d'un niveau de complexité élevé. Trois tâches de la deuxième partie sont d'un haut niveau de complexité, une est d'un niveau supérieur.

Lors de la prise de décision, il est nécessaire d'enregistrer une réponse détaillée (forme libre).
Dans certaines tâches, le texte de la condition est présenté simultanément dans cinq langages de programmation - pour la commodité des étudiants.

Points pour les devoirs d'informatique

1 point - pour 1 à 23 tâches
2 points - 25.
3 points - 24, 26.
4 points - 27.
Total : 35 points.

Pour entrer dans une université technique de niveau intermédiaire, vous devez obtenir au moins 62 points. Pour entrer à l'université de la capitale, le nombre de points doit correspondre à 85-95.

Pour réussir une épreuve d'examen, une connaissance claire de théorie et constante pratique pour résoudre tâches.

Votre formule pour réussir

Travailler + travailler sur les erreurs + lire attentivement la question du début à la fin pour éviter les erreurs = note maximale à l'examen d'État unifié en informatique.