Тема : Кодирование сообщений. Комбинаторика. Каждая ячейка памяти компьютера работающего в троичной системе счисления


Еще пример задания:

Каждая ячейка памяти компьютера, работающего в троичной системе счисления, может принимать три различных значения (-1, 0, 1). Для хранения некоторой величины отвели 4 ячейки памяти. Сколько различных значений может принимать эта величина?

Решение:

  1. непривычность этой задачи состоит в том, что используется троичная система

  2. фактически мы имеем дело с языком, алфавит которого содержит M=3 различных символа

  3. поэтому количество всех возможных «слов» длинойNравно

  4. для получаем

  5. таким образом, правильный ответ – 81.

Возможные ловушки:

  • если не осознать, что используется троичная (а не двоичная!) система, можно «по инерции» получить неправильный ответ

Еще пример задания:

В школьной базе данных хранятся записи, содержащие информацию об учениках:

    <Фамилия> – 16 символов: русские буквы (первая прописная, остальные строчные),

    <Имя> – 12 символов: русские буквы (первая прописная, остальные строчные),

    <Отчество> – 16 символов: русские буквы (первая прописная, остальные строчные),

    <Год рождения> – числа от 1992 до 2003.

Каждое поле записывается с использованием минимально возможного количества бит. Определите минимальное количество байт, необходимое для кодирования одной записи, если буквы е и ё считаются совпадающими.

1) 282) 293)464)56

Решение:

  1. очевидно, что нужно определить минимально возможные размеры в битах для каждого из четырех полей и сложить их;

  2. важно! известно, что первые буквы имени, отчества и фамилии – всегда заглавные, поэтому можно хранить их в виде строчных и делать заглавными только при выводе на экран (но нас это уже не волнует)

  3. таким образом, для символьных полей достаточно использовать алфавит из 32 символов (русские строчные буквы, «е» и «ё» совпадают, пробелы не нужны)

  4. для кодирования каждого символа 32-символьного алфавита нужно 5 бит (32 = 25555), поэтому для хранения имени, отчества и фамилии нужно (16 + 12 + 16)•5=220 бит

  5. для года рождения есть 12 вариантов, поэтому для него нужно отвести 4 бита (24 = 16 ≥ 12)

  6. таким образом, всего требуется 224 бита или 28 байт

  7. правильный ответ – 1.

Задачи для тренировки3:

  1. Световое табло состоит из лампочек. Каждая лампочка может находиться в одном из трех состояний («включено», «выключено» или «мигает»). Какое наименьшее количество лампочек должно находиться на табло, чтобы с его помощью можно было передать 18 различных сигналов?

1) 6 2) 5 3) 3 4) 4

  1. Метеорологическая станция ведет наблюдение за влажностью воздуха. Результатом одного измерения является целое число от 0 до 100 процентов, которое записывается при помощи минимально возможного количества бит. Станция сделала 80 измерений. Определите информационный объем результатов наблюдений.

1) 80 бит 2) 70 байт 3) 80 байт 4) 560 байт

  1. Обычный дорожный светофор без дополнительных секций подает шесть видов сигналов (непрерывные красный, желтый и зеленый, мигающие желтый и зеленый, красный и желтый одновременно). Электронное устройство управления светофором последовательно воспроизводит записанные сигналы. Подряд записано 100 сигналов светофора. В байтах данный информационный объем составляет

1) 37 2) 38 3) 50 4) 100

(Условие некорректно, имеется в виду количество целых байтов.)

  1. Сколько существует различных последовательностей из символов «плюс» и «минус», длиной ровно в пять символов?

1) 64 2) 50 3) 32 4) 20

  1. Шахматная доска состоит 8 столбцов и 8 строк. Какое минимальное количество бит потребуется для кодирования координат одного шахматного поля?

1) 4 2) 5 3) 6 4) 7

  1. Два текста содержат одинаковое количество символов. Первый текст составлен в алфавите мощностью 16 символов, а второй текст – в алфавите из 256 символов. Во сколько раз количество информации во втором тексте больше, чем в первом?

1) 12 2) 2 3) 24 4) 4

  1. Какое минимальное количество бит потребуется для кодирования положительных чисел, меньших 60?

1) 1 2) 6 3) 36 4) 60

  1. Двое играют в «крестики-нолики» на поле 4 на 4 клетки. Какое количество информации получил второй игрок, узнав ход первого игрока?

1) 1 бит 2) 2 бита 3) 4 бита 4) 16 бит

  1. Объем сообщения – 7,5 Кбайт. Известно, что данное сообщение содержит 7680 символов. Какова мощность алфавита?

1) 77 2) 256 3) 156 4) 512

  1. Дан текст из 600 символов. Известно, что символы берутся из таблицы размером 16 на 32. Определите информационный объем текста в битах.

1) 1000 2) 2400 3) 3600 4) 5400

  1. Мощность алфавита равна 256. Сколько Кбайт памяти потребуется для сохранения 160 страниц текста, содержащего в среднем 192 символа на каждой странице?

1) 10 2) 20 3) 30 4) 40

  1. Объем сообщения равен 11 Кбайт. Сообщение содержит 11264 символа. Какова мощность алфавита?

1) 64 2) 128 3) 256 4) 512

  1. Для кодирования секретного сообщения используются 12 специальных значков-символов. При этом символы кодируются одним и тем же минимально возможным количеством бит. Чему равен информационный объем сообщения длиной в 256 символов?

1) 256 бит 2) 400 бит 3) 56 байт 4) 128 байт

  1. Мощность алфавита равна 64. Сколько Кбайт памяти потребуется, чтобы сохранить 128 страниц текста, содержащего в среднем 256 символов на каждой странице?

1) 8 2) 12 3) 244)36

  1. Для кодирования нотной записи используется 7 значков-нот. Каждая нота кодируется одним и тем же минимально возможным количеством бит. Чему равен информационный объем сообщения, состоящего из 180 нот?

1) 180 бит 2) 540 бит 3)100 байт 4) 1 Кбайт

  1. В корзине лежат 8 черных шаров и 24 белых. Сколько бит информации несет сообщение о том, что достали черный шар?

1) 2 бита 2) 4 бита 3) 8 бит 4) 24 бита

  1. В коробке лежат 64 цветных карандаша. Сообщение о том, что достали белый карандаш, несет 4 бита информации. Сколько белых карандашей было в коробке?

1) 4 2) 8 3) 16 4) 32

  1. За четверть Василий Пупкин получил 20 оценок. Сообщение о том, что он вчера получил четверку, несет 2 бита информации. Сколько четверок получил Василий за четверть?

1) 2 2) 4 3) 5 4) 10

  1. В корзине лежат черные и белые шары. Среди них 18 черных шаров. Сообщение о том, что достали белый шар, несет 2 бита информации. Сколько всего шаров в корзине?

1) 18 2) 24 3) 36 4) 48

  1. В закрытом ящике находится 32 карандаша, некоторые из них синего цвета. Наугад вынимается один карандаш. Сообщение «этот карандаш – НЕ синий» несёт 4 бита информации. Сколько синих карандашей в ящике?

1) 16 2) 24 3) 30 4) 32

  1. Некоторый алфавит содержит 4 различных символа. Сколько трехбуквенных слов можно составить из символов этого алфавита, если символы в слове могут повторяться?

1) 4 2) 16 3) 64 4) 81

  1. В некоторой стране автомобильный номер длиной 6 символов составляется из заглавных букв (всего используется 12 букв) и десятичных цифр в любом порядке. Каждый символ кодируется одинаковым и минимально возможным количеством бит, а каждый номер – одинаковым и минимально возможным количеством байт. Определите объем памяти, необходимый для хранения 32 автомобильных номеров.

1) 192 байта 2) 128 байт 3) 120 байт 4) 32 байта

  1. В некоторой стране автомобильный номер длиной 5 символов составляется из заглавных букв (всего используется 30 букв) и десятичных цифр в любом порядке. Каждый символ кодируется одинаковым и минимально возможным количеством бит, а каждый номер – одинаковым и минимально возможным количеством байт. Определите объем памяти, необходимый для хранения 50 автомобильных номеров.

1) 100 байт 2) 150 байт 3) 200 байт 4) 250 байт

  1. Световое табло состоит из светящихся элементов, каждый из которых может гореть одним из трех различных цветов. Сколько различных сигналов можно передать с помощью табло, состоящего из четырех таких элементов (при условии, что все элементы должны гореть)?

1) 4 2) 16 3) 64 4) 81

  1. В некоторой стране автомобильный номер длиной 6 символов составляется из заглавных букв (всего используется 19 букв) и десятичных цифр в любом порядке. Каждый символ кодируется одинаковым и минимально возможным количеством бит, а каждый номер – одинаковым и минимально возможным количеством байт. Определите объем памяти, необходимый для хранения 40 автомобильных номеров.

1) 120 байт 2) 160 байт 3) 200 байт 4) 240 байт

  1. В некоторой стране автомобильный номер длиной 6 символов составляется из заглавных букв (всего используется 26 букв) и десятичных цифр в любом порядке. Каждый символ кодируется одинаковым и минимально возможным количеством бит, а каждый номер – одинаковым и минимально возможным количеством байт. Определите объем памяти, необходимый для хранения 20 автомобильных номеров.

1) 160 байт 2) 120 байт 3) 100 байт 4) 80 байт

  1. Для передачи сигналов на флоте используются специальные сигнальные флаги, вывешиваемые в одну линию (последовательность важна). Какое количество различных сигналов может передать корабль при помощи четырех сигнальных флагов, если на корабле имеются флаги трех различных видов (флагов каждого вида неограниченное количество)?

  2. Для передачи сигналов на флоте используются специальные сигнальные флаги, вывешиваемые в одну линию (последовательность важна). Какое количество различных сигналов может передать корабль при помощи пяти сигнальных флагов, если на корабле имеются флаги четырех различных видов (флагов каждого вида неограниченное количество)?

  3. В велокроссе участвуют 678 спортсменов. Специальное устройство регистрирует прохождение каждым из участников промежуточного финиша, записывая его номер с использованием минимально возможного количества бит, одинакового для каждого спортсмена. Каков информационный объем сообщения, записанного устройством, после того как промежуточный финиш прошли 200 велосипедистов?

1) 200 бит 2) 200 байт 3) 220 байт 4) 250 байт

  1. В некоторой стране автомобильный номер длиной 7 символов составляется из заглавных букв (всего используется 18 букв) и десятичных цифр в любом порядке. Каждый символ кодируется одинаковым и минимально возможным количеством бит, а каждый номер – одинаковым и минимально возможным количеством байт. Определите объем памяти, необходимый для хранения 60 автомобильных номеров.

1) 240 байт 2)300 байт 3)360 байт 4) 420 байт

  1. Некоторое сигнальное устройство за одну секунду передает один из трех сигналов. Сколько различных сообщений длиной в четыре секунды можно передать при помощи этого устройства?

  1. В базе данных хранятся записи, содержащие информацию о датах. Каждая запись содержит три поля: год (число от 1 до 2100), номер месяца (число от 1 до 12) и номер дня в месяце (число от 1 до 31). Каждое поле записывается отдельно от других полей с помощью минимально возможного числа бит. Определите минимальное количество бит, необходимых для кодирования одной записи.

  1. Вася и Петя передают друг другу сообщения, используя синий, красный и зеленый фонарики. Это они делают, включая по одному фонарику на одинаковое короткое время в некоторой последовательности. Количество вспышек в одном сообщении – 3 или 4, между сообщениями – паузы. Сколько различных сообщений могут передавать мальчики?

  1. Для кодирования 300 различных сообщений используются 5 последовательных цветовых вспышек. Вспышки одинаковой длительности, для каждой вспышки используется одна лампочка определенного цвета. Лампочки скольких цветов должны использоваться при передаче (укажите минимально возможное количество)?

  1. Каждая клетка поля 8×8 кодируется минимально возможным и одинаковым количеством бит. Решение задачи о прохождении «конем» поля записывается последовательностью кодов посещенных клеток . Каков объем информации после 11 сделанных ходов? (Запись решения начинается с начальной позиции коня).

1) 64 бит 2) 9 байт 3) 12 байт 4) 96 байт

  1. Каждая клетка поля 5×5 кодируется минимально возможным и одинаковым количеством бит. Решение задачи о прохождении «конем» поля записывается последовательностью кодов посещенных клеток . Каков объем информации после 15сделанных ходов? (Запись решения начинается с начальной позиции коня).

1) 10 байт 2) 25 бит 3) 16 байт 4) 50 байт

  1. Учитель, выставляя в журнал четвертные оценки по биологии за третью четверть (3, 4, 5), обратил внимание, что комбинация из трех четвертных оценок по этому предмету у всех учеников различна. Какое может быть максимальное количество учеников в этом классе?

  2. Некоторый алфавит содержит четыре различных символа. Сколько слов длиной ровно в 4 символа можно составить из слов данного алфавита (символы в слове могут повторяться)?

  3. В некоторой стране автомобильный номер длиной 10 символов составляется из заглавных букв (всего используется 21 буква) и десятичных цифр в любом порядке. Каждый символ кодируется одинаковым и минимально возможным количеством бит, а каждый номер – одинаковым и минимально возможным количеством байт. Определите объем памяти, необходимый для хранения 81 автомобильного номера.

1) 810 байт 2) 567 байт 3) 486 байт 4) 324 байта

  1. Квадратное световое табло 22 состоит из светящихся элементов, каждый из которых может гореть одним из четырех различных цветов. Сколько различных сигналов можно передать с помощью табло, состоящего из четырех таких элементов (при условии, что все элементы должны гореть)?

  2. Световое табло состоит из светящихся элементов, каждый из которых может гореть одним из восьми различных цветов. Сколько различных сигналов можно передать с помощью табло, состоящего из трех таких элементов (при условии, что все элементы должны гореть)?

  1. В некоторой стране автомобильный номер длиной 5 символов составляется из заглавных букв (всего используется 30 букв) и десятичных цифр в любом порядке. Каждый символ кодируется одинаковым и минимально возможным количеством бит, а каждый номер – одинаковым и минимально возможным количеством байт. Определите объем памяти, необходимый для хранения 50 автомобильных номеров.

1) 100 байт 2) 150 байт 3) 200 байт 4) 250 байт

  1. В некоторой стране автомобильный номер длиной 7 символов составляется из заглавных букв (всего используется 30 букв) и десятичных цифр в любом порядке. Каждый символ кодируется одинаковым и минимально возможным количеством бит, а каждый номер – одинаковым и минимально возможным количеством байт. Определите объем памяти, необходимый для хранения 32автомобильных номеров.

1) 160 байт 2)96байт 3)224байт 4)192байт

  1. В некоторой стране автомобильный номер длиной 5 символов составляется из заглавных букв (всего используется 26 букв) и десятичных цифр в любом порядке. Каждый символ кодируется одинаковым и минимально возможным количеством бит, а каждый номер – одинаковым и минимально возможным количеством байт. Определите объем памяти, необходимый для хранения 40 автомобильных номеров.

1) 160 байт 2) 200 байт 3) 120 байт 4) 80 байт

  1. В некоторой стране автомобильный номер длиной 7 символов составляется из заглавных букв (всего используется 22 буквы) и десятичных цифр в любом порядке. Каждый символ кодируется одинаковым и минимально возможным количеством бит, а каждый номер – одинаковым и минимально возможным количеством байт. Определите объем памяти, необходимый для хранения 50 автомобильных номеров.

1) 350 байт 2)300 байт 3)250 байт 4)200байт

  1. Световое табло состоит из цветных индикаторов. Каждый индикатор может окрашиваться в четыре цвета: белый, черный, желтый и красный. Какое наименьшее количество лампочек должно находиться на табло, чтобы с его помощью можно было передать 300 различных сигналов?

1) 4 2) 5 3) 6 4) 7

  1. Одна ячейка памяти троичного компьютера (один трит) может принимать одно из трех возможных значений: 0, 1 или –1. Для хранения некоторой величины в памяти такого компьютер отвели 4 ячейки. Сколько разных значений может принимать эта величина?

1) 8 2) 16 3) 64 4) 81

  1. Объем сообщения равен 11 Кбайт. Сообщение содержит 11264 символа. Какова максимальная мощность алфавита, использованного при передаче сообщения?

1) 64 2) 128 3) 256 4) 512

  1. В некоторой стране проживает 1000 человек. Индивидуальные номера налогоплательщиков (ИНН) содержат только цифры 0, 1, 2 и 3. Какова должна быть минимальная длина ИНН, если все жители имеют разные номера?

  2. В некоторой стране проживает 200 человек. Индивидуальные номера налогоплательщиков (ИНН) содержат только цифры 2, 4, 6 и 8. Какова должна быть минимальная длина ИНН, если все жители имеют разные номера?

  3. Два сторожевых отряда, расположенных на большом расстоянии друг от друга, условились передавать друг другу сообщения с помощью сигнальных ракет красного и зеленого цвета. Сколько различных сообщений можно передать, запустить ровно 3 ракеты?

  4. Сколько сообщений мог бы передавать светофор, если бы у него одновременно горели сразу три «глаза», и каждый из них мог бы менять цвет и становиться красным, желтым или зеленым?

  5. Некоторое устройство передает в секунду один из семи сигналов. Сколько различных сообщений длиной в 3 с можно передать при помощи этого устройства?

  6. Для передачи сигналов на флоте используются специальные сигнальные флаги, вывешиваемые в одну линию (последовательность важна). Какое количество различных видов флагов надо иметь, чтобы при помощи последовательности из трех флагов можно было передать 8 различных сигналов (флагов каждого вида неограниченное количество)?

  7. В школе 800 учащихся, коды учащихся записаны в школьной информационной системе с помощью минимального количества бит. Каков информационный объем сообщения о кодах 320 учащихся, присутствующих на конференции?

1) 2560 бит 2) 100 байт 3) 6400 бит 4) 400 байт

  1. В некоторой стране автомобильный номер состоит из 8 символов. Первый символ – одна из 26 латинских букв, остальные семь – десятичные цифры. Пример номера – A1234567. Каждый символ кодируется минимально возможным количеством бит, а каждый номер – одинаковым и минимально возможным количеством байт. Определите объем памяти, необходимый для хранения 30 автомобильных номеров.

1) 180 байт 2)150 байт 3)120 байт 4)250байт

  1. Для регистрации на сайте некоторой страны пользователю необходимо придумать пароль длиной ровно 11 символов. В пароле можно использовать десятичные цифры и 12 различных символов местного алфавита, причем все буквы используются в двух начертаниях – строчные и прописные. Каждый символ кодируется одинаковым и минимально возможным количеством бит, а каждый пароль – одинаковым и минимально возможным количеством байт. Определите объем памяти, необходимый для хранения 60 паролей.

1) 720 байт 2) 660 байт 3) 540 байт 4) 600байт

  1. Для кодирования сообщений решено использовать последовательности разной длины, состоящие из знаков «+» и «-».Сколько различных сообщений можно закодировать, используя в каждом из них не менее 2-х и не более 6 знаков?

  2. Для кодирования сообщений решено использовать последовательности разной длины, состоящие из знаков «+» и «-».Сколько различных сообщений можно закодировать, используя в каждом из них не менее 3-х и не более 7 знаков?

  3. Для регистрации на сайте некоторой страны пользователю необходимо придумать пароль длиной ровно 15 символов. В пароле можно использовать десятичные цифры и 11 различных символов местного алфавита, причем все буквы используются в двух начертаниях – строчные и прописные. Каждый символ кодируется одинаковым и минимально возможным количеством бит, а каждый пароль – одинаковым и минимально возможным количеством байт. Определите объем памяти, необходимый для хранения 30 паролей.

1) 360 байт 2)450 байт 3)330 байт 4)300байт

  1. Для регистрации на сайте некоторой страны пользователю необходимо придумать пароль длиной ровно 11 символов. В пароле можно использовать десятичные цифры и 32 различных символа местного алфавита, причем все буквы используются в двух начертаниях – строчные и прописные. Каждый символ кодируется одинаковым и минимально возможным количеством бит, а каждый пароль – одинаковым и минимально возможным количеством байт. Определите объем памяти, необходимый для хранения 50 паролей.

1) 450 байт 2) 400 байт 3) 550 байт 4) 500байт

1Часто килобайт обозначают «Кб», а мегабайт – «Мб», но в демо-тестах разработчики ЕГЭ привели именно такие обозначения.

2Фактически это не другой способ решения, а более строгое обоснование предыдущего алгоритма.

3Источники заданий:

  1. Демонстрационные варианты ЕГЭ 2004-2011 гг.

  2. Гусева И.Ю. ЕГЭ. Информатика: раздаточный материал тренировочных тестов. — СПб: Тригон, 2009.

  3. Якушкин П.А., Лещинер В.Р., Кириенко Д.П. ЕГЭ 2010. Информатика. Типовые тестовые задания. — М.: Экзамен, 2010.

  4. Крылов С.С., Ушаков Д.М. ЕГЭ 2010. Информатика. Тематическая рабочая тетрадь. — М.: Экзамен, 2010.

  5. Якушкин П.А., Ушаков Д.М. Самое полное издание типовых вариантов реальных заданий ЕГЭ 2010. Информатика. — М.: Астрель, 2009.

  6. Абрамян М.Э., Михалкович С.С., Русанова Я.М., Чердынцева М.И. Информатика. ЕГЭ шаг за шагом. — М.: НИИ школьных технологий, 2010.

  7. Чуркина Т.Е. ЕГЭ 2011. Информатика. Тематические тренировочные задания. — М.: Эксмо, 2010.

  8. Крылов С.С., Лещинер В.Р., Якушкин П.А. ЕГЭ 2011. Информатика. Универсальные материалы для подготовки учащихся. — М.: Интеллект-центр, 2011.

studfiles.net

Дискретная математика - Примеры из ЕГЭ

Что нужно знать:

  • мощность алфавита M  – это количество символов в этом алфавите
  • если алфавит имеет мощность M, то количество всех возможных «слов» (символьных цепочек) длиной N (без учета смысла) равно  Q=MN
  • для двоичного кодирования (мощность алфавита M  – 2 символа) получаем известную формулу: Q=2N
  • таблица степеней двойки, она же показывает, сколько вариантов Q  можно закодировать с помощью K  бит:
К, бит 1 2 3 4 5 6 7 8 9 10
Q, вариантов 2 4 8 16 32 64 128 256 512 1024

Пример задания:

Азбука Морзе позволяет кодировать символы для сообщений по радиосвязи, задавая комбинацию точек и тире. Сколько различных символов (цифр, букв, знаков пунктуации и т. д.) можно закодировать, используя код азбуки Морзе длиной не менее четырёх и не более пяти сигналов (точек и тире)?

Решение:

  1. согласно условию, алфавит содержит только два знака – точку и тире
  2. «не менее четырёх и не более пяти сигналов» означает, что нужно определить количество всех 4- и 5-буквенных слов в двоичном алфавите
  3. количество 4-буквенных слов равно 24 = 16, а количество 5-буквенных 25 = 32
  4. поэтому общее количество 4- и 5-буквенных слов равно 16 + 32 = 48
  5. ответ: 48.

Еще пример задания:

Какое наименьшее число символов должно быть в алфавите, чтобы при помощи всевозможных трехбуквенных слов, состоящих из символов данного алфавита, можно было передать не  менее 9 различных сообщений?

Решение:

  1. здесь используется только одна формула: если алфавит имеет мощность M, то количество всех возможных «слов» длиной N  равно Q=MN
  2. в данном случае нужно закодировать 9 сигналов (Q>=9) с помощью трехбуквенных слов (N=3)
  3. таким образом, нужно найти наименьшее целое M, такое что Q=M3>=9 (куб числа не меньше 9)
  4. проще всего использовать метод подбора: при M=2 получаем 23=8<9 (с помощью трех двоичных сигналов можно закодировать только 8 вариантов),  но уже при M=3 имеем 33=27>=9, поэтому нужно брать M>=3
  5. таким образом, правильный ответ – 3.

Еще пример задания:

Каждая ячейка памяти компьютера, работающего в троичной системе счисления, может принимать три различных значения (-1, 0, 1). Для хранения некоторой величины отвели 4 ячейки памяти. Сколько различных значений может принимать эта величина?

Решение:

  1. непривычность этой задачи состоит в том, что используется троичная система
  2. фактически мы имеем дело с языком, алфавит которого содержит M=3 различных символа
  3. поэтому количество всех возможных «слов» длиной N  равно Q=3N
  4. для N=4 получаем Q=34=81
  5. таким образом, правильный ответ – 81.

Возможные ловушки:

  • если не осознать, что используется троичная (а не двоичная!) система, можно «по инерции» получить неправильный ответ

Задачи для тренировки:

  1. Световое табло состоит из лампочек. Каждая лампочка может находиться в одном из трех состояний («включено», «выключено» или «мигает»). Какое наименьшее количество лампочек должно находиться на табло, чтобы с его помощью можно было передать 18 различных сигналов?
  2. Сколько существует различных последовательностей из символов «плюс» и «минус», длиной ровно в пять символов?
  3. Шахматная доска состоит 8 столбцов и 8 строк. Какое минимальное количество бит потребуется для кодирования координат одного шахматного поля?
  4. Какое минимальное количество бит потребуется для кодирования положительных чисел, меньших 60?
  5. Двое играют в «крестики-нолики» на поле 4 на 4 клетки.  Какое количество информации (в битах) получил второй игрок, узнав ход первого игрока?
  6. В корзине лежат 8 черных шаров и 24 белых. Сколько бит информации несет сообщение о том, что достали черный шар?
  7. В коробке лежат 64 цветных карандаша. Сообщение о том, что достали белый карандаш, несет 4 бита информации. Сколько белых карандашей было в коробке?
  8. За четверть Василий Пупкин получил 20 оценок. Сообщение о том, что он вчера получил четверку, несет 2 бита информации. Сколько четверок получил Василий за четверть?
  9. В корзине лежат черные и белые шары. Среди них 18 черных шаров. Сообщение о том, что достали белый шар, несет 2 бита информации. Сколько всего шаров в корзине?
  10. В закрытом ящике находится 32 карандаша, некоторые из них синего цвета. Наугад вынимается один карандаш. Сообщение «этот карандаш – НЕ синий» несёт 4 бита информации. Сколько синих карандашей в ящике?
  11. Некоторый алфавит содержит 4 различных символа.  Сколько трехбуквенных слов можно составить из символов этого алфавита, если символы в слове могут повторяться?
  12. Световое табло состоит из светящихся элементов, каждый из которых может гореть одним из трех различных цветов. Сколько различных сигналов можно передать с помощью табло, состоящего из четырех таких элементов (при условии, что все элементы должны гореть)?
  13. Для передачи сигналов на флоте используются специальные сигнальные флаги, вывешиваемые в одну линию (последовательность важна). Какое количество различных сигналов может передать корабль при помощи четырех сигнальных флагов, если на корабле имеются флаги трех различных видов (флагов каждого вида неограниченное количество)?
  14. Для передачи сигналов на флоте используются специальные сигнальные флаги, вывешиваемые в одну линию (последовательность важна). Какое количество различных сигналов может передать корабль при помощи пяти сигнальных флагов, если на корабле имеются флаги четырех различных видов (флагов каждого вида неограниченное количество)?
  15. Некоторое сигнальное устройство за одну секунду передает один из трех сигналов. Сколько различных сообщений длиной в пять секунд можно передать при помощи этого устройства?
  16. Вася и Петя передают друг другу сообщения, используя синий, красный и зеленый фонарики. Это они делают, включая по одному фонарику на одинаковое короткое время в некоторой последовательности. Количество вспышек в одном сообщении – 3 или 4, между сообщениями – паузы. Сколько различных сообщений могут передавать мальчики?
  17. Для кодирования 300 различных сообщений используются 5 последовательных цветовых вспышек. Вспышки одинаковой длительности, для каждой вспышки используется одна лампочка определенного цвета. Лампочки скольких цветов должны использоваться при передаче (укажите минимально возможное количество)?
  18. Каждая клетка поля 8×8 кодируется минимально возможным и одинаковым количеством бит. Решение задачи о прохождении «конем» поля записывается последовательностью кодов посещенных клеток . Определите объем информации в байтах после 11 сделанных ходов? (Запись решения начинается с начальной позиции коня).
  19. Каждая клетка поля 5×5 кодируется минимально возможным и одинаковым количеством бит. Решение задачи о прохождении «конем» поля записывается последовательностью кодов посещенных клеток . Определите объем информации в байтах после 15 сделанных ходов? (Запись решения начинается с начальной позиции коня).
  20. Учитель, выставляя в журнал четвертные отметки по биологии за третью четверть (3, 4, 5), обратил внимание, что комбинация из трех четвертных отметок по этому предмету у всех учеников различна. Какое может быть максимальное количество учеников в этом классе?
  21. Некоторый алфавит содержит четыре различных символа. Сколько слов длиной ровно в 4 символа можно составить из слов данного алфавита (символы в слове могут повторяться)?
  22. Квадратное световое табло 2´2 состоит из светящихся элементов, каждый из которых может гореть одним из четырех различных цветов. Сколько различных сигналов можно передать с помощью табло, состоящего из четырех таких элементов (при условии, что все элементы должны гореть)?
  23. Световое табло состоит из светящихся элементов, каждый из которых может гореть одним из восьми различных цветов. Сколько различных сигналов можно передать с помощью табло, состоящего из трех таких элементов (при условии, что все элементы должны гореть)?
  24. Световое табло состоит из цветных индикаторов. Каждый индикатор может окрашиваться в четыре цвета: белый, черный, желтый и красный. Какое наименьшее количество лампочек должно находиться на табло, чтобы с его помощью можно было передать 300 различных сигналов?
  25. Одна ячейка памяти троичного компьютера (один трит) может принимать одно из трех возможных значений: 0, 1 или –1. Для хранения некоторой величины в памяти такого компьютер отвели 4 ячейки. Сколько разных значений может принимать эта величина? 

Назад  В начало

diskmat.ucoz.ru

Лекция № 2. Системы счисления

    1. Позиционные и непозиционные системы

Системой счисления называется метод записи чисел в виде комбинаций графических символов. Число – это некоторая абстрактная сущность для описания количества, а цифры – знаки, используемые для записи чисел. В наше время самыми распространёнными являются арабские цифры, менее распространены римские цифры. Система римских цифр основана на употреблении особых знаков для десятичных разрядов: I=1, X=10, C=100, M=1000 и их половин: V=5, L=50, D=500. Существует множество других способов записи чисел. Например, древние греки использовали для этой цели буквы своего алфавита, а древние шумеры – клинописные знаки. Существуют позиционные и непозиционные системы счисления.

Позиционная система счисления – система записи чисел в виде последовательности символов, в которой численное значение каждого символа зависит от его положения в записи.

Примером позиционной системы является хорошо известная десятичная система счисления. Примером непозиционной системы – римская система. Выполнение арифметических действий над числами в непозиционной системе весьма неудобно. Поэтому позиционные системы в настоящее время получили наибольшее распространение.

Изобретение позиционной системы приписывается шумерам и вавилонянам. Затем она была развита индусами. В средневековой Европе позиционная десятичная система появилась благодаря итальянским купцам, которые заимствовали её у мусульман. В 9 веке великий арабский математик Мухаммед ибн Мусе Аль Хорезми впервые описал десятичную систему исчисления и правила выполнения простых арифметических действий в ней. В 12 веке его работы были переведены на латинский язык, благодаря чему Европа смогла познакомиться с этим изобретением человеческого ума.

    1. Десятичная система

Существуют различные позиционные системы исчисления, отличающиеся между собой количеством используемых знаков. Чтобы различать числа в разных системах исчисления, в конце числа ставят индекс – символ системы. Например, запись означает обычное число 483,56 в десятичной системе счисления, а записьозначает совсем другое число (хотя и похожее по виду) вшестнадцатеричной системе счисления (в десятичной оно равно 1155,335938). Если из контекста понятно, что используется только десятичная система (или только шестнадцатеричная, или какая-нибудь другая), то при записи числа индекс обычно опускают.

Десятичная система использует десять различных знаков: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 – которые обозначают натуральные числа в порядке их возрастания от нуля до девяти. Число 10 является основанием десятичной системы. Оно не имеет специального знака, а обозначается с помощью двух первых символов этой системы.

Например, запись 483,56 в десятичной системе означает, что данное число складывается из четырех сотен (), восьми десяток (), трех единиц (), пяти десятых частей единицы () и шести сотых частей единицы (). Другими словами, мы можем записать:

. (2.1)

    1. Двоичная система

Двоичная (бинарная) система счисления является самой простой из всех позиционных систем. Она содержит только два символа 0 и 1, и используется в компьютерной технике благодаря своей простоте и высокой надежности. Двоичная система была изобретена великим немецким ученым Готфридом Вильгельмом Лейбницем (1646-1716), который использовал ее в созданной им механической счетной машине. В первом столбце табл. 2.1 приведены десятичные числа, а во втором – соответствующие им двоичные числа.

Таблица 2.1

Десятичное

число

Бинарный код

Код Грея

Десятичное число

0

1

2

3 = 2 + 1

4

5 = 4 +1

6 = 4 + 2

7 = 4 + 2 + 1

8

9 = 8 + 1

10 = 8 + 2

11 = 8 + 2 + 1

12 = 8 + 4

13 = 8 + 4 + 1

14 = 8 + 4 + 2

15 = 8 + 4 + 2 + 1

0000

0001

0010

0011

0100

0101

0110

0111

1000

1001

1010

1011

1100

1101

1110

1111

0000

0001

0011

0010

0110

0111

0101

0100

1100

1101

1111

1110

1010

1011

1001

1000

0

1

2 = 3 – 1

3

4 = 7 – 3

5 = 7 – 3 +1

6 = 7 – 1

7

8 = 15 – 7

9 = 15 – 7 + 1

10 = 15 – 7 + 3 – 1

11 = 15 – 7 + 3

12 = 15 – 3

13 = 15 – 3 + 1

14 = 15 – 1

15

Предположим, что нам нужно преобразовать двоичное число с дробной частью 1100,1011 в более привычное десятичное число. В табл. 2.2 показано, как осуществляется такое преобразование.

Таблица 2.2

Двоичное число

Десятичное

число

Целая часть

Дробная часть

1

1

0

0,

1

0

1

1

+

+

+

+

+

+

+

=

Обратное преобразование десятичного числа d в двоичное число (бинарный код) осуществляется в соответствии со следующим алгоритмом. Присваиваем числу d индекс (), и ищем целое число, удовлетворяющее неравенству

, . (2.2)

Если , то задача выполнена – искомое двоичное число содержит единицу в старшем разряде инулей за ней.

Если , то вычисляем разность, и ищем для нее соответствующее число, пользуясь формулой (2.2) с. Операцию вычисления разницыи нахожденияповторяем до тех пор, пока при каком-либоне выполнится условие:.

Очевидно, что (т.е.). При построении искомого бинарного числа используют правило: численные значениясоответствуют разрядам бинарного кода, в котором стоят единицы. Остальные разряды заполняются нулями.

Используем это правило для нахождения бинарного кода десятичного числа 108,5. Согласно формуле (2.2), получаем: .

Искомое двоичное число равно: 1101100,1. Первая единица слева в записи числа соответствует 6 разряду, вторая за ней – пятому разряду. Четвертого разряда нет, поэтому за двумя первыми единицами записываем ноль. Третий и второй разряды есть – после нуля записываем две единицы. Единичного и нулевого разрядов также нет – после двух единиц записываем два нуля. Минус первый разряд есть – поэтому после запятой записываем единицу.

Арифметические операции в двоичной системе осуществляются так же, как и в десятичной («столбиком»). Например, возьмем числа 0111 () и 0101 (), и произведем операции сложения и умножения:

,

В результате получим 1100 () и 100011 (), что и следовало ожидать.

    1. Код Грея

Помимо двоичных чисел на практике применяются и другие коды, использующие два знака: 0 и 1. В этом разделе мы познакомимся с кодом Грея. При сортировке данных естественным представлением является обычное целочисленное описание, поскольку среди десяти цифр каждая на 1 больше предыдущей. При переходе к двоичному описанию эта естественность исчезает. Рассмотрим битовое представление чисел 6, 7, 8 и 9:

0110 0111 1000 1001.

Числа 6 и 7, а также 8 и 9 отличаются друг от друга на один бит. Однако числа 7 и 8 не имеют между собой ничего общего! Это свойство представления может вызвать большие проблемы при решении задач, требующих систематизации числовых данных. Для решения проблемы неоднородности представления используется код Грея.

Код Грея – система нумерации, в которой два соседних значения различаются только в одном разряде.

Код Грея показан в третьем столбце табл. 2.1. Наиболее часто на практике применяется рефлексивный двоичный код Грея, хотя в общем случае существует бесконечное множество кодов Грея для систем счисления с любым основанием. В большинстве случаев, под термином «код Грея» понимают именно рефлексивный бинарный код Грея. Название рефлексный (отражённый) двоичный код происходит от факта, что вторая половина значений в коде Грея эквивалентна первой половине, только в обратном порядке, за исключением старшего бита, который просто инвертируется. Если же разделить каждую половину ещё раз пополам, свойство будет сохраняться для каждой из половин половины и т.д.

Код Грея был разработан Фрэнком Греем, исследователем Bell Labs. Он использовал этот код в своей импульсной системе связи (на него был получен патент № 2632058).

При преобразовании бинарного кода в десятичное число мы умножаем ноль или единицу на , где – номер позиции бита в бинарном коде (; и т.д.), а затем суммируем полученные результаты.

При преобразовании кода Грея в десятичное число мы умножаем ноль или единицу на (), где – номер позиции бита в коде Грея (; и т.д.). Дальше вычитаем из результата, соответствующего старшей единице, результат, соответствующий единице меньшего разряда, прибавляем результат, соответствующий единице еще более меньшего разряда и т.д. (смотри последний столбец табл. 2.1).

    1. Троичная система счисления

Троичная система счисления – позиционная система счисления с целочисленным основанием равным 3. Она существует в двух вариантах: несимметричная и симметричная троичные системы. Несимметричная система обычно использует символы: 0, 1 и 2. Симметричная: –1, 0, +1. В табл. 2.3 показаны десятичные числа и соответствующие им числа в троичной системе счисления.

Таблица 2.3

Десятичная

-3

-2

-1

0

1

2

3

4

5

6

7

8

9

Троичная

несимметричная

-10

-2

-1

0

1

2

10

11

12

20

21

22

100

Троичная

симметричная

11

100

Элементы троичной системы существовали еще у древних шумеров. Полноценную симметричную троичную систему впервые предложил итальянский математик Фибоначчи (Леонардо Пизанский) (1170–1250). Симметричная троичная система позволяет изображать отрицательные числа, не используя отдельный знак минуса.

В момент зарождения компьютерной техники троичная система составляла серьезную конкуренцию двоичной системе. Ее преимущество заключается в том, что она обеспечивает наибольшую плотность записи чисел по сравнению с другими целочисленными системами. Поясним это на следующем примере.

Предположим, что в компьютере мы используем числа в позиционной системе с целочисленным основанием . При этом каждое число имеет максимумразрядов. Значит, для сохранения числа в памяти компьютера требуетсяячеек памяти, причем каждая ячейка должна быть способна находиться всостояниях. Аппаратные затраты составляют:.

Используя систему с основанием иразрядов, мы способны представитьразличных чисел. Эффективность применяемой в компьютере системы счисления можно оценить с помощью следующего числового критерия:

. (2.3)

Чем больше чисел мы можем представить в данной системе счисления, и чем меньше при этом аппаратные затраты, тем эффективнее система по данному критерию.

Чаще критерий эффективности используют в такой форме

. (2.4)

Практически критерий (2.4) равнозначен критерию (2.3), однако удобнее в использовании. Равнозначность основана на факте: если , то. График функциипоказан на рис. 2.1.

Рис.2.1. График функции

Эта функция имеет максимум для . При целых значенияхмаксимум достигается для= 3.

;

;

;

.

Таким образом, наиболее эффективной по критерию (2.4) является троичная система счисления (используемая в троичных компьютерах), следом за которой идут двоичная система счисления (традиционно используемая в большинстве распространённых компьютеров) и четверичная система счисления.

В 1958 году Николай Петрович Брусенцов из МГУ построил первую серийную электронную троичную ЭВМ «Сетунь» на ячейках из ферритдиодных магнитных усилителей переменного тока, работавших в двухбитном троичном коде, четвёртое состояние двух битов не использовалось. В 1970 году Брусенцов построил вторую серийную электронную троичную ЭВМ «Сетунь-70».

В 1973 году в США впервые был создан экспериментальный троичный компьютер, а в 2008 году там же была построена троичная цифровая компьютерная система TCA2 на 1484-х интегральных транзисторах.

Тем не менее, в настоящее время двоичные компьютеры доминируют в компьютерной технике благодаря своей простоте и высокой надежности.

    1. Восьмеричная и шестнадцатеричная системы счисления

Позиционную систему счисления можно построить по любому основанию. Однако наибольшее практическое значение имеют: двоичная, десятичная, восьмеричная и шестнадцатеричная. Причем, последние две используются, в основном, не для вычислений, а для представления двоичного кода в форме, удобной для человека.

В табл. 2.4 представлено 24-битное двоичное слово и соответствующие ему 8-ричный и 16-ричный коды.

Таблица 2.4

Двоичный код

1011001111000101100010112

Восьмеричный код

547426138

Шестнадцатеричный код

B3C58B16

Очевидно, что человеку легче воспринимать двоичный код в форме 8-ричного или 16-ричного кодов. При использовании 8-ричного кода три бита двоичного слова преобразуются в один символ. При использовании 16-ричного слова каждые четыре бита двоичного слова преобразуются в один символ. В табл. 2.5 показано, как осуществляется это преобразование. Как можно видеть, шестнадцатеричные числа обозначаются с помощью 10 арабских цифр и шести букв латинского алфавита.

Таблица 2.5

8-ричное

число

Бинарный код

16-ричное

число

Бинарный код

0

1

2

3

4

5

6

7

000

001

010

011

100

101

110

111

0

1

2

3

4

5

6

7

8

9

A

B

C

D

E

F

0000

0001

0010

0011

0100

0101

0110

0111

1000

1001

1010

1011

1100

1101

1110

1111

studfiles.net

Тема : Кодирование сообщений. Комбинаторика

Азбука Морзе позволяет кодировать символы для сообщений по радиосвязи, задавая комбинацию точек и тире. Сколько различных символов (цифр, букв, знаков пунктуации и т. д.) можно закодировать, используя код азбуки Морзе длиной не менее четырёх и не более пяти сигналов (точек и тире)?

Какое наименьшее число символов должно быть в алфавите, чтобы при помощи всевозможных трехбуквенных слов, состоящих из символов данного алфавита, можно было передать не менее 9 различных сообщений?

Каждая ячейка памяти компьютера, работающего в троичной системе счисления, может принимать три различных значения (-1, 0, 1). Для хранения некоторой величины отвели 4 ячейки памяти. Сколько различных значений может принимать эта величина?

  • Световое табло состоит из лампочек. Каждая лампочка может находиться в одном из трех состояний («включено», «выключено» или «мигает»). Какое наименьшее количество лампочек должно находиться на табло, чтобы с его помощью можно было передать 18 различных сигналов?

  • Сколько существует различных последовательностей из символов «плюс» и «минус», длиной ровно в пять символов?

  • Шахматная доска состоит 8 столбцов и 8 строк. Какое минимальное количество бит потребуется для кодирования координат одного шахматного поля?

  • Какое минимальное количество бит потребуется для кодирования положительных чисел, меньших 60?

  • Двое играют в «крестики-нолики» на поле 4 на 4 клетки. Какое количество информации (в битах) получил второй игрок, узнав ход первого игрока?

  • В корзине лежат 8 черных шаров и 24 белых. Сколько бит информации несет сообщение о том, что достали черный шар?

  • В коробке лежат 64 цветных карандаша. Сообщение о том, что достали белый карандаш, несет 4 бита информации. Сколько белых карандашей было в коробке?

  • За четверть Василий Пупкин получил 20 оценок. Сообщение о том, что он вчера получил четверку, несет 2 бита информации. Сколько четверок получил Василий за четверть?

  • В корзине лежат черные и белые шары. Среди них 18 черных шаров. Сообщение о том, что достали белый шар, несет 2 бита информации. Сколько всего шаров в корзине?

  • В закрытом ящике находится 32 карандаша, некоторые из них синего цвета. Наугад вынимается один карандаш. Сообщение «этот карандаш – НЕ синий» несёт 4 бита информации. Сколько синих карандашей в ящике?

  • Некоторый алфавит содержит 4 различных символа. Сколько трехбуквенных слов можно составить из символов этого алфавита, если символы в слове могут повторяться?

  • Световое табло состоит из светящихся элементов, каждый из которых может гореть одним из трех различных цветов. Сколько различных сигналов можно передать с помощью табло, состоящего из четырех таких элементов (при условии, что все элементы должны гореть)?

  • Для передачи сигналов на флоте используются специальные сигнальные флаги, вывешиваемые в одну линию (последовательность важна). Какое количество различных сигналов может передать корабль при помощи четырех сигнальных флагов, если на корабле имеются флаги трех различных видов (флагов каждого вида неограниченное количество)?

  • Для передачи сигналов на флоте используются специальные сигнальные флаги, вывешиваемые в одну линию (последовательность важна). Какое количество различных сигналов может передать корабль при помощи пяти сигнальных флагов, если на корабле имеются флаги четырех различных видов (флагов каждого вида неограниченное количество)?

  • Некоторое сигнальное устройство за одну секунду передает один из трех сигналов. Сколько различных сообщений длиной в пять секунд можно передать при помощи этого устройства?

  • Вася и Петя передают друг другу сообщения, используя синий, красный и зеленый фонарики. Это они делают, включая по одному фонарику на одинаковое короткое время в некоторой последовательности. Количество вспышек в одном сообщении – 3 или 4, между сообщениями – паузы. Сколько различных сообщений могут передавать мальчики?

  • Для кодирования 300 различных сообщений используются 5 последовательных цветовых вспышек. Вспышки одинаковой длительности, для каждой вспышки используется одна лампочка определенного цвета. Лампочки скольких цветов должны использоваться при передаче (укажите минимально возможное количество)?

  • Каждая клетка поля 8×8 кодируется минимально возможным и одинаковым количеством бит. Решение задачи о прохождении «конем» поля записывается последовательностью кодов посещенных клеток . Определите объем информации в байтах после 11 сделанных ходов? (Запись решения начинается с начальной позиции коня).

  • Каждая клетка поля 5×5 кодируется минимально возможным и одинаковым количеством бит. Решение задачи о прохождении «конем» поля записывается последовательностью кодов посещенных клеток . Определите объем информации в байтах после 15 сделанных ходов? (Запись решения начинается с начальной позиции коня).

  • Учитель, выставляя в журнал четвертные отметки по биологии за третью четверть (3, 4, 5), обратил внимание, что комбинация из трех четвертных отметок по этому предмету у всех учеников различна. Какое может быть максимальное количество учеников в этом классе?

  • Некоторый алфавит содержит четыре различных символа. Сколько слов длиной ровно в 4 символа можно составить из слов данного алфавита (символы в слове могут повторяться)?

  • Квадратное световое табло 22 состоит из светящихся элементов, каждый из которых может гореть одним из четырех различных цветов. Сколько различных сигналов можно передать с помощью табло, состоящего из четырех таких элементов (при условии, что все элементы должны гореть)?

  • Световое табло состоит из светящихся элементов, каждый из которых может гореть одним из восьми различных цветов. Сколько различных сигналов можно передать с помощью табло, состоящего из трех таких элементов (при условии, что все элементы должны гореть)?

  • Световое табло состоит из цветных индикаторов. Каждый индикатор может окрашиваться в четыре цвета: белый, черный, желтый и красный. Какое наименьшее количество лампочек должно находиться на табло, чтобы с его помощью можно было передать 300 различных сигналов?

  • Одна ячейка памяти троичного компьютера (один трит) может принимать одно из трех возможных значений: 0, 1 или –1. Для хранения некоторой величины в памяти такого компьютер отвели 4 ячейки. Сколько разных значений может принимать эта величина?

  • В некоторой стране проживает 1000 человек. Индивидуальные номера налогоплательщиков (ИНН) содержат только цифры 0, 1, 2 и 3. Какова должна быть минимальная длина ИНН, если все жители имеют разные номера?

  • В некоторой стране проживает 200 человек. Индивидуальные номера налогоплательщиков (ИНН) содержат только цифры 2, 4, 6 и 8. Какова должна быть минимальная длина ИНН, если все жители имеют разные номера?

  • Два сторожевых отряда, расположенных на большом расстоянии друг от друга, условились передавать друг другу сообщения с помощью сигнальных ракет красного и зеленого цвета. Сколько различных сообщений можно передать, запустить ровно 3 ракеты?

  • Сколько сообщений мог бы передавать светофор, если бы у него одновременно горели сразу три «глаза», и каждый из них мог бы менять цвет и становиться красным, желтым или зеленым?

  • Некоторое устройство передает в секунду один из семи сигналов. Сколько различных сообщений длиной в 3 с можно передать при помощи этого устройства?

  • Для передачи сигналов на флоте используются специальные сигнальные флаги, вывешиваемые в одну линию (последовательность важна). Какое количество различных видов флагов надо иметь, чтобы при помощи последовательности из трех флагов можно было передать 8 различных сигналов (флагов каждого вида неограниченное количество)?

  • Для кодирования сообщений решено использовать последовательности разной длины, состоящие из знаков «+» и «-». Сколько различных сообщений можно закодировать, используя в каждом из них не менее 2-х и не более 6 знаков?

  • Для кодирования сообщений решено использовать последовательности разной длины, состоящие из знаков «+» и «-». Сколько различных сообщений можно закодировать, используя в каждом из них не менее 3-х и не более 7 знаков?

  • Азбука Морзе позволяет кодировать символы для сообщений по радиосвязи, задавая комбинацию точек и тире. Сколько различных символов (цифр, букв, знаков пунктуации и т. д.) можно закодировать, используя код азбуки Морзе длиной не менее двух и не более четырёх сигналов (точек и тире)?

  • Азбука Морзе позволяет кодировать символы для сообщений по радиосвязи, задавая комбинацию точек и тире. Сколько различных символов (цифр, букв, знаков пунктуации и т. д.) можно закодировать, используя код азбуки Морзе длиной не более пяти сигналов (точек и тире)?

  • Азбука Морзе позволяет кодировать символы для сообщений по радиосвязи, задавая комбинацию точек и тире. Сколько различных символов (цифр, букв, знаков пунктуации и т. д.) можно закодировать, используя код азбуки Морзе длиной не менее трёх и не более пяти сигналов (точек и тире)?

  • На световой панели в ряд расположены 6 лампочек. Каждая лампочка может гореть красным цветом, желтым цветом или зеленым цветом. Сколько различных сигналов можно передать с помощью панели (все лампочки должны гореть, порядок цветов имеет значение)?

  • Сколько есть различных символьных последовательностей длины от одного до четырёх в трёхбуквенном алфавите {A, B, C}?

  • gigabaza.ru

    Троичная система счисления

    Троичная система счисления

    Автор: Кухаренко Егор,

    ученик 9А класса

    МОУ-СОШ №2

    г. Асино Томской Области

    Руководитель: Сарычева М.О. ,

    учитель информатики

    I квалификационной категории

    Содержание

    • Введение

    • Задача о гирях

    • Немного о троичной логике

    • Троичная система счисления

    • Задания ЕГЭ

    • Задачи, разработанные мной

    • Заключение

    • Рекомендация

    • Список литературы

    Введение

    Среди позиционных систем счисления наиболее известными являются десятичная и двоичная системы счисления. Это обусловлено их практическим применением в повседневной жизни и технических устройствах.

    Однако, существует система счисления, которая также была реализована в технике и которая, в последнее время, вызывает пристальное внимание создателей квантовых и оптических компьютеров. Это – троичная система счисления.

    В данной работе мною были поставлены следующие цели:
    • Рассмотреть исторические корни данного вопроса;

    • Познакомится с троичной логикой и троичной системой счисления;

    • Решить задания ЕГЭ и попробовать придумать собственные задачи по троичной системе счисления.

    Задача о гирях

    «Задача о поиске наилучшей системы гирь для взвешивания на рычажных весах" или просто "задача о гирях« была разработана известным итальянским математиком Леонардо Фибоначчи .

    Суть задачи:

    Суть задачи:

    при какой системе гирь, имея их по одной, можно взвесить всевозможные грузы от 0 до максимального груза Gmax, чтобы значение максимального груза Gmax было бы наибольшим среди всех возможных вариаций?

    Клод Гаспар Баше

    Клод Гаспар Баше (1581 – 1638 ) – французский математик, поэт, лингвист, переводчик. Один из первых членов Французской академии.

    Баше родился в состоятельной дворянской семье, рано лишился обоих родителей. Учился в Реймсе в иезуитском колледже .

    Дмитрий Иванович Менделеев

    Дмитрий Иванович Менделеев (1834 – 1907), великий русский химик . Родился в Тобольскe, в семье директора гимназии. После окончания Тобольской гимназии был принят на отделение естественных наук физико-математического факультета Главного педагогического института в Петербурге.

    Менделеев в 1856 году защитил в Петербурге магистерскую диссертацию и стал читать курс органической химии в Петербургском университете.

    Леонардо Фибоначчи

    Леонардо Пизанский (около 1170 – около 1250) – первый крупный математик средневековой Европы. Наиболее известен под прозвищем Фибоначчи. По арабским переводам он ознакомился с достижениями античных и индийских математиков. На основе усвоенных им знаний Фибоначчи написал ряд математических трактатов, представляющих собой выдающееся явление средневековой западноевропейской науки.

    Немного о Троичной логике…

    Троичная система счисления -

    • позиционная

    • с основанием 3

    Троичная симметричная система счисления

    • Для записи чисел используются три цифры -1, 0, 1 или знаки -, 0, +

    • Вес соседних разрядов различается в три раза (разряд единиц, разряд троек, разряд девяток, …)

    + 0 +

    • + 0 +

    • + – –

    • + – – 0

    1) + 0 + = 1*32 + 0*31 +1*30 = 1010

    1) + 0 + = 1*32 + 0*31 +1*30 = 1010

    2) + – – = 1*32 + (-1)*31 +(-1)*30=510

    3) + – – 0 = 1*33 + (-1)*32 +(-1)*31+0*30 = 1510

    Изменение знака числа в симметричном коде равносильно замене всех «–» на «+» и наоборот.

    Изменение знака числа в симметричном коде равносильно замене всех «–» на «+» и наоборот.

    Например: 7 = + – +, следовательно –7 = – + –. (Проверь это, записав закодированное число в развернутой форме и вычислив сумму ряда).

    А как записать –10, –8, –14?

    Проверь себя:

    10 = + 0 + -10 = – 0 –

    8 = + 0 – -8 = – 0 +

    14 = + – – – -14 = – + + +

    Задания ЕГЭ

    • Одна ячейка памяти троичной ЭВМ (компьютера, основанного на троичной системе счисления) может принимать одно из трёх возможных состояний. Для хранения некоторой величины отвели 4 ячейки памяти. Сколько различных значений может принимать эта величина?

    • Световое табло состоит из светящихся элементов, каждый из которых может гореть одним из трёх различных цветов. Сколько различных сигналов можно передать при помощи табло, состоящего из пяти таких элементов (при условии, что все элементы должны гореть)?

    Одна ячейка памяти троичной ЭВМ (компьютера, основанного на троичной системе счисления) может принимать одно из трёх возможных состояний. Для хранения некоторой величины отвели 4 ячейки памяти. Сколько различных значений может принимать эта величина?

    • Одна ячейка памяти троичной ЭВМ (компьютера, основанного на троичной системе счисления) может принимать одно из трёх возможных состояний. Для хранения некоторой величины отвели 4 ячейки памяти. Сколько различных значений может принимать эта величина?

    Световое табло состоит из светящихся элементов, каждый из которых может гореть одним из трёх различных цветов. Сколько различных сигналов можно передать при помощи табло, состоящего из пяти таких элементов (при условии, что все элементы должны гореть)?

    • Световое табло состоит из светящихся элементов, каждый из которых может гореть одним из трёх различных цветов. Сколько различных сигналов можно передать при помощи табло, состоящего из пяти таких элементов (при условии, что все элементы должны гореть)?

    Предлагаю решить задачи, придуманные мной

    • Светомузыкальная установка состоит из нескольких элементов, каждый из которых может принимать 3 разных значения. Из скольких элементов состоит установка, если она может передать 729 различных сочетаний?

    • Сколько значений может принимать каждый из 5 светодиодов, если они могут передать 243 разных цветовых сочетаний?

    • Для хранения информации отведено 2 ячейки памяти, каждая из которых может принимать 3 разных значения. В каком количестве сочетаний может кодироваться эта информация?

    • Для хранения информации отведено n ячеек, каждая из которых может принимать 3 разных значения. Какое минимальное количество ячеек необходимо для кодирования информации 700 различными способами?

    Светомузыкальная установка состоит из нескольких элементов, каждый из которых может принимать 3 разных значения. Из скольких элементов состоит установка, если она может передать 729 различных сочетаний?

    • Светомузыкальная установка состоит из нескольких элементов, каждый из которых может принимать 3 разных значения. Из скольких элементов состоит установка, если она может передать 729 различных сочетаний?

    2. Сколько значений может принимать каждый из 5 светодиодов, если они могут передать 243 разных цветовых сочетаний?

    2. Сколько значений может принимать каждый из 5 светодиодов, если они могут передать 243 разных цветовых сочетаний?

    4. Для хранения информации отведено n ячеек, каждая из которых может принимать 3 разных значения. Какое минимальное количество ячеек необходимо для кодирования информации 700 различными способами?

    4. Для хранения информации отведено n ячеек, каждая из которых может принимать 3 разных значения. Какое минимальное количество ячеек необходимо для кодирования информации 700 различными способами?

    Заключение

    На протяжении веков ученые изучали и разрабатывали теорию троичной логики и троичной системы счисления. В своих исследованиях они указывали на преимущества троичной логики над двоичной. В настоящее время интерес в многозначной логике значительно возрос, особенно у создателей квантовой и оптической компьютерной техники.

    В данной работе содержатся сведения из истории возникновения троичной логики и троичной системы счисления, рассмотрены некоторые вопросы касающиеся теории троичной системы счисления.

    Особый интерес для меня представляло решение заданий для подготовки к сдаче единого государственного экзамена. А также работа над формулированием и решением собственных задач.

    Рекомендация

    Данная презентация может использоваться в качестве дополнительного материала на уроках информатики при изучении темы «Системы счисления», на факультативных занятиях и спецкурсах по подготовке к ЕГЭ. Как правило, задания на троичную систему счисления, предложенные в материалах по подготовке к ЕГЭ, вызывают затруднения у обучающихся. Рассмотренные теоретические вопросы и практические задания помогут преодолеть возникающие затруднения.

    Работа выполнена учеником 9 класса Кухаренко Егором. Хотелось бы отметить большую самостоятельность обучающегося в подборе материала по плану, составленному с помощью учителя, а также исключительную самостоятельность в составлении и решении задач.

    Список литературы

    • «Универсальные материалы для подготовки учащихся. Информатика», под ред. В.Р.Лещинера, ФИПИ, «Интеллект-Центр», 2010г.

    rpp.nashaucheba.ru

    Замена двоичной логики — увеличит ли это производительность? / Хабр

    Наверняка на хабре уже немало постов на эту тему. Тем не менее, я попытаюсь рассказать свою точку зрения на всё это…

    Однажды я прочитал в интернете про троичную систему счисления и заинтересовался. Меня мучил вопрос, а нельзя использовать в основе компьютера симметричную троичную систему счисления (СС), и даже вдруг это увеличит производительность компьютера? Мне казалось, что это возможно, и я жаждал это проверить.

    Информация:Троичная система счисления — позиционная система счисления с целочисленным основанием, равным 3. Существует в двух вариантах: несимметричная и симметричная. В несимметричной троичной системе счисления чаще применяются цифры {0,1,2}, а в симметричной троичной системе счисления знаки {−,0,+}, {−1,0,+1}. У некоторых людей эта логика вызывает затруднения. Они говорят, например, приведите пример подобной логики в жизни. Человек, немного подумавший над этой логикой поймет, что она более жизненна чем двоичная. Обычный пример троичной логики в жизни связан с постоянным током: ток движется в одну сторону, в другую сторону, его нет.

    Оказалось, что симметричная троичная система счисления использовалась давным-давно для решения «задачи о гирях», использовалась в компьютере Сетунь, построенном в 50-е годы в МГУ. С 2008 года в университете « California Polytechnic State University of San Luis Obispo» функционирует цифровая компьютерная система TCA2, основанная на троичной системе счисления.

    В чем же плюсы троичной СС над двоичной? Рассмотрим эти плюсы:

    Меньше разрядов

    (Написано разжевано, чтобы каждый смог понять суть этого пункта) Возьмем число 10 в десятичной СС и переведем его в двоичную СС, получим 1010, переведем в троичную симметричную СС, получим +0+, ну а если в троичную несимметричную СС, то получим 101. Из этого мы видим, что в некоторых числах в троичной симметричной и несимметричной СС-ах меньше разрядов, чем в двоичной СС. Возьмем число 5 в десятичной СС и переведем его в двоичную СС, получим 101, переведем в троичную симметричную СС, то получим +--, ну а если в троичную несимметричную СС, то получим 12. Из этого мы видим, что в некоторых числах в троичной несимметричной СС меньше разрядов, чем в двоичной и троичной симметричной СС-ах.

    Емкость

    Троичная СС вмещает больший диапазон чисел, т.к. 3^n>2^n (где n-натуральное число). Например, если n=9, то 3^9=19683>2^9=512. 3.

    Экономичность системы счисления

    Экономичность системы счисления — запас чисел, который можно записать в данной системе с помощью определенного количества знаков. Чем больше запас тем экономичнее система. По затратам числа знаков (в трёхразрядном десятичном числе 3*10=30 знаков) наиболее экономична из позиционных показательных несимметричных систем счисления. Обозначим p основание системы счисления, n количество требуемых знаков. Тогда получим n/p разрядов требуемых для записи этого набора знаков в заданной системе счисления, а количество чисел которое при этом можно записать будет равно pn/p.

    Мы рассмотрели троичную арифметику, теперь затронем логику:

    В чем же проблемы двоичной логики? 1.Мощности компьютера, основанного на двоичной логике, не всегда хватает. Приведем пример. Одна из наиболее сложных систем защиты – криптосистема RSA. Вскрытие шифра RSA с длиной ключа 1024 бита (такая длина часто используется в информационных системах) займет в лучшем случае — при проведении распределенных вычислений на тысячах мощных ПК — не менее пятнадцати лет, а к тому времени данная система шифровки перестанет быть востребованной. Докажем математически какая система счисления будет наилучшей для максимальной мощности и емкости памяти. Для этого рассмотрим функцию f(p)=p^(n/p), в которой p – основание системы счисления, а n – количество требуемых знаков. Тогда получим n/p разрядов требуемых для записи этого набора знаков в заданной системе счисления, а количество чисел, которое при этом можно записать, будет равно pn/p

    f(p)=p^(n/p) Для того, чтобы определить максимальное значение функции, найдем ее производную: ln f = ln p^(n/p) ln f =n/p* ln p ...(Я не буду приводить здесь всю математику) n*p^(n/p-2) никогда не будет равно 0 => (1 — ln⁡ p)=0, ln p = 1, p = e e = 2,71, а ближайшее целое число к нему – это три. Значит, в этом плане лучшая система с целочисленным основанием — троичная.

    Самое вкусненькое — рассмотрим троичные логические операции:

    1.Отрицание

    2.Конъюнкция — логическое И

    3.Дизъюнкция — логическое ИЛИ

    4.Операция Выбора. Эта операция существует только для троичной логики. Таблица истинности каждой из этих трёх операций содержит везде „-“, кроме единственного значения, которое ею можно выбрать.

    5.Модификация. Полное название этих одноместных операций: увеличение на единицу по модулю три (INC) и уменьшение на единицу по модулю три (DEC). Увеличение на единицу по модулю три – это циклическое прибавление единицы. Здесь видны и прежде знакомые вам логические операции из двоичной логики, но добавились и новые…

    Квантовые компьютеры

    Квантовый компьютер — вычислительное устройство, работающее на основе квантовой механики. Квантовый компьютер принципиально отличается от классических компьютеров, работающих на основе классической механики. Благодаря огромной скорости разложения на простые множители, квантовый компьютер позволит расшифровывать сообщения, зашифрованные при помощи популярного асимметричного криптографического алгоритма RSA. До сих пор этот алгоритм считается сравнительно надёжным, так как эффективный способ разложения чисел на простые множители для классического компьютера в настоящее время неизвестен. Для того, например, чтобы получить доступ к кредитной карте, нужно разложить на два простых множителя число длиной в сотни цифр. Даже для самых быстрых современных компьютеров выполнение этой задачи заняло бы больше времени, чем возраст Вселенной, в сотни раз. Благодаря алгоритму Шора эта задача становится вполне осуществимой, если квантовый компьютер будет построен. Канадская компания D-Wave заявила в феврале 2007 года о создании образца квантового компьютера, состоящего из 16 кубит. Это устройство работает на кубитах — квантовых аналогах битов. Но можно построить компьютеры не на битах, а на кутритах — аналогах трита в квантовом компьютере. Кутрит (квантовый трит) — квантовая ячейка, имеющая три возможных состояния. Подлинное новаторство метода Ланьона в том, что, используя в универсальных квантовых вентилях кутриты вместо кубитов, исследователи могут существенно снизить количество необходимых вентилей. Ланьон утверждает, что компьютер, который в обычном случае использовал бы 50 традиционных квантовых вентилей, сможет обойтись всего девятью, если будет основан на троичном представлении. Также, согласно некоторым исследованиям, использование кутритов вместо кубитов позволит упростить реализацию квантовых алгоритмов и компьютеров.

    Итог: В конечном итоге видно, что троичная симметричная система лучше двоичной системы в некоторых показателях, но не сильно выигрывает. Но с пришествием квантовых компьютеров троичные вычисления получили новую жизнь. Универсальные квантовые логические вентили — краеугольный камень новорожденных квантовых вычислительных систем — требует сотни вентилей для завершения одной полезной операции. Квантовый компьютер канадской компании D-Wave, анонсированный в прошлом году, состоит всего из 16 квантовых битов — кубитов — минимум, необходимый для управляемого вентиля «NOT». Использование в квантовом компьютере кутритов нужно было бы намного меньше вентилей для завершения одной операции. Я думаю, если бы началось производство и тестирование таких компьютеров, то результаты были бы лучше, чем у обычных компьютеров, вскоре началось бы массовое их производство, и про двоичные компьютеры все бы забыли…

    habr.com


    Читайте также
    • Гиперскоростная звезда – более 1.000.000 миль в час
      Гиперскоростная звезда – более 1.000.000 миль в час
    • Астрономы обнаружили самую большую спиральную галактику
      Астрономы обнаружили самую большую спиральную галактику
    • Млечный путь содержит десятки миллиардов планет, схожих с Землей
      Млечный путь содержит десятки миллиардов планет, схожих с Землей
    • Млечный путь разорвал своего спутника на четыре отдельных хвоста
      Млечный путь разорвал своего спутника на четыре отдельных хвоста
    • Найден источник водородных газов для нашей Галактики
      Найден источник водородных газов для нашей Галактики