Методика использования систем счисления в базовом курсе информатики

Блестящие предсказания Лейбница сбылись только через два с половиной столетия, когда выдающийся американский ученый, физик и математик Джон фон  Нейман предложил использовать именно двоичную систему счисления в  качестве универсального способа кодирования  информации в электронных компьютерах ("Принципы Джона фон Неймана") [27].

Джон фон Нейман (1903-1957)

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

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

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

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

Чтобы преодолеть указанные недостатки двоичной системы, уже на этапе зарождения компьютерной эры был выполнен ряд проектов и сделано несколько интересных математических открытий, связанных  с системами счисления. Пожалуй, наиболее интересным проектом в этом отношении является троичный компьютер "Сетунь", разработанный в Московском университете под руководством Н. П. Брусенцова. Использование в нем так называемой троичной симметричной системы счисления для представления чисел впервые в истории компьютеров поставило знак равенства между отрицательными и положительными числами, позволив отказаться от различных "ухищрений" (обратный и дополнительный код), используемых для представления отрицательных чисел. Это обстоятельство, а также использование "троичной логики" при создании программ привело к созданию весьма совершенной архитектуры, которая и была воплощена в модели "Сетуни". Именно "Сетунь" является наиболее ярким историческим примером, подтверждающим влияние системы счисления на архитектуру компьютера [5].

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

В 1939г. бельгийский врач Эдуард Цекендорф, увлекавшийся числами Фибоначчи, опубликовал статью, посвященную так называемым "суммам Цекендорфа". Под представлением Фибоначчи - Цекендорфа понимается следующий позиционный способ представления чисел:

N=anF(n)+an-1F(n-1)+...+aiF(i)+...+a1F(1); где ai={0, 1} - двоичная цифра i-го разряда представления; n - разрядность представления; F(i) - число Фибоначчи, задаваемое с помощью следующего рекуррентного соотношения: F(i) = F(i-1) + F(i-2); F(1) + F(2) = 1; A= . Однако наиболее революционным предложением в современной теории систем счисления по праву можно считать систему счисления с иррациональным основанием, предложенную в 1957г. американским математиком Джорджем Бергманом. Под "Тау-системой", или системой Бергмана, понимается следующий способ представления действительного числа А: где ai - двоичные цифры, 0 или 1; i=0, +1, +2, +3; τ i - вес i-й цифры в представлении; τ - основание системы счисления.

На первый взгляд может показаться, что в система Бергмана не представляет собой ничего особенного по сравнению с традиционным позиционным представлением, но это только на первый взгляд. Вся суть состоит именно в том, что основанием системы счисления является знаменитое иррациональное число, которое является корнем следующего алгебраического уравнения: x 2=x+1; τ=2–1+√5. Будучи корнем указанного алгебраического уравнения, "золотая пропорция" обладает следующим математическим свойством: τ n = τ n-1+τ n-2, где n принимает значения из следующего множества: 0, +1, +2, +3 ... Именно в этом обстоятельстве (иррациональное основание τ) кроется причина ряда "экзотических" свойств "системы Бергмана" (более подробно о ней можно узнать на Web-сайте "Музей Гармонии и Золотого Сечения".

Существенно подчеркнуть, что "Тау-система" переворачивает наши традиционные представления о системах счисления, более того - традиционное соотношение между числами рациональными и иррациональными. В "Тау-системе" основанием, то есть началом счисления, является некоторое иррациональное отношение τ, с помощью которого, используя систему (2) можно представить все другие числа, включая натуральные, дробные и иррациональные. Идеи Цекендорфа и Бергмана получили дальнейшее развитие в работах автора настоящей статьи. В книге "Введение в алгоритмическую теорию измерения" (1977г.) представление Фибоначчи-Цекендорфа было обобщено с помощью понятия р-кода Фибоначчи, основанного на р-числах Фибоначчи, и разработана арифметика Фибоначчи для таких представлений. Под р-кодом Фибоначчи понимается следующий способ представления натурального числа N: N=anFp(n)+an-1Fp(n-1)+...+aiFp(i)+...+a1Fp (1), (3); где ai = {0, 1} - двоичная цифра i-го разряда представления; n - разрядность представления; Fp(i) - р-число Фибоначчи, задаваемое с помощью следующей рекуррентной формулы: Fp(i)=Fp(i-1)+Fp(i-p-1); (4) Fp(1)=Fp(2)=...=Fp(p+1)=1, (5) где р - целое неотрицательное число, принимающее значение из множества {0, 1, 2, 3 ...}. Заметим, что понятие "р-кода Фибоначчи" включает в себя бесконечное число представлений, так как каждому р соответствует свое представление; при этом для случая р=0 р-код Фибоначчи вырождается в классическое двоичное представление, а для случая р=1 - в представление Фибоначчи-Цекендорфа. При р=x любое р-число Фибоначчи равно 1, а это означает, что р-код Фибоначчи сводится к так называемому "унитарному коду": N=1+1+:+1; А это, в свою очередь, означает, что р-коды Фибоначчи как бы заполняют пробел между классической двоичной системой счисления и унитарным кодом, включая их в качестве частных крайних случаев. В книге "Коды золотой пропорции" (1984г.) с использованием так называемых обобщенных золотых пропорций была обобщена система счисления Бергмана. Такие способы представления чисел были названы кодами золотой пропорции. Под кодами золотой пропорции понимаются следующие способы ^{представления действительного числа А: A= aiτpi (6), где ai - двоичные} цифры, 0 или 1; i=0, +1, +2, +3 ...; τpi - вес i-й цифры в представлении; τp - "золотая р-пропорция", являющаяся действительным корнем следующего алгебраического уравнения: τp+1=τp+1, где целое число р принимает значение из множества {0, 1, 2, 3 ...}. Заметим, что при р=0 уравнение золотой р-пропорции вырождается в тривиальное уравнение x=2, и при этом tp=2; при р=1 оно вырождается в уравнение для классической золотой пропорции и корень τp совпадает с классической золотой пропорцией. Будучи корнем указанного алгебраического уравнения, "золотая р-пропорция" обладает следующим математическим свойством:  τpi=τpn-1+τpp-n-1=τp×τpn-1, где n принимает значения из следующего множества: 0, +1, +2, +3 ... Заметим, что код золотой пропорции (6) является весьма широким обобщением классической двоичной системы счисления (случай р = 0) и системы Бергмана (р=1). При р=x код золотой пропорции сводится к "унитарному коду". Таким образом, р-коды Фибоначчи (3) и коды золотой р-пропорции (6) есть не что иное, как весьма широкое обобщение классического двоичного представления. Для представления чисел они используют те же двоичные символы 0 и 1 и по форме представления ничем не отличаются от классического двоичного кода. Различие между ними возникает только на этапе интерпретации весов двоичных разрядов. Например, одна и та же комбинация двоичных знаков 1001101 представляет в двоичной системе счисления различные числа, а именно число 45=26+23+22+20 в классической двоичной системе счисления, число 19=13+3+2+1 в коде Фибоначчи (1) и число А=τ6+τ3+τ2+τ0 - в "Тау-системе" τ =2-1+√5 (2), Заметим, что число А является иррациональным числом! А это означает, что в "Тау-системе" мы можем представлять некоторые иррациональные числа в виде конечной совокупности битов! В этом и состоит первый неожиданный результат, вытекающий из теории кодов золотой пропорции.

Основное  преимущество кодов Фибоначчи и  кодов золотой пропорции для  практических применений состоит в  их "естественной" избыточности, которая может быть использована для целей контроля числовых преобразований. Эта избыточность проявляет себя в свойстве "Множественности" представлений одного и того же числа. Например, число 19 в коде Фибоначчи  имеет и другие кодовые представления:

19=1001101=1010001=1010010=0111101

При этом различные кодовые представления  одного и того же числа могут быть получены одно из другого с помощью  специальных фибоначчиевых операций "свертки" (011→100) и "развертки" (100→011), выполняемых над кодовым изображением числа. Если над кодовым изображением выполнить все возможные "свертки", то мы придем к специальному фибоначчиевому изображению, называемому "минимальной формой", в которой двух единиц рядом в кодовом изображении не встречается. Если же в кодовом изображении выполнить все возможные операции "развертки", то придем к специальному фибоначчиевому изображению, называемому "максимальной", или "развернутой" формой, в которой рядом не встречается двух нулей.

Именно  эти математические результаты стали  основой для проектов создания компьютерных и измерительных систем на основе "фибоначчиевого" и "золотого" представлений [27].

_{ГЛАВА 2. ПЕДАГОГИЧЕСКИЕ И МЕТОДИЧЕСКИЕ ОСОБЕННОСТИ ПРЕПОДАВАНИЯ ТЕМЫ «СИСТЕМЫ СЧИСЛЕНИЯ»}

2.1. Методика преподавания темы «Системы счисления»

Что такое система счисления?

Система счисления — это совокупность приемов и правил, по которым числа записываются и читаются.

Существуют позиционные и непозиционные  системы счисления. В непозиционных системах счисления вес цифры (т. е. тот вклад, который она вносит в значение числа) не зависит от ее позиции в записи числа. Так, в римской системе счисления в числе ХХХII (тридцать два) вес цифры Х в любой позиции равен просто десяти. В позиционных системах счисления вес каждой цифры изменяется в зависимости от ее положения (позиции) в последовательности цифр, изображающих число. Например, в числе 757,7 первая семерка означает 7 сотен, вторая — 7 единиц, а третья — 7 десятых долей единицы. Сама же запись числа 757,7 означает сокращенную запись выражения 700+50+7+0,7=7^.10²+5^.10¹+7^.10⁰+7^.10^—1= 757,7. Любая позиционная система счисления характеризуется своим основанием.

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

За основание системы можно  принять любое натуральное число  — два, три, четыре и т.д. Следовательно, возможно бесчисленное множество позиционных систем: двоичная, троичная, четверичная и т.д. Запись чисел в каждой из систем счисления с основанием q означает сокращенную запись выражения a_n-1 q^n-1 + a_n-2 q^n-2 + ... + a₁ q¹ + a₀ q⁰ + a_-1 q^-1 + ... + a_-m q^-m, где a_i —цифры системы счисления; n и m — число целых и дробных разрядов, соответственно. Например:

Как порождаются целые числа  в позиционных системах счисления?

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

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

Целые числа в любой системе  счисления порождаются с помощью  Правила счета [3]: Для образования целого числа, следующего за любым данным целым числом, нужно продвинуть самую правую цифру числа; если какая-либо цифра после продвижения стала нулем, то нужно продвинуть цифру, стоящую слева от неё.

Применяя это правило, запишем первые десять целых чисел

• в двоичной системе: 0, 1, 10, 11, 100, 101, 110, 111, 1000, 1001;
• в троичной системе: 0, 1, 2, 10, 11, 12, 20, 21, 22, 100;
• в пятеричной системе: 0, 1, 2, 3, 4, 10, 11, 12, 13, 14;
• в восьмеричной системе: 0, 1, 2, 3, 4, 5, 6, 7, 10, 11[16].

Какие системы счисления используют специалисты для общения с  компьютером?

Кроме десятичной широко используются системы с основанием, являющимся целой степенью числа 2, а именно:

• двоичная (используются цифры 0, 1);
• восьмеричная (используются цифры 0, 1, ..., 7);
• шестнадцатеричная (для первых целых чисел от нуля до девяти используются цифры 0, 1, ..., 9, а для следующих чисел — от десяти до пятнадцати — в качестве цифр используются символы A, B, C, D, E, F).

Полезно запомнить запись в этих системах счисления первых двух десятков целых  чисел: