На главную

4. Почему в теории сложности и в компьютерах используется двоичная система счисления?

 

На самом деле, троичная система счисления экономичнее двоичной [8].

В двоичной системе счисления используется два символа { 0, 1 }. Тогда, для n двоичных разрядов, общее количество символов будет равно

                                                                 h = 2·n .                                                                (1.3)

С их помощью можно задать

                                                                  N2 = 2n                                                                 (1.4)

натуральных чисел.

Теперь возьмем три знака { 0, 1, 2 }.

Найдем m = h/3 – количество троичных знаков для заданного h и

                                                                  N3 = 3m                                                                (1.5)

количество чисел, которое можно задать с помощью m троичных знаков.

Нетрудно показать, что для h > 5 , N3  всегда превышает N2.

Например, для h = 6 имеем  n = 3, m = 2  и N2 = 23 = 8, тогда как N3 = 32 = 9.

Интересно неформально посмотреть, в чем суть такого сжатия.

Если записать троичные знаки как { 0, 1, -1 }, то видно, что троичная система счисления это та же двоичная, но со знаковыми битами.

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

Однако, если мы просто будем увеличивать символьную емкость, путем увеличения основания системы счисления, например, представляя натуральные числа в 4 – ичной, 5 – ичной и тд. системе счисления, то эффект будет обратным. Это хорошо видно на рисунке 1, где показана зависимость потенциальной емкости N от основания системы счисления (для семи разрядов).

Рисунок 1.   N = x7/x

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

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

Однако закон сохраненя (B2) по-прежнему в силе – на халяву тут не пройдет. В случае троичной системы мы теряем во времени, а именно в скорости поиска информации. Хорошо известно, что двоичный поиск данных в отсортированном массиве самый быстрый. Поскольку стоимость быстродействия для программиста важнее затрат памяти (Microsoft это не касается), то оптимальной оказывается двоичная система, да и физически она проще в реализации.

Тем не менее, в будущем, троичная система может найти применение в распределенных вычислительных средах. Один из доводов – по двум каналам с тремя уровнями можно передать 9 сообщений, а тремя каналами с двумя уровнями только 8, при этом затраты h = 2·3 одинаковы.

 

              

 


The Programs And Source Codes Rambler's Top100 Rambler's Top100