Л.А. Внукова, О.А. Дерябина, Н.Н. Егорова, Е.В. Селезнева ОСНОВЫ ИНФОРМАТИКИ

2 Федеральное агентство по образованию Сибирская государственная автомобильно-дорожная академия (СибАДИ) Л.А. Внукова, О.А. Дерябина, Н.Н. Егорова, Е.В. Селезнева ОСНОВЫ ИНФОРМАТИКИ Учебно-методическое пособие Омск Издательство СибАДИ

3 ОГЛАВЛЕНИЕ Введение. 3 Раздел 1. Представление числовой информации Понятие о системах счисления. Основные определения Представление чисел в позиционных системах счисления Перевод десятичных чисел в другие системы счисления и обратно Арифметические операции в позиционных системах счисления 10 Практические задания. 11 Самостоятельная работа.. 12 Раздел 2. Измерение информации Основные сведения Алфавитный подход к измерению информации 21 Практические задания Содержательный подход к измерению информации 23 Практические задания Вероятностный подход к измерению информации Практические задания. 26 Самостоятельная работа. 26 Раздел 3. Основы логики и логические основы компьютера Алгебра высказываний. Логические выражения и таблицы истинности 33 Практические задания Логические формулы 37 Практические задания Логические схемы 38 Практические задания. 39 Самостоятельная работа.. 42 Раздел 4. Основы алгоритмизации Алгоритм и его свойства Свойства алгоритмов Формы записи алгоритмов Компоненты алгоритмического языка Стандартные функции Основные типы алгоритмических структур Практические задания. 64 Самостоятельная работа.. 67 Библиографический список 72 50

4 УДК ББК О 75 Рецензенты д-р пед. наук З.В. Семенова, канд. физ.-мат. наук Л.Г. Кузнецова Работа одобрена редакционно-издательским советом академии в качестве учебнометодического пособия для всех специальностей очного обучения Основы информатики / Л.А. Внукова, О.А. Дерябина, Н.Н. Егорова, Е.В. Селезнева: Учебно-методическое пособие. Омск: Изд-во СибАДИ, с. Учебно-методическое пособие предназначено для проведения практических занятий курса «Информатика» для студентов очной формы обучения всех специальностей СибАДИ. В пособие включены следующие разделы: «Представление числовой информации», «Измерение информации», «Основы логики и логические основы компьютера», «Основы алгоритмизации», темы которых соответствуют требованиям государственного образовательного стандарта высшего профессионального образования и программе «Информатика». Разделы содержат теорию и практические задания, а также практические задания в форме самостоятельной работы по вариантам для контроля знаний. Табл. 12. Библиогр.: 9 назв. 51 Л.А. Внукова, О.А. Дерябина,

5 ISN х Н.Н. Егорова, Е.В. Селезнева,

6 Введение Информатика входит в число базовых дисциплин системы высшего образования и в комплексе с другими фундаментальными дисциплинами формирует основу профессионального образования в вузе. Уже сегодня важнейшей составляющей образованности человека является свободное владение информационными технологиями, так как деятельность людей все в большей степени зависит от информированности и способности эффективно использовать информацию. Для этого квалифицированный специалист любого профиля должен уметь находить, обрабатывать и использовать информацию с помощью компьютеров и других вычислительных и телекоммуникационных средств. Знания информатики и информационных технологий необходимые требования профессиональной пригодности в XXI веке. Информатика как учебная дисциплина ориентирована прежде всего на формирование системного мировоззрения в информационной сфере и приобретение информационной культуры, т.е. умений целенаправленно и эффективно работать с информацией, используя информационные технологии. Последние в этом плане представляют собой не только инструмент, но и определяют технологии интеллектуальной, мыслительной деятельности человека. Практические занятия в первом семестре курса «Информатика» посвящены изучению таких понятий, как системы счисления, измерение информации, основы логики, основы алгоритмизации. В связи с этим в учебнометодическое пособие включены следующие разделы: «Представление числовой информации», «Измерение информации», «Основы логики и логические основы компьютера», «Основы алгоритмизации». Каждый раздел учебно-методического пособия содержит теоретический материал, практические задания и задания для самостоятельной работы по вариантам. Данный материал рассчитан на студентов очного обучения всех специальностей для проведения практических аудиторных работ вне компьютерного класса. Раздел 1. ПРЕДСТАВЛЕНИЕ ЧИСЛОВОЙ ИНФОРМАЦИИ 53

7 1.1. Понятие о системах счисления. Основные определения Система счисления это совокупность правил для обозначения и наименования чисел. Знаки, используемые при записи чисел, называются цифрами. Системы счисления делятся на непозиционные и позиционные. Непозиционной называется такая система счисления, в которой количественный эквивалент каждой цифры не зависит от ее положения (места, позиции) в коде числа. Следует отметить, что непозиционные системы счисления возникли раньше позиционных. Приведем примеры непозиционных систем счисления. Пример 1. Римская система счисления: I 1; V 5; X 10; L 50; 100; D 500; M 1000 и т. д. Пример 2. Система счисления Древнего Египта: Непозиционные системы счисления имеют недостатки: для записи больших чисел необходимо вводить новые цифры; нельзя записать дробные и отрицательные числа; сложно выполнять арифметические операции. Система счисления называется позиционной, если количественный эквивалент (значение) цифры зависит от ее места (позиции) в коде числа. Основные достоинства позиционных систем счисления: простота выполнения арифметических операций; ограниченное количество символов, необходимых для записи любого числа. Количество используемых цифр называется основанием позиционной системы счисления. Основанием (базисом) позиционной системы счисления называется количество знаков или символов, используемых для изображения числа в данной системе счисления. В повседневной жизни используется позиционная десятичная система. Основание равно десяти: для записи чисел используются десять различных знаков (цифры 0, 1, 2, 3, 4, 5, 6, 7, 8, 9). Из двух рядом стоящих цифр (например, число 35) левая цифра выражает число, в десять раз больше, чем правая. Кроме того, имеет значение не только сама цифра, но и ее место (позиция), что указывает на позиционный характер данной системы счисления Представление чисел в позиционных системах счисления 54

8 Для записи чисел в позиционной системе счисления с основанием, меньшим десяти, используются цифры от 0 до 9. При основании, большем десяти, к перечисленным цифрам добавляются буквы. Приведем пример для самых распространенных систем счисления (табл. 1). Таблица 1. Распространенные системы счисления Основание Название системы счисления Цифры для обозначения 2 Двоичная 0, 1 3 Троичная 0, 1, 2 5 Пятеричная 0, 1, 2, 3, 4 8 Восьмеричная 0, 1, 2, 3, 4, 4, 5, 6, 7 16 Шестнадцатеричная 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, А. D, E, F В системе счисления с основанием q ( q -ичная система счисления) единицами разрядов служат последовательные степени числа q, иначе говоря, q единиц какого-либо разряда образуют единицу следующего разряда. Для записи чисел в q -ичной системе счисления требуется q различных знаков (цифр), изображающих числа 0,1,, q 1. Запись числа q в q -ичной системе счисления имеет вид 10. Таким образом, в позиционной системе счисления любое вещественное число можно представить в следующем виде: q n1 n m ( a q a q. a q a q a q. a q ) (1) n1 n m или n 1 ai i m q, (1а) q i где само число; q основание системы счисления; a q i цифры данной системы счисления; n число разрядов целой части числа; m число разрядов дробной части числа. Приведенная выше формула называется развернутой формулой записи. Исходя из данной формулы можно получить формулу для записи произвольного целого числа: n1 n2 qц ( an 1 q an2 q. a0 q ), (2) а также формулу для записи произвольного дробного числа: 0 55

9 qдр 1 2 m 1 q a2 q am q. (3) a Перевод десятичных чисел в другие системы счисления и обратно Перевод целых чисел Алгоритм перевода. Пусть qц десятичное целое число. Тогда в разложении отсутствуют коэффициенты с отрицательными индексами. Данное число представляется в виде n1 1 0 qц an 1 q. a1 q a0 q. (4) n2 1. Число qц разделим на q. Неполное частное равно: an 1 q. a1, а остаток равен a Полученное неполное частное опять разделим на q, остаток от деления будет равен a Продолжим данный процесс деления, пока на n -м шаге не получим набор цифр: a 0, a1, a2. a n 1, которые входят в q -ичное представление числа и совпадают с остатками при последовательном делении данного числа qц на q. 4. Запишем десятичное целое число в новой системе счисления, начиная запись с последнего частного: qц an1 an2. a1a 0. (5) Пример. Переведите число в двоичную, восьмеричную и шестнадцатеричную системы счисления ( А 2 ; А 8 ; А 16 ) Результат: = Проверка: =

10 Результат: = Проверка: = Результат: =7 16. Проверка: = Перевод дробных чисел Алгоритм перевода. Пусть qдр правильная десятичная дробь. Тогда в разложении отсутствуют коэффициенты с положительными индексами. Данное число представим в виде 1 2 qдр a q a q. (6) Для нахождения коэффициентов a a. входящих в запись числа в 1, 2 q -ичной системе счисления, умножим правую и левую части выражения (6) на q. В результате в правой части получим a a q a q. Целая часть равна a 1 по степеням q. qдр, является старшим коэффициентом в разложении числа 2. Оставшуюся дробную часть умножим на q : a 2 a 3 q. где цифра a 2 представляет собой второй коэффициент после запятой в двоичном представлении исходного числа. 3. Продолжаем перемножение дробной части на q до тех пор, пока в правой части не получим нуль или не будет достигнута необходимая точность вычислений. Пример 1. Переведите десятичную дробь 0,5625 в двоичную систему счисления. 1 57

11 0, Результат: 0, =0, Пример 2. Переведите десятичную дробь 0,65625 в восьмеричную и шестнадцатеричную системы счисления. 0, Результат: 0, =0, , (А) Результат: 0, =0,А8 16. Пример 3. Переведите десятичную дробь 0,7 в восьмеричную систему счисления. 0,

12 Данный процесс может продолжаться бесконечно. Такой бесконечный процесс завершается на некотором шаге, когда считается, что получена требуемая точность представления числа. Пример 4. Переведите десятичную дробь 0, в двоичную систему счисления. В двоичной записи числа сохраните четыре знака. 0, Результат: 0,101 2 =0, Перевод смешанных чисел Перевод смешанных чисел, содержащих целую и дробную части, осуществляется в два этапа. Целая и дробная части исходного числа переводятся согласно приведенным выше алгоритмам. В итоговой записи в новой системе счисления целая часть отделяется от дробной запятой или точкой. Пример. Переведите число 12,25 10 в двоичную систему счисления. Переведем целую часть: Переведем дробную часть: 0,

13 Результат: 12,25 10 =1100, Арифметические операции в позиционных системах счисления Рассмотрим арифметические операции на примере двоичной системы счисления. Рассмотрим таблицы сложения, вычитания и умножения Сложение в двоичной системе счисления Примеры. Выполните операцию сложения над двоичными числами: Вычитание в двоичной системе счисления означает заем из старшего разряда. Примеры. Выполните операцию вычитания над двоичными числами: Умножение в двоичной системе счисления

14 Примеры. Выполните операцию умножения над двоичными числами: Деление в двоичной системе счисления Операция деления выполняется по алгоритму, подобному алгоритму операции деления в десятичной системе счисления. Примеры. Выполните операцию деления над двоичными числами: Практические задания 1. Переведите целые числа из десятичной системы счисления в двоичную систему счисления: а) 75; 137; 2897; 433; б) 17; 219; 7654; Переведите целые числа из десятичной системы счисления в восьмеричную систему счисления: а) 35; 737; 2853; 4123; б) 58; 759; 165;

15 3. Переведите целые числа из десятичной системы счисления в шестнадцатеричную систему счисления: а) 87; 234; 1987; 5124; б) 367; 79; 2222; Переведите числа из одной системы счисления в другую: а) =А 10 ; =А 10 ; =А 10 ; б) =А 10 ; =А 10 ; =А 10 ; в) =А 10 ; =А 10 ; г) =А 3 ; =А 5 ; =А Переведите десятичные дроби в двоичную систему счисления (ответ записать с шестью двоичными знаками): 0,17; 0,56; 0, Переведите смешанные десятичные числа в двоичную, восьмеричную и шестнадцатеричную системы счисления, оставив пять знаков в дробной части нового числа (X 10 А 2 ; X 10 А 8 ; X 10 А 16 ): 0,23; 0,79; 0, Выполните операцию сложения над двоичными числами: а) ; ; б) ; Выполните операцию вычитания над двоичными числами: а) ; ; б) ; Выполните операцию умножения над двоичными числами: а) ; ; б) ; Выполните операцию деления над двоичными числами: а) : ; : ; б) : ; : Самостоятельная работа Вариант 1 1. Переведите числа из одной системы счисления в другую с последующей проверкой: = 2 ; = 3 ; = 8 ; = 16 ; = 10 ; =

16 2. Переведите смешанные десятичные числа в двоичную, восьмеричную и шестнадцатеричную системы счисления, оставив пять знаков в дробной части нового числа (X 10 А 2 ; X 10 А 8 ; X 10 А 16 ): 173, ; 10123, ; 14567, Выполните операцию сложения над двоичными числами: ; Выполните операцию вычитания над двоичными числами: ; Выполните операцию умножения над двоичными числами: ; Выполните операцию деления над двоичными числами: : ; : Вариант 2 1. Переведите числа из одной системы счисления в другую с последующей проверкой: = 2 ; = 3 ; = 8 ; = 16 ; = 10 ; = Переведите смешанные десятичные числа в двоичную, восьмеричную и шестнадцатеричную системы счисления, оставив пять знаков в дробной части нового числа (X 10 А 2 ; X 10 А 8 ; X 10 А 16 ): 921, ; 3275, ; 10121, Выполните операцию сложения над двоичными числами: ; Выполните операцию вычитания над двоичными числами: ; Выполните операцию умножения над двоичными числами: ; Выполните операцию деления над двоичными числами: : ; : Вариант 3 1. Переведите числа из одной системы счисления в другую с последующей проверкой: 63

17 77 10 = 2 ; = 3 ; = 8 ; = 16 ; = 10 ; = Переведите смешанные десятичные числа в двоичную, восьмеричную и шестнадцатеричную системы счисления, оставив пять знаков в дробной части нового числа (X 10 А 2 ; X 10 А 8 ; X 10 А 16 ): 3678, ; 9973, ; 7632, Выполните операцию сложения над двоичными числами: ; Выполните операцию вычитания над двоичными числами: ; Выполните операцию умножения над двоичными числами: ; Выполните операцию деления над двоичными числами: : ; : Вариант 4 1. Переведите числа из одной системы счисления в другую с последующей проверкой: = 2 ; = 3 ; = 8 ; = 16 ; = 10 ; = Переведите смешанные десятичные числа в двоичную, восьмеричную и шестнадцатеричную системы счисления, оставив пять знаков в дробной части нового числа (X 10 А 2 ; X 10 А 8 ; X 10 А 16 ): 923, ; 11231, ; 993, Выполните операцию сложения над двоичными числами: ; Выполните операцию вычитания над двоичными числами: ; Выполните операцию умножения над двоичными числами: ; Выполните операцию деления над двоичными числами: : ; : Вариант 5 64

18 1. Переведите числа из одной системы счисления в другую с последующей проверкой: = 2 ; = 3 ; = 8 ; = 16 ; = 10 ; = 10 ; = Переведите смешанные десятичные числа в двоичную, восьмеричную и шестнадцатеричную системы счисления, оставив пять знаков в дробной части нового числа (X 10 А 2 ; X 10 А 8 ; X 10 А 16 ): 213, ; 3278, ; 2216, Выполните операцию сложения над двоичными числами: ; Выполните операцию вычитания над двоичными числами: ; Выполните операцию умножения над двоичными числами: ; Выполните операцию деления над двоичными числами: : ; : Вариант 6 1. Переведите числа из одной системы счисления в другую с последующей проверкой: = 2 ; = 3 ; = 8 ; = 16 ; = 10 ; = Переведите смешанные десятичные числа в двоичную, восьмеричную и шестнадцатеричную системы счисления, оставив пять знаков в дробной части нового числа (X 10 А 2 ; X 10 А 8 ; X 10 А 16 ): 1239, ; 956, ; 1247, Выполните операцию сложения над двоичными числами: ; Выполните операцию вычитания над двоичными числами: ; Выполните операцию умножения над двоичными числами: ; Выполните операцию деления над двоичными числами: : ; :

19 Вариант 7 1. Переведите числа из одной системы счисления в другую с последующей проверкой: = 2 ; = 3 ; = 8 ; = 16 ; 40D 15 = 10 ; = Переведите смешанные десятичные числа в двоичную, восьмеричную и шестнадцатеричную системы счисления, оставив пять знаков в дробной части нового числа (X 10 А 2 ; X 10 А 8 ; X 10 А 16 ): 917, ; 1238, ; 2151, Выполните операцию сложения над двоичными числами: ; Выполните операцию вычитания над двоичными числами: ; Выполните операцию умножения над двоичными числами: ; Выполните операцию деления над двоичными числами: : ; : Вариант 8 1. Переведите числа из одной системы счисления в другую с последующей проверкой: = 2 ; = 3 ; = 8 ; = 16 ; = 10 ; = Переведите смешанные десятичные числа в двоичную, восьмеричную и шестнадцатеричную системы счисления, оставив пять знаков в дробной части нового числа (X 10 А 2 ; X 10 А 8 ; X 10 А 16 ): 997, ; 1993,57 10 ; 215, Выполните операцию сложения над двоичными числами: ; Выполните операцию вычитания над двоичными числами: ; Выполните операцию умножения над двоичными числами: ; Выполните операцию деления над двоичными числами: : ; :

20 Вариант 9 1. Переведите числа из одной системы счисления в другую с последующей проверкой: = 2 ; = 3 ; = 8 ; = 16 ; = 10 ; = Переведите смешанные десятичные числа в двоичную, восьмеричную и шестнадцатеричную системы счисления, оставив пять знаков в дробной части нового числа (X 10 А 2 ; X 10 А 8 ; X 10 А 16 ): 1241, ; 998, ; 168, Выполните операцию сложения над двоичными числами: ; Выполните операцию вычитания над двоичными числами: ; Выполните операцию умножения над двоичными числами: ; Выполните операцию деления над двоичными числами: : ; : Вариант Переведите числа из одной системы счисления в другую с последующей проверкой: = 2 ; = 3 ; = 8 ; = 16 ; = 10 ; = Переведите смешанные десятичные числа в двоичную, восьмеричную и шестнадцатеричную системы счисления, оставив пять знаков в дробной части нового числа (X 10 А 2 ; X 10 А 8 ; X 10 А 16 ): 2168, ; 5432,69 10 ; 118, Выполните операцию сложения над двоичными числами: ; Выполните операцию вычитания над двоичными числами: ; Выполните операцию умножения над двоичными числами: ;

21 6. Выполните операцию деления над двоичными числами: : ; : Вариант Переведите числа из одной системы счисления в другую с последующей проверкой: = 2 ; = 3 ; = 8 ; = 16 ; = 10 ; = Переведите смешанные десятичные числа в двоичную, восьмеричную и шестнадцатеричную системы счисления, оставив пять знаков в дробной части нового числа (X 10 А 2 ; X 10 А 8 ; X 10 А 16 ): 567, ; 883,67 10 ; 124, Выполните операцию сложения над двоичными числами: ; Выполните операцию вычитания над двоичными числами: ; Выполните операцию умножения над двоичными числами: ; Выполните операцию деления над двоичными числами: : ; : Вариант Переведите числа из одной системы счисления в другую с последующей проверкой: = 2 ; = 3 ; = 8 ; = 16 ; = 10 ; = Переведите смешанные десятичные числа в двоичную, восьмеричную и шестнадцатеричную системы счисления, оставив пять знаков в дробной части нового числа (X 10 А 2 ; X 10 А 8 ; X 10 А 16 ): 557, ; 973, ; 1330, Выполните операцию сложения над двоичными числами: ; Выполните операцию вычитания над двоичными числами: ; Выполните операцию умножения над двоичными числами: ;

22 6. Выполните операцию деления над двоичными числами: : ; : Вариант Переведите числа из одной системы счисления в другую с последующей проверкой: = 2 ; = 3 ; = 8 ; = 16 ; = 10 ; = Переведите смешанные десятичные числа в двоичную, восьмеричную и шестнадцатеричную системы счисления, оставив пять знаков в дробной части нового числа (X 10 А 2 ; X 10 А 8 ; X 10 А 16 ): 158, ; 2389, ; 995, Выполните операцию сложения над двоичными числами: ; Выполните операцию вычитания над двоичными числами: ; Выполните операцию умножения над двоичными числами: ; Выполните операцию деления над двоичными числами: : ; : Вариант Переведите числа из одной системы счисления в другую с последующей проверкой: = 2 ; = 3 ; = 8 ; = 16 ; = 10 ; = Переведите смешанные десятичные числа в двоичную, восьмеричную и шестнадцатеричную системы счисления, оставив пять знаков в дробной части нового числа (X 10 А 2 ; X 10 А 8 ; X 10 А 16 ): 986, ; 1246, ; 2151, Выполните операцию сложения над двоичными числами: ; Выполните операцию вычитания над двоичными числами: ; Выполните операцию умножения над двоичными числами: ;

23 6. Выполните операцию деления над двоичными числами: : ; : Вариант Переведите числа из одной системы счисления в другую с последующей проверкой: = 2 ; = 3 ; = 8 ; = 16 ; = 10 ; = Переведите смешанные десятичные числа в двоичную, восьмеричную и шестнадцатеричную системы счисления, оставив пять знаков в дробной части нового числа (X 10 А 2 ; X 10 А 8 ; X 10 А 16 ): 1675, ; 160, ; 3580, Выполните операцию сложения над двоичными числами: ; Выполните операцию вычитания над двоичными числами: ; Выполните операцию умножения над двоичными числами: ; Выполните операцию деления над двоичными числами: : ; :

24 Раздел 2. ИЗМЕРЕНИЕ ИНФОРМАЦИИ 2.1. Основные сведения Информация сведения об объектах и явлениях окружающей среды, их параметрах, свойствах и состоянии, которые уменьшают имеющуюся о них степень неопределенности, неполноты знаний. За единицу измерения количества информации принимается 1 бит. 1 байт = 2 3 бит = 8 бит. Более крупными единицами измерения информации являются: 1Кбайт (килобайт) = 2 10 байт = 1024 байт. 1Мбайт (мегабайт) = 2 10 Кбайт = 1024 Кбайт. 1Гбайт (гигабайт) = 2 10 Мбайт = 1024 Мбайт. 1Тбайт (терабайт) = 2 10 Гбайт = 1024 Гбайт. 1Пбайт (петабайт) = 2 10 Тбайт = 1024 Тбайт. Пример 1. Получено сообщение, объём которого равен 45 битам. Определите, чему равен объём сообщения в Кбайтах. Решение: 45 5,625 45бит байт 5,625байт Кбайт 0,0055Кбайт Пример 2. Сколько файлов размером по 120 Кбайт каждый можно разместить на диске ёмкостью 210 Мбайт? Решение: 210 Мбайт = Кбайт (файла) Известно несколько подходов к измерению информации: 1) алфавитный; 2) содержательный; 3) вероятностный Алфавитный подход к измерению информации Использование алфавитного подхода при измерении информации позволяет определить количество информации, заключенной в тексте. Символы, используемые при записи текста, называются алфавитом. Полное число символов используемого алфавита называется мощностью алфавита. Обозначим мощность алфавита буквой N. Учитывая, что каждый символ алфавита может появиться в очередной позиции текста в любой момент и несет i бит информации, мощность алфавита можно посчитать по формуле N = 2 i. 71

25 Приведенная формула является показательным уравнением относительно неизвестной i. Решение такого уравнения имеет вид i = log 2 N логарифм от N по основанию 2. Следовательно, в 2-символьном алфавите каждый символ несет 1 бит информации (log 2 2 = 1), в 4-символьном 2 бита информации (log 2 4 = 2), в 8- символьном 3 бита (log 2 8 = 3) и т.д. Если весь текст состоит из K символов, то для расчета содержащейся в нем информации используется формула I = K i. Пример 1. Сообщение записано 32-символьным алфавитом и содержит 30 символов. Какой объём информации оно несёт? Решение:. i = log 2 N = log 2 32 = 5 (бит) информации содержит каждый символ данного алфавита. Так как в тексте содержится K = 30 символов, то I = K i = 30 5 = 150 (бит) информации содержит все сообщение. Пример 2. Книга, набранная с помощью компьютера, содержит 250 страниц; на каждой странице 40 строк, в каждой строке 50 символов. Каков объем информации в книге в килобайтах? Решение: Мощность компьютерного алфавита равна 256. Один символ несет 1 байт информации. Таким образом, страница содержит = 2000 байт информации. Объем информации во всей книге равен: = байт / 1024 = 488,28125 Кбайт. Пример 3. Сообщение, занимающее 4 страницы, содержит 1/2 Кбайта информации. Каждая страница состоит из 256 символов. Какова мощность алфавита, с помощью которого записано сообщение? Решение: Все сообщение состоит из = 1024 символов. Один символ несет 2 1/ 2Кбайт 1/ бит бит. Тогда мощность алфавита, с помощью которого записано сообщение, равна 2 4 = 16 символов. Практические задания 1. Сколько килобайт содержит сообщение из 64-символьного алфавита? 2. Для записи текста, каждая страница которого состоит из 20 строк по 60 символов, использовался 128-символьный алфавит. Какой объем информации содержат 3 страницы текста? 72

26 3. Сообщение, записанное с помощью 32-символьного алфавита, занимает 4 страницы по 24 строки каждая. Все сообщение содержит 42 байта информации. Сколько символов в строке? 4. Два сообщения содержат одинаковое количество символов. Во втором сообщении количество информации в 2 раза больше, чем в первом. Сколько символов содержит первый алфавит, с помощью которого записано сообщение, если известно, что размер второго алфавита равен 32? 5. Пользователь компьютера, хорошо владеющий навыками ввода информации с клавиатуры, может вводить в минуту 100 знаков. Какое количество информации в байтах может ввести пользователь в компьютер за 5 минут, если мощность алфавита равна 256? 2.3. Содержательный подход к измерению информации Данный подход дает количественную оценку информации: нужная, важная, интересная, вредная и т.д. Все люди имеющуюся информацию могут оценить по-разному. Сообщение, уменьшающее неопределённость знаний человека в два раза, несет 1 бит информации. Если в некотором сообщении сказано, что произошло одно из N равновероятных событий, т.е. ни одно событие не имеет преимуществ перед другим, тогда количество информации, заключённое в этом сообщении, i бит и число N связаны формулой Хартли: i = log 2 N. Для задач с применением данной формулы используется табл. 2. Таблица 2. Количество информации и числа равновероятных событий N i N i N i N i 1 0, , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , ,

27 16 4, , , ,00000 Пример 1. В корзине 16 мячей разного цвета. Сколько информации несет сообщение о том, что из корзины достали мяч синего цвета? Решение: Вытаскивание любого из 8 мячей равновероятно, следовательно, количество информации, заключенной в сообщении о вытаскивании одного такого мяча, находится по формуле i = log 2 16 = 4. Пример 2. При угадывании целого числа в диапазоне от 1 до M было получено 5 бит информации. Чему равно М? Решение: Число М находится из формулы 5 = log 2 М, отсюда М = 2 5 = 32. Пример 3. Сколько информации содержится в сообщении о том, что из колоды карт достали случайным образом даму пик (колода 36 карт)? Решение: i = log 2 36 = 5,16993 бит. Практические задания 1. В школьной библиотеке 16 стеллажей с книгами. На каждом стеллаже 10 полок. Библиотекарь сообщил Андрею, что нужная ему книга находится на втором стеллаже на третьей полке сверху. Какое количество информации библиотекарь передал Андрею? 2. В коробке лежат 7 цветных карандашей. Какое количество информации содержит сообщение, что из коробки достали красный карандаш? 3. Сколько бит информации несет угадывание числа из заданного диапазона, в котором находится 128 чисел? 4. Какое количество информации несет в себе сообщение о том, что нужный файл находится на одной из четырех дискет? 5. После прочтения статьи неопределенность знаний уменьшается в 8 раз. Какое количество информации содержит текст? 2.4. Вероятностный подход к измерению информации Рассмотрим ряд примеров. Пример 1. На ровную поверхность мы бросаем монету. При этом она окажется в одном из двух положений: «орел» или «решка». Каждое из этих событий произойдет с равной вероятностью. Решение: Обозначим р р вероятность выпадения «решки», р о вероятность выпадения «орла», тогда р р = р о = 1/2 = 0,5. 74

28 Пример 2. В коробке лежат 12 карандашей разного цвета. С равной вероятностью из коробки могут достать карандаш любого цвета. Решение: р = 1/12. Количество информации i и число равновероятных событий N связаны между собой формулой Хартли: i = log 2 N. Пример 3. В вазе лежат 16 конфет разного вида. Сколько информации несет сообщение о том, что из вазы взяли конфету «Ромашка»? Решение: То, что из вазы возьмут любую из 16 конфет, равновероятно, следовательно, количество информации об одной такой конфете находится по формуле i = log 2 16 = 4 бита. Зависимость вероятности события и общего числа этих событий определяется по формуле N = 1/p. Отсюда формула Хартли примет вид i = log 2 (1/p). Данная формула применяется и для тех случаев, когда вероятности результатов опыта неодинаковы. Пример 4. В коробке лежат 6 желтых, 10 красных, 8 синих и 6 зеленых кубиков. Сколько информации несет сообщение о том, что достали синий кубик, желтый кубик, красный кубик, зеленый кубик? Решение: Обозначим р ж вероятность попадания при вытаскивании желтого кубика; р к вероятность попадания при вытаскивании красного кубика; р с вероятность попадания при вытаскивании синего кубика; р з вероятность попадания при вытаскивании зеленого кубика. Тогда р ж = 6/30 = 1/5; i = log 2 5 = 2,32193; p к = 10/30 = 1/3; i = log 2 3 = 1,58496; p с = 8/30 = 4/15; i = log 2 3,75 = 1,90689; p з = 6/30 = 1/5; i = log 2 5 = 2, Вероятностный метод используется и для алфавитного подхода. В этом случае используется формула Шеннона I N p p i i log 1 2 i. Пример 5. Какое количество информации будет получено при бросании несимметричной четырехгранной пирамиды, если вероятности отдельных событий будут равны р 1 =1/4; р 2 = 3/8; р 3 = 1/8; р 4 =1/4. Решение: Количество информации, полученное при реализации одного из четырех возможных событий, равно I = (1/4 log 2 1/4 + 3/8 log 2 3/8 + 1/8 log 2 1/8 + 1/4 log 2 1/4) = = ( 1/2 +3/8 1,58 9/8 3/8 1/2) = 1,

29 Практические задания 1. В коробке 32 цветных мелка. Сколько оранжевых мелков в коробке, если сообщение о том, что достали оранжевый мелок, несет 2 бита информации? 2. В классе 24 ученика. Какое количество информации несет сообщение о том, что Сергей получил тройку за диктант, если всего в классе 8 троек? 3. Сколько информации несет сообщение о том, что достали зеленый мяч, если в корзине лежат 10 синих мячей и 22 зеленых? 4. В непрозрачном мешочке хранятся 25 белых, 30 красных, 35 синих и 10 зеленых фишек. Какое количество информации содержит зрительное сообщение о цвете вынутой фишки? 5. Вероятность первого события составляет 0,6, а второго и третьего 0,2. Какое количество информации мы получим после реализации одного из них? Самостоятельная работа Вариант 1 1. Определите объем текста в килобайтах, если его объем равен 64 бита? 2. Какой объем информации в байтах несет сообщение, записанное 64- символьным алфавитом, если оно содержит 400 символов? 3. На вопрос пассажира автобуса: «Вы будете выходить на следующей остановке?» получен ответ: «Да». Сколько информации несет в себе ответ? 4. В автомобильных гонках «Ралли Париж Дакар» участвуют 10 команд, из них 3 команды «Вольво». Сколько информации несет сообщение, что в заезде победила команда «Вольво»? 5. В пруду водится 144 карпа, 36 щук и 120 карасей. Какое количество информации несет сообщение о пойманной рыбе? Вариант 2 1. Объем информации в книге равен байт. Определите, чему равен объем книги в килобайтах. 76

30 2. Письмо, набранное на компьютере, содержит 1000 символов. Определите объем информации в килобайтах, полученный при прочтении письма. 3. Группа спортсменов пришла в бассейн, в котором 8 дорожек для плавания. Сколько информации получила группа, если тренер сообщил, что они поплывут по второй дорожке? 4. В авиакомпании есть 15 самолетов. Сколько информации несет сообщение о том, что вы полетите на самолете ТУ-154, если их в авиакомпании 5? 5. Вероятность первого события равна 0,4; второго 0,1; третьего 0,2; четвертого 0,3. Какое количество информации мы получим после реализации одного из них? Вариант 3 1. Какую часть диска емкостью 210 Мбайт занимают 2 файла, объем информации которых равен 60 байт и 150 Кбайт соответственно? 2. Объем сообщения, написанного 32-символьным алфавитом, составляет 8 байт. Определите, сколько символов содержит сообщение. 3. Каково было количество возможных событий, если после реализации одного из них было получено 4 бита информации? 4. В таксопарке 16 автомобилей «Волга» и 8 автомобилей «Лада». Сколько информации несет сообщение, что вы поедете на автомобиле «Лада»? 5. В аэропорту готовятся к вылету 5 самолетов ИЛ-86, 3 А-310, 7 ТУ- 134 и 2 «Боинг-737». Сколько информации несет сообщение о взлете самолета? Вариант 4 1. Информация записана на диск емкостью 700 Мбайт и занимает 1/8 его часть. Каков объем информации в байтах? 2. Учебное пособие, набранное с помощью компьютера, содержит 75 страниц по 45 строк, в каждой строке по 70 символов. Определите объем информации учебного пособия. 3. Какой объем информации содержит текст, если неопределенность знаний после его прочтения уменьшилась в 16 раз? 4. В пруду водится 100 рыб различных пород, из них 20 карпов. Рыбак поймал карпа. Сколько информации несет данное сообщение? 5. На автостоянке стоят 45 автомобилей «Лада», 32 автомобиля «Нива», 14 автомобилей «Тойота» и 9 автомобилей «Волга». Какое количество информации несет сообщение о выезде автомобиля со стоянки? 77

31 Вариант 5 1. Определите объем информации сообщения в байтах, если его объем в мегабайтах равен 0, Текст объемом 8,3 Кбайт содержит 8400 символов. Какова мощность алфавита? 3. Из колоды карт (56 карт) достали случайным образом одну. Сколько информации при этом было получено? 4. В уборке урожая принимают участие 16 комбайнов, из них 4 «Дон». Сколько информации несет сообщение о том, что комбайн «Дон» убрал больше всего урожая? 5. Поезд состоит из 2 вагонов класса «СВ», 4 «купе», 7 «плацкарт» и 3 общих вагонов. Сколько информации несет сообщение о классе вагона? Вариант 6 1. Сколько килобайтов составляет сообщение, содержащее бит? 2. Сколько символов в сообщении, записанном 8-символьным алфавитом, если оно несет 150 байт информации? 3. Чему равно К, если при угадывании числа из диапазона от 1 до К было получено 9 бит информации? 4. В автогонках «Формула-1» принимают участие 2 команды «Феррари», 3 команды «Тойота», 4 команды «Рено» и 4 команды «Ягуар». Сколько информации несет зрительное сообщение о выходе каждой команды на старт? 5. На конечной остановке транспорта стоит 7 автобусов, следующих по маршруту «22», 6 автобусов «110» маршрута, 3 автобуса «75» маршрута и 4 автобуса «1» маршрута. Сколько информации несет сообщение о выезде автобуса на маршрут? Вариант 7 1. Объем сообщения равен 0,1 Кбайт. Чему равен объем данного сообщения в битах? 2. Текст, набранный на компьютере, состоит из 7 страниц. Каждая страница текста содержит 40 строк. Сколько символов в строке, если весь текст содержит 20 Кбайт информации? 3. В коробке лежат 32 цветных воздушных шара. Сколько информации несет сообщение о том, что из коробки достали зеленый шар? 4. В авиакомпании «Сибирь» к вылету готовится 6 самолетов «Боинг- 747», 8 самолетов ИЛ-86 и 2 самолета ТУ-154. Чему равен объем сообщения «Следующий рейс выполняется на ИЛ-86»? 78

32 5. В автосалоне на данный момент находится 6 автомобилей «Вольво», 5 автомобилей «Опель», 10 автомобилей «Нива» и 9 автомобилей «Лада». Сколько информации несет сообщение о марке автомобиля? Вариант 8 1. Определите объем книги в мегабайтах, если известно, что он равен 25395,2 байт. 2. Информационное сообщение содержит символов. Какова мощность алфавита, с помощью которого записано сообщение, если его объем равен 15 Кбайт? 3. Ваши друзья живут на 7 этаже 8-этажного дома. Сколько информации несет полученное сообщение? 4. В ящике лежат 45 яблок и несколько апельсинов. Сообщение «Из ящика достали апельсин» несет 2 бита информации. Сколько бит информации несет сообщение «Из ящика достали яблоко»? 5. В уборке урожая принимают участие 5 автомобилей ЗИЛ, 4 автомобиля ГАЗ, 2 КамАЗ и 1 «Газель». Сколько информации несет сообщение о поломке автомобиля? Вариант 9 1. Определите объем файла в байтах, записанного на диск емкостью 210 Мбайт, если известно, что он занимает 1/1000 часть диска. 2. Книга, набранная на компьютере, содержит 300 страниц по 50 строк каждая. В каждой строке набрано по 55 символов. Определите объем информации данной книги. 3. Какое количество информации несет сообщение «День рождения Андрея в июне»? 4. На автозаводе работает несколько бригад по сборке автомобилей. Первая бригада за день собирает 2 автомобиля, вторая 4, третья 3, а четвертая 1. Сколько информации в сообщении «Машина собрана первой бригадой»? 5. Сколько информации несет сообщение о вылете самолета, если к вылету готовы 2 самолета авиакомпании «Сибирь», 5 самолетов авиакомпании «Омскавиа» и 3 самолета компании «Аэрофлот»? Вариант На дискету емкостью 1,44 Мбайт записан файл объемом 48 Кбайт. Какую часть дискеты занимает данный файл? 79

33 2. Сообщение, записанное 32-символьным алфавитом, содержит 1500 символов. Какой объем информации в килобайтах несет данное сообщение? 3. Сколько информации несет в себе ответ «Нет» на вопрос: «Вы соблюдаете правила дорожного движения»? 4. В автопарке завода находится 20 автомобилей, из них 5 автомобилей ГАЗ. Сколько информации несет сообщение, что в рейс выходит автомобиль не ГАЗ? 5. На автостоянке находятся 5 белых, 10 зеленых, 15 синих, 8 красных и 2 черных автомобилей. Сколько информации несет сообщение о цвете автомобиля? Вариант Объем текста равен 0,05 Кбайт. Определите объем информации в тексте в битах. 2. Определите объем информации письма в килобайтах, набранного на компьютере, если известно, что оно содержит 2300 символов. 3. Стадион разбит на 16 секторов. Сколько информации несет сообщение тренера спортсменам о том, что разминка будет проходить в секторе номер 4? 4. Сколько бит информации несет сообщение «Пойманная в пруду рыба щука», если всего в пруду 256 карасей, 40 щук и 104 карпа? 5. В таксопарке 10 автомобилей «Волга», 7 автомобилей «Лада» и 8 автомобилей «Вольво». Сколько информации несет сообщение о марке автомобиля? Вариант Определите, чему равен объем информации в книге в мегабайтах, если известно, что он равен байт. 2. Определите, сколько символов содержит сообщение, написанное 128- символьным алфавитом, если известно, что объем его информации равен 0,1 Кбайт. 3. После реализации одного из событий было получено 8 бит информации. Определите количество возможных событий. 4. В аэропорту к вылету готовятся самолеты следующих авиакомпаний: 4 самолета авиакомпании «Сибирь», 2 авиакомпании «Внуковские авиалинии», 6 авиакомпании «Омскавиа». Чему равен объем сообщения «Следующий рейс выполняет самолет авиакомпании «Сибирь»? 5. В цеху по изготовлению деталей для автомобилей работают 3 линии. Производительность каждой линии равна 100 деталей в день. Первая линия выпускает в день 3 бракованных детали, вторая 2, третья 4. 80

34 Сколько бит информации несет сообщение о том, что изготовленная деталь бракованная? Вариант На диск емкостью 210 Мбайт записаны два файла, объем информации на которых равен 40 байт и 170 Кбайт соответственно. Какая часть диска свободна? 2. Определите объем информации методического пособия, набранного на компьютере, если известно, что оно состоит из 45 страниц по 2800 символов на каждой. 3. При угадывании числа из диапазона от 1 до Р было получено 6 бит информации. Чему равно Р? 4. В уборке урожая принимали участие 7 комбайнов «Нива», 6 «Енисей», 4 «Дон», 4 «Доминатор». Сколько информации несет сообщение о поломке комбайна «Нива»? 5. Какое количество информации мы получим после реализации одного из событий, если вероятность первого из них равна 0,5; второго 0,1; третьего 0,4? Вариант Определите, какой объем информации в байтах записан на диске емкостью 700 Мбайт, если 3/4 его части свободно. 2. Определите мощность алфавита, если известно, что текст объемом 0,2 Кбайт содержит 245 символов. 3. После прочтения сообщения неопределенность знаний уменьшилась в 4 раза. Чему равен объем информации в сообщении? 4. В автопарке хлебозавода находятся 6 автомобилей «Газель», 8 автомобилей ГАЗ, 5 автомобилей ЗИЛ, 1 автомобиль КамАЗ. Сколько информации несет сообщение о выходе в рейс автомобиля ЗИЛ? 5. На выставке дорожно-строительной техники демонстрировались три вида продукции. Вероятность реализации первого вида равна 1/3, второго вида 2/4, третьего вида 1/6. Какое количество информации было получено при сообщении о реализации одного из видов продукции? Вариант Объем информации в сообщении равен 0,03 Мбайт. Определите его объем в битах. 2. Сколько символов содержит сообщение, записанное 32-символьным алфавитом, если оно несет 1,46 Кбайт? 81

35 3. Какое количество информации несет сообщение «Настя живет на четвертом этаже 16-этажного дома»? 4. На автостоянке находятся 140 автомобилей. Сколько информации несет сообщение о выезде со стоянки автомобиля «Нива», если всего их было 20? 5. Какое количество информации несет зрительное сообщение о цвете автомобиля, проезжающего через пост ГИБДД, если в среднем за день через пост проезжают 120 белых, 40 желтых, 60 зеленых и 80 черных автомобилей? Раздел 3. ОСНОВЫ ЛОГИКИ И ЛОГИЧЕСКИЕ ОСНОВЫ КОМПЬЮТЕРА 3.1. Алгебра высказываний. Логические выражения и таблицы истинности Конъюнкция (логическое умножение) Объединение двух (или нескольких) высказываний в одно с помощью союза И называется операцией логического умножения или конъюнкцией. Составное высказывание, образованное в результате операции логического умножения (конъюнкции), истинно тогда и только тогда, когда истинны все входящие в него простые высказывания. Обозначение: или. Примеры: F F. Таблица истинности составного высказывания F, которое получено в результате конъюнкции двух простых высказываний и, принимающих значения истина (1) или ложь (0), имеет вид А В F= Дизъюнкция (логическое сложение) Объединение двух (или нескольких) высказываний в одно с помощью союза ИЛИ называется операцией логического сложения или дизъюнкцией. Составное высказывание, образованное в результате операции логического сложения (дизъюнкция), истинно тогда и только тогда, когда истинно хотя бы одно входящее в него простое высказывание. 82

36 Обозначение: «+» или. Примеры: F F. Таблица истинности составного высказывания F, которое получено в результате конъюнкции двух простых высказываний и, принимающих значения истина (1) или ложь (0), имеет вид А В F= Инверсия (логическое отрицание) Присоединение частицы НЕ к высказыванию называется операцией логического отрицания или инверсией. Обозначение отрицания логического высказывания А: А или А. Истинность высказывания F= А для логического высказывания А задается следующей таблицей: А F= А Операция логического следования (импликация) Логическое следование (импликация) образуется соединением двух высказываний в одно с помощью оборота речи «если, то». Логическая операция импликация «если А, то В» обозначается А В. Составное высказывание, образованное с помощью операции логического следования (импликации), ложно тогда и только тогда, когда из истинной предпосылки (первое высказывание) следует ложное высказывание. Таблица истинности составного высказывания F= А В имеет вид А В F= Операция логического равенства (эквивалентность) Логическое равенство (эквивалентность) образуется соединением двух высказываний в одно с помощью оборота речи «тогда и только тогда, когда». 83

37 Логическая операция эквивалентность «А тогда и только тогда, когда В» обозначается А В. Составное высказывание, образованное с помощью операции логического равенства (эквивалентность), ложно тогда и только тогда, когда оба высказывания одновременно либо ложны, либо истинны. Таблица истинности составного высказывания F= А В имеет вид А В F= Операция «исключающая или» или «сложение по mod 2» Логическая операция «исключающая или» обозначается А В. Составное высказывание, образованное с помощью операции «исключающее или» истинно тогда и только тогда, когда одно из высказываний истинно. Таблица истинности составного высказывания F= А В А В имеет вид Теперь на основе полученных логических выражений можно построить из базовых логических элементов схему сложения одноразрядных двоичных чисел. Пример 1. Постройте таблицу истинности логической функции F= ( А В). А В С ( А В) F Пример 2. Постройте таблицу истинности логической функции F= ( А С ) ( ). 84