Реферат "Ей было тысяча сто лет" на тему: "Двоичная система счисления" + презентация
творческая работа учащихся по алгебре (11 класс) на тему

Орехово-Зуевский муниципальный район

Реферат

«Ей было тысяча сто лет…»

по теме:

«Двоичная система счисления»

Выполнила:

ученица 11 класса

МОУ «Дрезненская    

средняя общеобразовательная школа № 1»

Волкова Татьяна

Руководитель:

учитель математики

Моргунова Р.А.

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

СТРАННАЯ ДЕВОЧКА

Ей было тысяча сто лет.
Она в сто первый класс ходила,
В портфеле по сто книг носила -
Всё это правда, а не бред.
Когда пыля десятком ног,
Она шагала по дороге,
За ней всегда бежал щенок
С одним хвостом, зато стоногий.
Она ловила каждый звук
Своими десятью ушами,
И десять загорелых рук
Портфель и поводок держали.
И десять тёмно-синих глаз
Рассматривали мир привычно…

Но станет всё совсем обычным,
Когда поймёте мой рассказ.

А. Стариков

Содержание

Введение.

Краткая история двоичной системы.

Почему двоичная система удобна?

Книга перемен, Азбука Морзе, Шрифт Брайля и алфавитные коды.

Игра «Ним».

Лейбниц Готфрид Вильгельм.

«Машинные» системы счисления.

Фотопленка и штрих-код.

 Заключение.

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

Введение

                                                 Мы… никогда не стали бы разумными,

если бы исключили число из человеческой природы.

Платон

При записи чисел мы пользуемся одним удивительным обстоятельством, которому не поражаемся лишь потому, что сталкиваемся с ним с первых школьных лет: любое, сколь угодно большое или малое число мы ухитряемся записать, привлекая всего-навсего десять знаков: 0,1,2,3….9. Почему же это удаётся сделать? По двум причинам. Во-первых, потому, что наша система записи чисел  — десятичная, то есть десять единиц дают одну единицу второго разряда (десяток), десять десятков  — одну единицу третьего разряда и т.д. Во-вторых, потому, что наша система записи чисел — позиционная: одна и та же цифра указывает на число единиц того или иного разряда в зависимости от места в числе, где она помещается.

        Но обязательно ли десять единиц какого-либо разряда объединять в одну единицу другого разряда? Разумеется, это необязательно. Мы можем, например, считать парами: две единицы объединять в единицу следующего разряда. Тогда у нас образуется двоичная система счисления. В двоичной системе запись 100101 означает:

1. 25+0.24+0.23+1.22+0.22+1

то есть число 37.

Например, запись 0,101(2) означает, что в двоичной системе счисление задано следующее число:

1. 1/2 +0 . 1/22 + 1 . 1/23 , то есть 5/8

Вот один из простейших примеров:

          1)  Дана двоичная запись нескольких чисел;

          101; 100001; 0,0101; 1001,011. Какие числа записаны?

(Ответ:5; 33; 5/16; 9 . 3/8).

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

        Рассмотрю сначала для определенности двоичную систему счисления. Легко для последовательных натуральных чисел 1,2,3… найти их двоичную запись: число 1 имеет двоичную запись1; число 2 имеет двоичную запись 10 (один  ноль, одна двойка, и ничего в остатке); число 3 имеет двоичную запись 11 (один-один) – одна двойка и в остатке еще единица; число 4 имеет двоичную запись 100 (один – ноль - ноль) – один раз 22, и в остатке 0 раз 2 и 0 раз 1.

        Возьму произвольное натуральное число, например 25.

        Как найти его двоичную запись? Сначала узнаю, какая самая высокая степень двойки в нём содержится. Очевидно, 24, и притом 1 раз. В остатке (он равен 9) содержится 1 раз 23 (то есть 8). В новом остатке (1) содержится 0 раз число 22, 0 раз число 21, 1 раз число 1.

        Иначе говоря,

25 = 1.24+1.23+0.22+0.21+1.1,    т.е.     N = Pk. Qk-1+…+p3.q2+p2q1+p1.1

Так что его двоичная запись такова: 11001.

        Точно так же легко найти двоичную запись любого другого натурального числа.

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

        1)Угадывание предмета по таблицам.

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

Куб                                6. Циркуль                                11. Сегмент

Шар                                7. Цилиндр                                12. Транспортир

Окружность                        8. Треугольник                        13. Сектор

Круг                                9. Квадрат                                14. Пирамида

Линейка                         10. Параллелограмм                        15. Трапеция

Они же выписаны в этих четырех таблицах:

«Выберите любой из этих предметов так, чтобы я не видел. С помощью несложных расчетов можно установить, какой предмет выбран. Кто желает проделать фокус?» Допустим, что к доске выходит ученик М. Ведущий поворачивается так, чтобы видеть только таблицу, в которой 15 названий. Затем он продолжает: «Выбери, М., любой из предметов на столе. Подними  его так, чтобы видели все, кроме меня. Записан ли этот предмет в таблице 1?». «Да». «А в таблице 2?». «Нет». «А в таблице 3?». «Да». «А в таблице 4?» «Нет».

Ведущий: « Я угадываю: ты выбрал линейку».

Объяснение. Каждому предмету соответствует число – номер, под которым значится предмет в таблице с 15 предметами. Например, сектору соответствует число 13, линейка – число 5. Переведем  все эти номера в двоичную систему счисления. Тогда каждое из чисел записывается не более чем четырьмя цифрами. Например, число 5 запишется 101 (или, что то же самое, 0101).

В первой таблице помещаются такие и только такие слова, чьи номера в двоичной системе счисления имеют на первом месте справа цифру 1. Например, слову «сектор» соответствует число 13, а в двоичной системе счисления – 1101; на первом месте справа – 1; поэтому слово помещается в таблицу № 1. В таблицу № 2 помещены те слова, чьи номера в двоичной системе счисления имеют во втором месте (считая справа на лево) цифру 1. Например, слово «цилиндр» включает в таблицу № 2. Аналогично составлены таблицы № 3 и № 4. Когда М. говорит, что выбранный им предмет находится в таблице № 1, и № 3, но не значится в таблицах № 2 и № 4, можно записать номер этого предмета в двоичной системе счисления: 0101, или в десятичной системе счисления:                             0 .23+1 .22+0 .2+1, то есть число 5. Под номером 5 в таблице из 15 предметов значится линейка. Значит, М. выбрал линейку.

2) Угадывание любого целого числа от 1 до 31 с помощью двоичной системы счисления.

Пусть этот фокус проводят два ученика – А и В. В  выходит из комнаты, А вызывает к столу 5 учеников (по желанию) и выстраивает их в один ряд. Затем он предлагает присутствующим в комнате назвать любое число от 1 до 31. В уме он переводит число в двоичную систему счисления и расставляет учащихся так, чтобы нулю соответствовал ученик, стоящий лицом к классу, а единице – ученик, стоящий лицом к доске. Например, если предложено число 13, то в двоичной системе счисления оно записывается так: 1101 (или 01101). Затем А уходит в сторону (или вовсе выходит из класса). Приглашают ученика В. и он, посмотрев на пятерку учеников, восстанавливает в уме по их расположению загадочное число (сначала -  в двоичной системе, а затем переводит его в десятичную).

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

0+0=0                        0 . 0=0

                        0+1=1                        0 . 1=0

                        1+0=1                        1 . 0=0

                        1+1=10                1 . 1=1

        Выполняем следующие вычисления в двоичной системе счисления без перехода к десятичной:

        х    1001011                         х      1011              

              110111                                   1101

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

2. Краткая история двоичной системы

Число, выраженное десятичным знаком,              прочтёт и немец, и русский, и араб, и янки одинаково.               Менделеев Д.И.

Некоторые идеи, лежащие в основе двоичной системы, по существу были известны в Древнем Китае. Об этом свидетельствует  классическая книга «И-цзин» («Книга Перемен»), о которой речь пойдёт позже.

Идея двоичной системы была известна и древним индусам.

В Европе двоичная система, видимо, появилась уже в новое время. Об этом свидетельствует система объёмных мер, применяемая английскими виноторговцами: два джилла = полуштоф, два полуштофа = пинта, две пинты = кварта, две кварты = потл, два потла = галлон, два галлона = пек, два пека  =  полубушель, два полубушеля  =  бушель, два бушеля = килдеркин, два килдеркина = баррель, два барреля = хогзхед, два хогзхеда = пайп, два пайпа = тан.

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

И в английских мерах веса можно увидеть двоичный принцип. Так, фунт (обычный, не тройский) содержит 16 унций, а унция — 16 дрэмов. Тройский фунт содержит 12 тройских унций. В английских аптекарских мерах веса, однако, унция содержит восемь дрэмов.

Пропагандистом двоичной системы был знаменитый Г. В. Лейбниц (получивший, кстати, от Петра I звание тайного советника). Он отмечал особую простоту алгоритмов арифметических действий в двоичной арифметике в сравнении с другими системами и придавал ей определённый философский смысл. Говорят, что по его предложению была выбита медаль с надписью «Для того, чтобы вывести из ничтожества всё, достаточно единицы». Известный современный математик Т. Данциг о нынешнем положении дел

сказал: «Увы! То, что некогда возвышалось как монумент монотеизму, очутилось в чреве компьютера». Причина такой метаморфозы не только уникальная простота таблицы умножения в двоичной системе, но и особенности физических принципов, на основе которых работает элементная база современных ЭВМ (впрочем, за последние 40 лет она неоднократно менялась, но двоичная система и булева алгебра по-прежнему вне конкуренции).

3. Почему двоичная система удобна?

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

0/1 = 0, 1/1 = 1, благодаря чему деление столбиком многозначных двоичных чисел делается гораздо проще, чем в десятичной системе, и по существу сводится к многократному вычитанию.

Таблица сложения как ни странно чуть сложнее, потому что 1+1 = 10 и возникает перенос в следующий разряд. В общем виде операцию сложения однобитовых чисел можно записать в виде x+y = 2w+v, где w, v — биты результата. Внимательно посмотрев

на таблицу сложения, можно заметить, что бит переноса w — это просто произведение xy, потому что он равен единице лишь когда x и y равны единице. А вот бит v равен x+y, за исключением случая x = y = 1, когда он равен не 2, а 0. Операцию, с помощью которой по битам x, y вычисляют бит v, называют по-разному. Мы будем использовать для неё название «сложение по модулю 2» и символ . Таким образом, сложение битов выполняется фактически не одной, а двумя операциями.

Если отвлечься от технических деталей, то именно с помощью этих операций и выполняются все операции в компьютере.

Для выполнения сложения однобитовых чисел делают обычно даже специальный логический элемент с двумя входами x, y и двумя выходами w, v, как бы составленный из элемента умножения (его часто называют конъюнкцией, чтобы не путать с умножением многозначных чисел) и элемента сложения по модулю 2. Этот элемент часто называют полусумматором.

4. Книга Перемен,  Азбука Морзе, Шрифт Брайля и алфавитные коды

Возможно, что, если бы люди имели одиннадцать пальцев,

Была бы принята одиннадцатеричная  система счисления.

Лебег А.

Двоичная система, по крайней мере в своей комбинаторной ипостаси, по существу была известна в Древнем Китае. В классической книге «И-цзин» («Книга Перемен») приведены так называемые гексаграммы Фу-си, первая из которых имеет вид    , а последняя (64-я) — вид         , причём они расположены по кругу и занумерованы в точном соответствии с двоичной системой (нулям и единицам соответствуют сплошные и прерывистые линии). Китайцы не поленились придумать для этих диаграмм специальные иероглифы и названия (например, первая из них называлась «кунь», а последняя — «цянь», сплошной линией сопоставляется мужское начало янь, а прерывистой линии — женское начало инь).

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

Их также принято располагать циклически, но этот цикл не является кодом Грея.

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

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

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

Капитан французской армии Шарль Барбье в 1819 году предложил печатать выпуклыми не буквы, а точки и тире (или просто продавливать их на бумаге) и ими уже записывать буквы. Эту систему он назвал «ночное письмо» и предлагал вовсе не для слепых, а для использования в военно-полевых условиях. С появлением электрических фонариков военное значение этого изобретения упало до нуля.

Слепой мальчик Луи Брайль познакомился с этой системой в 12 лет. Она ему понравилась тем, что позволяла не только читать, но и писать. В течение трёх лет он её усовершенствовал и создал так называемый шрифт Брайля. В нём символы языка (буквы,

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

сверху вниз и 4, 5, 6 во втором столбце сверху вниз. Каждая точка либо продавливается специальной машинкой (или даже шилом) или остаётся целой. Всего различных способов продавить выпуклые точки в этой таблице 64 (в том числе и тот, в котором ни одна из точек не вдавлена). При желании теперь читатель может сопоставить каждому символу алфавита Брайля одну из гексаграмм Книги Перемен. Вряд ли, конечно, Брайль знал об этой книге.

Вероятно, не имеет смысла описывать все символы шрифта Брайля, тем более что после его смерти в 1852 году шрифт дополнялся и совершенствовался. Но несколько слов сказать, видимо, стоит. Буква «а», например, изображается одной выпуклой точкой в 1-м элементе таблицы, буква «б» изображается выпуклыми точками в 1-м и 2-м элементах таблицы и т. д. Для сокращения текстов некоторые часто встречающиеся слова или комбинации букв кодируются специальными таблицами. Для того чтобы отличать заглавную букву от строчной, перед ней ставят специальную таблицу, изображающую то, что сейчас называют эскейп - символом. Многие таблицы имеют несколько значений (например, буква и какой-нибудь специальный знак или знак препинания), выбор из которых делается в соответствии с контекстом. Цифры кодируются так же, как и первые буквы алфавита, и, чтобы их отличать, перед последовательностью цифр ставится специальный символ — признак числа, а заканчивается число символом отмены признака числа.

Азбука Брайля по известности уступает азбуке Морзе, хотя и применяется до сих пор в отличие от последней. Сэмюэль Морзе известен однако не только изобретением азбуки. Он был и художником-портретистом (его картина «Генерал Лафайет» до сих пор

висит в нью-йоркском Сити-Холле (Известна также его картина «Человек в предсмертной агонии», после просмотра которой его приятель, известный врач, сказал: «По-моему, малярия»)), и одним из первых фотографов в Америке (учился делать дагерротипные фотографии у самого Луи Дагерра), и политиком (он баллотировался в 1836 году на пост мэра Нью-Йорка), но самое главное его достижение — изобретение телеграфа (а азбука Морзе понадобилась ему для использования телеграфа). Заодно он изобрёл устройство, которое называется реле. Именно из реле спустя сто лет после Морзе были построены первые компьютеры.

Начал свои работы в этом направлении он в 1832 году, запатентовал своё изобретение в 1836 году, но публичная демонстрация телеграфа произошла только 24 мая 1844 года. По телеграфной линии, соединяющей Вашингтон с Балтимором, была успешно

передана фраза из Библии.

Точки и тире оказались самыми элементарными символами,

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

Азбука Морзе сопоставляет каждой букве алфавита последовательность из точек и тире. Естественней всего использовать такие последовательности длины 6, их всего 64 и хватит даже на русский алфавит. Но Морзе понимал, что длину сообщения желательно

уменьшить, насколько возможно, поэтому он решил использовать последовательности длины не более 4, их всего 2+4+8+16=30. В русском алфавите пришлось не использовать буквы «э» и «ё» и отождествить мягкий и твёрдый знаки. Кроме того, наиболее

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

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

букву на соответствующий ей элементарный код, и превратить исходное слово в более длинное слово в кодирующем алфавите. Таким образом, и код Брайля, и азбука Морзе являются алфавитными кодами.

Удобнее всего задать код Морзе в виде четырёх ярусного двоичного дерева. Из корня дерева выходят два ребра, из которых правому соответствует тире, а левому — точка. Это — рёбра первого яруса. Из их концов тоже аналогичным образом выходят по два ребра. Это — рёбра второго яруса. Дерево рисуем до четвёртого

    Ш      Ч      Щ      З      Ы      Ц      Ь       Б      Й       П      Я      Л      Ю    Ф      Ж      Х

   __  .      __        .     __        .    __        .     __        .     __        .     __        .      __        .   

         О                Г                К              Д                В               Р                У                С

        __                .                __               .                 __              .             __                   .

                  М                                 Н                                 А                                И

                      __                        .                                             __                      .

                                    Т                                                                      Е

                                                       __                           .

                                                                    Рис.1

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

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

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

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

таблицу 5X5 и каждая буква шифровалась парой своих координат (i, j) (номерами строки и столбца), а передаваться сообщения могли в то время с помощью факелов — i факелов в левой руке и j факелов в правой означали пару (i, j).

Дальнейшее развитие идеи алфавитного кодирования принадлежит знаменитому английскому философу, эзотерику и писателю сэру Френсису Бэкону, который первым начал использовать двоичный алфавит в качестве шифроалфавита. В криптографии, правда, это не нашло особого применения, главным образом из-за пятикратного удлинения шифртекста в сравнении с открытым текстом. Но сам Бэкон предложил использовать его как метод, сочетающий криптографию со стеганографией (так называется скрытие самого факта передачи секретного сообщения).

Вместо двоичных цифр он использовал обычный алфавит, но со шрифтами двух типов. Таким методом можно было в любом тексте спрятать шифровку, если, конечно, шрифты были достаточно мало различимы. Желательно при этом использовать разделимый код. Длина зашифрованного сообщения будет в несколько раз короче, чем длина содержащего его (и одновременно маскирующего его) текста, но если для передачи шифровки использовать книгу, то в ней можно таким образом незаметно разместить ещё целую книгу. Но эта красивая идея из-за дороговизны её реализации так и не нашла применения. В наше же время её нельзя рассматривать как серьёзный метод.

Интересно, что в XIX веке, главным образом в кругах, интересующихся наследием возникшего в средневековье тайного мистического ордена розенкрейцеров, появилась идея, что Френсис Бэкон, которого считали розенкрейцером, является настоящим

автором пьес Шекспира. Начали искать подтверждение этого в шифрах, которые мог оставить Бэкон в своих книгах, а также в первом знаменитом издании пьес Шекспира. Было, естественно, найдено много таких, якобы зашифрованных фрагментов. Серьёзные

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

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

Фабиан нанял на работу дипломированного генетика Уильяма Фридмана, сына эмигрантов из России. Через некоторое время Фридман уже возглавлял у Фабиана и лабораторию генетики, и лабораторию криптоанализа. Доказать авторство Бэкона он не смог, более того, он впоследствии опубликовал книгу, где опровергал возможность такого криптографического доказательства. Но он не на шутку увлёкся криптографией и своей подчинённой Элизабет Смит, с которой обвенчался в 1917 году. Они стали самой знаменитой супружеской парой в истории криптографии. После вступления Америки в войну у него с супругой появилась серьёзная работа по правительственным заказам. После войны он ушёл от Фабиана, и стал главным криптографом войск связи.

5. Игра «Ним»

Двоичная система находит неожиданное применение при анализе известной игры «Ним». Происхождение её, так же, как и шахмат, покрыто туманом. Возможно, она была изобретена в Китае.

Состоит она в следующем: на столе лежит несколько кучек спичек, и два игрока по очереди выбирают одну из кучек и забирают из неё сколько угодно спичек (хоть все); выигрывает тот, кто забирает последнюю (есть вариант игры, в котором забравший последнюю проигрывает).

Игра «Ним» являлась излюбленной темой математических кружков в МГУ. Иногда она представлялась в виде гонки нескольких пешек от одного края доски до другого. Можно самим сформулировать правила игры в таком её представлении.

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

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

В случае трёх и более кучек описание выигрышной позиции не так просто. Алгоритм распознавания выигрышной позиции следующий. Нужно количество спичек в каждой кучке записать в двоичной системе, и вычислить сумму по модулю 2 полученных двоичных наборов (далее для краткости будем называть её ним - суммой). Для этого вначале нужно вычислить покомпонентную сумму этих наборов, т. е. найти сумму всех младших разрядов, потом сумму следующих за ними разрядов (отсутствующие разряды заменяются нулями) и т. д., и записать полученные суммы в виде (возможно, недвоичного) набора, а потом каждую его компоненту заменить на остаток от деления на 2. Если получится набор из одних нулей, то позиция выигрышная.

Например, если в кучках было 3, 7, 12, 17 спичек, то покомпонентно складывать придётся наборы                        +    11 (=3)

    111 (=7)

  1100 (=12)

10001 (=17)

_____

11223

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

кучке число спичек, равное в двоичной записи ним - суммы наборов 10001 и 11001, т. е. 01000. Тогда ним - сумма чисел, образующих новую позицию, будет равна нулевому набору, так как эта сумма будет отличаться от прежней суммы 11001 прибавлением к ней по модулю 2 набора 11001, что даёт в результате, очевидно, нулевой набор. Поскольку

01000=8, из последней кучки надо взять 17−8=9 спичек.

Например, нужно доказать, что в общем случае из позиции с ненулевой ним - суммой за один ход можно попасть в позицию с нулевой ним - суммой, а из позиции с нулевой ним суммой любой ход ведёт к позиции с ненулевой ним - суммой.

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

Указанная выигрышная стратегия поддаётся для реализации даже на специализированных машинах. Одна из таких машин была выставлена после войны в Берлине на английской выставке и с успехом конкурировала с находящимся рядом бесплатным пивным залом. Знаменитый английский математик Алан Тьюринг вспоминал о том, как популярность этой машины повысилась ещё больше после победы над тогдашним бундесминистром экономики Л. Эрхардом.

Предоставляется возможность найти выигрышную стратегию при игре «ним» в поддавки.

Более интересная модификация игры ним получается, если ограничить число спичек, которые можно взять за один раз, например, числом 10. Тогда интерес представляет даже игра с одной кучкой спичек. Эту игру изобрёл в XVII веке французский математик Баше де Мезириак,  написавший кстати, одну из первых в Европе

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

6. Лейбниц Готфрид Вильгельм

Лейбниц (Leibniz, Leibnitz) Готфрид Вильгельм (21.VI.1646, Лейпциг - 14.XI.1716, Ганновер) - немецкий философ-идеалист, математик, ученый-энциклопедист. Основатель и президент Берлинской Академии Наук.

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

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

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

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

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

Ряд важнейших механизмов машины Лейбница применяли вплоть до середины XX века в некоторых типах машин. К типу машины Лейбница могут быть отнесены все машины, в частности и первые ЭВМ, производившие умножение как многократное сложение, а деление - как многократное вычитание. Главным достоинством этих машин являлись более высокие, чем у человека, скорость и точность вычислений. Их создание продемонстрировало принципиальную возможность механизации интеллектуальной деятельности человека.

Лейбниц первый понял значение и роль двоичной системы счисления. В рукописи на латинском языке, написанной в марте 1679 года Лейбниц разъясняет, как выполнять вычисление в двоичной системе, в частности умножение, а позже в общих чертах разрабатывает проект вычислительной машины, работающей в двоичной системе счисления. Вот что он пишет: "Вычисления такого рода можно было бы выполнять и на машине. Несомненно, очень просто и без особых затрат это можно сделать следующим образом: нужно проделать отверстия в банке так, что бы их можно было открывать и закрывать. Открытыми будут те отверстия, которые соответствуют 1, а закрытыми соответствующие 0. Через открытые отверстия в желоба будут падать маленькие кубики или шарики, а через закрытые отверстия ничего не выпадет. Банка будет перемещаться и сдвигаться от столбца к столбцу, как того требует умножение. Желоба будут представлять столбцы, причем ни один шарик не может попасть из одного желоба в какой либо другой, пока машина не начнет работать...". В дальнейшем в многочисленных письмах и в трактате "Explication de l`Arithmetique Binairy" (1703) Лейбниц снова и снова возвращался к двоичной арифметике. Идея Лейбница об использовании двоичной системы счисления в вычислительных машинах останется забытой в течение 250 лет.

7. «Машинные» системы счисления

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

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

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

 Двоичная система проста, так как для представления информации в ней используются всего два состояния или две цифры. Такое представление информации принято называть двоичным кодированием. Представление информации в двоичной системе использовалось человеком с давних времен. Так, жители островов Полинезии передавали необходимую информацию при помощи барабанов: чередование звонких и глухих ударов. Звук над поверхностью воды распространялся на достаточно большое расстояние, таким образом «работал» полинезийский телеграф. В телеграфе в ХIХ-ХХ веках информация передавалась с помощью азбуки Морзе — в виде последовательности из точек и тире. Часто мы договариваемся открывать входную дверь только по «условному сигналу» — комбинации коротких и длинных звонков. Двоичная система используется для решения головоломок и построения выигрышных стратегий в некоторых играх.

В конце XX века, века компьютеризации, человечество пользуется двоичной системой ежедневно, так как вся информация, обрабатываемая современными ЭВМ, хранится в них в двоичном виде. Каким же образом осуществляется это хранение? Каждый регистр арифметического устройства ЭВМ, каждая ячейка памяти представляет собой физическую систему, состоящую из некоторого числа однородных элементов. Каждый такой элемент способен находиться в нескольких состояниях и служит для изображения одного из разрядов числа. Именно поэтому каждый элемент ячейки называют разрядом. Нумерацию разрядов в ячейке принято вести справа налево, самый левый разряд имеет порядковый номер 0. Если при записи чисел в ЭВМ мы хотим использовать обычную десятичную систему счисления, то мы должны получать 10 устойчивых состояний для каждого разряда, как на счетах при помощи костяшек. Такие машины существуют. Однако конструкция элементов такой машины чрезвычайно сложна. Наиболее надежным и дешевым является устройство, каждый разряд которого может принимать два состояния: намагничено — не намагничено, высокое напряжение — низкое напряжение и т.д. В современной электронике развитие аппаратной базы ЭВМ идет именно в этом направлении. Следовательно, использование двоичной системы счисления в качестве внутренней системы представления информации вызвано конструктивными особенностями элементов вычислительных машин.

Преимущества двоичной системы счисления:

Простота совершаемых операций

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

Недостаток двоичной системы счисления:

Быстрый рост числа разрядов в записи, представляющей двоичное число.

Для представления двоичных чисел вне компьютера используют более компактные по длине чисел восьмеричную (для записи кодов чисел и машинных команд) и шестнадцатеричную (для записи адреса команд) системы счисления.

Из истории известен курьезный случай с восьмеричной системы счисления. Шведский король Карл XII в 1717 году увлекался восьмеричной системой счисления, считал её более удобной, чем десятичная, и намеревался королевским приказом ввести её как общепринятую. Неожиданная смерть помешала королю осуществить столь необычное намерение.

8. Фотопленка и штрих-код

Математика представляет искуснейшие изобретения,

способные удовлетворить любознательность,

облегчить ремёсла и уменьшить труд людей.

Декарт Р.

Рассмотрим теперь некоторые примеры реального применения двоичного кодирования в современной технике.

Как автоматические фотоаппараты узнают светочувствительность заправленной в них плёнки? Её измеряют в некоторых единицах, и вся выпускаемая сейчас в мире плёнка имеет одно из 24 стандартных значений светочувствительности. Эти значения кодируются некоторым стандартным образом наборами из нулей и единиц, естественно, длины 5. На поверхности кассеты для плёнки нанесены 12 квадратиков чёрного или серебристого цвета, образующих прямоугольник 2Х6. Квадратики его верхней части мысленно занумеруем от 1 до 6, начиная слева. Квадратики нижней части аналогично занумеруем

от 7 до 12. Серебристые квадратики — это просто металлическая поверхность кассеты, она проводит ток, который с контакта внутри аппарата подаётся на первый квадрат (он всегда серебристый). Чёрные квадраты покрыты краской, не проводящей ток.

Когда плёнка вставляется в аппарат, шесть его контактов соприкасаются с шестью первыми квадратиками, и с квадратиков со 2-го по 6-й снимается информация — нуль, если квадратик чёрный и ток по соответствующему контакту не идёт, и единица

в противном случае. Вся информация о светочувствительности плёнки заключена в квадратиках со 2-го по 6-й. В остальных квадратиках заключена информация о числе кадров в плёнке и т. п.

Ещё на поверхности кассеты можно увидеть штрих-код. Это так называемый универсальный код продукта, он сейчас ставится на всех продаваемых товарах. Для чего он нужен и как его прочитать?

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

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

нули. Полностью весь штрих-код сканер воспринимает как последовательность из 95 цифр 0 или 1 (их давно уже принято называть битами). Что же содержит этот код? Он кодирует 13-разрядное десятичное число, совершенно открыто написанное под самим

штрих - кодом. Если сканер не смог распознать штрих-код, то это число кассир вводит в аппарат вручную. Штрих-код нужен лишь для облегчения распознавания сканером изображения. Распознавать цифры, к тому же повёрнутые боком, может только сложная

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

Какую же информацию содержит это 13-значное число? Этот вопрос к математике никакого отношения не имеет. Первая цифра задаёт тип товара, например, у товаров переменного веса она равна 2. Следующие пять цифр — это код производителя, а следующие пять цифр — код самого продукта в принятой этим производителем

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

А вот 95-битный код, соответствующий штрих-коду, более интересен. Он содержит в себе только указанное 12-значное число (контрольная цифра в самом штрих - коде не содержится), но с большой избыточностью. Первые три бита в нём, так же, как и последние — это всегда 101. Они нужны только для того, чтобы сканер смог определить ширину полосы, соответствующей одному биту (ведь размеры штрих-кода на разных упаковках могут быть разными) и настроиться на распознавание. В центре кода всегда стоит комбинация 01010, а левая и правая части кода состоят каждая из шести блоков по семь битов и содержат информацию о левых шести и правых шести из данных 12 десятичных цифр. Центральная комбинация позволяет, в частности, отличать поддельные или плохо напечатанные коды.

Цифры 13-значного кода кодируются в левой и правой частях штрих-кода по-разному. В левой половине каждая цифра кодируется семёркой битов, начинающейся с 0 и заканчивающейся 1

согласно следующей таблице:

=0001101=0,                 =0111101=3,                 =0111011=7,

=0011001=1,                 =0100011=4,                 =0110111=8,

=0010011=2,                 =0110001=5,                 =0001011=9.

=0101111=6,

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

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

 Такая избыточная (не четырёхбитовая, а семибитовая) таблица кодов нужна для того, чтобы сканер мог правильно прочитать штрих-код и в случае, когда код направляют в него «вверх ногами». Как сканер может отличать одно направление от другого? По чётности или нечётности числа единиц в первом же прочитанном семибитовом блоке, идущем после комбинации 101. При правильном направлении оно будет нечётным, а при обратном направлении — чётным. Перепутать же коды, прочитанные слева, и коды, прочитанные справа, согласно свойству таблицы, невозможно.

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

9. Заключение

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

Так, например, довольно широкое распространение имела двенадцатеричная система.  Ее происхождение связано, несомненно,  тоже со счетом на пальцах, а именно, так как четыре пальца руки (кроме большого) имеют в совокупности 12 фаланг (рис. 2), то по этим фалангам, перебирая их по очереди большим пальцем, и ведут счет от 1 до 12. Затем 12 принимается за единицу следующего разряда и т.д. В устной речи  остатки двенадцатеричной системы сохранились и до наших дней: вместо того чтобы сказать «двенадцать», мы часто говорим «дюжина». Многие предметы (ножи, вилки, тарелки, носовые платки и т.п.) очень часто считают именно дюжинами, а не десятками. (Например, сервиз бывает, как правило, на 12 или на 6 человек и значительно реже на 10 или на 5.) Сейчас уже крайне                                                Рис. 2                редко встречается слово «гросс», означающее «дюжину дюжин» (т.е. единицу третьего разряда в двенадцатеричной системе), но еще несколько десятков лет тому назад оно было довольно широко распространено, особенно в торговом мире. Дюжина гроссов называлась «масса», однако сейчас такое значение слова «масса» мало кому известно, хотя, возможно, именно в нем лежит корень таких  употребительных выражений, как «масса дел», «масса людей» и т.п. Также можно сравнить с выражениями «тысяча дел» и т.д.).

Несомненно остатки двенадцатеричной системы счисления имеют у англичан – в системе мер (например, 1 фут = 12 дюймам) и в денежной системе (1 шиллинг = 12 пенсам).

Нужно заметить, что с математической точки зрения двенадцатеричная система имела бы, пожалуй, некоторые преимущества перед десятичной, поскольку число 12 делится на 2, 3, 4 и 6, а число 10 только на 2 и 5, а больший запас делителей у числа, служащего основанием системы счисления, создает известные удобства в ее использовании.

В древнем Вавилоне, культура которого, в том числе и математическая, была довольно высока, существовала весьма сложная шестидесятеричная система. Мнения историков по поводу того, как именно возникла такая система, расходятся. Одна из гипотез, впрочем не особенно достоверная, состоит в том, что произошло смешение двух племен, одно из которых пользовалось шестеричной системой, а другое – десятичной. Шестидесятеричная система возникла как компромисс между этими двумя системами. Другая гипотеза состоит в том, что вавилоняне считали продолжительность года равной 360 суткам, что, естественно, связывалось с числом 60. Однако это предположение тоже нельзя считать достаточно обоснованным: астрономические познания древних вавилонян были довольно значительны, поэтому следует думать, что погрешность, с которой они определяли продолжительность года, была значительно меньше, чем 5 суток. Несмотря на то, что происхождение шестидесятеричной системы остается неясным, сам факт  ее существования и широкого распространения в Вавилонском государстве достаточно хорошо установлен. Эта система, в какой-то степени сохранилась и до наших дней (например, в делении часа на 60 минут, а минуты – на 60 секунд и в аналогичной системе измерения углов: градус = 60 минутам, 1 минута = 60 секундам). В целом, однако, эта система, требующая шестидесяти различных «цифр», довольно громоздка и менее удобна, чем десятичная.

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

У ацтеков и майя – народов, населявших  в течение многих столетий обширные области американского континента и создавших там высокую культуру, почти полностью уничтоженную испанскими завоевателями в XVI – XVII вв., - была принята двадцатеричная система. Та же двадцатеричная система была принята у кельтов, населявших Западную Европу, начиная со второго тысячелетия до нашей эры. Некоторые следы двадцатеричной системы кельтов сохранились в современном французском языке: например, «восемьдесят» по-французски будет quatre-vingts, т.е. буквально «четырежды двадцать». Число 20 встречается и во французской денежной системе: основная денежная единица – франк – делится на 20 су.

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

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

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

1. Занимательные материалы по математике. 7 – 8 классы. / Составитель Галаева Е.А. – Волгоград: Издательско-торговый дом «Корифей», 2006. – 80 с.

2. Системы счисления и их применение. (Серия: «Библиотека «Математическое просвещение»») / Гашков С.Б. – Москва: Издательство Московского центра непрерывного математического образования, 2004. – 52 с., ил.

3. Сайт: http: //www. Infhist. H1. ru/

4. Раздел информатика, 2001 – 2007. Теле - школа. Интернет – школа «Просвещение.ru»

5. Биографический словарь деятелей в области математики. / Бородин А.И., Бугай А.С. – Киев: «Радянська школа», 1979.

6. Математики, механики. / Богомолов А.Н. – Киев: «Наукова думка», 1979.

7. Системы счисления. – 5-е издание. / Фомин С.В. - Москва: «Наука». Главная редакция физико-математической литературы, 1987. – 48 с. – (Популярные лекции по математике).

8. Энциклопедический словарь юного математика. / Составитель Савин А.П. – Москва: Педагогика, 1985. – 352 с., ил.