Matematikai kifejezések deriválása

Az előadáson szerepelt egy ötlet, amelyben bináris fában tároltunk műveleteket: összegeket, szorzatokat. Egy ilyen fának a felépítése, és a benne tárolt kifejezés kiértékelésének módja az előző írásban szerepelt.

A bináris fás tárolás előnye az volt, hogy a fában tárolt hierarchia, vagyis a fa felépítése meghatározza a műveletek sorrendjét. A fa csomópontjai pedig meghatározzák a típust: az elvégzendő műveletet. Észrevehetjük azt is, hogy a deriválás tulajdonképpen nagyon is egyszerű, hiszen minden típusnál ismerjük a képzési szabályt.

A deriválás alatt jelen esetben nem a differenciálhányados közelítését értjük, hanem szimbolikus deriválást, tehát a deriváltfüggvény meghatározását. Vagyis pl. az x2 függvényből a 2x előállítását. A program letölthető innen: deriv.c.

A deriválás meglepően egyszerű: konstansokat, változókat, összegeket, szorzatokat tárolunk, amelyekre vonatkozó deriválási szabályokat ismerjük:

Kifejezés	Derivált
c	0
x	1
a+b	a'+b'
ab	a'b+ab'

A deriválásnál a teendőt a függvény értékének kiszámolásához hasonlóan a csomópont típusa dönti el:

Kifejezes *derival(Kifejezes *m) {
    switch (m->tipus) {
    case Konstans: /* c -> 0 */
        return uj_konstans(0);
    case Valtozo:  /* x -> 1 */
        return uj_konstans(1);
    case Osszeg:   /* a+b -> a'+b' */
        return uj_osszeg(derival(m->bal), derival(m->jobb));
    case Szorzat:  /* ab -> a'b + ab' */
        return uj_osszeg(
                   uj_szorzat(derival(m->bal), masol(m->jobb)),  // !
                   uj_szorzat(masol(m->bal), derival(m->jobb)));
    }

    abort();
}

És már készen is vagyunk, ennyi volt.

Egy nagyon fontos dolgot viszont végig kell gondolni. Minden deriválásnál egy újonnan foglalt fával térünk vissza: egy új, frissen malloc()-olt konstanssal vagy összeggel. Az összeg esetén a rekurzió miatt a keletkező a'+b' kifejezés egyes részfái értelemszerűen ugyanígy fognak viselkedni. Szorzat esetén azonban erre külön figyelnünk kell: az a'b+ab' kifejezésben szerepel deriválatlanul az a és a b kifejezés is. A két szorzatba ezek pointereit nem tehetjük be, mivel azoknak ugyanúgy kell viselkedniük a memóriakezelés szempontjából, mint a deriváltaknak. Vagyis függetlennek kell lenniük azoktól. A sekély másolat, a pointer másolása nem elegendő, ezekről mély másolatot kell készíteni!

Egy kifejezés másolása a gyakorlaton bemutatott, rekurzív famásoló függvényhez hasonlóan történhet. Egy fa másolata a gyökér csomópont másolata, és a részfák másolata. Vagy másképpen: konstans másolata egy új konstans, összeg másolata egy új összeg (amelynek tagjai úgyszint másolatok) stb.

Kifejezes *masol(Kifejezes *m) {
    switch (m->tipus) {
      case Konstans:
        return uj_konstans(m->szam);
      case Valtozo:
        return uj_valtozo();
      case Osszeg:
        return uj_osszeg(masol(m->bal), masol(m->jobb));
      case Szorzat:
        return uj_szorzat(masol(m->bal), masol(m->jobb));
    }

    abort();
}

Így a deriváló függvényünk már helyesen működik. Nagyjából. Nézzük meg, a 2*3*x*x+3*x kifejezést hogyan írja ki, és hogyan deriválja le a program:

f(x)=2*3*x*x + 3*x
f'(x)=(0*3 + 2*0)*x*x + 2*3*(1*x + x*1) + 0*x + 3*1

A deriváltnál valami szörnyűséget kaptunk. Azonban ha megnézzük közelebbről, ez tele van 0-val és 1-gyel szorzással. Nézzük csak meg jobban! Egyszerűsítsük:

f'(x)=(0*3 + 2*0)*x*x + 2*3*(1*x + x*1) + 0*x + 3*1
f'(x)=(0 + 0)*x*x + 6*(x + x) + 0 + 3
f'(x)=(0)*x*x + 6*2*x + 3
f'(x)=12*x + 3

Ez helyes, mert 6x2+3x (2*3*x*x+3*x) deriváltja tényleg 12x+3. A deriváló program helyes, csak egyszerűsíteni kellene a kapott eredményt.

Az egyszerűsítés a deriválásból és a kiírásból ellesett ötletek alapján történhet. Például egy összeg esetén megnézhetjük, hogy az összeg valamelyik tagja konstans nulla-e, mert ha igen, akkor a másik tagot kell csak figyelembe venni. Ha mindkét tagja konstans, akkor pedig felesleges az összeget tárolni (ez három csomópontot jelent a fában: az összeget és a két konstanst), hanem elég lenne csak az elvégzett művelet eredményét, azaz egyetlen konstanst megjegyezni.

Az egyszerűsítéshez hasonló szabályokat írhatunk fel, mint a deriváláshoz. Alább a egy tetszőleges kifejezés, c pedig egy tetszőleges konstans:

Ezeket a mintákat kell felismernünk. Ha egyik sem illik rá az egyszerűsítendő kifejezésre, akkor úgy hagyjuk, ahogy van. Az egyszerűsítés természetesen rekurzív, pl. egy összeg egyszerűsítése a csomópontok egyszerűsítése után történik:

Kifejezes *egyszerusit(Kifejezes *m) {
    Kifejezes *bale, *jobbe;

    switch (m->tipus) {
        …
        …
      case Osszeg:
        bale = egyszerusit(m->bal);
        jobbe = egyszerusit(m->jobb);
        if (bale->tipus == Konstans && jobbe->tipus == Konstans) { /* szam+szam */
            double o = bale->szam + jobbe->szam;
            torol(bale);
            torol(jobbe);
            return uj_konstans(o);
        }
        if (bale->tipus == Konstans && bale->szam == 0) { /* 0+valami */
            torol(bale);
            return jobbe;
        }
        if (jobbe->tipus == Konstans && jobbe->szam == 0) { /* valami+0 */
            torol(jobbe);
            return bale;
        }
        return uj_osszeg(bale, jobbe);
        …
        …
    }

    abort();
}

Az automatikusan egyszerűsített derivált így a következő:

f(x)=2*3*x*x + 3*x
f'(x)=(0*3 + 2*0)*x*x + 2*3*(1*x + x*1) + 0*x + 3*1
egysz f'(x)=6*(x + x) + 3

Így már sokkal jobb a helyzet. Az x+x-ből ugyan így sem lett 2*x, hiszen olyan egyszerűsítési szabályunk nem volt… Az igazi, mindent figyelembe vevő egyszerűsítéshez ennél sokkal többet kellene írni. Azonban meg sem határoztuk, hogy mit jelent egy kifejezés „egyszerűsítése”. Ez nem is egyértelmű, hiszen amelyik forma egyszerű lehet egy adott művelethez (pl. kifejezések összeadásához a polinom alak), az haszonatlan lehet egy másikhoz (pl. zérushelyek meghatározásához, mert ahhoz a gyöktényezős alak alkalmasabb). Az „egyszerűség” fogalma relatív, az adott feladattól függ.

(Az innentől szereplő ötletek már nincsenek implementálva a letölthető programban.)

A program kódjában felismerhetünk egy mintát – a switch használatát. Minden művelet (deriválás, másolás, …) esetén a teendőket a típus határozza meg, vagyis minden függvényben egy ilyen switch-nek kell lennie. Ez nem túl előnyös. Ha bevezetünk egy új csomóponttípust (pl. kivonás vagy hatványozás), akkor az összes programrészt át kell néznünk, hogy hol kell módosítani. Segítséget csak az jelent, hogy a rendes fordítók figyelmeztetnek akkor, ha egy felsorolt típus alapján switch-elünk, és valamelyik lehetséges érték kimaradt.

Jobb megoldás lenne az, ami a függvénypointeres előadáson szerepelt – hogy minden csomópontba betesszük a függvényekre mutató pointereket, amelyek az adott csomópontot feldolgozzák. Így lesz pl. külön konstans_derival(), osszeg_derival() stb. függvény, és minden csomópontban lesz egy pointer, amely a sajátjára mutat. A switch-es problémát problémát ezzel az indirekcióval meg tudjuk oldani:

typedef struct Kifejezes {
    KifejezesTipus tipus;
    double szam;                     /* csak konstanshoz */
    struct Kifejezes *bal, *jobb;    /* csak muvelethez */

    struct Kifejezes (*derival_fv)(struct Kifejezes*);
} Kifejezes;

Kifejezes *konstans_derival(Kifejezes *) {
    /* konstans derivaltja 0 */
    return uj_konstans(0);
}

Kifejezes *osszeg_derival(Kifejezes *kif) {
    /* osszeg derivaltja a tagok derivaltjanak osszege */
    return uj_osszeg(kif->bal->derival_fv(kif->bal), kif->jobb->derival_fv(kif->jobb));
}

Kifejezes *uj_konstans(double szam) {
    Kifejezes *uj = (Kifejezes *) malloc(sizeof(Kifejezes));
    uj->derival_fv = konstans_derival; // !
    uj->tipus = Konstans;
    uj->szam = szam;
    return uj;
}

Kifejezes *uj_osszeg(Kifejezes *bal, Kifejezes *jobb) {
    Kifejezes *uj = (Kifejezes *) malloc(sizeof(Kifejezes));
    uj->derival_fv = osszeg_derival; // !
    uj->tipus = Osszeg;
    uj->bal = bal;
    uj->jobb = jobb;
    return uj;
}

Ez a gondolat odáig elvihető, hogy a típust jelző enum-ra egyáltalán nem lesz szükségünk. (Elvileg.) Problémát jelent azonban az, hogy mivel rengeteg műveletünk van egy csomópontra (kiértékelés, deriválás, törlés, másolás, …), ezért minden csomópontban sok pointer lesz, amelyek a helyet feleslegesen foglalják. Észrevehetjük azonban azt, hogy a csomópont típusától függő függvények mindig csoportban, együtt szerepelnek: szorzat_kiertekel(), szorzat_derival(), szorzat_torol(), szorzat_masol() stb. Ezeket betehetjük egy táblázatba (egy struktúrába), és csinálhatjuk azt is, hogy minden csomópontban csak erre a táblázatra mutató pointert tárolunk. Vagyis hozzáadunk egy újabb indirekciót. Van is egy ilyen mottó a programozásban: szinte minden probléma megoldható plusz egy indirekció bevezetésével. :) Szóval így két indirekciónk lesz. Az első pointer a táblázatra mutat, a táblázatban lévő pointer pedig a függvényre:

typedef struct Kifejezes Kifejezes;
typedef struct Fuggvenyek Fuggvenyek;

struct Fuggvenyek { // függvények táblázata
   Kifejezes* (*kiertekel)(Kifejezes*, double);
   Kifejezes* (*derival)  (Kifejezes*);
   void       (*torol)    (Kifejezes*);
   Kifejezes* (*masol)    (Kifejezes*);
};

struct Kifejezes {
   KifejezesTipus tipus;
   double szam;
   struct Kifejezes *bal, *jobb;

   Fuggvenyek *fuggvenyei; // pointer a táblázatra
};

…

Fuggvenyek osszeg_fuggvenyek = {  // összeghez tartozó táblázat
   osszeg_kiertekel, osszeg_derival, osszeg_torol, osszeg_masol
};

Fuggvenyek szorzat_fuggvenyek = { // szorzathoz tartozó táblázat
   szorzat_kiertekel, szorzat_derival, szorzat_torol, szorzat_masol
};

…

Kifejezes *uj_osszeg(Kifejezes *bal, Kifejezes *jobb) {
   …
   uj->fuggvenyei = &osszeg_fuggvenyek; // mutató az összeget kezelő fv-ek táblázatára
   …
   return uj;
}

Az összes függvényhívásnál mindig először kiválasztjuk a táblázatot, utána pedig a táblázatból a függvényt. Vagyis egy kifejezés deriválása:

Kifejezes *kif = …, *derivalt;

derivalt = kif->fuggvenyei->derival(kif);

Így működik ez C++-ban (Programozás alapjai 2.) az ún. virtuális függvényeknél, csak a mechanizmus rejtve van. Az egyszerűsítés és a kiírás problémáját egyébként nem ilyen egyszerű a függvényre mutató pointerekkel kezelni. Ha kivennénk a struktúrából a típust jelző enum-ot, akkor azok megvalósításánál problémába ütközünk: honnan tudja egy szorzat, hogy a kiírandó két tagja közül melyiket kell zárójelezni? Vagyis hogy melyik tagja összeg – ha nincs semmi, ami azok típusát mutatja?