stringtranslate.com

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

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

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

Унарная — биективная система счисления. Однако, поскольку значение цифры не зависит от ее позиции, она не является формой позиционной записи , и неясно, будет ли уместно говорить, что ее основание (или «основание») равно 1 , поскольку он ведет себя иначе, чем все другие базы. [ нужна цитата ]

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

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

Операции

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

Сложность

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

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

Приложения

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

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

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

Рекомендации

  1. ^ Ходжес, Эндрю (2009), От одного до девяти: Внутренняя жизнь чисел, Anchor Canada, стр. 14, ISBN 9780385672665.
  2. ^ Дэвис, Мартин; Сигал, Рон; Вейкер, Элейн Дж. (1994), Вычислимость, сложность и языки: основы теоретической информатики, информатики и научных вычислений (2-е изд.), Academic Press, с. 117, ISBN 9780122063824.
  3. ^ Hext, Январь (1990), Структуры программирования: машины и программы , том. 1, Прентис Холл, с. 33, ISBN 9780724809400.
  4. ^ Вудрафф, Чарльз Э. (1909), «Эволюция современных цифр из древних меток», American Mathematical Monthly , 16 (8–9): 125–33, doi : 10.2307/2970818, JSTOR  2970818.
  5. ^ Се, Хуэй-Куанг (1981), «Китайская метка», The American Statistician , 35 (3): 174, doi : 10.2307/2683999, JSTOR  2683999
  6. ^ Лунде, Кен; Миура, Дайсуке (27 января 2016 г.), «Предложение по кодированию пяти идеографических меток», Консорциум Unicode (PDF) , Предложение L2/16-046
  7. ^ Сазонов, Владимир Ю. (1995), «О допустимых числах», Логика и вычислительная сложность (Индианаполис, Индиана, 1994), Конспекты лекций по вычислениям. наук, том. 960, Springer, Берлин, стр. 30–51, номер документа : 10.1007/3-540-60178-3_78, ISBN. 978-3-540-60178-4, МР  1449655. См., в частности, стр. 48.
  8. ^ Блэкселл, Дэвид (1978), «Связывание записей путем сопоставления битовых шаблонов», в Хогбене, Дэвид; Файф, Деннис В. (ред.), Информатика и статистика - Десятый ежегодный симпозиум по интерфейсу, Специальная публикация NBS, том. 503, Министерство торговли США/Национальное бюро стандартов, стр. 146–156..
  9. ^ Хопкрофт, Джон Э .; Уллман, Джеффри Д. (1979), Введение в теорию автоматов, языки и вычисления , Аддисон Уэсли, пример 7.7, стр. 158–159, ISBN 978-0-201-02988-8.
  10. ^ Дьюдни, AK (1989), Новый омнибус Тьюринга: шестьдесят шесть экскурсов в информатику, Computer Science Press, стр. 209, ISBN 9780805071665.
  11. ^ Ренделл, Пол (2015), «5.3 Большой пример TM: унарное умножение», Универсальность машины Тьюринга в игре «Жизнь, возникновение, сложность и вычисления», том. 18, Спрингер, стр. 83–86, ISBN. 9783319198422.
  12. ^ Арора, Санджив ; Барак, Боаз (2007 г.), «Вычислительная модель - и почему она не имеет значения» (PDF) , Вычислительная сложность: современный подход (проект, январь 2007 г.), Cambridge University Press, §17, стр. 32–33 , получено 10 мая 2017 г..
  13. ^ Фейгенбаум, Джоан (осень 2012 г.), Набор решений CPSC 468/568 HW1 (PDF) , Факультет компьютерных наук, Йельский университет , получено 21 октября 2014 г.. [ постоянная мертвая ссылка ]
  14. ^ Мур, Кристофер ; Мертенс, Стефан (2011), Природа вычислений, Oxford University Press, стр. 29, ISBN 9780199233212.
  15. ^ Гэри, MR ; Джонсон, DS (1978), "«Сильные» результаты NP-полноты: мотивация, примеры и последствия», Journal of the ACM , 25 (3): 499–508, doi : 10.1145/322077.322090 , MR  0478747, S2CID  18371269.
  16. ^ Голомб, SW (1966), «Кодирование длин серий», Транзакции IEEE по теории информации , IT-12 (3): 399–401, doi : 10.1109/TIT.1966.1053907.
  17. ^ Маго, Николя; Берто, Ив (2002), «Изменение структур данных в теории типов: изучение натуральных чисел», Типы для доказательств и программ (Дарем, 2000) , Конспекты лекций по вычислениям. наук, том. 2277, Springer, Берлин, стр. 181–196, номер документа : 10.1007/3-540-45842-5_12, ISBN. 978-3-540-43287-6, МР  2044538.
  18. ^ Янсен, Ян Мартин (2013), «Программирование в λ-исчислении: от Черча до Скотта и обратно», Красота функционального кода , Конспекты лекций по информатике, том. 8106, Springer-Verlag, стр. 168–180, номер документа : 10.1007/978-3-642-40355-2_12, ISBN. 978-3-642-40354-5.
  19. ^ http://answers.uillinois.edu/illinois/page.php?id=49002

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

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