Задание 4 информатика дерево

ЕГЭ по информатике 2021 — Задание 4 (Условие Фано)

Привет! Сегодня узнаем, как решать 4 задание из ЕГЭ по информатике нового формата 2021.

Четвёртое задание из ЕГЭ по информатике раскрывает тему кодирование информации. Одним из центральных приёмов при решении задач подобного типа является построение дерева Фано. Рассмотрим на примерах этот метод.

По каналу связи передаются сообщения, содержащие только шесть букв: А, B, C, D, E, F. Для передачи используется неравномерный двоичный код, удовлетворяющий условию Фано. Для букв A, B, C используются такие кодовые слова: А — 11, B — 101, C — 0. Укажите кодовое слово наименьшей возможной длины, которое можно использовать для буквы F. Если таких слов несколько, укажите то из них, которое соответствует наименьшему возможному двоичному числу.

Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова. Коды, удовлетворяющие условию Фано, допускают однозначное декодирование

Т.к. код букв должен удовлетворять условию Фано (т.е. однозначно декодироваться), то расположим буквы, которые уже имеют код (A, B, C), на Дереве Фано.

Дерево Фано для двоичного кодирования начинается с двух направлений, которые означают 0(ноль) и 1(единицу) (цифры двоичного кодирования).

От каждого направления можно также рисовать только два направления: 0(ноль) и 1(единицу) и т.д. Для удобства будем рисовать 1(единицу) только вправо, а 0(ноль) только влево.

Получается структура похожая на дерево!

В конце каждой ветки можно располагать букву, которую мы хотим закодировать, но если мы расположили букву, от этой ветки больше нельзя делать новых ответвлений.

Такой подход позволяет однозначно декодировать сообщение, состоящее из этих букв.

Буква C заблокировала левую ветку, поэтому будем работать с правой частью нашего дерева.

Если мы расположим какую-нибудь букву на оставшуюся ветку (100), то эта ветка заблокируется, и нам некуда будет писать остальные 2 буквы. Поэтому продолжаем ветку (100) дальше.

Теперь свободно уже две ветки, а нам нужно закодировать ещё три буквы. Поэтому должны ещё раз продолжить дерево от какой-нибудь ветки.

Но уже видно, что букве F будет правильно присвоить код 1000, т.к. нам в условии сказано, что код буквы F должен соответствовать наименьшему возможному двоичному числу. Как расположить буквы D и E в данной задаче не принципиально.

Ещё один важный тип задания 4 из ЕГЭ по информатике нового формата 2021.

По каналу связи передаются сообщения, содержащие только семь букв: А, Б, И, К, Л, С, Ц. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: Б — 00, К — 010, Л — 111. Какое наименьшее количество двоичных знаков потребуется для кодирования слова АБСЦИССА?

Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.

Коды букв должны удовлетворять условию Фано. Некоторые буквы уже имеют заданные коды (Б, К, Л). Нам нужно, чтобы слово АБСЦИССА имело как можно меньше двоичных знаков. Заметим, что буква C встречается три раза, а буква A два раза, значит, этим буквам стараемся присвоить как можно меньшую длину!

Отметим на дереве Фано уже известные буквы (Б, К, Л).

У нас осталось 4 (четыре) буквы, а свободных веток 3(три), поэтому мы должны продолжить дерево. но какую ветку продолжить ?

Если продолжить линию 1-0, то получится такая картина :

Теперь получились 4(четыре) свободные ветки равной длины (3(трём) двоичным символам). Т.к. ветки равной длины, то не важно на какую ветку какую букву расположим.

Посчитаем общую длину слова АБСЦИССА.

3 + 2 + 3 + 3 + 3 + 3 + 3 + 3 = 23.

Продлим линию 1-1-0 (можно и 0-1-1, не принципиально, т.к. эти ветки имеют одинаковую длину.), то получится:

С мы присваиваем 1-0, т.к. это буква повторяется в сообщении самое большое количество раз, значит, ей присваиваем самый маленький код, чтобы всё сообщение имело наименьшую длину.

Из этих же соображений букве А присваиваем код из трёх двоичных символов 0-1-1.

Подсчитаем общее количество символов в сообщении.

3 + 2 + 2 + 4 + 4 + 2 + 2 + 3 = 22

Длина получилась меньше, чем в первом варианте. Других вариантов нет, поэтому ответ будет 22.

Для передачи по каналу связи сообщения, состоящего только из символов А, Б, В и Г, используется неравномерный (по длине) код: А-10, Б-11, В-110, Г-0. Через канал связи передаётся сообщение: ВАГБААГВ. Закодируйте сообщение данным кодом. Полученное двоичное число переведите в восьмеричный вид.

В этой задаче ничего не сказано про условие Фано. Здесь уже все буквы закодированы, осталось написать сам код.

Задача сводится к переводу из двоичной системы в восьмеричную систему. На эту тему был урок на моём сайте.

На этом всё! Увидимся на следующих занятиях по подготовке к ЕГЭ по информатике.

ОГЭ по информатике — Задание 6 (Анализируем программу)

Стас костюшкин 15-10-2020 в 15:48:52

Этого не знаю. Это просто примерные задачи, которые наиболее часто попадаются в книжках и на сайтах по подготовке к ЕГЭ по информатике.

Калужский Александр 15-10-2020 в 15:57:40

Глеб Цыбрий 15-11-2020 в 07:30:33

ГАГИЕВ 18-11-2020 в 12:24:30

Здравствуйте, а вот такое задание ПО КАНАЛУ СВЯЗИ ПЕРЕДАЮТСЯ СООБЩЕНИЯ, СОДЕРЖАЩИЕ ТОЛЬКО 4 БУКВЫ : А, Б, В, Г; ДЛЯ ПЕРЕДАЧИ ИСП. ДВОИЧНЫЙ КОД, ДОПУСКАЮЩИЙ ОДНОЗНАЧНОЕ ДЕКОДИРОВАНИЕ. ДЛЯ БУКВ А, Б, В ИСПОЛЬЗУЮТСЯ ТАКИЕ КОДОВЫЕ СЛОВА: А:00011, Б:1001, В: 01100. УКАЖИТЕ КРАТЧАЙШЕЕ КОДОВОЕ СЛОВО ДЛЯ БУКВЫ Г, ПРИ КОТОРОМ КОД БУДЕТ ДОПУСКАТЬ ОДНОЗНАЧНОЕ ДЕКОДИРОВАНИЕ. ЕСЛИ ТАКИХ КОДОВ НЕСКОЛЬКО, УКАЖИТЕ КОД С НАИМЕНЬШИМ ЧИСЛОВЫМ ЗНАЧЕНИЕМ. В ответе указано число 10. Не могу понять почему. У меня 11.

Ольга Владимировна Сорокина 05-03-2021 в 09:09:08

Здравствуйте, а вот такое задание ПО КАНАЛУ СВЯЗИ ПЕРЕДАЮТСЯ СООБЩЕНИЯ, СОДЕРЖАЩИЕ ТОЛЬКО 4 БУКВЫ : А, Б, В, Г; ДЛЯ ПЕРЕДАЧИ ИСП. ДВОИЧНЫЙ КОД, ДОПУСКАЮЩИЙ ОДНОЗНАЧНОЕ ДЕКОДИРОВАНИЕ. ДЛЯ БУКВ А, Б, В ИСПОЛЬЗУЮТСЯ ТАКИЕ КОДОВЫЕ СЛОВА: А:00011, Б:1001, В: 01100. УКАЖИТЕ КРАТЧАЙШЕЕ КОДОВОЕ СЛОВО ДЛЯ БУКВЫ Г, ПРИ КОТОРОМ КОД БУДЕТ ДОПУСКАТЬ ОДНОЗНАЧНОЕ ДЕКОДИРОВАНИЕ. ЕСЛИ ТАКИХ КОДОВ НЕСКОЛЬКО, УКАЖИТЕ КОД С НАИМЕНЬШИМ ЧИСЛОВЫМ ЗНАЧЕНИЕМ. В ответе указано число 10. Не могу понять почему. У меня 11.

Ольга Владимировна Сорокина 05-03-2021 в 09:09:14

Ольга Владимировна Сорокина, как я понимаю, суть задания в том, что здесь действует либо прямое, либо обратное условие Фано. (Примечание. Условие Фано означает, что соблюдается одно из двух условий. Либо никакое кодовое слово не является началом другого кодового слова, либо никакое кодовое слово не является окончанием другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.) Поэтому 10 является ответом, так как ни один код для букв не оканчивается на 10 (срабатывает обратное условие Фано)

Виталий 12-03-2021 в 18:00:35

Байэл 26-04-2021 в 18:50:57

Источник

Задание 4 ОГЭ информатика

4-е задание: «Формальные описания реальных объектов и процессов»
Уровень сложности — базовый,
Максимальный балл — 1,
Примерное время выполнения — 3 минуты.

Графы

Иногда очень трудно структурировать информацию описанными структурами из-за сложных «взаимоотношений» между объектами. Тогда можно использовать графы:

Граф – это набор вершин и связей между ними, называющихся рёбрами:

Граф, отображающий дороги между поселками

Матрица и список смежности

Связный граф – это граф, между любыми вершинами которого существует путь.

Дерево — связный граф без циклов

Взвешенные графы и весовая матрица

У взвешенных графов указан «вес ребра»:

Из взвешенных графов получается весовая матрица, обратное преобразование тоже возможно.

Поиск кратчайшего пути (перебор)

Определение кратчайшего пути между пунктами A и D

• В заданиях ОГЭ этой темы чаще всего используются две информационные модели — таблицы и схемы.
• Информация в таблице строится по следующим правилам: на пересечении строки и столбца находится информация, характеризующая комбинацию этой строки и столбца.
• На схеме информация строится по следующему правилу: если между объектами схемы имеется связь, то она отображается линией, соединяющей названия этих объектов на схеме.

ОГЭ информатика разбор задания 4

Подробный видеоразбор по ОГЭ 4 задания:

📹 Видеорешение на RuTube здесь

Актуальное

Рассмотрим, как решать 4 задание по информатике ОГЭ.

Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.

Определите длину кратчайшего пути между пунктами A и Е, проходящего через пункт С.
Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.

• Построим дерево протяженности дорог, на ветвях будем отображать протяженность. Учтем, что каждая ветвь, должна включить узел пересечения с С:

Разбор задания 4.6

Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице.

A	B	C	D	E	F
A	5	8	4	1
B	5	3	3	4
C	8	3	2	15
D	4	2	4	12
E	1	3	4	7
F	4	15	12	7

Определите длину кратчайшего пути между пунктами A и F, проходящего через пункт С.
Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.

• Найдём все варианты маршрутов из A в F , проходящих через пункт С , и выберем самый короткий.
• Пройдемся по таблице построчно слева-направо сверху-вниз:

A—B—C—D—E--F: длина маршрута 25 км. A—B—C—D--F: длина маршрута 29 км. A—B—C--F: длина маршрута 28 км. пропустим B: A—C--F: длина маршрута 23 км. A—C—D—E--F: длина маршрута 20 км. пропустим и D: A—C—E--F: длина маршрута 16 км. пропустим и E: A—C—D--F: длина маршрута 24 км. A—C--F: длина маршрута 23 км. поменяем следование маршрута, исключая пункты с большим числом км: A—C—B--F: длина маршрута 15 км. A—D—С—B--F: длина маршрута 13 км.

Тренировочные

Разбор задания 4.1:

В таблице приведена стоимость перевозок между соседними железнодорожными станциями, укажите схему, соответствующую таблице:

A	B	C	D	E
A	2	7	4
B	2
C	7	3	5
D	3	3
E	4	5	3

• Необходимо рассмотреть каждую схему и подсчитать количество ребер, выходящих из каждой вершины. В скобках будем указывать соответствующую данному «ребру» стоимость:

A: B(2), C(7), E(4) B: A(2), C(4) Здесь уже можно остановиться, т.к. для вершины B по схеме два ребра, а по таблице одно значение (B->A=2 ) 

A: B(2), C(7), E(4) B: A(2) C: A(7), D(5), E(3) Здесь уже можно остановиться, т.к. для вершины C стоимость по схеме и по таблице различается: по схеме C->D = 5, а по таблице на пересечении C и D цифра 3.

A: B(2), C(7), E(4) B: A(2) C: A(7), D(3), E(5) D: C(3), E(3) E: A(4), C(5), D(3) Данные на схеме полностью совпадают с табличными!

Разбор задания 4.2:

На схеме приведена стоимость перевозок между соседними железнодорожными станциями, укажите таблицу, соответствующую схеме:

• Необходимо рассмотреть каждую таблицу и подсчитать количество пересечений для каждой строки, т.е. для каждой ж.д. станции. В скобках будем указывать соответствующую данной станции стоимость:

A: B(3), E(2), F(2) Здесь уже можно остановиться, т.к. для станции A по схеме два ребра у вершины А, а по таблице уже три значения 

A: B(3), F(2) B: A(3), C(3), E(5), F(4) C: B(3), D(2), E(5) D: C(2), E(3) F: A(2), B(4) Данные на схеме полностью совпадают с табличными!

Разбор задания 4.3:

В таблице приведена стоимость перевозок между соседними железнодорожными станциями. Укажите таблицу, для которой минимальное расстояние от точки A до точки F больше 8.

Между населёнными пунктами А, В, С, D, Е, F построены дороги, протяжённость которых (в километрах) приведена в таблице:

A	B	C	D	E	F
A	5	5	4
B	5	2
C	5	2	1
D	4	1	3
E	1	1
F	1	3	1

Определите длину кратчайшего пути между пунктами А и F. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.

Источник