Simboličko računanje

U računarskoj matematici, kompjuterskoj algebri, drugačije rečeno simboličko računanje ili algebarsko računanje je naučna oblast koja se odnosi na proučavanje i razvoj algoritama i softvera za manipulisanje matematičkim izrazima i drugim matematičkim objektima. Iako, pravilno rečeno, kompjuterska algebra treba da bude potpolje naučnog računarstva, ona se generalno smatra različitim poljem jer se naučno računanje obično zasniva na numeričkom računanju sa približno Floating brojevima tačke, dok simbolično računanje ističe tačan obračun sa izrazima koji sadrži varijable koje imaju i vrednosti koje nisu date i time su izmanipulisani kao simboli (od toga je naziv simboličko računanje).

Softverske aplikacije koje obavljaju simboličke kalkulacije se nazivaju sistemi kompjuterse algebre, sa rokom sistem aludirajući na složenost glavnih aplikacija koje uključuju, najmanje, metod za predstavljanje matematičkih podataka u računaru, korisnički programski jezik (obično se razlikuje od jezika koji se koristi za realizaciju), namenski menadžer memorije, korisnički interfejs za ulaz / izlaz matematičkih izraza, veliki skup šablona za obavljanje uobičajenih poslova, kao pojednostavljivanje izraza, diferenciranje korišćenjem pravila lanca, polinoma faktorizacija, neodređene integracije, itd .

Na početku računarske algebre, oko 1970. godine, kada su odavno poznati algoritmi bili prvi put na računarima, ispostavilo se da je to bilo veoma neefikasno. Zbog toga, veliki deo istraživačkog posla na terenima se sastojao u ponovnom osvrtu na klasičnu algebru kako bi se učinili efikasnijim i otkrili efikasni algoritmi za ispunjenje ove efikasnosti. Tipičan primer ovakvog rada je izračunavanje polinoma najvećih zajedničkih delilaca, koji je potreban za pojednostavljivanje razlomaka. Iznenađujuće, ispostavilo se da je klasičan Euklidov algoritam bio neefikasan za polinoma u beskonačnim poljima, zbog toga je potrebno da se razvije novi algoritam. Isto je bilo i za klasične algoritme iz linearne algebre.

Kompjuterska algebra se široko koristi za eksperimente u matematici i dizajniranje formula koje se koriste u numeričkim programima. Takođe se koristi za kompletno naučno računanje, kada se numeričke metode ne izvrše u celini, kao u kriptografiji javnog ključa ili za neke nelinearne probleme.

Terminologija

Neki autori razlikuju kompjutersku algebru od simboličkog računanja pomoću drugih imena koja se odnose na vrste drugih simboličkih računanja ili obračuna sa matematičkim formulama. Neki autori koriste simbolično računanje za računarsku nauku i "kompjutersku algebru" za matematičke aspekte. U nekim jezicima naziv oblasti nema direktan prevod sa Engleskog. Tipično, to se zove kalkulacija formula na francuskom, što znači "formalno računanje".

Simboličko računanje se u prošlosti spominjalo takođe i kao simbolička manipulacija, algebarska manipulacija, simbolička obrada, simbolička matematika, ili simbolička algebra, ali ovih uslova, koji se takođe odnose na ne-računarske manipulaciju, nema više u upotrebi koja se odnosi na kompjurersku algebru.

Naučna zajednica

Ne postoji društvo koje je posebno za kompjutersku algebru, ali ovu funkcija preuzimaju grupe od posebnog interesa Association for Computing Machineri pod nazivom SIGSAM (Special Interest Group na simboličkim i Algebarskim manipulacijama).

Postoji nekoliko godišnjih konferencija vezanih za računarsku algebru prva je (Međunarodni simpozijum o simboličkom i Algebarskom računanju), koju redovno sponzoriše SIGSAM.

Postoji nekoliko časopisa specijalizovanih za računarsku algebru, na prvom mestu je žurnal simboličkog računanja osnovan 1985. godine od strane Bruna Buchbergera. Tu je i nekoliko drugih časopisa koji redovno objavljuju članke o kompjuterskoj algebri.^[1]

Aspekti računarske nauke

Predstavljanje podataka

Kako je numerički softver veoma efikasan za približno numeričko računanje, uobičajeno je, u kompjuterskoj algebri, da se naglase tačna računanja sa tačno predstavljenim podacima. Takav odraz implicira da, čak i kada je veličina izlaza mala, srednji podaci dobijeni tokom izračunavanja mogu rasti u nepredvidivom obliku. Ovo ponašanje se zove super izraz. Da bi se otklonio ovaj problem, koriste se razni metodi u predstavljanju podataka, kao i algoritama koji njima manipulišu.

Brojevi

Obično se sistemi brojeva koriste u numeričkom računanju koji su ili pokretni brojevi ili celi brojevi u fiksnoj ograničenoj veličini, koji se nepropisno nazivaju celim brojevima u većini programskih jezika. Ništa nije pogodno za kompjutersku algebrz, zbog super izraza.

Dakle, osnovni brojevi koji se koriste u računarskoj algebri su celi brojevi kod matematičara, obično predstavljaju od strane neograničenim potpisan niz cifara u nekoj bazi numeracije, obično najvećom bazom dozvoljenog mašine reči. Ovi celi brojevi omogućavaju da se definišu racionalnih brojeva, koji su neprivodimie frakcije dva celih brojeva.

Programiranje efikasne implementacije aritmetičkih operacija je težak zadatak. Dakle, većina besplatnih kompjuterskih algebarskih sistema i neki komercijalni, kao Maple (softver), koriste GMP biblioteku, koja je zapravo standardna.

Izrazi

Osim brojeva i varijabli, svaki matematički izraz se može posmatrati kao simbol operatora praćeno nizom operandi. U softveru kompjuterske algebre, izrazi se obično predstavljaju na ovaj način. Ovakvo predstavljanje je veoma fleksibilno, i mnoge stvari, za koje se čini da ne mogu biti matematički izrazi na prvi pogled, mogu biti predstavljeni i manipulisani tako. Na primer, jednačina je izraz sa "=" kao operatorom, matrica može biti predstavljena kao izraz sa "Matrik" kao operator, a njeni redovi, kao operande.

Čak i programi mogu biti smatrani i predstavljeni kao izrazi sa operatorom "procedure" i, najmanje, dva operanda, na listi parametara i tela, koji je sam izraz "tela" kao operator i niz uputstava kao operandi. Nasuprot tome, svaki matematički izraz može se posmatrati kao program. Na primer, izraz A + B se može posmatrati kao program za sabiranje, sa a i b kao parametrima. Izvođenje ovog programa se sastoji u proceni izraza za date vrednosti A i B; ako nemaju nikakvu vrednost onda su oni neodređeni-, rezultat procene je jednostavno njegov ulaz.

Ovaj proces odložene procene je od fundamentalnog značaja u kompjuterskoj algebri. Na primer, operator "=" je takođe jednačina, u većini kompjuterskih algebarskih sistema, naziv programa testa jednakosti: uobičajeno, izražavanje rezultata jednačine i brojevima, kada je potreban test jednakosti, bilo da izričito zatražen od strane korisnika kroz "evaluacije u Boolean" komande, bilo da je automatski sistem započet u slučaju testa unutar programa-onda procene da boolean 0 ili 1 je pogubljen.

Kako je veličina operande u izrazu nepredvidiva tako se ona može menjati tokom radnog sastanka, redosled operande se obično predstavlja kao niz bilo pokazivača (kao u Macsima) ili niz upisa u heš tabelu (kao u Maple).

Pojednostavljenje

Sirova primena osnovnih pravila diferenciranja u odnosu na k u izrazu a^ k daje rezultat $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.

Ovo pojednostavljivanje se obično vrši kroz ponovno pisanje pravila. Postoji nekoliko vrsta prepisivanja pravila koja se moraju uzeti u obzir. Najjednostavniji se sastoji u ponovnom pisanju pravila koja uvek smanjuju veličinu izražavanja, kao E - E → 0 ili sin (0) → 0. Oni se sistematski primenjuju u sistemima kompjuterske algebre.

Prva poteškoća se javlja sa asocijativnim operacijama kao što su sabiranje i množenje. Standardni način da se obave asocijativnost jesteda se uzme u obzir da sabiranje i množenje ima proizvoljan broj operanada, to jest da je a + b + c predstavljena kao "+" (A, B, C). Tako A + (B + C) i (A + B) + C su oba pojednostavljena da "+" (A, B, C), koji se prikazuje A + B + c. Šta je sa a - b + c? Kako biste se izborili sa ovim problemom, najjednostavniji način je da se prepravi sistematično -E, E - F, E / P kao, odnosno, (-1) ⋅E, E + (-1) ⋅F, E⋅F-1. Drugim rečima, u unutrašnjem predstavljanju izraza, nema ni podele, ni oduzimanja ni unarnog minusa, izvan predstavljanja brojeva.

Druga poteškoća se javlja sa komutatinošću sabiranja i množenja. Problem je da se brzo prepoznaju kao uslovi kako bi se kombinovali ili poništili. U stvari, postupak za pronalaženje sličnih izraza, sastoji se od testiranja svakog para termina, ovo previše košta i izvodljivo je samo sa veoma velikim novcem i proizvodima. Za rešavanje ovog problema, Macsima sortira operande sume i proizvoda sa funkcijom poređenja koja je dizajnirana kao termin na uzastopnim mestima, i na taj način ih je lako detektovati. Dizajn heš funkcije takođe omogućava da odmah prepoznate izraze ili subekpressions koji se pojavljuju više puta u izračunavanju i da ih čuvate samo jednom. Ovo omogućava ne samo da se uštedi nešto memorije, već i da se ubrza računanje, izbegavanjem ponovavljanja istih operacija na više istih izraza.

Neka prepisana pravila nekad povećavaju a nekad smanjuju veličinu izraza za koje se primenjuju. Ovo je slučaj distributivnih ili trigonometrijskih identiteta. Na primer, zakon dozvoljava distributivno prepisivanje $(x+1)^{4}\rightarrow x^{4}+4x^{3}+6x^{2}+4x+1$ i $(x-1)(x^{4}+x^{3}+x^{2}+x+1)\rightarrow x^{5}-1.$ Pošto ne postoji način da se napravi dobar opšti izbor primenom i takvo prepisivanje nije pravilno, takvo prepisivanje se vrši samo kada se izričito traži od strane korisnika. Za distributiviti, računarska funkcija koja primenjuje ovo prepisivanje pravila se obično naziva "širi". Obrnuto prepisivanje pravila, pod nazivom "faktor", zahteva netrivialni algoritam, koji je na taj način ključna funkcija u sistemima kompjuterske algebre (vidi razlaganje polinoma).

Matematički aspekti

U ovom odeljku razmatramo neka temeljna matematička pitanja koja se javljaju čim želimo da manipulišemo matematičkim izrazima u računaru. Mi smo uglavnom razmotrili slučaj multivarijantnih racionalnih frakcija. Ovo nije pravo ograničenje, jer, čim se iracionalni funkcije pojavljuju izrazisu pojednostavljeni, i oni se obično smatraju nerešenim. Na primer $(\sin(x+y)^{2}+\log(z^{2}-5))^{3}$ se posmatra kao polinom $\sin(x+y)$ i $\log(z^{2}-5)$

Jednakost

Postoje dva pojma jednakosti za matematičke izraze. Sintaksna ravnopravnost je jednakost izraza, što znači da su pisani (ili zastupljeni u računaru) na isti način. Trivijalno, retko tako smatraju i matematičari, ali to je jedina jednakost koja se lako može testirati sa programom. Semantička jednakost je kada dva izraza predstavljaju isti matematički predmet, kao u (k + i) ^ 2 = k ^ 2 + 2ki, i ^ 2.

Poznato je iz Ričardove teoreme da ne može postojati algoritam koji odlučuje da li dva izraza obuhvataju brojeve koji su semantički jednaki, ako su eksponenti i logaritmi dozvoljeni u izrazima. Stoga (semantička) jednakost može biti testirana samo na nekim vrstama izraza kao što su polinomi i racionalne razlomci.

Da bi se testirala jednakost dva izraza, umesto da se dizajnira poseban algoritam, uobičajeno je da se stave u neki kanonski oblik ili njihove razlike u normalan oblik i da se testira rezultat sintaksičke jednakosti.

Za razliku od uobičajene matematike, "kanonski oblik" i "normalni oblik" nisu sinonimi u kompjuterskoj algebri. Kanonski oblik je takav da dva izraza u kanonskom obliku su semantički jednaki ako i samo ako su sintaktički jednaki, dok je normalna forma takva da izraz u normalnom obliku je semantička nula samo ako je sintaksički nula. Drugim rečima nula ima jedinstvenu zastupljenost kod izraza u normalnom obliku.

Normalne forme su obično poželjne u kompjuterskoj algebri iz nekoliko razloga. Prvo, kanonske forme mogu biti skuplje za računanje od normalnih formi. Na primer, da se stavi polinom u kanonskom obliku, mora da se proširi po distributiviti svaki proizvod, a to nije neophodno kod normalnog oblika (vidi dole). Drugo, to može biti slučaj, kao i za izražavanje uključujući radikale, da kanonski oblik, ako postoji, zavisi od nekih proizvoljnih izbora i da ovi izbori mogu da razlikuju dva izraza koji su samostalni. Ovo može da napravi upotrebu kanonskog oblika nepraktičnom.

Vidi još

Teorija automatske provere
Dokaz računarske pomoći
Sistemi kompjuterske algebre
Dokaz kontrolora
Model kontrolora
Simboličko-numeričko računanje
Simbolička simulacija

Reference

^ SIGSAM list of journals

Literatura

Za detaljne definicije predmeta:

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

Udžbenici posvećeni temi:

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. Nedostaje ili je prazan parametar |title= (pomoć). 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. Nedostaje ili je prazan parametar |title= (pomoć). ISBN 978-3-211-81776-6.

[1] SIGSAM list of journals

[1]