Вопросы для подготовки к экзамену
1. Понятие информации. Виды и свойства информации.
2. Аналоговая и дискретная форма представления информации.
3. Подходы к измерению количества информации. Единицы измерения информации.
4. Системы счисления как основа представления числовой информации.
5. Правила переводов для целых и дробных чисел между позиционными системами счисления.
6. Переводы между системами счисления с кратными основаниями.
7. Арифметика в позиционных системах счисления
8. Представление целых чисел в компьютере.
9. Представление вещественных чисел в компьютере.
10. Представление текстовой информации в компьютере.
11. Представление графической информации.
12. Представление звуковой информации.
13. Кодирование символьной информации.
14. Способы построения двоичных кодов
15. Понятие алгоритма и исполнителя. Система команд исполнителя.
16. Понятие графического исполнителя.
17. Свойства и способы записи алгоритма.
18. Необходимость строго определения алгоритма. Функциональный подход.
19. Алгоритмическая машина Поста.
20. Алгоритмическая машина Тьюринга.
21. Нормальные алгоритмы Маркова.
Основные типы задач
1. Определить количество информации в соответствии с вероятностным подходом.
2. Определить количество информации в соответствии с алфавитным подходом.
3. Определить объем для графической информации.
4. Определить объем для звуковой информации.
5. Кодирование и декодирование данных.
6. Построение кода Шеннона-Фано и кода Хаффмана для заданного алфавита.
7. Перевод числа из одной системы счисления в другую (целое или дробное число).
8. В указанной позиционной системе счисления выполнить арифметические операции: сложение, вычитание, умножение и деление.
9. Получить компьютерное представление целого числа (без знака и со знаком).
10. По компьютерному представлению восстановить целое число.
11. Получить компьютерное представление вещественного числа (на примере типа Double).
12. По компьютерному представлению восстановить вещественное число (на примере типа Double).
13. Анализ и построение алгоритмов для исполнителей
14. Выполнение алгоритмов для исполнителя Робот
15. Написать машину Тьюринга для решения задачи.
16. По данной машине Тьюринга определить алгоритм.
17. Написать машину Поста для решения задачи.
18. По данной машине Поста определить алгоритм.
19. Выполнить заданный алгоритм Маркова.
Задачи для тренировки
1. Перевести в десятичную систему счисления: 2031,1324; 3A7,9C15; 2342,5217
2. Перевести из десятичной в указанную систему счисления:
3. Пользуясь правилом перевода между системами с кратными основаниями перевести: из шестеричной в тридцатишестеричную и наоборот (два примера (дробные числа) привести самостоятельно)
4. Выполнить арифметические действия в указанной системе счисления:
5. В какой системе счисления справедливо равенство (ответ обосновать):
705-213-357=124
6. Получить дополнительный код числа (8 бит со знаком): - 13; -100
7. По данному дополнительному коду (8 бит со знаком) определить число:
00010111; 11001011
8. Получить представление вещественного числа в виде величины типа Double (результат представить в 16-ричной системе): 77,15625
9. По имеющемуся компьютерному представлению восстановить вещественное число: C077880000000000
10. Имеется два мешка с монетами, в каждом из которых находится по одной фальшивой монете (более легкой). Для определения фальшивой монеты в первом мешке потребовалось провести 6 взвешиваний, во втором мешке – 4 взвешивания. Сколько всего монет было в двух мешках?
11. На уроке математики Незнайку вызывают к доске в 4 раза реже, чем Винтика. Определить количество информации в сообщении о том, что к доске вызвали Винтика, если сообщение о том, что вызвали Незнайку, несет 8 бит информации.
12. Алфавит одного племени содержит X символов, алфавит другого содержит в четыре раза больше символов. Племена обменялись приветствиями длиной по 100 символов каждое. Количество бит информации в приветствии первого племени обозначим Info1, в приветствии второго племени – Info2. Выбрать верное утверждение:
A. Info1 = 4Info2
B. Info2 = 4Info1
C. Info1 – Info2 = 4
D. Info2 – Info1 = 200
E. Info2 = Info1 + 400
13. В алфавите некоторого языка всего две буквы: «А» и «Б». Все слова, записанные на этом языке, состоят из 11 букв. Какой максимальный словарный запас может быть у этого языка?
14. Выбрать слово, имеющее наибольшую сумму кодов символов в таблице кодировки ASCII.
А. окно В. кино С. ника D. конь E. ночь
15. Голубой цвет на компьютере с объемом страницы видеопамяти 125 Кбайт кодируется кодом 0011. Какова разрешающая способность графического дисплея?
A. 640×200 B. 320×400 C. 640×400 D. 640×800 E. 512×400
16. Часть страниц книги является цветными изображениями в шестнадцатицветной палитре и в формате 320×640 точек; страницы, содержащие текст, имеют формат 64 строки по 48 символов в строке. Сколько страниц книги можно сохранить на жестком магнитном диске объемом 40 Мбайт, если количество страниц с цветными изображениями на 80 больше количества страниц, содержащих только текст?
17. Для передачи сигналов на флоте используются специальные сигнальные флаги, вывешиваемые в одну линию (последовательность важна). Какое количество различных видов флагов надо иметь, чтобы при помощи последовательности из трех флагов можно было передать 8 различных сигналов (флагов каждого вида неограниченное количество)?
18. Для кодирования сообщений решено использовать последовательности разной длины, состоящие из знаков «+» и «-».Сколько различных сообщений можно закодировать, используя в каждом из них не менее 3-х и не более 7 знаков?
19. Для регистрации на сайте некоторой страны пользователю необходимо придумать пароль длиной ровно 15 символов. В пароле можно использовать десятичные цифры и 11 различных символов местного алфавита, причем все буквы используются в двух начертаниях – строчные и прописные. Каждый символ кодируется одинаковым и минимально возможным количеством бит, а каждый пароль – одинаковым и минимально возможным количеством байт. Определите объем памяти, необходимый для хранения 30 паролей.
20. Какое минимальное количество бит потребуется для кодирования положительных чисел, меньших 1060?
21. В закрытом ящике находится 32 карандаша, некоторые из них синего цвета. Наугад вынимается один карандаш. Сообщение «этот карандаш – НЕ синий» несёт 4 бита информации. Сколько синих карандашей в ящике?
22. В таблице ниже представлена часть кодовой таблицы ASCII:
| Символ | J | K | P | j | k | ||
| Десятичный код | |||||||
| Шестнадцатеричный код | 4A | 4B | 6A | 6B |
Каков шестнадцатеричный код символа «p»?
23. Текстовый документ, состоящий из 4096 символов, хранился в 16-битной кодировке Unicode. Этот документ был преобразован в 8-битную кодировку Windows-1251. Укажите, на сколько Кбайт уменьшился объем файла. В ответе запишите только число.
24. Производится одноканальная (моно) звукозапись с частотой дискретизации 64 Гц. При записи использовались 64 уровня дискретизации. Запись длится 5 минут 20 секунд, её результаты записываются в файл, причём каждый сигнал кодируется минимально возможным и одинаковым количеством битов. Какое из приведённых ниже чисел наиболее близко к размеру полученного файла, выраженному в килобайтах?
1) 10 2) 15 3) 32 4) 64
25. Производится двухканальная (стерео) звукозапись с частотой дискретизации 8 кГц и глубиной кодирования 24 бит. Запись длится 4 минуты, ее результаты записываются в файл, сжатие данных не производится. Какое из приведенных ниже чисел наиболее близко к размеру полученного файла, выраженному в мегабайтах?
1) 11 2) 12 3) 13 4) 15
26. Для кодирования букв И, Д, Т, О, Х используются двоичные коды чисел 0, 1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления). Если таким способом закодировать последовательность символов ТИХОХОД и записать результат в шестнадцатеричном коде, то получится:
1) CD89 2) 89CD 3) 3154542 4) 2043431
27. Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А–11, Б–10, В–011, Г–000, Д–001. Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны. Выберите правильный вариант ответа.
1) для буквы Г – 00 2) это невозможно
3) для буквы В – 01 4) для буквы Б – 1
28. Построить код Шеннона-Фано и код Хаффмана для следующих алфавитов:
| A1 | A2 | A3 | A4 | A5 | A6 | A7 | A8 | A9 | A10 |
| 0,14 | 0,16 | 0,13 | 0,1 | 0,11 | 0,12 | 0,09 | 0,05 | 0,06 | 0,04 |
29. Зашифруйте с помощью шифра Цезаря со сдвигом 6 высказывание “ЛЮДИ ОХОТНО ВЕРЯТ ТОМУ, ЧЕМУ ЖЕЛАЮТ ВЕРИТЬ”
30. У исполнителя Утроитель две команды, которым присвоены номера:
Вычти 2
Умножь на три
Первая из них уменьшает число на экране на 2, вторая – утраивает его. Запишите порядок команд в программе получения из 11 числа 13, содержащей не более 5 команд, указывая лишь номера команд. (Например, 21211 – это программа:
Умножь на три
Вычти 2
Умножь на три
Вычти 2
Вычти 2,
которая преобразует число 2 в 8). (Если таких программ более одной, то запишите любую из них.)
31. У исполнителя Калькулятор две команды, которым присвоены номера:
Прибавь 2
Умножь на 3
Выполняя первую из них, Калькулятор прибавляет к числу на экране 2, а выполняя вторую, утраивает его. Запишите порядок команд в программе получения из 0 числа 28, содержащей не более 6 команд, указывая лишь номера команд. (Например, программа 21211 – это программа:
Умножь на 3
Прибавь 2
Умножь на 3
Прибавь 2
Прибавь 2,
которая преобразует число 1 в 19).
32. У исполнителя УТРОИТЕЛЬ две команды, которым присвоены номера:
Вычти 1
Умножь на 3
Первая из них уменьшает число на экране на 1, вторая – увеличивает его в три раза.
Запишите порядок команд в программе получения из числа 3 числа 16, содержащей не более 5 команд, указывая лишь номера команд.
(Например, программа 21211 это программа
Умножь на 3
Вычти 1
Умножь на 3
Вычти 1
Вычти 1
которая преобразует число 1 в 4.)
33. Имеется исполнитель Кузнечик, который живет на числовой оси. Система команд Кузнечика:
Вперед N (Кузнечик прыгает вперед на N единиц);
Назад M (Кузнечик прыгает назад на M единиц).
Переменные N и M могут принимать любые целые положительные значения. Известно, что Кузнечик выполнил программу из 50 команд, в которой команд “Назад 2” на 12 больше, чем команд “Вперед 3”. Других команд в программе не было. На какую одну команду можно заменить эту программу, чтобы Кузнечик оказался в той же точке, что и после выполнения программы?
34. Исполнитель КАЛЬКУЛЯТОР имеет только две команды, которым присвоены номера:
Умножь на 2
Вычти 2
Выполняя команду номер 1, КАЛЬКУЛЯТОР умножает число на экране на 2, а выполняя
команду номер 2, вычитает из числа на экране 2. Напишите программу, содержащую не
более 5 команд, которая из числа 7 получает число 44. Укажите лишь номера команд.
Например, программа 11221 – это программа:
Умножь на 2;
Умножь на 2;
Вычти 2;
Вычти 2;
Умножь на 2,
которая преобразует число 5 в число 32.
35. Система команд исполнителя РОБОТ, «живущего» в прямоугольном лабиринте на клетчатой плоскости:
вверх вниз влево вправо.
При выполнении любой из этих команд РОБОТ перемещается на одну клетку соответственно: вверх ↑, вниз ↓, влево ←, вправо →. Четыре команды проверяют истинность условия отсутствия стены у каждой стороны той клетки, где находится РОБОТ: