Симболичко рачунање

У рачунарској математици, компјутерској алгебри, другачије речено симболичко рачунање или алгебарско рачунање је научна област која се односи на проучавање и развој алгоритама и софтвера за манипулисање математичким изразима и другим математичким објектима. Иако, правилно речено, компјутерска алгебра треба да буде потпоље научног рачунарства, она се генерално сматра различитим пољем јер се научно рачунање обично заснива на нумеричком рачунању са приближно Флоатинг бројевима тачке, док симболично рачунање истиче тачан обрачун са изразима који садржи варијабле које имају и вредности које нису дате и тиме су изманипулисани као симболи (од тога је назив симболичко рачунање).

Софтверске апликације које обављају симболичке калкулације се називају системи компјутерсе алгебре, са роком систем алудирајући на сложеност главних апликација које укључују, најмање, метод за представљање математичких података у рачунару, кориснички програмски језик (обично се разликује од језика који се користи за реализацију), наменски менаџер меморије, кориснички интерфејс за улаз / излаз математичких израза, велики скуп шаблона за обављање уобичајених послова, као поједностављивање израза, диференцирање коришћењем правила ланца, полинома факторизација, неодређене интеграције, итд .

На почетку рачунарске алгебре, око 1970. године, када су одавно познати алгоритми били први пут на рачунарима, испоставило се да је то било веома неефикасно. Због тога, велики део истраживачког посла на теренима се састојао у поновном осврту на класичну алгебру како би се учинили ефикаснијим и открили ефикасни алгоритми за испуњење ове ефикасности. Типичан пример оваквог рада је израчунавање полинома највећих заједничких делилаца, који је потребан за поједностављивање разломака. Изненађујуће, испоставило се да је класичан Еуклидов алгоритам био неефикасан за полинома у бесконачним пољима, због тога је потребно да се развије нови алгоритам. Исто је било и за класичне алгоритме из линеарне алгебре.

Компјутерска алгебра се широко користи за експерименте у математици и дизајнирање формула које се користе у нумеричким програмима. Такође се користи за комплетно научно рачунање, када се нумеричке методе не изврше у целини, као у криптографији јавног кључа или за неке нелинеарне проблеме.

Терминологија

Неки аутори разликују компјутерску алгебру од симболичког рачунања помоћу других имена која се односе на врсте других симболичких рачунања или обрачуна са математичким формулама. Неки аутори користе симболично рачунање за рачунарску науку и "компјутерску алгебру" за математичке аспекте. У неким језицима назив области нема директан превод са Енглеског. Типично, то се зове калкулација формула на француском, што значи "формално рачунање".

Симболичко рачунање се у прошлости спомињало такође и као симболичка манипулација, алгебарска манипулација, симболичка обрада, симболичка математика, или симболичка алгебра, али ових услова, који се такође односе на не-рачунарске манипулацију, нема више у употреби која се односи на компјурерску алгебру.

Научна заједница

Не постоји друштво које је посебно за компјутерску алгебру, али ову функција преузимају групе од посебног интереса Ассоциатион фор Цомпутинг Мацхинери под називом СИГСАМ (Специал Интерест Гроуп на симболичким и Алгебарским манипулацијама).

Постоји неколико годишњих конференција везаних за рачунарску алгебру прва је (Међународни симпозијум о симболичком и Алгебарском рачунању), коју редовно спонзорише СИГСАМ.

Постоји неколико часописа специјализованих за рачунарску алгебру, на првом месту је журнал симболичког рачунања основан 1985. године од стране Бруна Буцхбергера. Ту је и неколико других часописа који редовно објављују чланке о компјутерској алгебри.^[1]

Аспекти рачунарске науке

Представљање података

Како је нумерички софтвер веома ефикасан за приближно нумеричко рачунање, уобичајено је, у компјутерској алгебри, да се нагласе тачна рачунања са тачно представљеним подацима. Такав одраз имплицира да, чак и када је величина излаза мала, средњи подаци добијени током израчунавања могу расти у непредвидивом облику. Ово понашање се зове супер израз. Да би се отклонио овај проблем, користе се разни методи у представљању података, као и алгоритама који њима манипулишу.

Бројеви

Обично се системи бројева користе у нумеричком рачунању који су или покретни бројеви или цели бројеви у фиксној ограниченој величини, који се непрописно називају целим бројевима у већини програмских језика. Ништа није погодно за компјутерску алгебрз, због супер израза.

Дакле, основни бројеви који се користе у рачунарској алгебри су цели бројеви код математичара, обично представљају од стране неограниченим потписан низ цифара у некој бази нумерације, обично највећом базом дозвољеног машине речи. Ови цели бројеви омогућавају да се дефинишу рационалних бројева, који су неприводимие фракције два целих бројева.

Програмирање ефикасне имплементације аритметичких операција је тежак задатак. Дакле, већина бесплатних компјутерских алгебарских система и неки комерцијални, као Мапле (софтвер), користе ГМП библиотеку, која је заправо стандардна.

Изрази

Осим бројева и варијабли, сваки математички израз се може посматрати као симбол оператора праћено низом операнди. У софтверу компјутерске алгебре, изрази се обично представљају на овај начин. Овакво представљање је веома флексибилно, и многе ствари, за које се чини да не могу бити математички изрази на први поглед, могу бити представљени и манипулисани тако. На пример, једначина је израз са "=" као оператором, матрица може бити представљена као израз са "Матрик" као оператор, а њени редови, као операнде.

Чак и програми могу бити сматрани и представљени као изрази са оператором "процедуре" и, најмање, два операнда, на листи параметара и тела, који је сам израз "тела" као оператор и низ упутстава као операнди. Насупрот томе, сваки математички израз може се посматрати као програм. На пример, израз А + Б се може посматрати као програм за сабирање, са а и б као параметрима. Извођење овог програма се састоји у процени израза за дате вредности А и Б; ако немају никакву вредност онда су они неодређени-, резултат процене је једноставно његов улаз.

Овај процес одложене процене је од фундаменталног значаја у компјутерској алгебри. На пример, оператор "=" је такође једначина, у већини компјутерских алгебарских система, назив програма теста једнакости: уобичајено, изражавање резултата једначине и бројевима, када је потребан тест једнакости, било да изричито затражен од стране корисника кроз "евалуације у Боолеан" команде, било да је аутоматски систем започет у случају теста унутар програма-онда процене да боолеан 0 или 1 је погубљен.

Како је величина операнде у изразу непредвидива тако се она може мењати током радног састанка, редослед операнде се обично представља као низ било показивача (као у Мацсима) или низ уписа у хеш табелу (као у Мапле).

Поједностављење

Сирова примена основних правила диференцирања у односу на к у изразу а^ к даје резултат $x\cdot a^{x-1}\cdot 0+a^{x}\cdot \left(1\cdot \log a+x\cdot {\frac {0}{a}}\right).$ Such an awful expression is clearly not acceptable, and a procedure of simplification is needed as soon as one works with general expressions.

Ово поједностављивање се обично врши кроз поновно писање правила. Постоји неколико врста преписивања правила која се морају узети у обзир. Најједноставнији се састоји у поновном писању правила која увек смањују величину изражавања, као Е - Е → 0 или син (0) → 0. Они се систематски примењују у системима компјутерске алгебре.

Прва потешкоћа се јавља са асоцијативним операцијама као што су сабирање и множење. Стандардни начин да се обаве асоцијативност јестеда се узме у обзир да сабирање и множење има произвољан број операнада, то јест да је а + б + ц представљена као "+" (А, Б, C). Тако А + (Б + C) и (А + Б) + C су оба поједностављена да "+" (А, Б, C), који се приказује А + Б + ц. Шта је са а - б + ц? Како бисте се изборили са овим проблемом, најједноставнији начин је да се преправи систематично -Е, Е - Ф, Е / П као, односно, (-1) ⋅Е, Е + (-1) ⋅Ф, Е⋅Ф-1. Другим речима, у унутрашњем представљању израза, нема ни поделе, ни одузимања ни унарног минуса, изван представљања бројева.

Друга потешкоћа се јавља са комутатиношћу сабирања и множења. Проблем је да се брзо препознају као услови како би се комбиновали или поништили. У ствари, поступак за проналажење сличних израза, састоји се од тестирања сваког пара термина, ово превише кошта и изводљиво је само са веома великим новцем и производима. За решавање овог проблема, Мацсима сортира операнде суме и производа са функцијом поређења која је дизајнирана као термин на узастопним местима, и на тај начин их је лако детектовати. Дизајн хеш функције такође омогућава да одмах препознате изразе или субекпрессионс који се појављују више пута у израчунавању и да их чувате само једном. Ово омогућава не само да се уштеди нешто меморије, већ и да се убрза рачунање, избегавањем поновављања истих операција на више истих израза.

Нека преписана правила некад повећавају а некад смањују величину израза за које се примењују. Ово је случај дистрибутивних или тригонометријских идентитета. На пример, закон дозвољава дистрибутивно преписивање $(x+1)^{4}\rightarrow x^{4}+4x^{3}+6x^{2}+4x+1$ и $(x-1)(x^{4}+x^{3}+x^{2}+x+1)\rightarrow x^{5}-1.$ Пошто не постоји начин да се направи добар општи избор применом и такво преписивање није правилно, такво преписивање се врши само када се изричито тражи од стране корисника. За дистрибутивити, рачунарска функција која примењује ово преписивање правила се обично назива "шири". Обрнуто преписивање правила, под називом "фактор", захтева нетривиални алгоритам, који је на тај начин кључна функција у системима компјутерске алгебре (види разлагање полинома).

Математички аспекти

У овом одељку разматрамо нека темељна математичка питања која се јављају чим желимо да манипулишемо математичким изразима у рачунару. Ми смо углавном размотрили случај мултиваријантних рационалних фракција. Ово није право ограничење, јер, чим се ирационални функције појављују изразису поједностављени, и они се обично сматрају нерешеним. На пример $(\sin(x+y)^{2}+\log(z^{2}-5))^{3}$ се посматра као полином $\sin(x+y)$ и $\log(z^{2}-5)$

Једнакост

Постоје два појма једнакости за математичке изразе. Синтаксна равноправност је једнакост израза, што значи да су писани (или заступљени у рачунару) на исти начин. Тривијално, ретко тако сматрају и математичари, али то је једина једнакост која се лако може тестирати са програмом. Семантичка једнакост је када два израза представљају исти математички предмет, као у (к + и) ^ 2 = к ^ 2 + 2ки, и ^ 2.

Познато је из Ричардове теореме да не може постојати алгоритам који одлучује да ли два израза обухватају бројеве који су семантички једнаки, ако су експоненти и логаритми дозвољени у изразима. Стога (семантичка) једнакост може бити тестирана само на неким врстама израза као што су полиноми и рационалне разломци.

Да би се тестирала једнакост два израза, уместо да се дизајнира посебан алгоритам, уобичајено је да се ставе у неки канонски облик или њихове разлике у нормалан облик и да се тестира резултат синтаксичке једнакости.

За разлику од уобичајене математике, "канонски облик" и "нормални облик" нису синоними у компјутерској алгебри. Канонски облик је такав да два израза у канонском облику су семантички једнаки ако и само ако су синтактички једнаки, док је нормална форма таква да израз у нормалном облику је семантичка нула само ако је синтаксички нула. Другим речима нула има јединствену заступљеност код израза у нормалном облику.

Нормалне форме су обично пожељне у компјутерској алгебри из неколико разлога. Прво, канонске форме могу бити скупље за рачунање од нормалних форми. На пример, да се стави полином у канонском облику, мора да се прошири по дистрибутивити сваки производ, а то није неопходно код нормалног облика (види доле). Друго, то може бити случај, као и за изражавање укључујући радикале, да канонски облик, ако постоји, зависи од неких произвољних избора и да ови избори могу да разликују два израза који су самостални. Ово може да направи употребу канонског облика непрактичном.

Види још

Теорија аутоматске провере
Доказ рачунарске помоћи
Системи компјутерске алгебре
Доказ контролора
Модел контролора
Симболичко-нумеричко рачунање
Симболичка симулација

Референце

^ SIGSAM list of journals

Литература

За детаљне дефиниције предмета:

Symbolic Computation (An Editorial), Bruno Buchberger, Journal of Symbolic Computation (1985) 1. стр. 1–6.

Уџбеници посвећени теми:

Davenport, James H.; Siret, Yvon; Tournier, Èvelyne (1988). Computer algebra: systems and algorithms for algebraic computation. Translated from the French by A. Davenport and J.H. Davenport. . Academic Press. ISBN 978-0-12-204230-0.
von zur Gathen, Joachim; Gerhard, Jürgen (2003). Modern computer algebra (second ed.). . Cambridge University Press. ISBN 978-0-521-82646-4.
Geddes, K. O.; Czapor, S. R.; Labahn, G. (1992). "Algorithms for Computer Algebra". . doi:10.1007/b102438. Недостаје или је празан параметар |title= (помоћ). ISBN 978-0-7923-9259-0.
Buchberger, Bruno; Collins, George Edwin; Loos, Rüdiger; Albrecht, Rudolf, eds. (1983). "Computer Algebra". Computing Supplementa 4. . doi:10.1007/978-3-7091-7551-4. Недостаје или је празан параметар |title= (помоћ). ISBN 978-3-211-81776-6.

[1] SIGSAM list of journals

[1]