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

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

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

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

Использование меток при подсчете является применением унарной системы счисления. Например, используя метку | (𝍷), число 3 представляется как ||| . В культурах Восточной Азии цифра 3 представлена как 三 , символ, нарисованный тремя штрихами. ^{[ 6 ]} (Один и два представлены аналогично.) В Китае и Японии иероглиф 正, нарисованный пятью штрихами, иногда используется для обозначения пяти в качестве подсчета. ^{[ 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 ]}

См. также

Ссылки

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

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

Последовательность OEIS A000042 (унарное представление натуральных чисел)

[1] Ходжес, Эндрю (2009), От одного до девяти: внутренняя жизнь чисел , Anchor Canada, стр. 14, ISBN 9780385672665 .

[2] Дэвис, Мартин; Сигал, Рон; Вейкер, Элейн Дж. (1994), Вычислимость, сложность и языки: основы теоретической информатики , информатики и научных вычислений (2-е изд.), Academic Press, стр. 117, ISBN 9780122063824 .

[3] Хекст, Январь (1990), Структуры программирования: машины и программы , том. 1, Прентис Холл, с. 33, ISBN 9780724809400 .

[4] Брайан Хейс (2001), «Третья база» , American Scientist , 89 (6): 490, doi : 10.1511/2001.40.3268 , заархивировано из оригинала 11 января 2014 г. , получено 28 июля 2013 г.

[5] Здановский, Конрад (2022), «Об эффективности обозначений натуральных чисел», Theoretical Computer Science , 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

[Lunde_2016-2-8] Лунде, Кен; Миура, Дайсуке (27 января 2016 г.), «Предложение по кодированию пяти идеографических меток», Консорциум Unicode (PDF) , Предложение L2/16-046

[9] Сазонов Владимир Юрьевич. (1995), «О допустимых числах», Логика и вычислительная сложность (Индианаполис, Индиана, 1994) , Конспекты лекций по вычислительной технике. наук., вып. 960, Springer, Берлин, стр. 30–51 , номер документа : 10.1007/3-540-60178-3_78 , ISBN. 978-3-540-60178-4 , МР 1449655 . См., в частности, стр. 48.

[blaxell-10] Блэкселл, Дэвид (1978), «Связывание записей путем сопоставления битовых шаблонов», в Хогбене, Дэвид; Файф, Деннис В. (ред.), Информатика и статистика - Десятый ежегодный симпозиум по интерфейсу , Специальная публикация NBS, том. 503, Министерство торговли США/Национальное бюро стандартов, стр. 146–156 .

[11] Хопкрофт, Джон Э .; Уллман, Джеффри Д. (1979), Введение в теорию автоматов, языки и вычисления , Аддисон Уэсли, Пример 7.7, стр. 158–159 , ISBN 978-0-201-02988-8 .

[12] Дьюдни, AK (1989), Новый омнибус Тьюринга: шестьдесят шесть экскурсов в информатику , Computer Science Press, стр. 209, ISBN 9780805071665 .

[13] Ренделл, Пол (2015), «5.3 Большой пример ТМ: унарное умножение», Универсальность машины Тьюринга в игре жизни , возникновение, сложность и вычисления, том. 18, Спрингер, стр. 83–86, ISBN. 9783319198422 .

[14] Арора, Санджив ; Барак, Боаз (2007 г.), «Вычислительная модель - и почему она не имеет значения» (PDF) , Вычислительная сложность: современный подход (проект, январь 2007 г.), Cambridge University Press, §17, стр. 32–33 , получено 10 мая 2017 г.

[15] Мур, Кристофер ; Мертенс, Стефан (2011), Природа вычислений , Oxford University Press, стр. 29, ISBN 9780199233212 .

[16] Гэри, MR ; Джонсон, Д.С. (1978), «Сильные» результаты NP-полноты: мотивация, примеры и последствия», Journal of the 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] Маго, Николя; Берто, Ив (2002), «Изменение структур данных в теории типов: изучение натуральных чисел», Типы для доказательств и программ (Дарем, 2000) , Конспекты лекций по вычислениям. наук., вып. 2277, Springer, Berlin, стр. 181–196, номер документа : 10.1007/3-540-45842-5_12 , ISBN. 978-3-540-43287-6 , МР 2044538 .

[19] Янсен, Ян Мартин (2013), «Программирование в λ-исчислении: от Черча до Скотта и обратно», Красота функционального кода , Конспекты лекций по информатике, том. 8106, Springer-Verlag, стр. 168–180, номер документа : 10.1007/978-3-642-40355-2_12 , ISBN. 978-3-642-40354-5 .

[20] Электронная почта, Контроль спама, Как получить услугу для почтовых серверов ведомства

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]

[ 20 ]