Методическое пособие "Информация и и информационные технологии"

Департамент образования Вологодской области БОУ СПО ВО «Череповецкий строительный техникум имени А.А.Лепехина» О.А.Белова ИНФОРМАЦИЯ И ИНФОРМАЦИОННЫЕ ПРОЦЕССЫ Методические рекомендации  для обучающихся и студентов по дисциплине «Информатика и ИКТ» Череповец 2011г. ­ 2 ­ Рассмотрено на заседании методической комиссии Протокол №____________________от_______2011 г. Разработали:  О.А.Белова, второй квалификационной категории БОУ СПО ВО «Череповецкий строительный техникум им.А.А.Лепехина».   информатики     преподаватель Рецензенты: Р.П.Швец,   преподаватель   высшей   квалификационной категории   БОУ   СПО   ВО   «Череповецкий   строительный   техникум им.А.А.Лепехина». А.А.Материкова,   преподаватель   первой   квалификационной категории   ФГОУ   СПО   «Череповецкий   лесомеханический   техникум им. В. П. Чкалова». ­ 3 ­ ОГЛАВЛЕНИЕ Введение Информация. Измерение количества информации 1. Общие сведения 2. Задачи    о   количестве информации с   выбором  ответа и рекомендациями по   решению 3. Задачи    о   количестве информации с   выбором  ответа и  решением 4. Задачи о количестве информации с выбором ответа Системы счисления 1. Виды систем счисления 2. Перевод из одной системы счисления в другую 3. Двоичная арифметика 4. Рекомендации по решению 5. Задачи Алгебра логики 1. Логические операции 2. Логические законы 3. Примеры тестовых заданий ЕГЭ с решением 4. Задачи с выбором ответа Список литературы 4 стр. 5 стр. 7 стр. 12 стр. 15 стр. 18 стр. 19 стр. 23 стр. 26 стр. 36 стр. 39 стр. 43 стр. 44 стр. 48 стр. 50 стр. ­ 4 ­ ВВЕДЕНИЕ Получение   и   преобразование   информации   является   необходимым условием жизнедеятельности любого организма. В наиболее общем случае под   «информацией»   понимаются   сведения     которые воспринимаются   живым   существом   или   устройством   и   сообщаются (получаются,   передаются,   преобразуются,   сжимаются,   разжимаются, теряются,   находятся,   регистрируются)   с   помощью   знаков.   Слово «информация» происходит от латинского слова information, что в переводе означает сведения, разъяснение, ознакомление. (данные), Для   обмена   информацией  с   другими   людьми  человек   использует естественные   языки  (русский,   английский,   китайский   и   др.),   то   есть информация   представляется  с   помощью   естественных   языков.   В   основе языка   лежит  алфавит,  то  есть  набор  символов  (знаков),   которые  человек различает по их начертанию. Язык – это определенная система символов и правил представления информации. Наряду   с   естественными   языками   были   разработаны  формальные языки (системы счисления, язык алгебры, языки программирования и др.).  Для   записи   информации   о   количестве   информации   о   количестве объектов используются числа.  Числа записываются с использованием особых знаковых систем, которые называются системами счисления. В   данном   учебно­методическом   пособии   рассмотрены   следующие основные   вопросы   темы   «Информация   и   информационные   процессы»: «Информация. Измерение количества информации», «Системы счисления», «Алгебра   логики».   Каждый   раздел   содержит   краткий   теоретический материал   по   данной   теме,   примеры   решения   задач   с   подробными методическими   указаниями   по   их   решению,   задачи   для   самостоятельного решения. Данное   учебно­методическое   пособие   может   выполнять   функции руководства   по   изучению   данной   темы,   как   на   занятиях,   так   и   для самостоятельной   работы   учащихся   и   студентов.   Пособие   выступает средством   обучения,   с   помощью   которого   осуществляется   организация образовательного процесса. ­ 5 ­ ИНФОРМАЦИЯ.  ИЗМЕРЕНИЕ   КОЛИЧЕСТВА ИНФОРМАЦИИ 1. ОБЩИЕ СВЕДЕНИЯ В теории информации количеством информации называют числовую характеристику сигнала, которая не зависит от его формы и содержания и характеризует   неопределенность,   которая   исчезает   после   получения сообщения в виде данного сигнала. В этом случае количество информации зависит от вероятности получения сообщения о том или ином событии. Для   абсолютно   достоверного   события   (событие   обязательно произойдет,  поэтому  его вероятность   равна 1)  количество  информации  в сообщении   о   нем   равно   0.   Чем   невероятнее   событие,   тем   большее  количество информации несет сообщение о нем. Лишь при равновероятных ответах ответ “да” или “нет” несет один бит информации. В   качестве   единицы   информации   принято   такое   количество информации, которое содержит сообщение, уменьшающее неопределённость знаний в два раза. Такая единица названа бит.               Бит – наименьшая «порция» памяти, необходимую для хранения одного из двух знаков 0 или 1, используемых для внутримашинного представления данных и команд.   которого можно представить один символ. Информационный   объем   сообщения  (информационная   емкость сообщения)   ­   количество   информации   в   сообщении,   измеренное   в   битах, байтах или производных единицах (Кбайтах, Мбайтах и т.д.). Для решения задач на измерение количества информации  целесообразно  выписать следующие «подсказки»: 1. Степени двойки от нулевой до десятой: ­ 6 ­ 1. 2. 3. 4. Бит ­ двоичный знак двоичного алфавита {0, 1}. Бит­ минимальная единица измерения информации. Байт ­ единица количества информации в системе СИ. Байт   ­   это   восьмиразрядный   двоичный   код,   с   помощью 2. Общая формула кодирования: где m — количество символов (знаков) в алфавите, с помощью которого  кодируют; k — длина кода, т.е. число знакомест, которое используется для  кодирования одного символа исходного сообщения; N — максимальное количество разных символов исходного сообщения,  которое можно закодировать с помощью алфавита из m знаков при  постоянной длине кода в k знакомест. 3.  Формула Хартли. I = log2 N   или   2I = N,  где       N ­ количество равновероятных событий (число возможных выборов),              I ­ количество информации.  4.  Модифицированная формула Хартли. и формула имеет вид I = log2 (1/p) = ­ log2 p где         p  равновероятных событий. ­   вероятность   наступления   каждого   из  N  возможных 5.  Формула Шеннона. H = S pi hi = ­ S pi log2 pi  где       pi ­ вероятность появления в сообщении i­го символа алфавита;              hi   =   log2  1/pi  =   ­   log2  pi  ­   количество   собственной   информации, переносимой одним символом;             Н ­ среднее значением количества информации. 6. Единицы измерения информации в вычислительной технике 1 бит 1 байт   = 8 бит      1 Кбайт (килобайт) = 210 байт = 1024 байт ~ 1 тысяча байт ­ 7 ­ 1 Мбайт (мегабайт) = 210 Кбайт = 220 байт ~ 1 миллион байт 1 Гбайт (гигабайт) = 210 Мбайт = 230 байт ~ 1 миллиард байт 2. ЗАДАЧИ    О   КОЛИЧЕСТВЕ  ИНФОРМАЦИИ С   ВЫБОРОМ  ОТВЕТА    И РЕКОМЕНДАЦИЯМИ   ПО   РЕШЕНИЮ Задача 1 Считая, что каждый символ кодируется 16 битами, оцените информационный объем сообщения в кодировке Unicod: Привычка свыше нам дана: Замена счастию она. 1. 44 бита 2. 704 бита 3. 44 байта 4. 704 байта Рекомендации по решению задачи. 1. 16­битная кодировка означает, что 1 символ кодируется 2 байтами. 2.   Считем   количество   символов   в   сообщении,  обязательно  считая   все пробелы и знаки препинания. Количество символов — 44. 3. «Переводим» количество символов (44) в байты и биты: 44•2 байта = 88 байт = 88•8 бит = 704 бит. 4. Правильный вариант ответа — 2. Задача 2 В   кодировке  Unicode  на  каждый   символ  отводится  2 байта.   Определите информационный объем слова из 24 символов в этой кодировке. 1. 2. 3. 4. 384 бита 192 бита 256 бит 48 бит Рекомендации по решению задачи. 1. То, что один символ кодируется 2 байтами, означает, что используется 16­ битная кодировка. ­ 8 ­ 2.   «Переводим»   количество   символов   (24)   в   биты   и   байты   (в   данном варианте достаточно переводить только в биты, поскольку все ответы даны в битах.): 24•2 байт = 48 байт = 48•8 бит = 384 бит (или 24•16 бит = 384 бит). 3. Правильный вариант ответа — 1. Задача 3 Автоматическое устройство осуществило перекодировку информационного сообщения на русском языке, первоначально записанного в 16­битном коде Unicode,   в  8­битную  кодировку  КОИ­8.   При   этом   информационное сообщение уменьшилось на 480 бит. Какова длина сообщения в символах? 1. 2. 3. 4. 30 60 120 480 Рекомендации по решению задачи. 1. Суть многословной формулировки задания: кодировка поменялась с 16­ битной   (1   символ —   2   байта)   на   8­битную   (1   символ —   1   байт),   память уменьшилась на 480 бит (60 байт). 2. Составляем и решаем математическое уравнение: пусть x — количество символов в исходном сообщении. Тогда 16x — 8x = 480. Следовательно x = 60. Можно проще: 2x — 1x= 60. Отсюда x = 60. 3. Правильный вариант ответа — 2. Задача 4 Световое табло состоит из лампочек. Каждая лампочка может находиться в одном  из   трех   состояний  («включено»,  «выключено», «мигает»).   Какое наименьшее количество лампочек должно находиться на табло, чтобы с его помощью можно было передать 18 различных сигналов? 1. 2. 3. 4. 6 5 4 3 Рекомендации по решению задачи. 1. Используем формулу кодирования, при этом m = 3, N = 18, k­ ?. 2.  Поскольку  N≤m   в степени  k,  т.  е.  18≤3  в степени  k,  то  k = 3, 4, 5... Минимальным будет k = 3. ­ 9 ­ 3. Правильный вариант ответа — 4.  Задача 5 Одна   ячейка   памяти   «троичной   ЭВМ»   (компьютера,   основанного   на использовании троичной системы счисления) может принимать одно из трех возможных  состояний.  Для  хранения  некоторой  величины  отвели 5  ячеек памяти. Сколько различных значений может принимать эта величина? 1. 2. 3. 4. 32 125 243 256 Рекомендации по решению задачи. 1. Используем формулу кодирования, при этом m=3, k=5, N — ? 2. Поскольку N = m в степени k, то N = 3 в степени 5 = 243. 3. Правильный вариант ответа — 3.  Задача 6 В   велокроссе   участвуют  119  спортсменов.   Специальное   устройство регистрирует прохождение каждым из участников промежуточного финиша, записывая его номер с использованием минимального возможного количества бит, одинакового для каждого спортсмена. Каков информационный объем сообщения, записанного устройством, после того как промежуточный финиш прошли 70 велосипедистов? 1. 2. 3. 4. 70 бит 70 байт 490 бит 119 байт Рекомендации по решению задачи. 1. Суть многословной формулировки задания:  Используется   двоичное   кодирование   (m=2).   Надо   закодировать 119 чисел (N = 119). Длина кода (k) постоянна.  Число   кодируется   k   битами.   Сколько   места   потребует кодирование 70 чисел? 2. Нужно найти k. Используем формулу кодирования, при этом m = 2, N = 119,   k —   ?   По   таблице   степеней   двойки   определяемставляем   и   решаем математическое   уравнение:   пусть   x —   количество   символов   в   исходном сообщении. Тогда 16x — 8x = 480. Следовательно x = 60. Можно проще: 2x — 1x= 60. Отсюда x = 60. 3. Правильный вариант ответа — 2. ­ 10 ­ Задача 7 Укажите   минимальный   объем   памяти   (в   килобайтах),   достаточный   для хранения   любого   растрового   изображения   размером   32Х32   пикселя,   если известно, что в изображении используется палитра из  палитру хранить не нужно. 1. 2. 3. 4. 1 1024 4096 4  цветов. Саму Рекомендации по решению задачи. 1. Фраза «используется палитра из   цветов» означает, в соответствии с формулой кодирования, что длина кода k=32 бита. То есть каждый пиксель кодируется 32 битами. 2. Поскольку на экзамене по информатике пользоваться калькуляторами не разрешается, то в вычислениях лучше переходить к степеням двойки.  Так, в битах объем памяти потребуется такой: 32•32 (пикселей) •32 (бит) = (2²•2³ ) •(2²•2³ )•(2²•2³ )=2 в 15 степени бит. 3. Переходим от бит к килобайтам: 1 Кбайт = 2 в 10 степени байт = 2 в 13 степени  бит.  Поэтому 2  в 15  степени  бит = 2  в 15  степени  бит/2  в 13 степени бит = 2² Кбайт = 4 Кбайт. 4. Правильный вариант ответа — 4. Задача 8 Для хранения растрового изображения размером 64Х64 пикселя отвели 512 байтов памяти. Каково максимально возможное число цветов в палитре? 1. 2. 3. 4. 2 16 256 1024 Рекомендации по решению задачи. 1.   Определяем   общее   количество   точек:   64•64   =   2  в   6   степени   •   2   в 6 степени = 2 в 12 степени (точек — пикселей). 2. Переводим байты памяти в биты, поскольку количество цветов (N) зависит от длины кода (k), а k задается в битах: 512 байт = 2 в 9 степени байт = 2 в 9 степени • 2³ бит = 2 в 12 степени бит. 3. Определяем, сколько бит приходится на 1 пиксель: k= 2 в 12 степени/2 в 12 степени = 1. ­ 11 ­ 4.   По   формуле   кодирования   определяем   максимально   возможное   число цветов: N= 2¹ = 2. 5. Правильный вариант ответа — 1. Задача 9 Для   кодирования   цвета   фона   страницы   Интернета   используется   атрибут bgcolor=#XXXXXX,   где   задаются   шестнадцатиричные   значения интенсивности   цветовых   компонент   в   24­битной   RGB­модели   следующим образом: XX — красный XX — зеленый XX — синий Какой цвет будет у страницы, заданной тегом ? белый 1. 2. фиолетовый 3. 4. зеленый черный Рекомендации по решению задачи. 1.   Суть   RGB­модели   кодирования   в   том,   что   указывается   интенсивность (яркость)   красного,   зеленого   и   синего   цветов.   Указываться   она   может шестнадцатиричными числами от 0 до FF или десятичными числами от 0 до 255. Важно помнить:      если интенсивность всех цветов нулевая (#000000 или 0.0.0), то это соответствует черному цвету; если   интенсивность  всех  цветов  максимальная  (#FFFFFF   или 255.255.255), то это соответствует белому цвету; если   интенсивность  всех  цветов  одинакова,   то   это   соответствует серому    #A5A5A5   или   165.165.165 — среднесерый; #404040 или 64.64.64 — темно­серый); если выражен  какой­то один цвет,  а остальные —  нули,  то это и будет  оттенок  данного   цвета.   Например,   #DD0000  или  224.0.0 — красный, #00EE00 или 0.238.0 — зеленый, #0000FF или 0.0.255 — синий; в остальных случаях действуем «методом исключения». цвету   (например, 2. В данном случае: RED — GREEN —     ­ 12 ­ EE 00 BLUE — EE Т.е.   у   зеленого   цвета   нулевая   интенсивность,   у   красного   и   синего — интенсивность, близкая к максимальной. 3. Анализируя предложенные варианты ответов, это НЕ  белый, НЕ черный, НЕ зеленый цвета, т.е фиолетовый. 4. Правильный вариант ответа — 2. ­ 13 ­ 3. ЗАДАЧИ О КОЛИЧЕСТВЕ ИНФОРМАЦИИ  С ВЫБОРОМ ОТВЕТА И РЕШЕНИЕМ Задача   1.  Алфавит   племени   содержит   всего   8   букв.   Какое   количество информации несет одна буква этого алфавита? 1) 8 бит 2) 1 байт 3) 3 бита 4) 2 бита     Решение. Мощность алфавита племени – 8 букв. Применим формулу 2х = N, где N – мощность алфавита, х – количество бит на один символ алфавита. 2х =8, х=3 бит, что соответствует варианту ответа №3. Ответ: 3. Задание 2. Если вариант теста в среднем имеет объем 20 килобайт (на каждой странице теста   40   строк   по   64   символа   в   строке,   1   символ   занимает   8   бит),   то количество страниц в тесте равно: 4) 8 3) 4 2) 16 1) 10   Решение. Известен   информационный   объем   теста   и   информационный   «вес»   одного символа в нем. Найдем объем одной страницы: 40*64*8 бит.   20 Кбайт = 20*1024   байт   =   20*1024*8   бит.   Найдем   количество   страниц:   20*1024*8/ (40*64*8) = 8 (стр.) (Ответ № 4) Ответ: 4. Задание 3. В пяти килобайтах: 3) 500 байт 4) 5000 бит 2) 5120 байт 1) 5000 байт    Решение. 5   Кб   =   5*1024   байт   =   5120   байт,   что   соответствует   ответу   №2. Ответ: 2 Задание 4 Сколько байт в 32 Гбайт? 1) 235  Решение. 4) 222 2) 16*220 3) 224 ­ 14 ­ 32Гб = 25 Гб = 25*210 Мб = 25*210 *210 Кб =25*210 *210*210 байт  = 235 байт, что соответствует №1. Ответ: 1. ответу     3) 3 4) 4 2) 2 Задание 5. Считая, что один  символ кодируется  одним  байтом, подсчитать  в байтах количество   информации,   содержащееся   в   фразе:   “Терпение   и   труд   все перетрут.” Решение. В фразе  29  символов (включая точку и пробелы), 1 символ несет  1  байт информации, значит фраза содержит 29 байт. Ответ: 29. Задание 6. (Задание А4  демоверсии 2004 г.) Получено   сообщение,   информационный   объём   которого   равен   32   битам. Чему равен этот объём в байтах? 1) 5  Решение.  1 байт = 8 бит, следовательно, 32/8=4, что соответствует ответу №4. Ответ: 4. Задание 7. (Задание А2  демоверсии 2004 г.) Считая,   что   каждый   символ   кодируется   одним   байтом,   оцените информационный объём предложения: «Мой дядя самых   честных правил, Когда не в шутку занемог, Он уважать себя заставил И лучше выдумать не мог.» 1) 108 бит Решение. Предложенная   строка   содержит   ровно   108   символов,   включая   кавычки, пробелы   и   знаки   препинания.   При   кодировании   каждого   символа   одним байтом   на   символ   будет   приходиться   по   8   бит,   поэтому   объём   этого предложения   составит   108   байт   или   108х8=864   бит,   что   соответствует ответу №2. Ответ: 2. Задание 8. (Задание А3  демоверсии 2004 г.) Шахматная   доска   состоит   из   64   полей:   8   столбцов   и   8   строк.   Какое минимальное   количество   бит   потребуется   для   кодирования   координат одного шахматного поля? 4) 864 килобайт 3) 108 килобайт 2) 864 бит 1) 4 2) 5 3) 6 4) 7 ­ 15 ­ Решение. Для   того,   чтобы   различить   64   клетки   шахматного   поля   потребуются   64 значения двоичного кода. Поскольку 64=26,  то в двоичном коде потребуется шесть разрядов. Верный ответ№3. Ответ: 3. 2) 100 3) 125 4) 1000 Задание 9. Каждое показание счётчика, фиксируемое в памяти компьютера, занимает 10 бит. Записано 100 показаний этого датчика. Каков информационный объём снятых значений в байтах? 1) 10 Решение.  10   бит*100=   1000   бит,   1   байт   =   8   бит,   следовательно:   1000/8=125   байт. Значит, верный ответ №3. Ответ: 3. Задание 10. В коробке 32  карандаша,  все карандаши  разного  цвета.  Наугад вытащили красный. Какое количество информации при этом было получено? Решение. Так как вытаскивание карандаша любого цвета из имеющихся в коробке 32 карандашей является равновероятным, то число возможных событий равно 32. N = 32, I = ? N = 2I, 32 = 25, I = 5 бит. Ответ: 5 бит. ­ 16 ­ 4. ЗАДАЧИ О КОЛИЧЕСТВЕ ИНФОРМАЦИИ С ВЫБОРОМ ОТВЕТА  1. Наибольшее натуральное число, кодируемое 8 битами:  127;  255;  256;  512;  99999999. 2. Число байт, необходимое для записи числа 282:  5 ;  10;  11;  82;  256. 3. Число байт, необходимое для записи числа 244:  5;   6;  11;   44;   88. 4. Число байт, необходимое для записи числа 814:  6; 10; 42; 112; 192. 5. Для хранения области экрана монитора размером 256х128 точек выделено 32 Кбайт оперативной памяти. Для раскраски точек максимально допустимо использовать цветов:  16;  4;  512;  256;  218. 6.   Если   для   хранения   области   экрана   монитора   размером   512х256   точек выделено   64   Кбайта   оперативной   памяти,   то   максимальное   количество цветов, которое допустимо использовать для раскраски точек, равно:  8;  4;  256;  16;  2. 7. Емкость одного условного печатного листа равна приблизительно 32Кбайт (1 символ занимает 8 бит), скорость печати ­ 64 символа в секунду. Без учета смены бумаги для распечатки текста одной газеты (2 усл. п.л.) на матричном принтере потребуется минут (ответ округлить до целого числа):  256; 9; 17; 12; 1024. 8. Если емкость одного условного печатного листа равна приблизительно 96 Кбайтам, а 1 символ занимает 8 бит, то для распечатки текста одной газеты (4   усл.   п.л.)   на   лазерном   принтере   (скорость   печати   ­   512   символов   в секунду) без учета смены бумаги потребуется минут:  13; 15; 17; 19; 21. (ответ округлен до целого числа) ­ 17 ­ 9. Если досье на преступников занимают 45 мегабайт и каждое из них имеет объем 12 страниц ( 48 строк по 64 символа в каждой, 1 символ занимает 8 бит), то число досье равно:  1280; 3840; 1250; 1560; 1024. 10. В пяти килобайтах:  5000 байт; 5120 байт; 500 байт; 5000 бит; 5120 бит. 11. Количество чисел, которое можно закодировать нулями и единицами в 10 позициях, равно: 1000; 1024; 10; 256; 512.   12. Даны системы счисления: с основанием 2, 8, 10, 16. Запись вида 100 1) отсутствует в двоичной; 2) существует во всех перечисленных; 3) отсутствует в десятичной; 4) отсутствует в восьмеричной; 5) отсутствует в 16­ной. 13. Если вариант  текста в среднем  имеет  объем 20  килобайт  (на каждой странице текста 40 строк по 64 символа в каждой , 1 символ занимает 8 бит), то количество страниц в тексте равно  10; 16; 8; 4; 12. 14.   Сведения   о   сотруднике   хранятся   в   виде   строки   из   2048   символов. Сведения   обо   всех   8192   сотрудниках   можно   разместить   на   минимальном числе дискет емкостью 1.2М, равном:  14; 12; 10; 8; 16. 15. Если информационная емкость человеческой яйцеклетки приблизительно равна   233   бит,   то   минимальное   количество   винчестеров   (по   20   Мб),   на котором можно уместить генетическую информацию одного человека, равно: 2; 20; 33; 52; 51. 16. Максимальное количество страниц книги (32 строки по 64 символа, 1 символ занимает 8 бит), которое поместится в файле объемом 640 Кбайт:  320; 640; 160; 540; 1280. 17. Наибольшее натуральное число, кодируемое 16 битами:  255; 255; 32768; 65535; 99999999. ­ 18 ­ 18. Если область экрана имеет размеры 512х128 точек и каждая точка может иметь   один   из   256   оттенков,   то   минимальный   объем   памяти   (Кбайт), необходимый для хранения этой области, равен 32; 64; 74; 128; 256. 19. Число байт, необходимое для записи выражения 84*48:  3; 4; 8; 12; 16. 20. Средняя скорость чтения учащихся 9­11 классов составляет 160 слов в минуту (одно слово в среднем ­ 6 символов). За четыре часа непрерывного чтения ученик успеет переработать (Кбайт): 9; 25; 225; 256; 4096. 21. Для записи выражения VELE, VIDE, VICI необходимо (бит):  14; 16; 72; 88; 128. 22.   Сколько   целых   чисел   со   знаком   можно   записать   в   1   байт: 1024; 256; 255; 127; 128 23. Наибольшее целое число при представлении чисел со знаком, кодируемое 1 байтом: 128; 256; 127; 255; 510   24. Количество различных символов, закодированных байтами в сообщении 1110010100111100011111011110010101111101, равно: 3; 4; 5; 1; 2.   25.   Количество   различных   символов,   закодированных   полубайтами   в сообщении равно 2; 4; 5; 1; 3. 10111000101110001001,     26.   Количество   бит   информации   в   сообщении   "выбранный   из   урны   шар является   черным"   равно   (в   урне   8   черных   и   56   белых   шаров) 2; 4; 3; 5; 1. 27. Количество бит информации в сообщении "пойманная в пруду рыба ­ карп"   (всего   в   пруду   256   карасей,   44   щуки,   100   карпов)   равно 2; 4; 3; 5; 1.   Количество 28. сообщении «Миша   на   олимпиаде   по   информатике   занял   одно   из   16   мест» равно 3; 5; 4; 2; 424. информации бит       в   ­ 19 ­ 29.   Наибольшее   целое   решение   X   неравенства 4х+4   бит   >   8x­3   Кбайт   равно 2; 4; 3; 5; 9. 30. Объем текстовой информации в сообщении на 40 страницах (на странице   40 равен 1 Мбайт; 120 Кбайт; 12 Кбайт; 125 Кбайт; 0,1 Мбайт. символов строке) строк 80 и в             31. Максимальное количество книг (каждая объемом 200 страниц, на каждой странице   60   строк,   80   символов   в   строке),   полностью   размещенных   на лазерном   равно диске 655; 6005; 63; 10; 6522. емкостью     Мбайт, 600     32.   Сообщение   "школьники   изучали   Basic"   несет   4   бита   информации. Вероятность изучения Pascal в 8 раз меньше. Количество бит информации в сообщении равно 2; 3; 6; 8; 7. "школьники изучали Pascal"         СИСТЕМЫ СЧИСЛЕНИЯ 1. ВИДЫ СИСТЕМ СЧИСЛЕНИЯ Система счисления ­ это способ записи чисел с помощью заданного набора специальных символов.  Существуют позиционные и непозиционные системы счисления.  В  непозиционных   системах  счисления   вес   цифры   (то   есть   тот вклад, который она вносит в значение числа)  не зависит  от ее позиции в записи числа.  Так, в римской системе счисления в числе ХХХII (тридцать два) вес цифры Х в любой позиции равен просто десяти. В позиционных системах счисления  вес  каждой цифры  изменяется  в зависимости  от  ее положения (позиции) в последовательности цифр, изображающих число.  Например,  в   числе  357,6   первый   символ   3  означает  3  сотни;   второй символ 5 означает 5 десятков, третий символ   7 означает 7 единиц, а четвертый символ  6 означает 6 десятых долей единицы.  Любая   позиционная   система   счисления   характеризуется   своим основанием. Основание   позиционной   системы   счисления  ­   это   количество различных символов, используемых для изображения чисел в данной системе счисления.  ­ 20 ­ В   настоящее   время,   кроме   хорошо   известной   нам   десятичной системы   счисления   в   вычислительной   технике   используются   двоичная, восьмеричная, и шестнадцатеричная системы счисления. Все применяемые в настоящее время системы счисления позиционные. В  десятичной   системе  счисления   для   изображения   чисел используются 10 символов: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Поэтому основанием десятичной системы счисления является число 10. В двоичной системе счисления для изображения чисел используется 2 символа: 0,  1. Поэтому основанием двоичной системы счисления является число 2. В  восьмеричной   системе  счисления   для   изображения   чисел используются   8   символов:  0,   1,   2,   3,   4,   5,   6,   7.  Поэтому   основанием восьмеричной системы счисления является число 8. В  шестнадцатеричной системе  счисления для изображения чисел используются 16 символов: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, А, B, C, D, E, F, где: А = 10;   B = 11;  C = 12;  D = 13;  E = 14;  F = 15. Поэтому   основанием   шестнадцатеричной   системы   счисления является число 16.   ­ 21 ­ 2. ПЕРЕВОД ИЗ ОДНОЙ СИСТЕМ     СЧИСЛЕНИЯ В ДРУГУЮ Перевод целого числа из десятичной системы счисления в любую другую систему счисления. При   переводе   целого   числа   из   десятичной   системы   счисления   в любую другую систему счисления, нужно это число последовательно делить на основание новой системы  счисления так, чтобы в остатках от деления были   только   символы   новой   системы   счисления.   Число   в   новой   системе счисления   записывается   как   последовательность   остатков   от   деления, записанных в обратном порядке, начиная с последнего. Например,   переведём   число   75   из   десятичной   системы   в   двоичную, восьмеричную и шестнадцатеричную системы счисления:                                           Таким образом, число 7510 = 10010112 = 1138 = 4В16  Перевод дробной части числа из десятичной системы счисления в любую другую систему счисления. ­ 22 ­ При переводе дробной части числа из десятичной системы счисления в   любую   другую   систему   счисления,   нужно   дробную   часть   числа последовательно умножать на основание новой системы счисления. Дробная часть числа в новой системе счисления записывается как последовательность целых   частей   от   умножения,   записанных   в   прямом   порядке,   начиная   с первого. Например,   переведём   дробное   число   0,   96   из   десятичной   системы   в двоичную, восьмеричную и шестнадцатеричную системы счисления:  Таким образом, число  0,9610 = 0,1111012 = 0,753418 = 0.F5C28F16                                              Перевод чисел из любой системы счисления в десятичную систему счисления. При   переводе   числа   из   любой   системы   счисления   в   десятичную систему   счисления   нужно   каждый   символ   этого   числа   умножить   на основание   системы   счисления,   в   которой   записано   это   число,   в   степени соответствующей   положению   символа  в   записи   числа   и  все   произведения сложить.   Например: ­ 23 ­ 1)   переведём   число   101100,10112   из   двоичной   системы   счисления   в десятичную систему счисления: 101100, 1012 = 1*25 + 0*24 + 1*23 + 1*22 + 0*21 + 0*20  + 1*2­1 + 0*2­2 + 1*2­3  =  = 32 + 0 + 8 + 4 + 0 + 0 + 0,5 + 0 + 0,125 = 44, 62510   2)   переведём   число   375,6248   из   восьмеричной   системы   счисления   в десятичную систему счисления: 375, 6248  = 3*82 + 7*81 + 5*80 + 6*8­1 + 2*8­2 + 4*8­3 = = 192 + 56 + 5 + 0,75 + 0,03125 + 0,00781835938 = 253, 7890683593810   3) переведём число ACF,5D16  из шестнадцатеричной системы счисления в десятичную систему счисления: ACF,   5D16   =   10*162  +   12*161  +   15*160  +   5*16­1  +   13*16­2  = = 256 + 192 + 15 + 0,3125 + 0,050775 = 463, 36327510   Перевод чисел из двоичной системы счисления в восьмеричную систему счисления. При переводе числа из двоичной системы счисления в восьмеричную систему счисления, нужно это число влево и вправо от запятой разбить на триады символов (группы по три символа) и каждую триаду записать в виде символа восьмеричной системы счисления. В том случае, если крайняя левая или   правая   триады   получаются   неполными,   нужно   в   этих   триадах   слева добавить недостающее количество до полной триады нулей. Например,  переведём   число   1101111100,111001112  в   восьмеричную систему счисления.                                                              Перевод чисел из восьмеричной системы счисления в двоичную систему счисления. При переводе числа из восьмеричной системы счисления в двоичную систему   счисления,   нужно   каждый   символ   этого   числа   записать   в   виде триады   символов   двоичной   системы   счисления.   В   том   случае,   если   при записи очередного символа триадой, триада получается неполной, нужно в ­ 24 ­ этой   триаде   слева   добавить   недостающее   количество   до   полной   триады нулей. Например, переведём число 6374, 258  в двоичную систему счисления.                                                                                                             Перевод чисел из двоичной системы счисления в шестнадцатеричную систему счисления. При   переводе   числа   из   двоичной   системы   счисления   в шестнадцатеричную систему счисления, нужно это число влево и вправо от запятой разбить на  тетрады  символов (группы по три четыре) и каждую тетраду записать в виде символа шестнадцатеричной системы счисления. В том случае, если крайняя левая или правая тетрада получаются неполными, нужно в этих тетрадах слева добавить недостающее количество до полной тетрады нулей. Например, переведём число 1101111100, 111001112 в шестнадцатеричную систему счисления.                                                                              Перевод чисел из шестнадцатеричной системы счисления в двоичную систему счисления. При   переводе   числа   из   шестнадцатеричной   системы   счисления   в двоичную систему счисления, нужно каждый символ этого числа записать в виде тетрады символов двоичной системы счисления. В том случае, если при записи очередного символа тетрадой, тетрада получается неполной, нужно в этой тетраде слева добавить недостающее  количество  до  полной тетрады нулей. Например, переведём число АЕС2, 3В16  в двоичную систему счисления. ­ 25 ­ 3. ДВОИЧНАЯ АРИФМЕТИКА Сложение чисел  в двоичной системе счисления. При   сложении   чисел   в   двоичной   системе   счисления,   нужно использовать следующую таблицу сложения:                                              1 + 0 = 1                                              0 + 1 = 1                                              0 + 0 = 0                                              1 + 1 = 10 Например, сложим числа 11011112  и 10111012                                          Умножение чисел в двоичной системе счисления.    ­ 26 ­ При умножении чисел в двоичной системе счисления, нужно использовать следующую таблицу умножения:                                              1 * 0 = 0                                              0 * 1 = 0                                              0 * 0 = 0                                              1 * 1 = 1       Например, перемножим числа 111112    и    1012                                                Вычитание чисел  в двоичной системе счисления. Вычитание   чисел   в   двоичной   системе   счисления   заменяется вычитаемого.   Вычитаемое   при   этом сложением   уменьшаемого   и   записывается в обратном коде.  Обратный код получается из прямого кода путём замены всех нулей на 1, а всех единиц на 0. Процесс вычитания чисел в двоичной системе счисления происходит в два этапа. ­ 27 ­ Первый   этап:  выравнивается   количество   разрядов   у   уменьшаемого   и вычитаемого   и   добавляются   знаковые   разряды.   В   знаковом   разряде   у положительного   числа   записывается   1,   а   в   знаковом   разряде   у отрицательного числа записывается 0. Второй этап: вычитаемое записывается в обратном коде. Для этого все нули у вычитаемого заменяются на 1 а все единицы у вычитаемого заменяются на 0. Затем происходит сложение уменьшаемого, записанного  в прямом коде с вычитаемым, записанным в обратном коде.  На этом же этапе происходит анализ полученного ответа. Например,  вычтем   из   большего   числа   меньшее   число:     110111101   – 10110112                              Анализ   ответа   говорит   о   том,  что   ответ   положителен   (так   как   в знаковом разряде стоит 0), и поэтому он записан в прямом коде.  Таким образом, ответ:  1011000102                                Вычтем из меньшего числа большее число:      110111 – 11101101   ­ 28 ­ Анализ   ответа   говорит   о   том,   что   ответ   отрицателен   (так   как   в знаковом разряде стоит 1), и поэтому он записан пока что в обратном коде. Для получения  окончательного ответа нужно  преобразовать  его в прямой код, то есть заменить все нули на 1 а все единицы на 0. Таким образом, окончательный ответ:  ­ 101101102  ­ 29 ­ 4. РЕКОМЕНДАЦИИ ПО РЕШЕНИЮ ЗАДАЧ Все задачи можно разбить на следующие классы:  1. Задачи на перевод из системы счисления по основанию 10 в любую систему счисления.  2. Задачи на перевод из любой системы счисления в десятичную.  3. Задачи на теоретические знания темы.  4. Задачи на перевод чисел в системах счисления 2, 4, 8, 16.  5. Задачи на совершение арифметических действий.  Задачи на перевод из десятичной системы счисления в любую систему счисления По формулировкам все задачи, относящиеся к данному типу, бывают следующими:  –  как представлено число X10 в системе счисления Y?  –   сколько   нулей   (единиц   …)   в   двоичной   (четверичной, восьмеричной…) записи десятичного числа Х.  Укажем основные этапы решения подобных задач:  1. В числе выделяем отдельно дробную и целую часть.  2. Переводим целую часть в нужную систему счисления.  3. Переводим дробную часть в нужную систему счисления. 4. Выполняем   с   полученным   числом   необходимые   действия (сравниваем с оригинальными числами в ответе, считаем нули)  ­ 30 ­ Примеры тестовых заданий из ЕГЭ А4 (2005   год).  Как   представлено   число   8310  в   двоичной   системе счисления?  Решение  83=64+19=64+16+2+1=26+24+21+20=1×26+0×25+1×24+0×23+0×22+1×21 +1×20=10100112 Ответ: 3).  A4   (2006   год).  Количество   значащих   нулей   в   двоичной   записи десятичного числа 126 равно Решение 126=64+62=64+32+30=64+32+16+14=64+32+16+8+6=64+32+16+8+4 +2=26+25+24+23+22+21 Из развернутой записи числа видим, что нет только 20. Значит всего 0 в числе буден 1.  Ответ: 1).  A4 (2007 год). Сколько единиц в двоичной записи числа 195?  1) 5 2) 2 3) 3 4) 4 Решение 195=128+67=128+64+3=128+64+2+1 Из развернутой записи видно, что в записи числа будут всего четыре единицы.  Ответ: 4).  A4 (2008 год). Сколько единиц в двоичной записи десятичного числа 194,5?  1) 5 2) 6 3) 3 4) 4 Решение  194,5=128+66+0,5=128+64+2+1/2 Из развернутой записи видно, что единиц будет четыре.  Ответ: 4).  ­ 31 ­ Задачи на теоретические знания темы По формулировкам все задачи, относящиеся к данному типу, бывают следующими:  –   в   системе   счисления   с   некоторым   основанием   число   X записывается в виде Y. Укажите это основание;  –   укажите   через   запятую   в   порядке   возрастания   все   десятичные числа,  не   превосходящие  Х,   запись   которых   в   системе   счисления   с основанием Y оканчивается на Z;  –   укажите   через   запятую   в   порядке   возрастания   все   основания систем счисления, в которых запись числа X оканчивается на Y.  Укажем основные этапы решения подобных задач:  Записать «основное уравнение» для исходного числа.  1. 2. Решить уравнение (может быть уравнение с параметром). 3. Сделать соответствующий вывод.  4. Запись «основного уравнения» для исходного числа осуществляется по принципам перевода из любой системы счисления в десятичную.  Пример 1:  В системе счисления с некоторым основанием число 12 записывается в виде 110.  Решение:  Пусть  основание   системы   счисления   равно  х.  Составим уравнение: 1×х2+1×х+0=12.  Пример 2:  В системе счисления с некоторым основанием число 12 записывается в виде 110.  Решение:  Пусть  основание   системы   счисления   равно  х.  Составим уравнение: 1×х2+1×х+0=12.  Пример 3:  В системе счисления с некоторым основанием число 12 записывается в виде 110.  Решение:  Пусть  основание   системы   счисления   равно  х.  Составим уравнение: 1×х2+1×х+0=12.  ­ 32 ­ Примеры тестовых заданий из ЕГЭ B1 (2004 год). В системе счисления с некоторым основанием число 12 записывается в виде 110. Укажите это основание.  Решение  Можно записать уравнение  . Корни . Основание системы положительно и равно 3. Значит уравнения  1103 = 12.  Ответ: 3.  B1.  Укажите через  запятую в порядке возрастания  все  основания систем счисления, в которых запись числа 23 оканчивается на 2.  Решение Способ простого перебора:  Оканчиваются на 2 числа в системе счисления по основаниям 3, 7,21. Способ второй по уравнению с параметром:  Пусть   х   –   основание   системы   счисления.   Составим   уравнение   с параметром   (для   решения   учтем,   что   для   того,   чтобы   нечетное   число   в десятичной системе счисления заканчивалось цифрой, обозначающей четное число, необходимо, чтобы основание системы счисления было нечетным. Для числа   23   минимальное   нечетное   основание   –   3,   переводя   23   в   троичную систему счисления получим три значащих цифры в числе): a1×x2+a2×x+2=23. В данной ситуации числа a1 и a2 можно считать параметрами. Произведение равно 21 (решение необходимо представить в целых числах), если сомножители равны: 7 и 3, или 3 и 7, или 1 и 21, или 21 и 1. Последний   вариант   мы   не   учитываем,   т.к.   не   рассматривается   в   школе унарная система счисления.  Вариант: 7 и 3. A1×x+a2=7 и х=3. A1×3+a2=7, a1=2, a2=1. Тогда: 2123 Вариант: 3 и 7. a1×x+a2=3 и х=7. a1×7+a2=3, a1=0, a2=3. Тогда: 327 Вариант: 1 и 21. A1×x+a2=1 и х=21.  A1×21+a2=1, a1=0, a2=1.  Тогда: 1221 ­ 33 ­ Ответ: 3, 7, 21.  B1 (2005 год). В системе счисления с некоторым основанием число 17 записывается в виде 101. Укажите это основание.  Решение  Составим   уравнение   системы счисления 4.  Ответ: 4.  .   Основание B1 (2006 год).  Укажите через запятую в порядке возрастания все основания систем счисления, в которых запись числа 22 оканчивается на 4.  Решение Способ простого перебора Оканчиваются   на   4   числа   в   системе   счисления   по   основаниям 6, 9, 18.  Способ второй по уравнению с параметром:  Пусть   х   –   основание   системы   счисления.   Составим   уравнение   с параметром (для решения учтем, что для числа 22 минимальное основание, числа в котором могут заканчиваться на 4 – это 5, переводя 22 в пятеричную систему   счисления   получим   две   значащие   цифры   в   числе):   a×x+4=22.   В данной ситуации число a можно считать параметром.  a×x+4=22 a×x=18 Произведение равно 18 (решение необходимо представить в целых числах), если сомножители равны: 6 и 3, или 3 и 6, или 2 и 9, или 9 и 2, или 1 и   18,   или   18   и   1.   Последний   вариант   мы   не   учитываем,   т.к.   не рассматривается   в   школе   унарная   система   счисления.   Из   рассмотрения автоматически убираются варианты 6 и 3, или 9 и 2, т.к. х – это основание системы счисления и оно не может быть меньше значений цифр числа.  Вариант: 3 и 6. a=3 и х=6. Тогда: 346 Вариант: 2 и 9. a=2 и х=9. Тогда: 249 Вариант: 1 и 18. a=1 и х=18. Тогда: 1418 Ответ: 6,9,18.  ­ 34 ­ B3 (2007 год).  Укажите через запятую в порядке возрастания все  не   превосходящие  25,   запись   которых   в   системе десятичные   числа, счисления с основанием четыре оканчивается на 11.  Решение Способ простого перебора: 25   =   1×42  +   2×4   +   1   =   1214.   Получили   максимальное   число   с основанием четыре, которое не превосходит 25.  1214 – 104= 1114, 1114 – 104 = 1014, 1014 – 104 = 314, 314 – 104 = 214, 214 = 104 = 114 – это последнее, которое оканчивается на 11.  Получили   два   числа   1114,   114,   переведём   в   десятичную   систему счисления.  1114 = 1×42 + 1×4 + 1 = 21, 114 = 1×4 + 1 = 5.  Способ второй по неравенству с параметром:  Пусть х –  первая  цифра числа в четверичной системе  счисления, заканчивающейся на 11. Составим неравенство с параметром (при решении необходимо учитывать,  что полученные числа не более  как трехзначные): х=0, х=1.  Пусть х=0. Тогда число равно 5=114. Пусть х=1. Тогда число равно 21=1114. Ответ: 5, 21.  B3   (2009   год).  В   системе   счисления   с   некоторым   основанием десятичное число 49 записывается в виде 100. Укажите это основание.  Решение  Составим уравнение  Основание системы счисления 7. Ответ: 7.  ­ 35 ­ Задачи на перевод чисел  в системах счисления 2, 4, 8, 16. По формулировкам все задачи, относящиеся к данному типу, бывают следующими.  1. Дано а16, b8. Какое из чисел c, записанных в двоичной системе, отвечает условию a 2.   Для   кодирования   нескольких   букв   латинского   (русского) алфавита   решили   использовать   двух­   (трех­,   четырех­)   значные   двоичные коды. Если таким образом закодировать последовательность символов Х и записать результат 16­тиричным кодом, то получим Y.  Укажем основные этапы решения подобных задач:  1. Перевести числа из системы счисления по основанию 2 (4, 8, 16) в систему счисления по основанию 4 (2, 8, 16).  2. Сделать соответствующий вывод.  Перевод чисел из двоичной системы счисления в восьмеричную и шестнадцатеричную системы счисления Чтобы   перевести   двоичное   число   в   четверичную   (4=22), восьмеричную   (8=23),   шестнадцатеричную   (16=24)   систему   счисления необходимо:  o разбить данное число от запятой на группы по 2 (для перевода в систему   четверичную   систему   счисления),   3   (для   перевода   в восьмеричную   систему   счисления),   4   для   перевода   в шестнадцатеричную   систему   счисления)   цифры   в   каждой.   Если недостаточно   знаков   для   образования   группы   можно   добавить незначащие нули слева от целой части числа или справа от дробной части;  o рассмотреть каждую группу и записать ее соответствующей цифрой четверичной,   восьмеричной   или   шестнадцатеричной   системы счисления.  ­ 36 ­ Таблица   переводов   чисел   между   системами   счисления   с основаниями 2 – 4 – 8 – 16 Пример 1: Перевести число 1110011012 в восьмеричную систему счисления.  Решение: Разделим число 110011012 на группы по три цифры справа налево и добавим незначащий 0 в начале числа: 011 001 1012. 0112=38, 0012=18, 1012=58. Тогда 1110011012=3158.  Пример  2:  Перевести  число  1010110011012  в шестнадцатеричную  систему счисления.  Решение: Разделим число 1010110011012 на группы по четыре цифры справа налево:   1010   1100   11012.   10102=А16,   11002=С16,   11012=D16.   Тогда 1010110011012=ACD16. Пример 3: Перевести число 111,0011012 в восьмеричную систему счисления.  Решение:  Разделим число 111,0011012  на группы по три цифры от запятой целую часть справа налево, а дробную – слева направо: 111,001 1012. 1112=78, 0012=18, 1012=58. Тогда 111,0011012=7,158 Пример 4: Перевести число в шестнадцатеричную систему счисления.  Решение: Разделим число 11101001000,110100102 на группы по три цифры от запятой целую часть справа налево, а дробную – слева направо:  0111 0100 1000 , 1101 00102.  01112=716, 01002=416, 10002=816, 11012=D16, 00102=216.  Тогда 11101001000,110100102=748,D216 ­ 37 ­ Перевод чисел из восьмеричной и шестнадцатеричной систем счисления в двоичную систему счисления  Правило:  для   того,   восьмеричное шестнадцатеричное   число   перевести   в   двоичную   систему   счисления, необходимо каждую цифру этого числа заменить соответствующим числом, состоящим из 2, 3 или 4 цифр двоичной системы счисления соответственно.    чтобы   четверичное, Пример 1: Перевести число 5238 в двоичную систему счисления А8 А→ 2 5238=101|010|0112 Пример 2: Перевести число C1B.316 в двоичную систему счисления А16 А→ 2 C1B.316=1100|0001|1011.|00112 Примеры тестовых заданий из ЕГЭ A3 (2009 год). Дано а=D716, b=3318. Какое из чисел c, записанных в двоичной системе, отвечает условию a 1) 11011001 2) 11011100 3) 11010111 4) 11011000 Решение Переведём числа а = D716 b=3318 в двоичную систему счисления.  D716=1101 01112.  3318=011 011 0012=110110012 110101112 < 110110002 < 110110012. Ответ: 4).  A1 (2009 год). Дано A=9D16, B=2378. Какое из чисел C, записанных в двоичной системе, отвечает условию A 1)100110102 2) 100111102 3) 100111112 4) 110111102 Решение Переведём числа A=9D16, B=2378 в двоичную систему счисления.  A=9D16=1001 11012 B=2378=010 011 1112=10011111 100111012 < 100111102 < 100111112. ­ 38 ­ Ответ: 2).  А11   (2009   год).  Для   кодирования   букв   А,   Б,   В,   Г   решили использовать двухразрядные последовательности двоичных чисел (от 00 до 11 соответственно). Если таким образом закодировать последовательность символов БАВГ и записать шестнадцатеричным кодом, то получится:  1) 4В 2) 411 3) ВАСD 4) 1023 Решение Составим кодировочную таблицу: A 00 Б 01 В 10 Г 11 Тогда код БАВГ имеет вид 01001011. Переведем полученное число в двоичной системе счисления в шестнадцатеричную. 0100 1011Б2=4В16. Ответ: 1)  А13   (2008   год).  Для   кодирования   букв   А,   Б,   В,   Г   решили использовать двухразрядные последовательности двоичных чисел (от 00 до 11 соответственно). Если таким образом закодировать последовательность символов ГБАВ и записать шестнадцатеричным кодом, то получится:  1) 132 2) D2 3) 3102 4) 2D Решение Составим кодировочную таблицу:  A 00 Б 01 В 10 Г 11 Тогда код ГБАВ имеет вид 11010010. Переведем полученное число в двоичной системе счисления в шестнадцатеричную. 1101 00102=D216.  Ответ: 2)  А11 (2010 год ­ демо).  Для передачи по каналу связи сообщения, состоящего   только   из   символов   А,   Б,   В   и   Г   используется   посимвольное кодирование: А – 00, Б – 11, В – 010, Г – 011.Через канал связи передается сообщение   ВАГБГВ.   Закодируйте   сообщение   данным   кодом.   Полученную двоичную последовательность переведите в шестнадцатеричный код. 1) AD34 2) 43DA 3) 101334 4) CADBCD Решение Код ВАГБГВ имеет вид 0100001111011010. Переведем полученное число в двоичной системе счисления в шестнадцатеричную. 0100 0011 1101 10102=43DA16. Ответ: 2)  ­ 39 ­ 5. ЗАДАЧИ (СИСТЕМЫ СЧИСЛЕНИЯ) 1. Покажите,   что   любое   натуральное   число   может   быть   представлено   в виде различных неотрицательных степеней числа 2.  2. В каких P­ичных системах счисления 5p + 5p = 10p? 3. 4. Во сколько раз увеличится число 3256, если приписать нему справа один Записать в системе счисления с основанием 234 число 235.  ноль?  5. Будут ли справедливы признаки делимости натуральных чисел на 2, 3, 5, 9, 10, сформулированных для десятичной системы счисления, и в других P­ичных системах?  6. Для десятичного числа 371 найти систему счисления с основанием P, в которой   данное   число   будет   представлено   теми   же   цифрами,   но записанными в обратном порядке, т.е. 371 = 173p. 7. Существует ли такая система счисления, в которой 3 + 4 =7, 3 х 4 =13 и 39 +29 =70?  8. Восстановите цифры двоичных чисел, на месте которых в приведенном примере стоит знак "х": 1х012 + 1хх2 = 101002.  9. Выпишите   в   пятеричной   системе   счисления   все   четные   числа   из диапазона от 1 до 20.  10. Даны числа в четверичной системе счисления от 1 до 33. Выпишите все числа, делящиеся на 3 без остатка.  11. Десятичное  число  20,45  перевели  в четвертичную  систему  счисления. Найти 1999­ю цифру после запятой.  12. Школьный калькулятор работает в троичной системе счисления и для вывода числа на экран имеет только четыре знакоместа. С каким самым большим   десятичным   числом,   переведенным,   конечно,   в   троичную систему счисления, мы можем работать? 13. Трехзначное десятичное число оканчивается цифрой 3. Если эту цифру переместить   на   два   разряда   влево,   то   есть   так,   что   с   нее   будет начинаться запись нового числа, то это новое число будет на единицу больше утроенного исходного числа. Найдите исходное число. 14. Шестизначное   число   оканчивается   цифрой   4.   Если   эту   цифру переставить из конца числа в начало, то есть приписать ее перед первой, не   изменяя   порядок   остальных   пяти,   то   получится   число,   которое   в четыре раза больше первоначального. Найдите это число. 15. Некогда был пруд, в центре которого вырост один лист водяной линии. Каждый   день   число   листьев   удваивалось,   и   на   десятый   день   вся поверхность пруда уже была заполнена листьями лилий. Сколько дней ­ 40 ­ понадобилось, чтобы заполнить листьями половину пруда? Сосчитайте, сколько листьев выросло к концу десятого дня. 16. Этот случай вполне мог иметь место во время «золотой лихорадки». На одном   из   приисков   старатели   были   возмущены   действиями   Джо Макдональда – хозяина салуна, принимавшего от них в уплату золотой песок.   Очень   уж   необычными   были   гири,   с   помощью   которых   тот взвешивал золото: 1, 2, 4, 8, 16, 32 и 64 грамма. Джо утверждал, что с помощью такого набора гирь он может взвесить с точностью до грамма любую порцию золотого песка, вес которой не превышает 100 граммов. Прав ли Джо Макдональд? Какой наибольший вес могут «взять» такие гири? Как с помощью названных гирь набрать вес: 25 г, 48 г, 72, 105 г? 17. Найдите такой набор из пяти гирь, чтобы, располагая их на одной чаше весов, можно было бы взвесить с точностью до 1 кг любой груз до 31 кг включительно. 18. Каким наименьшим числом гирь можно взвесить груз от 1 до 63 кг с точностью до 1 кг, помещая гири только на одну чашку весов? 19. Можно ли с помощью трех гирь (1, 3 и 9 кг) взвесить с точностью до 1 кг любой   груз   до   13   кг   включительно,  если   гири   можно   располагать   на обеих чашах весов, в том числе и на чаше с грузом? 20. Один кладовщик оказался в большом затруднении: заказанный комплект гирь   для   простых   чашечных   весов   не   прибыл   в   срок,   а   на   соседнем складе   лишних   гирь   не   было.   Тогда   он   решил   подобрать   несколько кусков железа разной массы и временно пользоваться ими как гирями. Ему удалось выбрать такие четыре «гири», с помощью которых можно было   бы   взвешивать   с   точностью   до   100   г   товар   от   100   г   до   4   кг. Подумайте, какой массы были эти гири? 21. Запишите наибольшее двузначное число и определите его десятичный восьмеричной системы счисления; эквивалент для следующих систем счисления: 1) 2) пятеричной системы счисления; троичной системы счисления; 3) 4) двоичной системы счисления. 23. Запишите наименьшее трехзначное число и определите его десятичный восьмеричной системы счисления; эквивалент для следующих систем счисления: 1) 2) пятеричной системы счисления; 3) троичной системы счисления; 4) двоичной системы счисления. ­ 41 ­ 24. Упорядочите   следующие   числа   по   убыванию:   1436,   509,   12223,   10114, 1100112, 1283. 25. В   классе   1111002%   девочек   и   11002  мальчиков.   Сколько   учеников   в классе? 26. У меня 100 братьев. Младшему 1000 лет, а старшему 1111 лет. Старший учится в 1001­м классе. Может ли такое быть? 27. В классе 1000q учеников, из них 120q девочек и 110q мальчиков. В какой системе счисления велся счет учеников? 28. В саду 88q фруктовых деревьев, из них 32q яблонь, 22q груш, 16q слив и 17q вишен. В какой системе счисления посчитаны деревья? 29. Было 53q яблока. После того как каждое из них разрезали пополам, стало 136q половинок. В системе счисления с каким основанием вели счет? 30. Один мальчик так написал о себе: «У меня 24 пальца, на каждой руке по 5, а на ногах 12». Как это могло быть? 31. Расставьте   знаки   арифметических   операций   так,   чтобы   были   верны следующие равенства в двоичной системе счисления: 1) 1100 ? 11? 100 = 100000; 2) 1100 ? 10 ? 10 = 100; 3) 1100 ? 10 ? 10 = 110000; 4) 1100 ? 10 ? 10 = 1011; 5) 1100 ? 11 ? 100 = 0. 32. Как измениться запись  P­ичной дроби с нулевой целой частью, если ее разделить на P2? 33. Записать в системе счисления с основанием 234 число 235. 34. Будут ли справедливы признаки делимости натуральных чисел на 2, 3, 5, 9, 10, сформулированные для десятичной системы счисления, и в других P­ичных системах? 35. Число,   записанное   в   десятичной   системе   счисления,   оканчивается цифрой 5. Будет ли оно делиться на 510, если записать его в троичной системе счисления? 36. Существуют   ли   системы   счисления   с   основаниями  p  и  q,   в   которых 12p>21q? ­ 42 ­ 37. Для десятичного числа 371 найти систему счисления с основанием  p, в которой   данное   число   будет   представлено   теми   же   цифрами,   но записанными в обратном порядке, то есть 37110 = 173p. ­ 43 ­ АЛГЕБРА ЛОГИКИ 1. ЛОГИЧЕСКИЕ ОПЕРАЦИИ Высказывание (суждение) –  некоторое предложение, которое может быть истинно (верно) или ложно Утверждение – суждение, которое требуется доказать или опровергнуть Рассуждение   –  цепочка   высказываний   или   утверждений,   определенным образом связанных друг с другом Умозаключение – логическая операция, в результате которой из одного или нескольких данных суждений получается (выводится) новое суждение Логическое выражение – запись или устное утверждение, в которое, наряду с   постоянными,   обязательно   входят   переменные   величины   (объекты).   В зависимости   от   значений   этих   переменных   логическое   выражение   может принимать одно из двух возможных значений: ИСТИНА (логическая 1) или ЛОЖЬ (логический 0) Сложное логическое выражение – логическое выражение, составленное из одного   или   нескольких   простых   (или   сложных)   логических   выражений, связанных с помощью логических операций. Логическое отрицание (инверсия) Логическое   отрицание   образуется   из   высказывания   с   помощью добавления частицы «не» или использования оборота речи «неверно, что…». Обозначения: ¬А; Ā. Пример. А= {Аристотель основоположник логики.} Ā= {Неверно, что Аристотель основоположник логики.} Таблица истинности А 0 1 Ā 1 0 Инверсия высказывания истинна, когда высказывание ложно, и ложна, когда высказывание истинно. ­ 44 ­ Мнемоническое   правило:   слово   «инверсия»   означает,   что   белое меняется на чёрное, добро на зло, красивое на безобразное, истина на ложь, ложь на истину, ноль на один, один на ноль. Логическое умножение (конъюнкция) Логическое умножение (конъюнкция) образуется соединением двух высказываний в одно с помощью союза «и». Обозначения: А∙В; А^В; А&В. Пример.  А= {3+4=8}.     В= {2+2=4}.      А&В={3+4=8 и 2+2=4} Таблица истинности А∙В А 0 0 0 0 1 0 1 1 В 0 1 0 1 Конъюнкция двух высказываний истинна тогда и только тогда, когда оба высказывания истинны, и ложна, когда хотя бы одно высказывание ложно. Мнемоническое правило: конъюнкция – это логическое умножение, и мы не сомневаемся, что вы заметили, что равенства 0∙0=0; 0∙1=0; 1∙0=0; 1∙1=1, верные для обычного умножения, верны и для операции конъюнкции. Логическое сложение (дизъюнкция) Логическое   сложение   (дизъюнкция)   образуется   соединением   двух высказываний в одно с помощью союза «или». В русском языке союз «или» используется в двояком смысле. Например, в предложении Обычно в 8 вечера я смотрю телевизор или пью чай союз «или» взят в неисключающем (объединительном) смысле, так как вы можете только смотреть телевизор или только пить чай, но вы можете также пить чай и смотреть телевизор одновременно, потому что мама у вас нестрогая. Такая операция называется нестрогой дизъюнкцией. (Если бы мама была строгая, то она разрешила бы или только смотреть телевизор, или   только   пить   чай,   но   не   совмещать   приём   пищи   с   просмотром телепередач.) В высказывании Данное существительное во множественном или используется   в   исключающем  строгой   Такая   операция   называется единственном   числе  (разделительном)   смысле. дизъюнкцией. союз   «или»  Определите самостоятельно вид дизъюнкции: Высказывание Вид дизъюнкции ­ 45 ­ Петя   сидит   на   западной   или   восточной трибуне стадиона. Студент едет в электричке или читает книгу. Ты женишься на Вале или на Свете Учителя бывают или строгие , или не наши. Строгая Нестрогая Строгая Нестрогая Далее будем рассматривать только нестрогую дизъюнкцию. Обозначение: А В. Таблица истинности А В А 0 0 1 1 В 0 1 0 1 0 1 1 1 Дизъюнкция двух высказываний ложна тогда и только тогда, когда оба высказывания ложны, и истинна, когда хотя бы одно высказывание истинно. Мнемоническое правило: дизъюнкция – это логическое сложение и легко заметить, что равенства 0+0=0; 0+1=1; 1+0=1; верные для обычного сложения, верны и для операции дизъюнкции, но  1 1=1. Логическое следование (импликация) высказываний в одно с помощью оборота речи «если….., то…..». Логическое следование (импликация) образуется соединением двух Обозначения: А В→ , А В. Пример. А={2∙2=4} и В={3∙3=10}.  А В={Если 2∙2=4, то 3∙3=10 } Таблица истинности А 0 0 1 1 В 0 1 0 1 А 1 1 0 1 В Импликация двух высказываний ложна тогда и только тогда, когда из истинного высказывания следует ложное. Логическое равенство (эквивалентность) ­ 46 ­ Эквивалентность образуется соединением двух высказываний в одно при помощи оборота речи «….тогда и только тогда, когда…». Обозначение эквивалентности: А=В; А В; А~В. Пример: А={Угол прямой}; В={Угол равен 900} А В={Угол называется прямым тогда и только тогда, когда он равен 900} Таблица истинности А 0 0 1 1 В 0 1 0 1 А 1 0 0 1 В Эквивалентность двух высказываний истинна тогда и только тогда, когда оба высказывания истинны или оба ложны. Приоритет операций: 1) инверсия; 2) конъюнкция; 3) дизъюнкция; 4) импликация и эквивалентность. ­ 47 ­ 2. ЛОГИЧЕСКИЕ ЗАКОНЫ   ­ 48 ­ 3. ПРИМЕРЫ ТЕСТОВЫХ ЗАДАНИЙ ИЗ ЕГЭ С РЕШЕНИЕМ Задача №1 (А7): Для какого имени истинно высказывание: ¬(Первая буква имени гласная  →  Четвертая буква имени согласная) 1)     Елена 2)     Вадим 3)     Антон 4)     Федор → →  С4) = 1  Решение задачи:  Обозначим гласную букву – Г, согласную букву – С и запишем данное выражение с помощью наших обозначений: ¬( Г1  Поскольку данное высказывание истинно, а его отрицание – ложно. Г1   С4 = 0, это высказывание является импликацией и ложно только в том случае, когда Г1 = 1, а С4 = 0, т.е. первая и четвертая буквы – гласные. Этому условию удовлетворяет ответ 4, имя Антон. Задача №2 (А7):  Для какого имени истинно высказывание: Первая буква имени согласная   Четвертая буква имени гласная)  (¬ Вторая буква имени согласная  → Λ 1)     Иван 2)     Петр 3)     Павел 4)     Елена Λ →   Г4)   =1,   а   это   высказывание   является   импликацией   и  Г4) = 1, это высказывание является конъюнкцией и истинно  Решение задачи: Запишем выражение с помощью наших обозначений: → С1   (¬ С2  только, когда С1   =1   и   (¬   С2   истинно,  когда ¬ С2 = 1 и Г4=1, т.е. первая буква – согласная, вторая и четвертая буквы – гласные, этому условию соответствует ответ 3, имя Павел или ¬ С2 = 0 и Г4=1, т.е. первая и вторая буквы – согласная, четвертая буква – гласная, или ¬ С2 = 0 и Г4=0, т.е. первая, вторая и четвертая буквы – согласные, последние два условия не удовлетворяют ни одному из ответов. Задача №3 (А8): Укажите какое логическое выражение равносильно выражению ¬(¬АvВ)v¬С? ­ 49 ­ Решение задачи: Используя закон де Моргана ¬(АvВ) = (¬А  ¬(¬А)=А упростим выражение ¬(¬АvВ)v ¬С =( ¬(¬А)  ¬С, ответ 1. Задача №4 (А8): Укажите какое логическое выражение равносильно выражению ¬(А  С? Λ  ¬В) и закон двойного отрицания  ¬В)v  ¬В)v ¬С = (А  Λ  ¬В)v Λ Λ Λ  ¬В) v ¬С 1)     (А  2)     ¬А v В v ¬С 3)     А v ¬В v ¬С 4)     (¬А  Λ  В) v ¬С 1)     (А v В) v ¬С Λ  В) v С 2)     (¬А  3)     (¬А v В) v С 4)     (¬А v В) v ¬С Λ Λ Z 0 1 0 Y 1 1 1   В)   =   (¬А   v   ¬В)   и   закон   двойного  ¬В)v С = (¬А v ¬(¬В))v С = Решение задачи: Используя   закон   де   Моргана   ¬(А   отрицания ¬(¬В)=В упростим выражение ¬(А  (¬А v В) v С, ответ 3. Задача №5 (А9): Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения F: X 0 0 1 Какое выражение соответствует F? Λ 1)     ¬X   ¬Y v ¬Z Λ Λ  ¬Z 2)     X   ¬Y   ZΛ 3)     (X v Y)  Λ Λ 4)     X   Y   Z  Решение задачи:  Решение   сводится   к   проверке   приведенных   функций   на   их   соответствие фрагменту таблицы истинности. Построим четыре таких фрагмента и затем сравним: 1)  X 0 0 1 ¬X  1 0 1 Λ  ¬Y v ¬Z Y 1 1 1 Z 0 1 0 F 0 1 0 ­ 50 ­ ¬Z 0 1 0 Z 0 1 0 Z 0 1 0 Z 0 1 0 X  0 0 0 Y 1 1 1 Y 1 1 1 Y 1 1 1 X  0 0 0 (X v Y)   ZΛ Λ Λ  Y   Z Λ Λ  ¬Y   2)  X 0 0 1   3)  X 0 0 1  4)  X 0 0 1   В   результате   таблица   истинности   третьего   выражения   соответствует заданной. Ответ 3. Задача №6 (В4): Дано логическое выражение (K  Укажите   значение   переменных   K,   L,   M,   N,   при   которых   логическое выражение ложно. Ответ запишите в виде строки из четырех символов: значений переменных K, L, M, N (в указанном порядке). Так, например, строка 0101 соответствует тому, что K=0, L=1, M=0, N=1. Решение задачи: Дизъюнкция (a v b v c) ложна тогда и только тогда, когда a ­ ложно, b­ ложно, c­ ложно,  a= (K  a ложно лишь при (К,М)=(1,0) => К=1, М=0 b ложно при (L, M, K)=(0, 0, 1) => L=0, а К и М мы определили раньше c ложно при N=0. Поэтому ответ 1000. Задача №7 (В4): Сколько различных решений имеет уравнение (K V L V M) Λ (¬L V M V N) = 0 Где K, L, M, N – логические переменные? Λ  ¬M   K), c= N  M), b= (L  Λ Λ  ¬M   K) V N →  M) V (L  → Λ ­ 51 ­ M 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 N 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 L 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 ¬L 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 В ответе не нужно перечислять все различные наборы значений K, L, M, N, при   которых   выполнено   данное   равенство.   В   качестве   ответа   вам   нужно указать количество таких наборов. Решение задачи: Построим таблицу истинности для этой функции:  K 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1   Из таблицы истинности видим, что функция ложна 4 раза. Ответ: 4. Задача №8 (В6): Пятеро   одноклассников   –   Аня,   Саша,   Лена,   Вася   и   Миша   –   стали победителями   олимпиад   школьников   по   физике,   математике,   литературе, информатике и географии. Известно, что: 1)      победитель олимпиады по информатике учит Аню и Сашу работе на K V L V M ¬L V M V N 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 F 0 0 1 1 0 1 1 1 1 1 1 1 0 1 1 1 компьютере; 2)     Лена и Вася тоже заинтересовались информатикой; 3)     Саша всегда побаивался физики; 4)      Лена,   Саша   и   победитель   олимпиады   по   литературе   занимаются плаванием; 5)     Саша и Лена поздравили победителя олимпиады по математике; 6)     Аня сожалеет о том, что у нее остается мало времени на литературу. Победителем какой олимпиады стал каждый из этих ребят? В ответе перечислите подряд без пробелов заглавные буквы названий предметов соответствующие именам Аня, Саша, Лена, Вася и Миша).  Решение задачи: ­ 52 ­ Задачу будем решать рассуждениями. Из условия 1 и 2 задачи следует, что Аня, Саша, Лена и Вася участвовали в олимпиаде   не   по   информатике,   значит   победитель   по  информатике   – Миша. Из условия 3 задачи следует, что Саша участвовал в олимпиаде не по физике. Из   условия   4   следует,   что   и   не   по   литературе,   а   из   условия   5   –   не   по математике, значит Саша победитель по географии. Из условий 4 и 5 задачи следует, Лена победитель по физике. Из условия 6 задачи следует, что Аня победитель по математике. А Вася победитель по литературе. Ответ: МГФЛИ 4. ЗАДАЧИ С ВЫБОРОМ ОТВЕТА 1. Известно, что Единорог лжет по понедельникам, вторникам и средам и говорит правду во все остальные дни недели. Он может сказать: "Вчера я лгал. После завтрашнего дня я буду лгать два дня подряд": 1) в понедельник   2) во вторник        3) в воскресенье       4) в четверг          5) в среду. 2.  Известно, что  Лев лжет по понедельникам, вторникам и средам  и в остальные дни говорит правду, а Единорог лжет по четвергам, пятницам и субботам  и говорит правду в остальные дни. Однажды Лев сказал:  "Вчера был один из дней, когда я лгу", на что Единорог заметил "Вчера был один из дней, когда я тоже лгу".    День беседы: 1) вторник              2) среда               3) четверг                 4) суббота              5) воскресенье. 3. Истинность двух высказываний: «гонщик А участвует в ралли, а гонщик В не участвует в ралли» и «из двух гонщиков В и С участвует в ралли только один» означает участие в ралли гонщиков 1) А, В, С               2) А, В                   3) А                  4) В, С               5) А, С 4. Истинность двух высказываний: «неверно, что если полк В участвует в учениях, то полк С участвует в учениях»  и  «если полк А участвует в учениях, то полк В не участвует» означает учения полков 1) С                       2) А, В                   3) А                    4) В                   5) А, С 5.  Истинность   двух   высказываний:  «фирма   А   организует   выставку,   а фирма   С   не   организует»  и  «если   фирма   В   организует   выставку,   то фирма С тоже организует» означает организацию выставок фирмами ­ 53 ­ 1) А, В, С               2)А                        3) А, С                4) В, С              5)А,В 6.  Истинность двух высказываний:  «неверно, что если будет экскурсия в город В, то не будет экскурсии в город С»  и  «если будет экскурсия в город С, то не будет экскурсии в город А» означает проведение экскурсии в городах 1) А, В, С               2) А, В                    3) А                    4) В, С                    5)А,С 7.  Истинность   двух   высказываний:  «школьник   В   пойдет   в   кино,   а школьник С не пойдет»  и  «из двух школьников А и С пойдет в кино только один» означает посещение кинотеатра школьниками 1) А, В, С               2) В                        3) А, В                4) В, С               5) А, С 8. Истинность двух высказываний: «неверно, что если корабль А вышел в море, то корабль С ­ нет» и «в море вышел корабль В или корабль С, но не оба вместе» означает выход в море кораблей 1) А, В, С               2) А, В                    3) А                    4) В, С             5) А, С 9.  Истинность   двух   высказываний:  «неверно,   что   если   магазин   А организует распродажу, то магазин С тоже» и «из двух магазинов В и С организует распродажу только один» означает организацию распродажи в магазинах 1) А, В, С               2) А, В                    3) А                    4) В, С             5) А, С 10. В очереди стоят Вика, Соня, Боря, Денис и Алла. Вика стоит впереди Сони, но после Аллы; Боря и Алла не стоят рядом; Денис не находится   рядом   ни   с   Аллой,   ни   с   Викой,   ни   с   Борей. Третьим в очереди стоит … Ответы: Задание 1.    Ответ:  1 (в понедельник). Задание 2.    Ответ: 3. Задание 3.    Ответ: 5. Задание 4.     Ответ: 4 (В ­ участвует). Задание 5.    Ответ 2. Задание 6.    Ответ:4. Задание 7.    Ответ: 3. Задание 8.    Ответ: 5. Задание 9.    Ответ: 2. Задание 10.   Ответ Боря    (А, В, Б, С, Д) ­ 54 ­ ­ 55 ­ СПИСОК ЛИТЕРАТУРЫ 1. Шауцукова Л.З. Информатика.  ­М.: Просвещение, 2000. 2. Угринович Н.Д. Информатика и информационные технологии. – М.:  «Юнимедиастайл», 2002. http://festival.1september.ru http://www.metod­kopilka.ru http://informatika.sch880.ru http://khpi­iip.mipk.kharkiv.edu http://www.klyaksa.net/test_online/ 3. 4. 5. 6. 7. ­ 56 ­