Перегляд вихідного коду сторінки Унарна система числення

{{Системи числення}}
'''Унарна система числення'''&nbsp;— це {{нп|Бієктивна нумерація|бієктивна|en|Bijective numeration}} [[Система числення|система числення]] із [[Основа системи числення|базисом]]-[[1 (число)|1]]. Це найпростіша система числення для представлення [[Натуральні числа|дійсних чисел]]:<ref>{{citation|title=One to Nine: The Inner Life of Numbers|first=Andrew|last=Hodges|publisher=Anchor Canada|year=2009|isbn=9780385672665|page=14|url=https://books.google.com/books?id=UCuwrtBax7AC&pg=PA14|quote=The simplest way to write the natural numbers is by the unary notation}}.</ref> для того, щоб в ній представити число ''N'', довільно вибраний символ, який використовується як 1 повторюється ''N'' разів.<ref>{{citation|title=Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science|first1=Martin|last1=Davis|first2=Ron|last2=Sigal|first3=Elaine J.|last3=Weyuker|edition=2nd|publisher=Academic Press|year=1994|series=Computer Science and Scientific Computing|isbn=9780122063824|page=117|url=https://books.google.com/books?id=GRWOqKwZGRAC&pg=PA117|quote=the base 1 (or unary) representation of the number {{mvar|x}} is simply a string of ones of length {{mvar|x}}}}.</ref> Наприклад, числа 1, 2, 3, 4, 5, … будуть виглядати в такій системі як показано нижче<ref>{{citation|page=33|title=Programming Structures: Machines and programs|volume=1|series=Programming Structures|first=Jan|last=Hext|publisher=Prentice Hall|year=1990|isbn=9780724809400}}.</ref>
: 1, 11, 111, 1111, 11111, …
Ці числа не слід плутати із [[Репюніти|репюнітами]], які також задаються у вигляді послідовностей одиниць але мають свою звичайне [[Десяткова система числення|десяткову]] числову інтерпретацію.

== Застосування ==
Унарні числа використовуються в деяких алгоритмах стиснення даних, таких як [[код Голомба]].<ref>{{citation
 | last = Golomb | first = S.W. | author-link = Solomon W. Golomb
 | issue = 3
 | journal = IEEE Transactions on Information Theory
 | pages = 399–401
 | title = Run-length encodings
 | url = http://urchin.earth.li/~twic/Golombs_Original_Paper/
 | volume = IT-12
|doi =10.1109/TIT.1966.1053907
 | year = 1966}}.</ref> Це поняття також є основою для [[Аксіоми Пеано|аксіом Пеано]], що формалізують арифметику в рамках [[Математична логіка|математичної логіки]].<ref>{{citation
 | last1 = Magaud | first1 = Nicolas
 | last2 = Bertot | first2 = Yves
 | contribution = Changing data structures in type theory: a study of natural numbers
 | doi = 10.1007/3-540-45842-5_12
 | mr = 2044538
 | pages = 181–196
 | publisher = Springer, Berlin
 | series = Lecture Notes in Comput. Sci.
 | title = Types for proofs and programs (Durham, 2000)
 | volume = 2277
 | year = 2002}}.</ref>
Форма унарної нотації, яка називається {{нп|Кодування Чорча|кодування Черча|en|Church encoding}} використовується для представлення чисел в [[Лямбда-числення|Лямбда-численні]].<ref>{{citation
 | last = Jansen | first = Jan Martin
 | contribution = Programming in the λ-calculus: from Church to Scott and back
 | doi = 10.1007/978-3-642-40355-2_12
 | pages = 168–180
 | publisher = Springer-Verlag
 | series = Lecture Notes in Computer Science
 | title = The Beauty of Functional Code: Essays Dedicated to Rinus Plasmeijer on the Occasion of His 61st Birthday
 | volume = 8106
 | year = 2013}}.</ref>

==Складність==
У порівнянні зі стандартним [[Позиційна нотація|позиційним записом]], унарна система незручна і тому не використовується на практиці для великих обчислень. Вона зустрічається в описах деяких [[проблема вибору|проблем вибору]] в [[теорія алгоритмів|теорії алгоритмів]] (наприклад в деяких {{нп|P-повна задача|P-повних|en|P-complete}} задачах), де її використовують, щоб «штучно» зменшити час виконання або просторові вимоги задачі. Наприклад, підозрюють, що задача [[факторизація цілих чисел|факторизації цілих чисел]] вимагає часу виконання більшого ніж поліномна функція від довжини її входу в [[Двійкова система числення|двійковому записі]], але їй потрібен лише лінійний час якщо вхід представлено унарно.<ref>{{citation
 | last1 = Arora | first1 = Sanjeev | author-link1 = Sanjeev Arora
 | last2 = Barak | first2 = Boaz
 | year = 2007
 | chapter = The computational model&nbsp;—and why it doesn't matter
 | trans_chapter = Обчислювальна модель і чому вона не має значення
 | title = Computational Complexity: A Modern Approach
 | trans_title = Обчислювальна складність: Сучасний підхід
 | publisher = Cambridge University Press
 | at = §17, с. 32–33
 | edition = січень 2007, чорнетка
 | chapter-url = http://www.cs.princeton.edu/theory/complexity/modelchap.pdf
 | access-date = 10 травня 2017
 }}.</ref> Однак, це потенційно оманливо. Використання унарного входу повільніше для будь-якого заданого числа, не швидше. Відмінність у тому, що двійковий (або більшої основи) вхід пропорційний логаритму з основою два (або більше) числа тоді як унарний вхід пропорційний самому числу. Отже, хоча з унарною системою час виконання і просторові вимоги як функції від довжини входу виглядають краще, вони не представляють дієвішого розв'язання.<ref>{{citation|title=The Nature of Computation|trans_title=Природа обчислень|first1=Cristopher|last1=Moore|first2=Stephan|last2=Mertens|publisher=Oxford University Press|year=2011|isbn=9780199233212|page=29|url=https://books.google.com/books?id=z4zMiZyAE1kC&pg=PA29}}.</ref>

У [[теорія складності обчислень|теорії складності обчислень]], унарні числа використовуються, щоб відрізнити {{нп|сильно NP-повна задача|сильно NP-повні|en|strongly NP-complete}} задачі від [[NP-повна задача|NP-повних]], але не сильно NP-повних. Задача, що має на вході якісь числові параметри сильно NP-повна, якщо вона залишається NP-повною навіть коли розмір входу штучно збільшують переводячи його в унарну систему. Для такої задачі, існують складні випадки для яких значення всіх параметрів майже поліномно великі.<ref>{{citation
 | last1 = Garey | first1 = M. R.
 | last2 = Johnson | first2 = D. S. | author2-link = Девід Джонсон
 | doi = 10.1145/322077.322090
 | issue = 3
 | journal = Journal of the ACM
 | mr = 478747
 | pages = 499–508
 | title = 'Strong' NP-completeness results: Motivation, examples, and implications
 | trans_title = Висліди в ''сильній'' NP-повноті: Спонука, приклади і наслідки
 | volume = 25
 | year = 1978| s2cid = 18371269 }}.</ref>

== Примітки ==
{{reflist|30em}}

[[Категорія:Системи числення]]
[[Категорія:Елементарна математика]]