stringtranslate.com

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

Унарная система счисления является простейшей системой счисления для представления натуральных чисел : [1] чтобы представить число N , символ, представляющий 1, повторяется N раз. [2]

В унарной системе число (ноль) представлено пустой строкой , то есть отсутствием символа. Числа 1, 2, 3, 4, 5, 6, ... представлены в унарной системе как 1, 11, 111, 1111, 11111, 111111, ... [3]

Унарная система счисления является биективной . Однако, хотя ее иногда описывают как «основание 1», [4] она отличается в некоторых важных отношениях от позиционных обозначений , в которых значение цифры зависит от ее положения в числе. Например, унарная форма числа может быть экспоненциально длиннее, чем его представление в других основаниях. [5]

Использование меток счета при счете является применением унарной системы счисления. Например, при использовании метки счета | (𝍷) число 3 представляется как ||| . В восточноазиатских культурах число 3 представляется как 三, иероглиф, нарисованный тремя чертами. [6] (Один и два представляются аналогично.) В Китае и Японии иероглиф 正, нарисованный пятью чертами, иногда используется для представления числа 5 в качестве счета. [7] [8]

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

Операции

Сложение и вычитание особенно просты в унарной системе, поскольку они требуют немного больше, чем просто конкатенации строк . [9] Операция подсчета веса Хэмминга или популяции, которая подсчитывает количество ненулевых битов в последовательности двоичных значений, также может быть интерпретирована как преобразование из унарных в двоичные числа . [10] Однако умножение более громоздко и часто использовалось в качестве тестового случая для проектирования машин Тьюринга . [11] [12] [13]

Сложность

По сравнению со стандартными позиционными системами счисления , унарная система неудобна и, следовательно, не используется на практике для больших вычислений. Она встречается в некоторых описаниях задач принятия решений в теоретической информатике (например, некоторые P-полные задачи), где она используется для «искусственного» уменьшения времени выполнения или требований к пространству для задачи. Например, предполагается, что задача целочисленной факторизации требует больше, чем полиномиальная функция длины входных данных в качестве времени выполнения, если входные данные заданы в двоичном виде , но ей требуется только линейное время выполнения, если входные данные представлены в унарных числах. [14] Однако это может ввести в заблуждение. Использование унарных входных данных медленнее для любого заданного числа, а не быстрее; различие заключается в том, что двоичные (или с большим основанием) входные данные пропорциональны логарифму числа по основанию 2 (или большему основанию), в то время как унарные входные данные пропорциональны самому числу. Поэтому, хотя время выполнения и требования к пространству в унарных числах выглядят лучше как функция размера входных данных, они не представляют собой более эффективного решения. [15]

В теории вычислительной сложности унарная нумерация используется для различения сильно NP-полных задач от задач, которые являются NP-полными , но не сильно NP-полными. Задача, в которой входные данные включают некоторые числовые параметры, является сильно NP-полной, если она остается NP-полной даже при искусственном увеличении размера входных данных путем представления параметров в унарной форме. Для такой задачи существуют сложные примеры, для которых все значения параметров не более чем полиномиально велики. [16]

Приложения

Помимо применения в подсчетах, унарная нумерация используется как часть некоторых алгоритмов сжатия данных, таких как кодирование Голомба . [17] Она также формирует основу для аксиом Пеано для формализации арифметики в математической логике . [18] Форма унарной нотации, называемая кодированием Чёрча, используется для представления чисел в лямбда-исчислении . [19]

Некоторые фильтры спама в электронной почте помечают сообщения несколькими звездочками в заголовке электронной почты , такими как X-Spam-Bar или X-SPAM-LEVEL . Чем больше число, тем больше вероятность, что электронное письмо будет считаться спамом. Использование унарного представления вместо десятичного числа позволяет пользователю искать сообщения с заданным рейтингом или выше. Например, поиск **** выдает сообщения с рейтингом не менее 4. [20]

Смотрите также

Ссылки

  1. ^ Ходжес, Эндрю (2009), От одного до девяти: Внутренняя жизнь чисел, Anchor Canada, стр. 14, ISBN 9780385672665.
  2. ^ Дэвис, Мартин; Сигал, Рон; Вейукер, Элейн Дж. (1994), Вычислимость, сложность и языки: основы теоретической информатики, информатика и научные вычисления (2-е изд.), Academic Press, стр. 117, ISBN 9780122063824.
  3. ^ Хекст, Ян (1990), Структуры программирования: машины и программы , т. 1, Prentice Hall, стр. 33, ISBN 9780724809400.
  4. ↑ Брайан Хейс (2001), «Третья база», American Scientist , 89 (6): 490, doi :10.1511/2001.40.3268, заархивировано из оригинала 2014-01-11 , извлечено 2013-07-28
  5. ^ Здановски, Конрад (2022), «Об эффективности обозначений для натуральных чисел», Теоретическая информатика , 915 : 1–10, doi :10.1016/j.tcs.2022.02.015, MR  4410388
  6. ↑ Вудрафф, Чарльз Э. (1909), «Эволюция современных цифр от древних меток счета», American Mathematical Monthly , 16 (8–9): 125–33, doi :10.2307/2970818, JSTOR  2970818.
  7. ^ Хсие, Хуэй-Куан (1981), «Китайская метка счета», The American Statistician , 35 (3): 174, doi : 10.2307/2683999, JSTOR  2683999
  8. ^ Лунде, Кен; Миура, Дайсуке (27 января 2016 г.), «Предложение о кодировании пяти идеографических меток», Консорциум Unicode (PDF) , Предложение L2/16-046
  9. ^ Сазонов, Владимир Ю. (1995), «О возможных числах», Логика и вычислительная сложность (Индианаполис, Индиана, 1994), Lecture Notes in Comput. Sci., т. 960, Springer, Берлин, стр. 30–51, doi :10.1007/3-540-60178-3_78, ISBN 978-3-540-60178-4, г-н  1449655. См. в частности стр. 48.
  10. ^ Блакселл, Дэвид (1978), «Связывание записей с помощью сопоставления битовых шаблонов», в Хогбен, Дэвид; Файф, Деннис В. (ред.), Компьютерные науки и статистика — Десятый ежегодный симпозиум по интерфейсу, Специальная публикация NBS, т. 503, Министерство торговли США / Национальное бюро стандартов, стр. 146–156.
  11. ^ Хопкрофт, Джон Э .; Ульман, Джеффри Д. (1979), Введение в теорию автоматов, языки и вычисления , Addison Wesley, Пример 7.7, стр. 158–159, ISBN 978-0-201-02988-8.
  12. ^ Дьюдни, AK (1989), Новый Тьюринг Омнибус: Шестьдесят шесть экскурсов в информатику, Computer Science Press, стр. 209, ISBN 9780805071665.
  13. ^ Ренделл, Пол (2015), «5.3 Более крупный пример TM: Унарное умножение», Универсальность машины Тьюринга в игре «Жизнь», «Эмерджентность, сложность и вычисления», т. 18, Springer, стр. 83–86, ISBN 9783319198422.
  14. ^ Арора, Санджив ; Барак, Боаз (2007), «Вычислительная модель — и почему она не имеет значения» (PDF) , Computational Complexity: A Modern Approach (черновик, январь 2007 г.), Cambridge University Press, §17, стр. 32–33 , получено 10 мая 2017 г..
  15. ^ Мур, Кристофер ; Мертенс, Стефан (2011), Природа вычислений, Oxford University Press, стр. 29, ISBN 9780199233212.
  16. ^ Гэри, MR ; Джонсон, DS (1978), "«Сильные» результаты NP-полноты: мотивация, примеры и последствия», Журнал ACM , 25 (3): 499–508, doi : 10.1145/322077.322090 , MR  0478747, S2CID  18371269.
  17. ^ Голомб, SW (1966), «Кодирование длин серий», Труды IEEE по теории информации , IT-12 (3): 399–401, doi :10.1109/TIT.1966.1053907.
  18. ^ Magaud, Nicolas; Bertot, Yves (2002), «Изменение структур данных в теории типов: исследование натуральных чисел», Типы для доказательств и программ (Durham, 2000) , Lecture Notes in Comput. Sci., т. 2277, Springer, Berlin, стр. 181–196, doi :10.1007/3-540-45842-5_12, ISBN 978-3-540-43287-6, МР  2044538.
  19. ^ Янсен, Ян Мартин (2013), «Программирование в λ-исчислении: от Чёрча до Скотта и обратно», Красота функционального кода , Lecture Notes in Computer Science, т. 8106, Springer-Verlag, стр. 168–180, doi :10.1007/978-3-642-40355-2_12, ISBN 978-3-642-40354-5.
  20. ^ Электронная почта, борьба со спамом, как получить обслуживание для серверов ведомственной электронной почты

Внешние ссылки

На Викискладе есть медиафайлы по теме Унарная система счисления.