Unary raqamli tizim - Unary numeral system

Raqamli tizimlar
Hind-arab raqamlar tizimi
Sharqiy Osiyo
Evropa
Amerika
Alifbo
Avvalgi
Pozitsion tizimlar tomonidan tayanch
Nostandart pozitsion raqamli tizimlar
Raqamli tizimlar ro'yxati

The unary raqamlar tizimi ifodalash uchun eng oddiy raqamlar tizimidir natural sonlar:[1] raqamni ifodalash N, 1 ni ifodalovchi belgi takrorlanadi N marta.[2]

Unary tizimida raqam 0 (nol). bilan ifodalanadi bo'sh satr, ya'ni belgining yo'qligi. 1, 2, 3, 4, 5, 6, ... raqamlari unaryda 1, 11, 111, 1111, 11111, 111111, ... sifatida ifodalanadi.[3]

In pozitsion yozuvlar doirasi, unary bu ikki tomonlama tayanch -1 raqamlar tizimi. Biroq, raqamning qiymati uning pozitsiyasiga bog'liq emasligi sababli, unary pozitsion tizim emasligi haqida bahslashish mumkin.[iqtibos kerak ]

Dan foydalanish balli belgilar sanashda unary raqamli tizimining qo'llanilishi. Masalan, balli belgisidan foydalanish |, 3 raqami quyidagicha ifodalanadi |||. Yilda Sharqiy Osiyo madaniyatlar, 3 raqami quyidagicha ifodalanadi 三, uchta zarba bilan chizilgan belgi.[4] (Bitta va ikkitasi bir xil tarzda ifodalanadi.) Xitoy va Yaponiyada ba'zan 5 zarbasi bilan chizilgan 正 belgisi ishlatiladi.[5][6]

Unary raqamlarini ajratish kerak birlashmalar, ular ham ketma-ketliklar sifatida yozilgan, ammo odatdagidek o‘nli kasr raqamli talqin.

Amaliyotlar

Qo'shish va ayirish unary tizimida ayniqsa sodda, chunki ular bundan ozroq narsani o'z ichiga oladi torli birikma.[7] The Hamming vazni yoki ikkilik qiymatlar ketma-ketligidagi nolga teng bo'lmagan bitlar sonini hisoblaydigan populyatsiyani hisoblash operatsiyasi ham unary-dan konversiya sifatida talqin qilinishi mumkin. ikkilik raqamlar.[8] Biroq, ko'paytirish ko'proq noqulay va ko'pincha dizayni uchun sinov sifatida ishlatilgan Turing mashinalari.[9][10][11]

Murakkablik

Standart bilan taqqoslaganda pozitsion raqamli tizimlar, unary tizimi noqulay va shuning uchun katta hisob-kitoblar uchun amalda foydalanilmaydi. Bu ba'zilarida uchraydi qaror muammosi tavsiflari nazariy informatika (masalan, ba'zilari P tugallangan muammolar), bu muammoning ishlash vaqtini yoki bo'sh joy talablarini "sun'iy ravishda" kamaytirish uchun ishlatiladi. Masalan, muammo tamsayı faktorizatsiyasi Agar kirish berilgan bo'lsa, kirish uzunligidagi polinom funktsiyasidan ko'proq vaqtni talab qiladi deb taxmin qilinadi ikkilik, lekin kirish faqat unary-da taqdim etilsa, u faqat chiziqli ish vaqtiga muhtoj.[12][13][doimiy o'lik havola ] Biroq, bu potentsial ravishda chalg'itishi mumkin. Bir martalik kiritishni ishlatish har qanday raqam uchun sekinroq, tezroq emas; farqi shundaki, ikkilik (yoki kattaroq tayanch) kirish sonning 2 (yoki kattaroq asos) logarifmiga mutanosib, unary kirish esa raqamning o'ziga mutanosibdir. Shuning uchun, unary-dagi ish vaqti va bo'shliqqa ehtiyoj kirish hajmining funktsiyasi sifatida yaxshiroq ko'rinsa-da, u yanada samarali echimni anglatmaydi.[14]

Yilda hisoblash murakkabligi nazariyasi, ajratish uchun unary raqamlash ishlatiladi kuchli NP bilan to'ldirilgan muammolardan kelib chiqadigan muammolar To'liq emas ammo kuchli NP emas. Kiritish ba'zi bir sonli parametrlarni o'z ichiga olgan muammo, parametrlarni unary formatida ifodalash orqali kirish kattaligi sun'iy ravishda kattalashtirilgan bo'lsa ham, NP to'liq bo'lib qolsa, kuchli NP-ni to'ldiradi. Bunday muammo uchun barcha parametr qiymatlari eng ko'p polinomial katta bo'lgan qiyin holatlar mavjud.[15]

Ilovalar

Unary raqamlash ba'zi ma'lumotlarni siqish algoritmlarining bir qismi sifatida ishlatiladi Golomb kodlash.[16] Bu shuningdek uchun asos yaratadi Peano aksiomalari ichida arifmetikani rasmiylashtirish uchun matematik mantiq.[17]Yagona notatsiya shakli deb nomlangan Cherkovni kodlash ichida raqamlarni ko'rsatish uchun ishlatiladi lambda hisobi.[18]

Shuningdek qarang

Adabiyotlar

  1. ^ Xodjes, Endryu (2009), To'qqizgacha: raqamlarning ichki hayoti, Anchor Canada, p. 14, ISBN  9780385672665.
  2. ^ Devis, Martin; Sigal, Ron; Veyuker, Eleyn J. (1994), Hisoblash, murakkablik va tillar: nazariy informatika asoslari, Informatika va ilmiy hisoblash (2-nashr), Academic Press, p. 117, ISBN  9780122063824.
  3. ^ Hext, yanvar (1990), Dasturlash tuzilmalari: mashinalar va dasturlar, Dasturlash tuzilmalari, 1, Prentice Hall, p. 33, ISBN  9780724809400.
  4. ^ Woodruff, Charlz E. (1909), "Qadimgi Tally belgilaridan zamonaviy raqamlarning rivojlanishi", Amerika matematik oyligi, 16 (8–9): 125–33, doi:10.2307/2970818, JSTOR  2970818.
  5. ^ Hsieh, Hui-Kuang (1981), "Xitoylik Tally Mark", Amerika statistikasi, 35 (3): 174, doi:10.2307/2683999
  6. ^ Lunde, Ken; Miura, Daisuke (2016 yil 27-yanvar), "Beshta ideografik talli belgilarini kodlash to'g'risida taklif", Unicode konsortsiumi (PDF), Taklif L2 / 16-046
  7. ^ Sazonov, Vladimir Yu. (1995), "Mumkin bo'lgan raqamlar to'g'risida", Mantiqiy va hisoblash murakkabligi (Indianapolis, IN, 1994), Kompyuterda ma'ruza yozuvlari. Ilmiy., 960, Springer, Berlin, bet.30–51, doi:10.1007/3-540-60178-3_78, ISBN  978-3-540-60178-4, JANOB  1449655. Xususan qarang. 48.
  8. ^ Blaxell, Devid (1978), "Bit naqshini moslashtirish bo'yicha yozuvlarni bog'lash", Xogbenda, Devid; Fife, Dennis V. (tahr.), Kompyuter fanlari va statistika - interfeys bo'yicha o'ninchi yillik simpozium, NBS Maxsus nashri, 503, AQSh Savdo vazirligi / Standartlarning milliy byurosi, 146–156-betlar.
  9. ^ Hopkroft, Jon E.; Ullman, Jeffri D. (1979), Avtomatika nazariyasi, tillar va hisoblash bilan tanishish, Addison Uesli, 7.7-misol, 158-159 betlar, ISBN  978-0-201-02988-8.
  10. ^ Devidni, A. K. (1989), Yangi Turing Omnibus: Kompyuter fanlari bo'yicha oltmish oltita ekskursiyalar, Computer Science Press, p. 209, ISBN  9780805071665.
  11. ^ Rendell, Pol (2015), "5.3 Katta misol TM: Unary ko'paytmasi", Turing Machine Hayot O'yinining Universalligi, Paydo bo'lishi, murakkabligi va hisoblashi, 18, Springer, 83–86-betlar, ISBN  9783319198422.
  12. ^ Arora, Sanjeev; Barak, Boaz (2007), "Hisoblash modeli - va nima uchun bu muhim emas" (PDF), Hisoblash murakkabligi: zamonaviy yondashuv (2007 yil yanvar oyidagi tahrir nashri), Kembrij universiteti matbuoti, 17-§, 32-33-betlar, olingan 10 may, 2017.
  13. ^ Feygenbaum, Joan (2012 yil kuz), CPSC 468/568 HW1 eritmasi to'plami (PDF), Yel universiteti kompyuter fanlari bo'limi, olingan 2014-10-21.
  14. ^ Mur, Kristofer; Mertens, Stefan (2011), Hisoblashning mohiyati, Oksford universiteti matbuoti, p. 29, ISBN  9780199233212.
  15. ^ Garey, M. R.; Jonson, D. S. (1978), "'NP-ning to'liq natijalari: motivatsiya, misollar va natijalar ", ACM jurnali, 25 (3): 499–508, doi:10.1145/322077.322090, JANOB  0478747.
  16. ^ Golomb, S.W. (1966), "Uzunlikdagi kodlashlar", Axborot nazariyasi bo'yicha IEEE operatsiyalari, IT-12 (3): 399-401, doi:10.1109 / TIT.1966.1053907.
  17. ^ Magud, Nikolas; Bertot, Iv (2002), "Turlar nazariyasida ma'lumotlar tuzilmalarini o'zgartirish: natural sonlarni o'rganish", Dalillar va dasturlarning turlari (Durham, 2000), Kompyuterda ma'ruza yozuvlari. Ilmiy., 2277, Springer, Berlin, 181–196-betlar, doi:10.1007/3-540-45842-5_12, ISBN  978-3-540-43287-6, JANOB  2044538.
  18. ^ Jansen, Jan Martin (2013), "B-hisobi bo'yicha dasturlash: Cherkovdan Skottgacha va orqaga", Funktsional kodning go'zalligi: Rinus Plasmeyerning 61 yoshga to'lishi munosabati bilan bag'ishlangan insholar, Kompyuter fanidan ma'ruza matnlari, 8106, Springer-Verlag, 168-180 betlar, doi:10.1007/978-3-642-40355-2_12, ISBN  978-3-642-40354-5.

Tashqi havolalar