Правила четности и двоичная арифметика

С понятием «четность» познакомилась на уроках математики. Чем больше узнавала об этом понятии, тем больше вопросов возникало. Кто первым ввел в математику понятие четного и нечетного числа? Какое число называют четным? Существуют ли правила, позволяющие определить четным или нечетным будет число, полученное при сложении двух четных/нечетных чисел?

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

Правила четности и двоичная арифметика

Какое число называют четным?

Определение: Четное число – целое число, делящееся на два. Всякое число можно представить в виде 2n, где n принадлежит множеству целых чисел.

Кто первым ввел в математику понятие четного числа?

Впервые ввел в математику это понятие древнегреческий ученый Пифагор. Числа подразделялись пифагорейцами на два вида: четные и нечетные. Четность и нечетность понимались как признаки, относящиеся к делимости и женскому и мужскому началу.

Существуют ли правила, позволяющие определить четным или нечетным будет число, полученное при сложении двух четных/нечетных чисел? Оказывается, существуют, и их нетрудно проверить. Вот они:

• Чётное ± чётное=чётное;

• Чётное ± нечётное=нечётное;

• Нечётное ± нечётное=чётное;

• Чётное * любое = чётное;

• Нечётное * нечётное=нечётное.

Эти правила были известны из далекой древности. Еще древнегреческий ученый Пифагор и его ученики смогли их классифицировать.

Правила, позволяющие определить, четным или нечетным будет число, полученное при сложении или умножении двух четных или нечетных чисел (будем их называть «правилами четности») нетрудно записать в виде двоичной таблицы.

+ Ч Н * Ч Н

Ч Ч Н Ч Ч Ч

Н Н Ч Н Ч Н

(Здесь «ч» означает четное число, «н» - нечетное. )

Добавим к этому влияние на четность числа прибавления к нему или вычитания из него единицы: ч±1=>н н±1=>ч (1)

Люди предпочитают десятичную систему счисления вероятно потому, что с древних времен они считали по пальцам, а пальцев у людей по 10 на руках и ногах. Десятичная система счисления пришла к нам из Индии.

Но не всегда и везде используют десятичную систему счисления. В Китае, например, долгое время пользовались пятеричной системой счисления.

А вот сравнительно недавно, в XIX в. появились представления о двоичной арифметике.

Для общения с ЭВМ используют, кроме десятичной, двоичную, восьмеричную и шестнадцатеричную систему счисления.

Изобретатель компьютера - таким титулом награжден немецкий инженер Конрад Цузе, который в 30-х годах занимался проектированием самолетов в компании Henschel Aircraft и ему приходилось выполнять огромные объемы вычислений для определения оптимальной конструкции крыльев. В то время существовали только механические калькуляторы с десятичной системой счисления, и Цузе заинтересовала проблема автоматизации всего процесса вычислений, так как он вынужден был выполнять множество однообразных рутинных расчетов по заданной схеме.

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

← использовать двоичную систему счисления;

← использование устройств, работающих по принципу "да/нет" (логические 1 и 0).

Он первым в мире сказал, что обработка данных начинается с бита (бит он называл да/нет-статусом, а формулы двоичной алгебры - условными суждениями).

В ЭВМ используют двоичную систему, потому что она имеет ряд преимуществ перед другими системами:

• Для ее реализации нужны технические элементы с двумя возможными состояниями (есть ток, нет тока; включено, выключено и т. д. Одному из состояний ставится в соответствие 1, другому – 0), а не десять, как в десятичной системе;

• Представление информации посредством только двух состояний надежно и помехоустойчиво;

• Двоичная арифметика намного проще десятичной;

• Двоичные таблицы сложения и умножения предельно просты.

А теперь сравним правила с известными из двоичной арифметики правилами сложения и умножения битов, которое выражается двойной таблицей:

+ 0 1 * 0 1

0 0 1 0 0 0

1 1 0( 1 0 1

Символ «(» означает перенос в старший разряд).

Сходство между ними обнаруживается с первого же взгляда. Но почему?

Ответ нетрудно найти, если вывести правило четности для двоичных чисел. Начнем с того, как определяется четность в десятичной системе счисления:

Если А mod 2=0, то число А – четное;

Если А mod 2=1, то число А – нечетное, где mod – функция вычисления остатка при целочисленном делении первого аргумента на второй, т. е. в данном случае число А на 2.

Теперь посмотрим, как производится деление на «2» в двоичной системе. Вспомним: если нам нужно разделить десятичное число на 10- просто берем и «отрезаем» от числа крайний справа разряд (единицы) и, если он не равен нулю, то это и будет остаток от деления. Аналогично при умножении на 10 мы просто дописываем к числу справа нуль.

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

С учетом этого в двоичной системе единственный и всецело определяющий признак четности числа – это значение его младшего (крайнего справа при общепринятой записи) бита:

Если младший бит равен нулю, число четное,

Если младший бит равен единице, число нечетное.

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

Так же просто выводится и условие (1): ведь единица остается единицей в любой системе счисления, поэтому из «двоичной» записи:

1-10;1-01;0-00;0-11(,

(где ( - заем из старшего разряда) cовсем нетрудно получить правила (1).

Практическое применение понятия «четность»

Рассмотрим на практике, как же информатике может пригодиться математическое понятие «четность».

Передача информации всегда осуществляется от источника информации к ее приемнику посредством некоторого канала связи. Канал связи подобен транспортному средству, осуществляющему доставку информации от источника приемнику:

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

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

В 19 веке сперва создание электрических и электромагнитных средств связи (Шеллинг П. Л. , 1832 г. – изобретение электрического телеграфа; Морзе С. , 1837 г. – создание электромагнитного телеграфного аппарата; Белл А. , 1876 г. – изобретение телефона), затем открытие радиоволн и изобретение устройств, способных их генерировать и улавливать (Попов А. С. , 1895 г. – изобретение радио), привели к революционным изменениям в деле передачи информации. В последние полстолетия прорывом в организации каналов связи стало изобретение оптических квантовых генераторов (лазеров и мазеров), а также использования оптоволокна как передающей среды.

Вот как выглядит схема передачи информации, или, как еще говорят, схема коммуникации:

Передача информации неосуществима без использования какого-либо физического процесса, происходящего в пространстве между источником и получателем информации. На этот физический процесс может оказывать внешнее воздействие так называемый «шум», который будет искажать передаваемую информацию. С учетом данного воздействия схема коммуникации обычно изображается так:

Первые идеи борьбы с шумом относились к созданию таких приемников информации, которые могли бы устранять воздействие помех. Листая потенты, выданные до 40-го года прошлого столетия, можно найти такие названия: «Приемник без помех», «Фильтр, устраняющий помехи», «Схемы полной компенсации помех» и т. п. И действительно, в этом направлении сделано очень многое.

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

Например, вместо сообщения 110011101 передается сообщение 111100001111110011.

Если получено сообщение 111100111011, то сразу ясно, что оно ошибочно, - после разбивки его на два символа имеем 11 11 00 11 10 11, т. е. в предпоследней паре цифр либо вместо 0 пришла 1, либо наоборот. Тем самым, предложенный код распознает (но не помогает исправить!) ошибки в сообщении. Конечно, плата за это довольно велика – удвоение длины сообщения, а значит, удвоение времени передачи и энергозатрат. Можно предложить более экономную процедуру контроля: подсчитать количество символов 1 в сообщении и приписывать к сообщению 1, если это количество нечетно, и 0, если количество четно (смотри (3) - «Признак четности двоичных чисел).

Например, сообщение 110011101 превратиться в сообщение 1100111010.

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

Вот так, математическое понятие «четность» пригодилось информатике, для распознания ошибок, при передаче/получение сообщений.

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

В работе конкретно сформулирована тема, четко поставлены цели и задачи исследования, определены ожидаемые результаты.

План исследования составлен логически правильно, тема полностью раскрыта.

В проекте отражены историографии отечественного и зарубежного опыта по рассматриваемой проблеме.

Материал данной работы будет интересен на факультативных занятиях или на элективных курсах.

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

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