Algoritmo per riorganizzare equazioni / predicati di confronto

2

Supponiamo di avere un'equazione come x1 + c1 * x2 + c2 / (y1 + c3) = y2 - x3

Il mio obiettivo è di riorganizzarlo in modo che tutte le x siano su un lato dell'equazione, e tutte le y sono sull'altro, f(x1, x2, ..., xi) = g(y1, y2, ..., yj) (quindi, per il mio esempio, x1 + c1 * x2 + x3 = y2 - c2 / (y1 + c3) è una soluzione)

Prima di tutto, c'è un nome per questa trasformazione?

Sto cercando algoritmi esistenti che possano farlo (non è necessario coprire tutti i casi, alcuni semplici potrebbero essere un buon inizio) o restituire ciò che non può. È piuttosto semplice se si consente solo +/-, ma diventa più complicato quando è consentita la moltiplicazione / divisione o altri operatori ...

    
posta Bwmat 08.09.2016 - 19:44
fonte

2 risposte

3

Dove cercare questo tipo di problemi?

Il campo dell'informatica / matematica " calcolo simbolico " è una disciplina (non una famiglia di algoritmi) che mira a trovare soluzioni e algoritmi per risolvere questo tipo di problemi.

Più precisamente, una categoria di software chiamata "Computer algebra system (CAS)" riguarda la manipolazione simbolica applicata all'algebra . Per semplificare, questo tipo di sistemi ha bisogno di un parser e il loro core è un motore per la risoluzione delle equazioni e il riordino delle equazioni.

Anatomia (molto semplificata) di un CAS

Il parser applicherà le regole grammaticali per analizzare i termini in un'equazione e il raggruppamento di termini usando le regole grammaticali

Il motore implementa sistemi di riscrittura dei termini molto elaborati, il tipo di algoritmi che applica una serie di "regole di semplificazione" o "regole di riscrittura", al fine di raggiungere un obiettivo (ad esempio, tutte le x su un lato, tutte le y sull'altro).

Questo articolo offre una rapida introduzione a questa famiglia di algoritmi.

Ad esempio, una regola potrebbe essere

     A + expression1 = expression2   ==>    expression = expression2 - (A)

Ma ci sarebbero centinaia di regole come questa.

Inoltre, un sistema di riscrittura a termine deve avere una logica guida, per scegliere le riscritture più promettenti (ad esempio riarrangiamento). Puoi immaginarlo come una sorta di algoritmo di individuazione dei percorsi che cerca un percorso ottimale in un grafico di possibili riscritture, un po 'come se il tuo sistema GPS fosse alla ricerca di un percorso ottimizzato per le strade. E in questa logica, è necessario aggiungere alcune strategie, che rendono il TRS preferisce mettere gruppi di simboli da una parte o dall'altra del segno di uguale.

Non è un gioco da ragazzi!

Inutile dire che sono sistemi molto complessi. È più la cosa per un laboratorio di ricerca. Fortunatamente ci sono alcuni dei quali disponibili , anche alcuni open source con cui potresti iniziare.

    
risposta data 12.09.2016 - 23:37
fonte
2

Il nome per la trasformazione che stai cercando è "Algebraic Simplification". Il superset degli algoritmi e del codice in cui vuoi dare un'occhiata si chiama "Compendio simbolico".

    
risposta data 12.09.2016 - 21:24
fonte

Leggi altre domande sui tag