Mikroszámítógép Magazin, 1985/5, pp 14-15


Képletkezelõ programok

(Mathematical Formula Manipulation Systems)

Márk Géza

mark@sunserv.kfki.hu
http://www.mfa.kfki.hu/~mark/

Mit tud egy képletkezelõ program? Egyszerûsíteni, összevonni, behelyettesíteni, több tagot szorozni több taggal, alkalmazni a nevezetes és a trigonometrikus azonosságokat, differenciálni és esetleg integrálni is, tehát azokat a mûveleteket képes elvégezni, amelyeket régebben a középiskolában algebrának neveztek. Lássunk egy alkalmazási példát. Keressük egy ellenálláshálózat (1. ábra) eredõ ellenállását.

Ellenallashalozat
R megadva emeletes torttel
1. ábra. Ellenálláshálózat, sorosan és párhuzamosan kapcsolt ellenállásokkal
 Az 1. ábra ellenálláshálózatának eredõ ellenállása emeletes törttel kifejezve


Az R-re kapott képletet begépeljük programunknak:

R := 1/(1/R1 + 1/(R1 + 1/(1/R2+ 1/R3)))

A program válasza:

( Rl**2*R2 + Rl**2*R3 + Rl*R2*R3) / (2*R1*R2 + 2*Rl*R3 + R2*R3 )

(Itt a hatványozást - a FORTRAN nyelvhez hasonlóan - két csillag jelöli.) Ha most tudjuk, hogy például R1= 0.5 Ohm és R3 = 2*R2, ezt beadhatjuk a programnak, majd megkérdezzük R új értékét, tehát begépeljük:

R1 := 1/2; R3 := 2*R2; R

A válasz:

(3 + 4*R2) / (12 + 8*R2)

Egy program megírásakor két dolgot döntünk el: az adatok abrázolási (tárolási) és feldolgozási módját. Azaz meghatározzuk a megfelelõ adatszerkezetet és a hozzá illõ algoritmust.


Adatszerkezet: a kifejezések ábrázolása fával

A BASIC nyelvben a kifejezéseket egy karaktersorozattal adjuk meg. Ez hasonlít a képletek szokásos matematikai írásmódjához. Az ilyen felírást infix formának nevezzük, mert a mûveleti jelek mindig a számok vagy változók között állnak. A FORTH nyelv esetén is karaktersorozattal adjuk meg a kifejezéseket (ezeket a FORTH kétbájtos címek sorozataként tárolja), de itt például a 2 + 3 + 4-et így kell írni: 2 3 + 4 +, vagy 2 3 4 + +. Ez a postfix forma, a mûveleti jel (operátor) mindig a mûveletben részt vevõ értékek (operandusok) után áll. Olyan nyelv is létezik - például a LISP -, ahol az operátort mindig az operandusok elé kell írni, például + 2 3. Ez a prefix forma.

Kifejezeskezelésre ezek egyike sem ideális, mert nem tükrözik a képletek szerkezetét, ezért célszerûbb a fa szerkezetû ábrázolást választani. A fának ágai vannak, az ágakból újabb ágak eredhetnek, azokból még további ágak, az ágak végén pedig levelek vagy gyümölcsök ülnek. Egy matematikai képlet abban hasonlít egy ilyen fára, hogy mindkettõ " önmagába skatulyázott szerkezetû ". A leveleknek a képletben szereplõ számok és betûk felelnek meg.

(A+B(*C fa abrazolasa
2. ábra. Az  (A+B)*C  kifejezés ábrázolása fával


Az (A + B)*C képletnek megfelelõ fát mutatja a 2. ábra. Ez egy furcsa fa, mert lefelé nõ, de így szokták rajzolni. Bonyolultabb példa a 3. ábra.


Masodfoku egyenlet megoldokeplet fa alakja  
3. ábra. A másodfokú egyenlet megoldóképletének ábrázolása fával



Masodfoku egyenlet megoldokeplet

A fa ábrázolásból egyszerû algoritmussal visszakapható a képlet BASIC vagy FORTH alakja.


Algoritmus: a helyettesítés

A helyettesítés a kifejezés-fák kezelésének alapmûvelete. Például adott a ( 2*(Y + Z)*X )**3 kifejezés, ezt szeretnénk átalakítani az (A*B)**N = A**N*B**N nevezetes azonosság segítségével. Ezt megtehetjük, mert olyan a képlet szerkezete, mint az azonosság bal oldaláé, csak A helyett 2, B helyett ( (Y + Z)*X ), N helyett 3 áll. A 4. ábra az azonosságot, az 5. ábra pedig a próbakifejezést szemlélteti. Látjuk, hogy az azonosság bal oldalát ábrázoló fa ráilleszthetõ a próbakifejezést ábrázoló fára (vastag vonallal kihúzott rész), A-nak megfelel 2, N-nek 3, B-nek pedig az ábrán nem vastagított rész.


A helyettesitesi szabalyt abrazolo ket fa  
4. ábra. A helyettesítési szabályt ábrázoló két fa


  A helyettesitesi szabaly illeszkedese
  A szabaly alkalmazasanak eredmenye
5. ábra. A helyettesítési szabály illeszkedése a próbakifejezésre
 6. ábra. A szabály alkalmazásának eredménye


Ha ezeket beírjuk az azonosság jobb oldalába A, B, N helyére, akkor már meg is kaptuk a próbakifejezés átalakított formáját (6. ábra), azaz 2 **3 * ( (Y + Z) *X ) **3-at. Erre az eredményre még egyszer alkalmazhatjuk az azonosságot, az azonosság bal oldala a kifejezés egy részfájára illeszkedik (7. ábra). A-nak az ábrán külön kiemelt rész, B-nek X, N-nek 3 felel meg. A végeredményt a 8. ábra mutatja.


   Ujboli illesztes
   Vegeredmeny
7. ábra. A helyettesítési szabály illeszkedése egy részfára
 8. ábra. A szabály alkalmazásának végeredménye


Néhány elnevezés: a helyettesítéshez használt azonosságot itt helyettesítési szabálynak hívjuk, utalva arra, hogy csak az egyik irányban kívánjuk használni (el kell dönteni, hogy éppen beszorozni vagy kiemelni akarunk, különben a program oda-vissza ismételné a két mûveletet a végtelenségig). A helyettesítési szabályban szereplõ betûket (a szabályt ábrázoló fa leveleit) formális paraméternek nevezzük, az ezeknek megfelelõ részfák a próbakifejezésben az aktuális paraméterek.


Tobbtagu osszeg lehetseges fa abrazolasai    
9. ábra. Többtagú összeg lehetséges fa ábrázolásai


Megjegyezzük, hogy egy összeget többféleképpen rajzolhatunk le fával, mivel az összeadás mûveletét hallgatólagosan kétargumentumúnak ábrázoltuk (a BASIC és FORTH nyelveknél is mindig két operandusra érvényes a " + " jel). Például az A + B + C + D kifejezést a 9. ábrán látható változatok bármelyikével ábrázolhatjuk. Az egy-egyértelmû ábrázolás az lenne, amit a 10. ábra mutat.


Tobbtagu osszeg egyertelmu fa abrazolasa    
10. ábra. Többtagú összeg egy-egy értelmû fa ábrázolása


Az összeadásnak azt a tulajdonságát, hogy (A + B) + C = A + (B + C), asszociatív törvénynek nevezzük. Csakhogy ha így ábrázonánk az összegeket és szorzatokat, elbonyolódna a helyettesítés definíciója, ezért most maradunk az eredeti, kétargumentumos megoldásnál. A fának ezt az önkényes (csak az ábrázolásból adódó) szerkezetét a FORTH (postix) forma egyértelmûen megadja, a BASIC (infix) formában pedig zárójelezéssel írhatjuk le. Például az elõbbi fák esetén így:

((A+B)+C)+D
 AB+C+D+
 (A+B)+(C+D)
 A B + C D + +
 A+(B+(C+ D))
 A B C D + + +

A BASIC nyelv - ha nem használunk zárójeleket - az elsõ formának megfelelõ sorrendben végzi a mûveleteket, a balról jobbra szabály szerint. Mi is ezt a felírást hasznaljuk a következõ példában.

Tekintsünk egy nagyon egyszerû "algebrát", amelyben csak összeadás van, azaz a kifejezések csak számokból (pozitív vagy negatív számokból), betûkbõl és " + " jelbõl épülhetnek fel. Ilyen kifejezés például:

-1 + B + A + 2    azaz: ((-1 + B) + A) + 2

Ennél az "alig-algebránál" a kifejezések feldolgozása két dolgot jelent: a változók ABC sorrendbe rendezését és a számok összevonását. Megadjuk azokat a helyettesítési szabályokat, amelyek elvégzik ezeket:

1. X + Y -> Y + X
 ha X szám vagy betû Y is szám vagy betû és X>Y
2. (X + Y) + Z -> (X + Z) + Y
 ha Y szám vagy betû Z is szám vagy betû és Y > Z
3. N+M -> val( N+M )
4. (X+N)+M -> X+val( N+M )
5. X+0 -> X

Az 1. és 2. szabály biztosítja a rendezést. A betûk legyenek "kisebbek", mint a számok (az ASCII kódnál például fordítva van, a számok kódja a kisebb), így a helyettesítés a kifejezés végére rendezi a számokat. A 3., 4., 5. szabályok végzik a számok összevonását, N és M (pozitív vagy negatív) szám lehet. A "val" a kifejezés számértékét jelenti.

Próbakifejezésünk átalakításának lépései a következõk:

((-1 +B)+A) +2 -> ((B+ -1)+A)+2
 1. szerint
((B+ -1)+A)+2 -> ((B+A)+ -1)+2-->(B+A)+2)+ -1
 2. szerint
((B+A)+2)+ -1 ->((A+B)+2)+ -1
 1. szerint
((A+B)+2)+ - 1 -> (A+B)+ 1
  4. szerint

Többféle mûvelet, bonyolultabb szabályrendszer esetén is meg lehet próbálni a kifejezésfeldolgozó algoritmust helyettesítési szabályok segítségével megadni. De ez azzal jár, hogy bonyolultabbá válnak a szabályok alkalmazásának feltételei, és az algoritmus nagyon lassú lesz, mert minden kifejezésnél és annak minden részkifejezésénél végig kell vizsgálni az összes szabály alkalmazhatóságát. Ezért a gyakorlatban közvetlen algoritmusokat használnak a sûrûn elõforduló mûveletekre: a rendezésre, összevonásra, differenciálásra stb. Ezek az algoritmusok "behuzalozva" tartalmazzák az alapmûveletek tulajdonságait (a nevezetes azonossagokat), így hátrányuk a helyettesítéses módszerhez képest az, hogy merevebbek annál.

A rendszerek egy része úgy dolgozik, hogy minden kifejezést egy egységes "kanonikus" formára alakít (például a betûket mindig ABC-be rendezi, a hatványokat nagyság szerint, a zárójeleket felbontja, a törteket közös nevezõre hozza stb.). Két kifejezést akkor vesz egyenlõnek, ha az egységesítés után a kifejezéseket egyforma fa ábrázolja: összevonásnál és egyszerûsítésnél az egyenlõ kifejezések különbsége nulla, hányadosa egy.


A mûködõ formulamanipulációs rendszerek

Egy egyszerûbb képletkezelõ program az alábbi részekbõl áll:
  • Kifejezések beolvasása és kiírása, a belsõ ábrázolás (fa) és külsõ ábrázolás (karaktersorozat) közötti átalakítás. Kényelmes, ha a külsõ ábrázolás közel áll a szokásos matematikai írásmódhoz (törtvonal, alsó-felsõ indexek).
  • Helyettesítõ algoritmus, változtatható helyettesítési szabályokkal.
  • Képletegységesítõ algoritmus. Ennek is többé-kevésbé befolyásolható a mûködése: "kapcsolók" állításával meg lehet adni, hogy fel, akarjuk-e bontani a zárójeleket, ki akarjuk-e fejteni az összegek hatványait stb.
Néhányat felsorolunk a bonyolultabb rendszerek lehetõségei közül:
  • Számítási program tárolása. Egy BASIC-hez vagy Pascalhoz hasonló nyelven le lehet írni a feladat programját; a programban szereplõ változók értéke vagy egy kifejezés (fa), vagy egy szám. A számok lehetnek egészek, törtek és lebegõpontos számok. Általában több száz jegyû egész számok is alkalmazhatók.
  • Vektorok, mátrixok.
  • Egyenletek, egyenletrendszerek megoldása.
  • Integrálás.

Milyen nyelven célszerû képletkezelõ programot írni? Jó, ha a nyelv tud fa szerkezetekkel és rekurzív szubrutinokkal dolgozni. A legelterjedtebb ilyen nyelv az 1960-ban kidolgozott LISP (LISt Processor). A futási idõ és a szükséges memória nagymértékben függ az alkalmazott nyelvtõl és algoritmusoktól.

Az elsõ formulamanipulációs programokat már az ötvenes évek végén megírták. A fejlõdés fõ ösztönzõje a fizikai kutatás volt, többek között az égi mechanika és a relativitáselmélet. Sokszor elõnyösebb egy eredményt képlet  formájában, mint numerikusan (számok, ábrák alakjában) megkapni, fõleg, ha az eredmény több változótól függ. Ezenkívül a numerikus számítást mindig terhelik a kerekítésbõl adódó hibák, a hibák hatása pedig néha drasztikus, és nem is mindig becsülhetõ meg pontosan. A képletkezelés felhasználja a formális logika eredményeit, szegrõl-végrõl rokonságban van a tételbizonyító és programhelyesség-bizonyító rendszerekkel is.

A nagyszámítógépekre több formulamanipulációs program is létezik: REDUCE, FORMAC, MACSYMA stb. Ezek egy része hazai számítóközpontokban is hozzáférhetõ. A  gyakorlatban is érdekes feladatok esetén a tárigeny több száz kbájt, a futási idõ több perc vagy több óra. Kézzel, papíron a megoldás általában évekig tartana. A nagygépes rendszerek legtöbbször nem interaktívak. A "nagygép" kifejezés persze relatív. A személyi számítógépek napjainkban elérik azt a teljesítményt, ami a komolyabb képletkezelõ rendszerek futtatásához kell (16 bites mikroprocesszor, 256 k memória, 10 MHz órajel stb.). De egy egyszerûbb rendszer akár egy C64 gépen is futhat, CP/M-re is létezik ilyen program. A formulamanipulációnál nagy elõny az interaktivitás, mert az ember sokszor csak a képlet alakítása közben jön rá, hogy milyen mûveleteket lenne érdemes kipróbálni.

Feladatok

  1. Hogyan célszerû ábrázolni a fa szerkezetet a számítógép memóriájában?
  2. Írjuk meg a kifejezéseket fává (és vissza) alakító programot!
  3. Írjuk meg a helyettesítõ algoritmust!

Last updated: Dec 12, 2002 by Géza I. Márk , mark@sunserv.kfki.hu
This page was accessed  times since Dec 12, 2002.