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

Системы счисления
Индусско-арабская система счисления
Западный арабский Восточно-арабский Бенгальский Деванагари Гуджарати Гурмукхи Одиа Сингальский Тамильский Малаялам телугу Каннада Дзонгка тибетский Балийский Бирманский Яванский Кхмерский Лаосский Монгольский Тайский
Восточная Азия
Китайский Сучжоу Хоккиен Японский Корейский вьетнамский Тангутский Счетные стержни
Американец
Кактовик (инупиак)
По алфавиту
Абджад Армянский Ryabhaṭa Кириллица Geʽez Грузинский Греческий иврит Римский
Бывший
Эгейский Чердак Вавилонский Брахми Чувашский Цистерцианский Египтянин Этрусский Глаголица Харости майя Муиска Pentimal Доисторический счет Подсчетные отметки Quipu
Позиционные системы по основанию
2 3 4 5 6 8 10 12 16 20 60
Нестандартные позиционные системы счисления
Биективная нумерация ( 1 ) Знаковое представление ( сбалансированное троичное ) смешанный ( факториал ) отрицательный Комплексно-базовая система ( 2 i ) Нецелое основание счисления ( φ ) Асимметричные системы счисления
Список систем счисления
v т е

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

В унарной системе число 0 (ноль) представлено пустой строкой , то есть отсутствием символа. Числа 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]

См. Также [ править ]

Унарное кодирование
Быстрое кодирование

Ссылки [ править ]

↑ Ходжес, Эндрю (2009), Один к девяти: Внутренняя жизнь чисел , Anchor Canada, p. 14, ISBN 9780385672665.
^ Дэвис, Мартин; Сигал, Рон; Вейкер, Элейн Дж. (1994), Вычислимость, сложность и языки: основы теоретической информатики , информатики и научных вычислений (2-е изд.), Academic Press, стр. 117, ISBN 9780122063824.
^ Hext, Ян (1990), Программирование Структура: Машины и программа , Программирование Структуры, 1 , Prentice Hall, стр. 33, ISBN 9780724809400.
^ Вудрафф, Charles E. (1909), "Эволюция современных числительных от древнего Tally Marks" , American Mathematical Monthly , 16 (8-9): 125-33, DOI : 10,2307 / 2970818 , JSTOR 2970818 .
^ Се, Хуэй-Куаны (1981), "Китайский Tally Марк", американский статистик , 35 (3): 174, DOI : 10,2307 / 2683999
^ Лунде, Кен; Миура, Дайсуке (27 января 2016 г.), «Предложение о кодировании пяти идеографических меток подсчета », Консорциум Unicode (PDF) , предложение L2 / 16-046
^ Сазонов, Владимир Ю. (1995), «О допустимых числах», « Логическая и вычислительная сложность» (Индианаполис, Индиана, 1994) , Конспекты лекций по вычислениям. Sci., 960 , Springer, Berlin, стр. 30–51 , DOI : 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.
^ Dewdney, AK (1989), The New Тьюринг Omnibus: Шестьдесят шесть Экскурсия по информатике , Computer Science Press, стр. 209, ISBN 9780805071665.
^ Ренделл, Пол (2015), «5.3 Более крупный пример TM: унарное умножение», Универсальность машины Тьюринга игры жизни , возникновения, сложности и вычислений, 18 , Springer, стр. 83–86, ISBN 9783319198422.
^ Арора, Санджив ; Барак, Боаз (2007), «Вычислительная модель - и почему это не имеет значения» (PDF) , Computational Complexity: A Modern Approach (январь 2007 г., проект изд.), Cambridge University Press, §17, стр. 32–33 , получено 10 мая, 2017 .
^ Фейгенбаум, Joan (осень 2012), CPSC 468/568 HW1 Solution Set (PDF) , факультет информатики, Йельский университет , извлекаться 2014-10-21 .
^ Мур, Кристофер ; Мертенс, Стефан (2011), Природа вычислений , Oxford University Press, стр. 29, ISBN 9780199233212.
^ Garey, MR ; Джонсон, DS (1978), " ' Сильные' NP-полнота результатов: Мотивация, примеры и последствия", Журнал ACM , 25 (3): 499-508, DOI : 10,1145 / 322077,322090 , MR 0478747 .
^ Голомб, SW (1966), "кодирование длин серий" , IEEE Transactions по теории информации , IT-12 (3): 399-401, DOI : 10,1109 / TIT.1966.1053907.
^ Маго, Николя; Берто, Ив (2002), "Изменение структур данных в теории типов: исследование натуральных чисел", Типы для доказательств и программ (Дарем, 2000) , Конспекты лекций в Comput. Sci . , 2277 ., Springer, Berlin, С. 181-196, DOI : 10.1007 / 3-540-45842-5_12 , ISBN 978-3-540-43287-6, Руководство по ремонту 2044538.
^ Янсен, Ян Мартин (2013), «Программирование в λ-исчислении: от Черча до Скотта и обратно», Красота функционального кода: Очерки, посвященные Ринусу Пласмейеру по случаю его 61-летия , Лекционные заметки по компьютерным наукам, 8106 , Springer-Verlag, стр. 168–180, DOI : 10.1007 / 978-3-642-40355-2_12 , ISBN 978-3-642-40354-5.

Внешние ссылки [ править ]

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

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

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

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

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

[4] Вудрафф, Charles E. (1909), "Эволюция современных числительных от древнего Tally Marks" , American Mathematical Monthly , 16 (8-9): 125-33, DOI : 10,2307 / 2970818 , JSTOR 2970818 .

[5] Се, Хуэй-Куаны (1981), "Китайский Tally Марк", американский статистик , 35 (3): 174, DOI : 10,2307 / 2683999

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

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

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

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

[10] Dewdney, AK (1989), The New Тьюринг Omnibus: Шестьдесят шесть Экскурсия по информатике , Computer Science Press, стр. 209, ISBN 9780805071665.

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

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

[13] Фейгенбаум, Joan (осень 2012), CPSC 468/568 HW1 Solution Set (PDF) , факультет информатики, Йельский университет , извлекаться 2014-10-21 .

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

[15] Garey, MR ; Джонсон, DS (1978), " ' Сильные' NP-полнота результатов: Мотивация, примеры и последствия", Журнал ACM , 25 (3): 499-508, DOI : 10,1145 / 322077,322090 , MR 0478747 .

[16] Голомб, SW (1966), "кодирование длин серий" , IEEE Transactions по теории информации , IT-12 (3): 399-401, DOI : 10,1109 / TIT.1966.1053907.

[17] Маго, Николя; Берто, Ив (2002), "Изменение структур данных в теории типов: исследование натуральных чисел", Типы для доказательств и программ (Дарем, 2000) , Конспекты лекций в Comput. Sci . , 2277 ., Springer, Berlin, С. 181-196, DOI : 10.1007 / 3-540-45842-5_12 , ISBN 978-3-540-43287-6, Руководство по ремонту 2044538.

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