Разработать алгоритмы решения задач из приведенных ниже вариантов, а также определить входные, выходные и промежуточные данные. При этом использовать методы: нисходящее проектирование, модульность, структурное программирование. Для представления алгоритмов применить язык графических символов. При представлении блок-схем придерживаться требований ГОСТ. Выбор варианта задания выполнять по своему порядковому номеру в списке учебной группы (уточнить у преподавателя).
Варианты заданий:
00) задан текст, не имеющий пробелов. Сформировать алфавит А, т.е. множество символов, из которых составлен текст (см. преобразование (1) в (2));
01) задан текст, не имеющий пробелов. Сформировать алфавит А, т.е. множество символов, из которых составлен текст (см. предыдущее задание), определить его мощность N (см. (3)) и рассчитать требуемый размер l прямого двоичного кода постоянной длины (см. (4) и (5));
02) задан исходный алфавит А, размер l прямого двоичного кода постоянной длины (см. (4)) для кодирования этого алфавита. Сформировать для символов алфавита А двоичный код постоянной длины размером l с начальным номером по порядку, равным нулю (см. графы 2 и 3 табл. 1);
03) задан исходный текст, не имеющий пробелов, и известен код постоянной длины для алфавита, в котором составлен текст (графы 1 и 3 табл. 1). Закодировать исходный текст (см. (6));
04) задан исходный текст, не имеющий пробелов. Сформировать алфавит А, т.е. множество символов, из которых составлен текст (см. задание 00), и рассчитать число появлений каждого символа алфавита А в исходном тексте (см. графу 2 табл. 2);
05) задан размер кода l. Рассчитать общее число кодовых двоичных комбинаций, получаемых при заполнении l двоичных разрядов методом перестановок с повторениями разными способами (см. табл. 3);
06) задан алфавит А, его мощность N, частота символов алфавита А, размер кода l. Заданы количества кодовых комбинаций, получаемых при заполнении l двоичных разрядов разными способами (см. табл. 3). Сформировать двоичные коды для символов алфавита А с учетом частоты символов (см. табл. 4);
07) задана мощность N множества А. Определить размер таблицы для построения кода Грея для элементов множества А (см. шаг 1 выполнения задания 3);
08) задан размер таблицы для построения кода Грея - nxm. Сформировать нумерацию строк и столбцов этой таблицы (см. шаг 2 выполнения задания 3);
09) задано упорядоченное по алфавиту множество А. Определен размер таблицы для построения кода Грея nxm и сформирована нумерация строк и столбцов этой таблицы. Получить код Грея для символов алфавита А (графа 2 табл. 7);
10) задан исходный алфавит А. Задать символам алфавита А произвольные десятичные номера в пределах от 0 до N-1, где N - мощность алфавита А (использовать функцию получения случайного числа) (см. графу 2 табл. 8);
11) задан исходный текст и ключ кодирования К. «Выписать» ключ под исходным текстом (см. строки 1 и 3 табл. 10);
12) заданы две числовые десятичные последовательности длиной L (см. строки 2 и 4 табл. 10). Выполнить сложение элементов этих последовательностей по модулю N (см. строку 5 табл. 10);
13) задан размер исходного текста L, алфавит А, из которого составлен текст, и число появлений каждого символа mi. Рассчитать частоты символов fi по формуле (14) (графа 3 табл. 11). При этом добиваться того, чтобы сумма частот была равна 1 (путем увеличения самой большой частоты или уменьшения самой маленькой частоты);
14) задан упорядоченный по невозрастанию список частот мощностью N. Выполнить его итерационное деление на N одноэлементных подмножеств, каждый раз в цикле проводя деление очередного подмножества на 2 части, руководствуясь при этом примерным равенством частот обоих подмножеств. Окончание процесса деления подмножества на две части определить по одноэлементности подмножества (см. графы 2 и 3 табл. 12);
15) модифицировать алгоритм из задания 14, формируя в процессе деления исходного множества частот результирующие коды Шеннона-Фано (см. графу 4 табл. 12);
16) задан упорядоченный по невозрастанию список частот мощностью N. Выполнить объединение частот в соответствии с алгоритмом Хаффмена (см. табл. 13). Результат представить в виде матрицы размером Nx(N-1);
17) модифицировать алгоритм задания 16, указывая связи между исходными и объединенными частотами (см. стрелки в табл. 13);
18) модифицировать алгоритм задания 17, «нагружая» связи между исходными и объединенными частотами символами 1 и 0;
19) задано кодовое дерево, подобное изображенному на рис. 2. Сформировать по нему коды для каждого символа, расположенного в «листе» дерева (см. табл. 14);
20) задан эффективный код, содержащий N кодовых комбинаций. Определить, является ли он префиксным;
21) заданы кодовые таблицы, построенные методами Шеннона-Фано и Хаффмена, для символов алфавита А. Известны частоты символов алфавита А. Дан размер прямого кода постоянной длины l для символов алфавита А. По формуле (17) определить эффективность кодирования каждым методом и установить, какой из методов наиболее эффективен;
22) задана кодовая таблица эффективного кода (например, подобная табл. 12). Задана кодовая последовательность, представляющая некоторый текст, закодированный в этом коде. Раскодировать заданный текст;
23) задан исходный алфавит А и коды Грея для него. Построить помехозащитный код для обнаружения ошибки кратности 1 (см. табл. 15);
24) задан помехозащитный код (см. табл. 15). Определить расстояния между всеми парами кодовых комбинаций (табл. 16);
25) заданы расстояния между всеми парами кодовых комбинаций некоторого помехозащитного кода. Определить минимальное кодовое расстояние и кратность ошибки, которую этот код может обнаруживать и/или исправлять;
26) задан l-разрядный помехозащитный код. Построить алгоритм искажения его составляющих ошибкой заданной кратности q (см. (18));
27) задана искаженная кодовая комбинация и некоторый помехозащитный код. Построить алгоритм обнаружения ошибки;
28) задана искаженная кодовая комбинация и некоторый помехозащитный код. Построить алгоритм исправления ошибки (или диагностировать невозможность исправления);
29) задано С двоичных последовательностей, о каждой из которых известно, каким методом из описанных в заданиях 1 – 9 настоящих методических указаний она закодирована. Определить наиболее короткую последовательность и метод, которым она была получена;
30) задан исходный алфавит А и частоты символов, его составляющих. Рассчитать предельное значение размера кода по формуле (29);
31) дано 5-значное целое число. Сформировать из него 2 отрицательных вещественных числа по правилу, приведенному в задании 11 (см. (30));
32) дана десятичная дробь. Перевести ее в двоичную систему счисления с точностью р разрядов;
33) дано десятичное вещественное число. Представить его в нормализованной экспоненциальной форме;
34) даны целое двоичное число со знаком и разрядная сетка размером р двоичных разрядов, старший разряд зарезервирован под знак числа. Разместить двоичное число в разрядной сетке;
35) даны нормализованная мантисса двоичного числа со знаком и разрядная сетка для ее размещения размером р двоичных разрядов, старший разряд зарезервирован под знак мантиссы. Разместить мантиссу в разрядной сетке;
36) дано двоичное число, помещенное в разрядную сетку размером р двоичных разрядов в виде прямого кода. Старший разряд зарезервирован под знак числа. Построить обратный код числа;
37) дано двоичное число, помещенное в разрядную сетку размером р двоичных разрядов в виде обратного кода. Старший разряд зарезервирован под знак числа. Построить дополнительный код числа;
38) даны два отрицательных двоичных числа, помещенных в разрядные сетки размером р двоичных разрядов в виде обратных кодов. Старший разряд зарезервирован под знак числа. Выполнить сложение слагаемых. Результат представить в виде обратного кода;
39) даны два отрицательных двоичных числа, помещенных в разрядные сетки размером р двоичных разрядов в виде дополнительных кодов. Старший разряд зарезервирован под знак числа. Выполнить сложение слагаемых. Результат представить в виде дополнительного кода;
40) дано двоичное число, помещенное в разрядную сетку размером р двоичных разрядов в виде обратного кода. Старший разряд зарезервирован под знак числа. Построить прямой код числа;
41) дано двоичное число, помещенное в разрядную сетку размером р двоичных разрядов в виде дополнительного кода. Старший разряд зарезервирован под знак числа. Построить обратный код числа;
42) дано двоичное число, помещенное в разрядную сетку размером р двоичных разрядов. Старший разряд зарезервирован под знак числа. Выполнить сдвиг числовых разрядов на к разрядов вправо.
В качестве примера рассмотрим решение следующей задачи: разработать алгоритм для перевода заданного положительного целого десятичного числа в двоичную систему счисления. Представить алгоритм в виде блок-схемы и использовать при его составлении методы нисходящего проектирования, модульности, структурного программирования.
Решение:
1) определим входные, выходные и промежуточные данные, их типы и обозначения в блок-схеме. Очевидно, исходное и результирующее число можно определить как простые переменные. Сложнее дело обстоит с другими данными. Как показывает анализ известной схемы перевода (см., например, табл. 21), для решения задачи требуется «знать» все остатки от деления на 2. Для их хранения введем промежуточную переменную, которую опишем как одномерный массив. Кроме того, в каждом шаге перевода (суть деления очередного частного на 2) делимое меняет значение. Для его хранения можно использовать простую переменную. Важно также отметить, что в силу циклического характера схемы перевода в каждом шаге частное от деления становится делимым. Таким образом, введенные переменные сведены в табл. 23: