ИКТ. Раздел 1 Понятие информации
 Скачать 57.12 Kb.
|
|
Содержание:…………………………………………………….1 Раздел 1 Понятие информации…………………………………2 Раздел 2 Системы счисления…………………………………...6 Раздел 3 Обработка беззнаковых целых числе……………….12 Раздел 4 Битовая обработка данных…………………………..16 Раздел 5 Представление знаковых целых чисел……………...19 Раздел 6 Сложение и вычитание знаковых целых чисел…….24 Раздел 7 Устройство сумматора……………………………….27 Раздел 8 Умножение целых чисел……………………………..28 Список литературы……………………………………………..30 Раздел 1 Понятие информации Понятие информации Информатика – наука о способах её представления информации, её получении, преобразовании и передаче. Информация – это сведения об объектах и явлениях окружающей среды, их параметрах, свойствах и состоянии, которые уменьшают степень неопределённости, неполноты знаний о них. Энтропия – численная мера неопределённости информации H= f (n), n – количество вариантов сообщений, которые можно получить от источникаминформации. Свойства энтропии: 1 f (1)=0, полученное сообщение не является случайным, неопределённость отсутствует. 2 f (n) возрастает с ростом n. 3 Количество Информации I Определяется степенью снятия неопределённости при получении сообщения от источника информации I=H 1−H 2, где H 1 – неопределённость до получения сообщения, H 2 – оставшаяся неснятой неопределённость после получения сообщения. Задача 1. Дана колода из 36 игральных карт (это наш алфавит). Каково количество информации, измеренной в битах, заключено в сообщении: а) вытащенная из колоды карта является дамой пик; б) вытащенная из колоды карта является бубновой; в) вытащенная из колоды карта старше десятки; г) вытащенная из колоды карта чёрной масти; д) вытащенная из колоды карта является тузом. е) вытащенная из колоды карта является тузом или дамой красной масти; ё) из колоды вытащили пиковый туз, а потом из оставшейся колоды вытащили валет червей; ж) из колоды вытащили туз, а потом из оставшейся колоды вытащили семёрку; з) из колоды вытащили шестёрку красной масти, потом из оставшейся колоды вытащили семёрку, а потом из оставшейся колоды вытащили шестёрку пик. Объяснение: а) В колоде одна дама пик, поэтому шанс ее достать равен 1 из 36. По формуле Хартли получаем ㏒₂36 бит. Или, примерно, 5.17 бит. б) Всего карт (событий выбора) - 36 Бубновой масти ( положительный исход) - 9 З=9/36 = 1/4=0,25 в) Старше десятки в колоде из 36 карт будут валет, дама, король и туз. 4 карты одной масти. Мастей 4, поэтому всего таких карт 4×4=16. Шанс достать такую карту равен 16 из 36 или 4 из 9. Снова по формуле Хартли получаем ㏒₂(9/4) бит. Или, примерно, 1.17 бит. г) Карт черной масти - половина колоды. В этом случае дробь 1/2, перевернутая дробь 2, количество информации ㏒₂2 = 1 (бит). д) Туза в колоде 4, шанс оценивается как 4/36 = 1/9, переворачиваем дробь, получаем 9, ㏒₂9 ≈ 3,17 е) В колоде 4 туза и 4 дамы, всего 8 интересующих нас карт.Шанс успеха составит 8 / 36 =2 / 9. По формуле Хартли количество информации составит ㏒₂(9/2) = 2.17 бит. ё) Шанс вытащить туза пик 1 из 36. Осталось 35 карт. Шанс вытащить червового валета составит 1 из 35. Оба события нам нужны одновременно, поэтому перемножим эти шансы. Получим 1 из 1260. По формуле Хартли количество информации составит ㏒₂1260 ≈ 10.3 бит. ж) Шанс вытащить одного из четырех тузов равен 4 из 36, т.е. 1 из 9. Шанс вытащить из оставшихся 35 карт одну из четырех семерок равен 4/35. Оба события нам нужны одновременно, поэтому перемножим эти шансы. Получим 4 / 315. По формуле Хартли количество информации составит ㏒₂(315 / 4) ≈ 6.3 бит. з) Шанс вытащить одного из двух красных семерок равен 2 / 36 или 1 / 18. Шанс вытащить из оставшихся 35 карт семерку (а их 4) составит 4 / 35. Шанс вытащить из оставшихся 34 карт шестерку пик составит 1 / 34. Все три события нам нужны одновременно, поэтому перемножим эти шансы. Получим (2 × 4) / (36 × 35 × 34) = 8 / 42840 = 1 / 5355.По формуле Хартли количество информации составит ㏒₂5355 ≈ 12.4 бит. Задача 2. Дан мешок, в котором лежат 3 чёрных шара, 5 красных и 7 белых шаров (это наш алфавит). Каково количество информации, измеренной в натах, заключено в сообщении: а) вытащенный из мешка шар является чёрным; б) вытащенный из мешка шар является чёрным или белым; в) из мешка вытащили красный шар, а потом ещё один красный шар; г) из мешка вытащили красный шар, а потом не красный шар; д) из мешка вытащили красный шар, а потом не белый шар. Объяснение: Для начала найдем общее количество шаров в мешке и не надо брать в голову слово "алфавит" - оно лишь сбивает с толку. Тут везде используем формулу Хартли - события равновероятны. Формулу Хартли обычно используют по упрощенной для вычислений схеме: переврачивают "вверх ногами" простую дробь, полученную при оцнке вероятности и берут от нее логарифм. В мешке 3+5+7 = 15 шаров а) Вытащен черный шар. Таких шаров 3, шанс (вероятность) вытащить черный шар 3 из 15. 3/15, "перевернем", будет 15/3 = 5. Результат в натах равен ㏑5 ≈ 1.609 б) Черный или белый шар. Этих шаров 3+7=10, шанс наступления события 10 из 15, "переворачиваем", 15/10 = 1.5, находим наты: ㏑1.5 ≈ 0.405 в) Красный, потом еще красный. Для первого красного шанс 5 из 15. При удаче в мешке останется 14 шаров, из них 4 красных, шанс получить такой 4 из 14. События должны наступить вместе, поэтому полученные дроби перемножаем. (5/15) * (4/14) = 2/21. Перевернем дробь, возьмем логарифм. ㏑(21/2) ≈ 2.351 (нат) г) красный и не красный. Как показано выше, для красного шанс 5/15 = 1/3. Для некрасного 10/14 (надеюсь, тут ясно, что некрасных 3+7=10 шаров). Перемножаем, переворачиваем, берем логарифм.( 1/3) × (10/14) = 5/21. ㏑(21/5) ≈ 1.435 (нат) д) Красный и не белый. По-прежнему для первого красного шанс 1/3. Не белых из 14 останется 7 (4 красных и 3 черных) и шанс составит 7/14 = 1/2. Перемножаем, переворачиваем, логарифмируем. (1/3) × (1/2) = 1/6. ㏑6 ≈ 1.792 (нат) Задача 5. Сколько символов должно быть в алфавите, из которого составлено слово, длиной четыре символа, содержащее 32 бита информации? Объяснение: Определим "вес" одного символа в битах: 32 / 4 = 8 бит. Поскольку 2⁸ = 256, в алфавите не может быть больше 256 символов. Задача 6 Какая строка содержит большее количество информации: а) «1100» в алфавите {0,1} или «120» в алфавите {0,1,2}? б) «100» в алфавите {0,1} или «20» в алфавите {0,1,2}? в) «1001» в алфавите {0,1} или «31» в алфавите {0,1,2,3}? г) «шар» в русском алфавите или «sphere» в английском алфавите? Объяснение: а) Алфавит {0,1} содержит два символа 2 = 2¹, поэтому для кодирования одного символа требуется 1 бит. «1100» содержит 4 символа и будет кодироваться 4 × 1 = 4 битами. Алфавит {0,1,2} содержит три символа 2¹ < 3 < 2², поэтому для кодирования одного символа требуется 2 бита. «120» содержит 3 символа и будет кодироваться 3 × 2 = 6 битами. Вторая строка содержит больше информации, т.е. 6 > 4 б) «100» в aлфaвитe {0,1} займет 3× 1 = 3 бита (рассуждения см выше), «20» в aлфaвитe{0,1,2} займет 2 × 2 = 4 бита. Вторая строка содержит больше информации, т.е. 4 > 3 в) «1001» в aлфaвитe {0,1} займет 4 × 1 = 4 бита. Алфавит {0,1,2,3} содержит четыре символа 4 = 2², поэтому для кодирования одного символа требуется 2 бита. «31» содержит 2 символа и будет кодироваться 2 × 2 = 4 битами. Здесь обе строки содержат равное количество информации, 4 = 4 г) Русский алфавит без "ё" содержит 32 = 2⁵ символа, поэтому один символ кодируется 5 битами. Если с "ё", потребуется уже 6 бит на символ. Латинский алфавит содержит 2⁴ < 26 < 2⁵ символов, поэтому для кодирования одного символа потребуется 5 бит. В слове "sphere" 6 латинских букв, поэтому его объем 6 × 5 = 30 бит. В слове "шар" 3 русские буквы. Даже в алфавите с "ё" под них достаточно отвести 3 × 6 = 18 бит. В английском слове "sphere" информации больше, чем в русском "шар". Раздел 2 Системы счисления Двоичная СС Целые числа в двоичной СС представляются последовательностью двоичных разрядов an−1…a1a0 и значение числа можно вычислить по формуле: N=an−1∙2 n−1+…+a1∙2 1+a0 ∙2 0 2 – основание СС; n – количество разрядов числа N; a i – коэффициенты полинома, a iϵ {0,1 }. Пример перевода четырёхразрядного двоичного числа 10012 в десятичную СС: N = 1∙8 + 0∙4 + 0∙2 + 1∙1 = 910 Вещественные числа в двоичной СС представляются последовательностью двоичных разрядов an−1…a1a0 . b0b1…bm−1 и значение числа можно вычислить по формуле: N=a ∙2n−1n−1 +…+a1 ∙2 1+a ∙20+b ∙2−10 0 +b1 ∙2 −2+…+bm−1 ∙2 −m+1 n – количество разрядов целой части числа N; m – количество разрядов дробной части числа N; a i – коэффициенты целой части полинома; b i – коэффициенты дробной части полинома, b iϵ {0,1 }. Задача 5 Какие максимальные целые числа представимы в 32-разрядном, 64- разрядном и 128-разрядном компьютерах? Решение: 232-1 264-1 2128-1 Задача 6 Переведите десятичные вещественные числа в двоичные: а) 8,125 б) 7,625 в) 10,875 г) 15,5078125 Решение: а) Переведем 8.12510 в двоичную систему вот так: Целая часть числа находится делением на основание новой
Получилось:810 = 10002 Дробная часть числа находится умножением на основание новой
Получилось:0.12510 = 0.0012 Сложим вместе целую и дробную часть вот так: 10002 + 0.0012 = 1000.0012 Результат перевода: 8.12510 = 1000.0012 б) Переведем 7.62510 в двоичную систему вот так: Целая часть числа находится делением на основание новой
Получилось:710 = 1112 Дробная часть числа находится умножением на основание новой
Получилось:0.62510 = 0.1012 Сложим вместе целую и дробную часть вот так: 1112 + 0.1012 = 111.1012 Результат перевода: 7.62510 = 111.1012 в) Переведем 10.87510 в двоичную систему вот так: Целая часть числа находится делением на основание новой
Получилось:1010 = 10102 Дробная часть числа находится умножением на основание новой
Получилось:0.87510 = 0.1112 Сложим вместе целую и дробную часть вот так: 10102 + 0.1112 = 1010.1112 Результат перевода: 10.87510 = 1010.1112 г) Переведем 15.507812510 в двоичную систему вот так: Целая часть числа находится делением на основание новой
Получилось:1510 = 11112 Дробная часть числа находится умножением на основание новой
Получилось:0.507812510 = 0.10000012 Сложим вместе целую и дробную часть вот так: 11112 + 0.10000012 = 1111.10000012 Результат перевода: 15.507812510 = 1111.10000012 Задача 10 Переведите дату своего рождения в двоично-десятичных формат.02.08.1996 Решение: Переведем 2.080199610 в двоичную систему вот так: Целая часть числа находится делением на основание новой
Получилось:210 = 102 Дробная часть числа находится умножением на основание новой
Получилось:0.080199610 = 0.000101001002 Сложим вместе целую и дробную часть вот так: 102 + 0.000101001002 = 10.000101001002 Результат перевода: 02.08.199610 = 10.000101001002 Задача 12 Выполните инкремент числа 1010101fib и запишите ответ в минимальной форме фибоначчиевой СС и в десятичной СС. Ответ: 10000000fid 3410 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
