Kompyuter algebrasi

Matematika va informatikada^[1] kompyuter algebrasi, ramziy hisoblash yoki algebraik hisoblash deb ham ataladi. Bu matematik ifodalar va boshqa matematik obyektlarni manipulyatsiya qilish uchun algoritmlar va dasturiy taʼminotni oʻrganish va ishlab chiqishga ishora qiluvchi ilmiy sohadir. Kompyuter algebrasini ilmiy hisoblashning kichik sohasi deb hisoblash mumkin boʻlsa-da, ular odatda alohida sohalar sifatida koʻrib chiqiladi, chunki ilmiy hisoblash odatda taxminiy suzuvchi nuqta raqamlari bilan raqamli hisoblashga asoslanadi, ramziy hisoblash esa berilgan qiymatga ega boʻlmagan va oʻzgaruvchilarni oʻz ichiga olgan ifodalar bilan aniq hisoblashni taʼkidlaydi. belgilar sifatida boshqariladi.

$f(x) = .mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num,.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0 0.1em}.mw-parser-output .sfrac .den{border-top:1px solid}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}x/Andoza:Sqrt$ algebraik funksiyaning ramziy integrali

Ramziy hisob-kitoblarni amalga oshiradigan dasturiy taʼminot dasturlari kompyuter algebra tizimlari deb ataladi. Tizim atamasi kompyuterda matematik maʼlumotlarni taqdim etish usulini, foydalanuvchi dasturlash tilini (odatda tildan farq qiladi) oʻz ichiga olgan asosiy ilovalarning murakkabligini anglatadi. Tizim, shuningdek, ajratilgan xotira menejeri, matematik ifodalarni kiritish va chiqarish uchun foydalanuvchi interfeysi, oddiy operatsiyalarni bajarish uchun katta tartiblar toʻplami, masalan, ifodalarni soddalashtirish, zanjir qoidasi yordamida differentsiallash, polinom faktorizatsiyasi, noaniq integratsiya va boshqalarni amalga oshirish uchun ishlatiladi.

Kompyuter algebrasi matematikada tajriba oʻtkazish va raqamli dasturlarda qoʻllanadigan formulalarni loyihalash uchun keng qoʻllanadi. Bundan tashqari, ochiq kalit kriptografiyasida boʻlgani kabi, sof raqamli usullarni bajarish qiyin boʻlgan vaziyatlar uchraganda yoki baʼzi bir chiziqsiz hisoblashlarni bajarish uchun toʻliq ilmiy hisoblashlarni amalga oshirishda ishlatiladi.

Terminologiya

Baʼzi mualliflar matematik formulalar bilan hisoblashdan tashqari, ramziy hisoblash turlariga murojaat qilish uchun oxirgi nomdan foydalanib, kompyuter algebrasini ramziy hisoblashdan ajratadilar. Baʼzi mualliflar mavzuning informatika aspekti uchun ramziy hisoblashdan va matematik jihat uchun „kompyuter algebrasi“dan foydalanadilar^[2]. Baʼzi tillarda maydon nomi uning inglizcha nomining toʻgʻridan-toʻgʻri tarjimasi hisoblanmaydi. Odatda, u fransuz tilida „rasmiy hisoblash“ degan maʼnoni anglatuvchi „calcul formel“ deb ataladi. Bu nom ushbu sohaning rasmiy usullar bilan bogʻliqligini aks ettiradi.

Oʻtmishda ramziy hisoblash, shuningdek, ramziy manipulyatsiya, algebraik manipulyatsiya, ramziy ishlov berish, ramziy matematika yoki ramziy algebra deb ham atalgan, ammo hisoblashsiz manipulyatsiyaga ham tegishli boʻlgan bu atamalar endi kompyuter algebrasiga nisbatan ishlatilmaydi.

Ilmiy hamjamiyat

Kompyuter algebrasiga xos boʻlgan oʻrganilgan jamiyat yoʻq, lekin bu funksiyani SIGSAM (Special Interest Group on Simbolic and Algebraic Manipulation) nomli Hisoblash mashinalari assotsiatsiyasining maxsus qiziqish guruhi oʻz zimmasiga oladi^[3].

Kompyuter algebrasi boʻyicha har yili bir necha konferensiya boʻlib oʻtadi.Birinchi konferensiyasi SIGSAM tomonidan muntazam homiylik qilinadigan ISSAC (Ramzlar and algebraik hisoblash boʻyicha xalqaro simpozium) hisoblanadi^[4].

Kompyuter algebrasiga ixtisoslashgan bir nechta jurnallar mavjud boʻlib, ulardan eng yaxshisi 1985-yilda Bruno Buchberger tomonidan asos solingan Symbolic Computation jurnali hisoblanadi^[5]. Bundan tashqari, kompyuter algebrasi boʻyicha maqolalarni muntazam nashr etadigan yana bir qancha jurnallar mavjud^[6].

Kompyuter fanining aspektlari

Maʼlumotlarni taqdim etish

Raqamli dasturiy taʼminot taxminiy sonli hisoblash uchun yuqori samarali boʻlgani sababli, kompyuter algebrasida aniq koʻrsatilgan maʼlumotlar bilan aniq hisoblashni taʼkidlash odatiy holdir. Bunday aniq tasavvur shuni anglatadiki, hatto chiqish hajmi kichik boʻlsa ham, hisoblash jarayonida hosil boʻlgan oraliq maʼlumotlar oldindan aytib boʻlmaydigan tarzda oʻsishi mumkin. Ushbu muammoni bartaraf etish uchun maʼlumotlarni koʻrsatishda, shuningdek ularni manipulyatsiya qiluvchi algoritmlarda turli xil usullar qoʻllanadi.

Raqamlar

Raqamli hisoblashda qoʻllanadigan odatiy raqamlar tizimlari oʻzgaruvchan nuqtali raqamlar va belgilangan chegaralangan oʻlchamdagi butun sonlardir.

Kompyuter algebrasida qoʻllanadigan asosiy raqamlar matematiklarning butun sonlari boʻlib, odatda baʼzi bir raqamlash bazasida cheksiz raqamlar ketma-ketligi bilan ifodalanadi. Butun sonlar ikki butun sonning qaytarilmas kasrlari boʻlgan ratsional sonlarni aniqlash imkonini beradi.

Arifmetik amallarni samarali amalga oshirishni dasturlash qiyin ishdir. Shuning uchun, koʻpgina bepul kompyuter algebra tizimlari va baʼzi tijorat tizimlari, masalan, Mathematica va Maple (dasturiy taʼminot) GMP kutubxonasidan foydalanadi.

Ifodalar

(8-6)*(3+1) ifodasining Lisp daraxti sifatida ifodalanishi, 1985-yilgi magistrlik dissertatsiyasidan.

Raqamlar va oʻzgaruvchilardan tashqari, har bir matematik ifodani operatorning belgisi sifatida koʻrish mumkin, undan keyin operandlar ketma-ketligi keladi . Kompyuter algebra dasturida ifodalar odatda shu tarzda ifodalanadi. Bu belgilar juda moslashuvchan va birinchi qarashda matematik ifodalar boʻlmagan koʻp narsalar shunday koʻrsatilishi va boshqarilishi mumkin. Masalan, tenglama operator sifatida „=“ ga ega ifoda, matritsa operator sifatida „matritsa“ va uning qatorlari operandlar sifatida ifodalanishi mumkin.

Hatto dasturlarni „protsedura“ operatori va kamida ikkita operand, parametrlar roʻyxati va berilgan parametr qismlari sifatida koʻrib chiqish va koʻrsatish mumkin. Va yana har qanday matematik ifodani dastur sifatida koʻrish mumkin. Masalan, $a + b$ ifodasini a va b parametr sifatida qoʻshish dasturi sifatida koʻrish mumkin. Bu dasturni bajarish a va b ning berilgan qiymatlari uchun ifodani baholashdan iborat; agar ular hech qanday qiymatga ega boʻlmasa, yaʼni ular noaniq boʻlsa, baholash natijasi shunchaki uning kiritilishi hisoblanadi.

Ifoda operandlarining oʻlchamini oldindan aytib boʻlmaydigan va ish seansi davomida oʻzgarishi mumkinligi sababli, operandlar ketma-ketligi odatda koʻrsatkichlar ketma-ketligi (Macsymadagi kabi) yoki xesh-jadvaldagi yozuvlar (Mapledagi kabi) sifatida taqdim etiladi.

Soddalashtirish

Ifodada $x$ ga nisbatan asosiy farqlash qoidalarini qoʻllash $a^{x}$ natijani beradi

x\cdot a^{x-1}\cdot 0+a^{x}\cdot \left(1\cdot \log a+x\cdot {\frac {0}{a}}\right).

Bunday murakkab ibora aniq qabul qilinishi mumkin emas va umumiy iboralar bilan ishlash orqali soddalashtirish tartibi kerak boʻladi.

Ushbu soddalashtirish odatda qayta yozish qoidalari orqali amalga oshiriladi^[7]. Koʻrib chiqilishi kerak boʻlgan qayta yozish qoidalarining bir necha sinflari mavjud. Eng oddiysi $E - E \to 0$ yoki $sin(0) \to 0$ kabi ifoda hajmini har doim kamaytiradigan qayta yozish qoidalaridan iborat. Ular tizimli ravishda kompyuter algebra tizimlarida qoʻllanadi.

Birinchi qiyinchilik qoʻshish va koʻpaytirish kabi assotsiativ operatsiyalarda yuzaga keladi. Assotsiativlik bilan shugʻullanishning standart usuli qoʻshish va koʻpaytirish operandlarining ixtiyoriy soniga ega ekanligini hisobga olishdir, yaʼni $a + b + c$ $"+"(a, b, c)$ sifatida ifodalanadi. Shunday qilib $a + (b + c)$ va $(a + b) + c$ $"+"(a, b, c)$ ga soddalashtiriladi, bu $a + b + c$ koʻrsatiladi. $a - b + c$ haqida nima deyish mumkin? Ushbu muammoni hal qilishning eng oddiy usuli $- E$ , $E - F$ , $E / F$ ni mos ravishda $(-1)\cdot E$ , $E + (-1)\cdot F$ , $E \cdot F -1$ ni tizimli ravishda qayta yozish. Boshqacha qilib aytadigan boʻlsak, ifodalarning ichki koʻrinishida sonlarning koʻrinishidan tashqarida ayirish ham, boʻlish ham, minus belgisi ham mavjud emas.

Ikkinchi qiyinchilik qoʻshish va koʻpaytirishning kommutativligi bilan yuzaga keladi. Muammo shu kabi atamalarni birlashtirish yoki bekor qilish uchun ularni tezda tanib olishdir. Aslida, har bir atama juftligini sinab koʻrishdan iborat boʻlgan oʻxshash atamalarni topish usuli juda uzoq summalar va mahsulotlarni talab qiladi. Ushbu muammoni hal qilish uchun Macsyma yigʻindilar va mahsulotlarning operandlarini taqqoslash funksiyasi bilan tartibga soladi. Misolda ular oʻxshash atamalar sifatida ketma-ket joylarda joylashgan va shuning uchun ular osongina aniqlanadi. Mapleda xesh funksiyasi oʻxshash shartlar kiritilganda toʻqnashuvlarni yaratish uchun moʻljallangan boʻlib, ular kiritilgan zahoti ularni birlashtirishga imkon beradi. Xesh-funksiyaning bunday dizayni hisoblashda bir necha marta paydo boʻladigan iboralar yoki pastki ifodalarni darhol tanib olish va ularni faqat bir marta saqlash imkonini beradi. Bu nafaqat xotirada boʻsh joyni tejash, balki bir xil amallarning bir nechta bir xil ifodalar ustida takrorlanishini oldini olish orqali hisoblashni tezlashtirish imkonini beradi.

Baʼzi qayta yozish qoidalari ular qoʻllanadigan iboralarning hajmini baʼzan kattalashtiradi va baʼzan kamaytiradi. Bu distributivlik yoki trigonometrik oʻziga xosliklarning holati hisoblanadi. Masalan, distributivlik qonuni qayta yozishga ruxsat beradi $(x+1)^{4}\rightarrow x^{4}+4x^{3}+6x^{2}+4x+1$ va $(x-1)(x^{4}+x^{3}+x^{2}+x+1)\rightarrow x^{5}-1.$ Bunday qayta yozish qoidasini qoʻllash yoki qoʻllamaslikda umumiy tanlashning hech qanday usuli yoʻqligi sababli, bunday qayta yozishlar faqat foydalanuvchi tomonidan aniq soʻralganda amalga oshiriladi. Tarqatish uchun ushbu qayta yozish qoidasini qoʻllaydigan kompyuter funksiyasi odatda „kengaytirish“ deb ataladi. „Factor“ deb ataladigan teskari qayta yozish qoidasi ahamiyatsiz boʻlmagan algoritmni talab qiladi, shuning uchun bu kompyuter algebra tizimlarida asosiy funksiyadir (qarang: Polinom faktorizatsiyasi).

Matematik jihatlar

Ushbu boʻlimda biz kompyuterda matematik ifodalarni manipulyatsiya qilmoqchi boʻlgan zahoti paydo boʻladigan baʼzi fundamental matematik savollarni koʻrib chiqamiz. Biz asosan koʻp oʻzgaruvchan ratsional kasrlar holatini koʻrib chiqamiz. Ifodada paydo boʻladigan irratsional funksiyalar soddalashtirilgandan soʻng, ular yangi noaniqlar sifatida qabul qilinadi. Masalan,

(\sin(x+y)^{2}+\log(z^{2}-5))^{3}

ichida koʻphad sifatida qaraladi $\sin(x+y)$ va $\log(z^{2}-5)$

Tenglik

Matematik ifodalar uchun tenglikning ikkita tushunchasi mavjud. Sintaktik tenglik — bu iboralarning tengligi, yaʼni ular bir xil tarzda yozilgan (yoki kompyuterda ifodalangan). Arzimas boʻlgani sababli, sintaktik tenglik matematiklar tomonidan kamdan-kam hollarda koʻrib chiqiladi, garchi bu dastur yordamida tekshirish oson boʻlgan yagona tenglikdir. Semantik tenglik — ikkita ifoda bir xil matematik obyektni ifodalashda qoʻllanadi. Masalan,

(x+y)^{2}=x^{2}+2xy+y^{2}.

Richardson teoremasidan maʼlumki, sonlarni ifodalovchi ikkita ifoda semantik jihatdan teng yoki yoʻqligini aniqlash quyidagicha boʻladi. Agar ifodalarda koʻrsatkichlar va logarifmlarga ruxsat berilgan boʻlsa, hal qiluvchi algoritm mavjud boʻlmasligi mumkin. Shuning uchun (semantik) tenglik faqat koʻphadlar va ratsional kasrlar kabi baʼzi iboralar sinflarida tekshirilishi mumkin.

Ikki ifodaning tengligini tekshirish uchun, aniq algoritmlarni loyihalash oʻrniga, iboralarni qandaydir kanonik shaklda qoʻyish yoki ularning farqini oddiy shaklda qoʻyish va natijaning sintaktik tengligini tekshirish odatiy holdir.

Odatiy matematikadan farqli oʻlaroq, „kanonik shakl“ va „normal shakl“ kompyuter algebrasida sinonim hisoblanmaydi^[8]. Kanonik shakl shundayki, kanonik shakldagi ikkita ibora sintaktik jihatdan teng bo‘lgandagina ular maʼno jihatdan teng bo‘ladi, normal shakl esa, oddiy shakldagi ifoda faqat sintaktik jihatdan nolga teng bo‘lsagina, semantik jihatdan nolga teng bo‘ladi. Boshqacha qilib aytganda, nol oddiy shakldagi iboralar boʻyicha oʻziga xos koʻrinishga ega.

Tarixi

Kompyuter algebrasining boshida, taxminan 1970-yilda, uzoq vaqtdan beri maʼlum boʻlgan algoritmlar birinchi marta kompyuterlarga kiritilganda, ular juda samarasiz boʻlib chiqdi^[9]. Shu sababli, ushbu sohadagi tadqiqotchilar ishining katta qismi klassik algebrani samarali qilish uchun qayta koʻrib chiqish va ushbu samaradorlikni amalga oshirishning samarali algoritmlarini topishdan iborat edi. Bunday ishning tipik misoli kasrlarni soddalashtirish uchun zarur boʻlgan koʻphadli eng katta umumiy boʻluvchilarni hisoblashdir. Ajablanarlisi shundaki, klassik Evklid algoritmi cheksiz maydonlardagi polinomlar uchun samarasiz boʻlib chiqdi va shuning uchun yangi algoritmlarni ishlab chiqish kerak edi.

Manbalar

↑ „ACM Association in computer algebra“.
↑ Watt, Stephen M. (2006). "Making Computer Algebra More Symbolic (Invited)". Proc. Transgressive Computing 2006: A conference in honor of Jean Della Dora, (TC 2006). pp. 43–49. http://www.csd.uwo.ca/~watt/pub/reprints/2006-tc-sympoly.pdf.
↑ SIGSAM official site
↑ „SIGSAM list of conferences“. 2013-yil 8-avgustda asl nusxadan arxivlangan. Qaraldi: 2012-yil 15-noyabr.
↑ Cohen, Joel S.. Computer Algebra and Symbolic Computation: Mathematical Methods. AK Peters, Ltd., 2003 — 14-bet. ISBN 978-1-56881-159-8.
↑ SIGSAM list of journals
↑ Buchberger, Bruno, and Rüdiger Loos. „Algebraic simplification.“ Computer algebra. Springer, Vienna, 1982. 11-43.
↑ Davenport, J. H., Siret, Y., & Tournier, É. (1988). Computer algebra. London: Academic.
↑ Kaltofen, Erich (1982), „Factorization of polynomials“, in Buchberger, B.; Loos, R.; Collins, G. (muh.), Computer Algebra, Springer Verlag, 95–113-bet

[1] „ACM Association in computer algebra“.

[2] Watt, Stephen M. (2006). "Making Computer Algebra More Symbolic (Invited)". Proc. Transgressive Computing 2006: A conference in honor of Jean Della Dora, (TC 2006). pp. 43–49. http://www.csd.uwo.ca/~watt/pub/reprints/2006-tc-sympoly.pdf.

[3] SIGSAM official site

[4] „SIGSAM list of conferences“. 2013-yil 8-avgustda asl nusxadan arxivlangan. Qaraldi: 2012-yil 15-noyabr.

[5] Cohen, Joel S.. Computer Algebra and Symbolic Computation: Mathematical Methods. AK Peters, Ltd., 2003 — 14-bet. ISBN 978-1-56881-159-8.

[6] SIGSAM list of journals

[7] Buchberger, Bruno, and Rüdiger Loos. „Algebraic simplification.“ Computer algebra. Springer, Vienna, 1982. 11-43.

[8] Davenport, J. H., Siret, Y., & Tournier, É. (1988). Computer algebra. London: Academic.

[9] Kaltofen, Erich (1982), „Factorization of polynomials“, in Buchberger, B.; Loos, R.; Collins, G. (muh.), Computer Algebra, Springer Verlag, 95–113-bet

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]