Wikipedia

Sistem unar

Sistemul unar este cel mai simplu sistem de numerație pentru a reprezenta numerele naturale:[1] pentru a reprezenta un număr N, un simbol care reprezintă pe „1” se repetă de N ori.[2]

Sistem de numerație
Sistem Bază
  Unar 1
  Binar 2
  Ternar 3
  Cuaternar 4
  Cvinariu 5
  Senar 6
  Octal 8
  Zecimal 10
  Duodecimal 12
  Hexazecimal 16
  Vigesimal 20
  Hexatrigesimal 36
  Sexagesimal 60

În sistemul unar, numărul 0 (zero) este reprezentat de șirul vid, adică absența vreunui simbol. Numerele 1, 2, 3, 4, 5, 6, ... sunt reprezentate în sistemul unar ca 1, 11, 111, 1111, 11111, 111111, ...[3]

În viziunea sistemelor de numerație poziționale, sistemul unar ar fi o corespondență biunivocă cu baza 1. Însă deoarece valoarea unei cifre nu depinde de poziția sa, se poate argumenta că sistemul unar nu este un sistem pozițional.

Utilizarea semnelor pe răboj în numărare este un exemplu de sistem de numerație unar. De exemplu, folosind semnul |, numărul 3 este reprezentat ca |||. În culturile Asia de Est, numărul 3 este reprezentat ca 三, un caracter trasat din trei linii.[4] (Numerele 1 și 2 sunt reprezentate similar.) În China și Japonia caracterul 正, trasat din cinci linii, este uneori folosit ca semn de răboj.[5][6]

Numerele unare nu trebuie confundate cu cele repunit, care sunt, de asemenea, scrise ca șiruri de unități, dar au interpretarea numerică zecimală obișnuită.

Operații

modificare

În sistemul unar adunarea și scăderea sunt foarte simple, reducându-se practic la concatenarea, respectiv separarea șirurilor de semne.[7] Ponderea Hamming sau numărarea unul câte unul pot fi interpretate ca o conversie de la sistemul unar la unul pozițional, de exemplu binar.[8] Însă înmulțirea este mai greoaie și a fost adesea folosită ca un mod de testare la proiectarea mașinilor Turing.[9][10][11]

Complexitate

modificare

Comparat cu sistemele de numerație poziționale, sistemul unar este incomod, prin urmare nu este utilizat în practică pentru calcule mari. Apare în unele descrieri ale problemelor de decizie din informatica teoretică (de exemplu unele probleme P-complete⁠(d)), unde este folosită pentru a reduce „artificial” timpul de rulare sau cerințele de spațiu ale unei probleme. De exemplu, problema descompunerii în factori primi este suspectată că necesită un timp de rulare mai mult decât polinomial în funcție de lungimea intrării dacă intrarea este dată în binar, dar numai un timp de rulare liniar dacă intrarea este prezentată în unar.[12][13][nefuncțională] Totuși, acest lucru este potențial înșelător. Utilizarea unei intrări unare este mai lentă pentru orice număr; deosebirea este că o intrare binară (sau cu bază mai mare) este proporțională cu logaritmul în baza 2 (sau în baza mai mare) al numărului, în timp ce intrarea unară este proporțională cu numărul în sine. Prin urmare, în timp ce în unar necesarul de timp și spațiu este mai mic în funcție de dimensiunea intrării, global asta nu reprezintă o soluție mai eficientă.[14]

În teoria complexității numerotarea unară este folosită pentru a distinge problemele NP-complete dificile de problemele care sunt NP-complete, dar nu și dificile. O problemă în care intrarea include unii parametri numerici este NP-completă dificilă dacă rămâne NP-completă chiar și atunci când dimensiunea intrării este mărită artificial prin prezentarea parametrilor în unar. Pentru o astfel de problemă, există cazuri dificile pentru care toate valorile parametrilor sunt cel mult polinomial mari.[15]

Aplicații

modificare

Numărarea unară este utilizată ca parte a unor algoritmi de compresie a datelor, cum ar fi codarea Golomb⁠(d).[16] De asemenea, formează baza pentru axiomele Peano⁠(d) pentru formalizarea aritmeticii în logica matematică.[17] O formă de notație unară numită codarea Church⁠(d) este folosită pentru a reprezenta numere în calculul lambda⁠(d).[18]

Note

modificare
  1. ^ en Hodges, Andrew (), One to Nine: The Inner Life of Numbers, Anchor Canada, p. 14, ISBN 9780385672665 
  2. ^ en Davis, Martin; Sigal, Ron; Weyuker, Elaine J. (), Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science, Computer Science and Scientific Computing (ed. 2nd), Academic Press, p. 117, ISBN 9780122063824 
  3. ^ en Hext, Jan (), Programming Structures: Machines and Programs, Programming Structures, 1, Prentice Hall, p. 33, ISBN 9780724809400 
  4. ^ en Woodruff, Charles E. (), „The Evolution of Modern Numerals from Ancient Tally Marks”, American Mathematical Monthly, 16 (8–9): 125–33, doi:10.2307/2970818, JSTOR 2970818 
  5. ^ en Hsieh, Hui-Kuang (), „Chinese Tally Mark”, The American Statistician, 35 (3): 174, doi:10.2307/2683999 
  6. ^ en Lunde, Ken; Miura, Daisuke (), „Proposal to Encode Five Ideographic Tally Marks”, Unicode Consortium (PDF), Proposal L2/16-046 
  7. ^ en Sazonov, Vladimir Yu. (), „On feasible numbers”, Logic and computational complexity (Indianapolis, IN, 1994), Lecture Notes in Comput. Sci., 960, Springer, Berlin, pp. 30–51, doi:10.1007/3-540-60178-3_78, ISBN 978-3-540-60178-4, MR 1449655 . V. în special p.  48
  8. ^ en Blaxell, David (), „Record linkage by bit pattern matching”, În Hogben, David; Fife, Dennis W., Computer Science and Statistics--Tenth Annual Symposium on the Interface, NBS Special Publication, 503, U.S. Department of Commerce / National Bureau of Standards, pp. 146–156 
  9. ^ en Hopcroft, John E.; Ullman, Jeffrey D. (), Introduction to Automata Theory, Languages, and Computation , Addison Wesley, Example 7.7, pp. 158–159, ISBN 978-0-201-02988-8 
  10. ^ en Dewdney, A. K. (), The New Turing Omnibus: Sixty-Six Excursions in Computer Science, Computer Science Press, p. 209, ISBN 9780805071665 
  11. ^ en Rendell, Paul (), „5.3 Larger Example TM: Unary Multiplication”, Turing Machine Universality of the Game of Life, Emergence, Complexity and Computation, 18, Springer, pp. 83–86, ISBN 9783319198422 
  12. ^ en Arora, Sanjeev; Barak, Boaz (), „The computational model —and why it doesn't matter” (PDF), Computational Complexity: A Modern Approach (ed. January 2007 draft), Cambridge University Press, §17, pp. 32–33, accesat în  
  13. ^ en Feigenbaum, Joan (), CPSC 468/568 HW1 Solution Set (PDF), Computer Science Department, Yale University, accesat în  
  14. ^ en Moore, Cristopher; Mertens, Stephan (), The Nature of Computation, Oxford University Press, p. 29, ISBN 9780199233212 
  15. ^ en Garey, M. R.; Johnson, D. S. (), „'Strong' NP-completeness results: Motivation, examples, and implications”, Journal of the ACM, 25 (3): 499–508, doi:10.1145/322077.322090, MR 0478747 
  16. ^ en Golomb, Solomon W. (), „Run-length encodings”, IEEE Transactions on Information Theory, IT-12 (3): 399–401, doi:10.1109/TIT.1966.1053907 
  17. ^ en Magaud, Nicolas; Bertot, Yves (), „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, pp. 181–196, doi:10.1007/3-540-45842-5_12, ISBN 978-3-540-43287-6, MR 2044538 
  18. ^ en Jansen, Jan Martin (), „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, pp. 168–180, doi:10.1007/978-3-642-40355-2_12, ISBN 978-3-642-40354-5 

Legături externe

modificare
  Portal Matematică
Adus de la https://ro.wikipedia.org/w/index.php?title=Sistem_unar&oldid=15973198