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

Системи числення
Індо-арабська система числення
Східна Азія
Алфавітні
Давні
  • Доісторичні[en]
Позиційні системи числення за основою
Не стандартні позиційні системи числення[en]
Список систем числення[en]

Унарна система числення — це бієктивна[en] система числення із базисом-1. Це найпростіша система числення для представлення дійсних чисел:[1] для того, щоб в ній представити число N, довільно вибраний символ, який використовується як 1 повторюється N разів.[2] Наприклад, числа 1, 2, 3, 4, 5, … будуть виглядати в такій системі як показано нижче[3]

1, 11, 111, 1111, 11111, …

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

Застосування

Унарні числа використовуються в деяких алгоритмах стиснення даних, таких як код Голомба.[4] Це поняття також є основою для аксіом Пеано, що формалізують арифметику в рамках математичної логіки.[5] Форма унарної нотації, яка називається кодування Черча[en] використовується для представлення чисел в Лямбда-численні.[6]

Складність

У порівнянні зі стандартним позиційним записом, унарна система незручна і тому не використовується на практиці для великих обчислень. Вона зустрічається в описах деяких проблем вибору в теорії алгоритмів (наприклад в деяких P-повних[en] задачах), де її використовують, щоб «штучно» зменшити час виконання або просторові вимоги задачі. Наприклад, підозрюють, що задача факторизації цілих чисел вимагає часу виконання більшого ніж поліномна функція від довжини її входу в двійковому записі, але їй потрібен лише лінійний час якщо вхід представлено унарно.[7] Однак, це потенційно оманливо. Використання унарного входу повільніше для будь-якого заданого числа, не швидше. Відмінність у тому, що двійковий (або більшої основи) вхід пропорційний логаритму з основою два (або більше) числа тоді як унарний вхід пропорційний самому числу. Отже, хоча з унарною системою час виконання і просторові вимоги як функції від довжини входу виглядають краще, вони не представляють дієвішого розв'язання.[8]

У теорії складності обчислень, унарні числа використовуються, щоб відрізнити сильно NP-повні[en] задачі від NP-повних, але не сильно NP-повних. Задача, що має на вході якісь числові параметри сильно NP-повна, якщо вона залишається NP-повною навіть коли розмір входу штучно збільшують переводячи його в унарну систему. Для такої задачі, існують складні випадки для яких значення всіх параметрів майже поліномно великі.[9]

Примітки

  1. ↑ Hodges, Andrew (2009). One to Nine: The Inner Life of Numbers. Anchor Canada. с. 14. ISBN 9780385672665. «The simplest way to write the natural numbers is by the unary notation» .
  2. ↑ Davis, Martin; Sigal, Ron; Weyuker, Elaine J. (1994). Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science. Computer Science and Scientific Computing (вид. 2nd). Academic Press. с. 117. ISBN 9780122063824. «the base 1 (or unary) representation of the number x is simply a string of ones of length x» .
  3. ↑ Hext, Jan (1990). Programming Structures: Machines and programs. Programming Structures. Т. 1. Prentice Hall. с. 33. ISBN 9780724809400. .
  4. ↑ Golomb, S.W. (1966). Run-length encodings. IEEE Transactions on Information Theory. IT-12 (3): 399–401. doi:10.1109/TIT.1966.1053907. .
  5. ↑ Magaud, Nicolas; Bertot, Yves (2002). Changing data structures in type theory: a study of natural numbers. Types for proofs and programs (Durham, 2000). Lecture Notes in Comput. Sci. Т. 2277. Springer, Berlin. с. 181–196. doi:10.1007/3-540-45842-5_12. MR 2044538. .
  6. ↑ Jansen, Jan Martin (2013). Programming in the λ-calculus: from Church to Scott and back. The Beauty of Functional Code: Essays Dedicated to Rinus Plasmeijer on the Occasion of His 61st Birthday. Lecture Notes in Computer Science. Т. 8106. Springer-Verlag. с. 168–180. doi:10.1007/978-3-642-40355-2_12. .
  7. ↑ Arora, Sanjeev; Barak, Boaz (2007). The computational model —and why it doesn't matter [Обчислювальна модель і чому вона не має значення]. Computational Complexity: A Modern Approach [Обчислювальна складність: Сучасний підхід] (вид. січень 2007, чорнетка). Cambridge University Press. §17, с. 32–33. Процитовано 10 травня 2017. .
  8. ↑ Moore, Cristopher; Mertens, Stephan (2011). The Nature of Computation [Природа обчислень]. Oxford University Press. с. 29. ISBN 9780199233212. .
  9. ↑ Garey, M. R.; Johnson, D. S. (1978). 'Strong' NP-completeness results: Motivation, examples, and implications [Висліди в сильній NP-повноті: Спонука, приклади і наслідки]. Journal of the ACM. 25 (3): 499–508. doi:10.1145/322077.322090. MR 0478747. S2CID 18371269. .