Popolare un vettore di numeri per esporre un errore in un'implementazione della funzione

Question

Quindi diciamo che sto scrivendo un algoritmo che prende un vettore come input. Voglio sapere che sto scrivendo questo algoritmo correttamente, tuttavia, quindi ovviamente scrivo test per vedere se l'output equivale a ciò che mi aspetto su ingressi specifici. In effetti potrei farlo per tutte le dimensioni vettoriali sotto una certa dimensione, ma non enumerei mai tutti i valori possibili, solo tutte le dimensioni vettoriali possibili.

Si verifica per me tuttavia che potrebbe essere possibile popolare i valori del vettore in modo che io possa ancora verificare ogni possibile vettore sotto una certa dimensione fino a quando apporto una certa assunzione sull'attuazione della funzione in prova.

Dì che ho una funzione $ f: \ mathbb {n} ^ n \ in \ mathbb {n} $ tale che $ f (x)=sum_ {i= 1} ^ nc_i \ Prod_ {j= 1} ^ n x_j ^ {e_ {ij}} $ per qualche $ e $ e $ c $ tale che $ e_ {ij} \ in \ {0,1 \} $ e $ c_i \ in \ {0, 1 \} $ . Voglio vedere se questo è uguale ad una funzione dorata conosciuta $ G $ ma dovrò risolvere manualmente $ G $ per ingressi specifici. Lo credo ad essere vero che esiste un ingresso $ r $ in modo tale che $ f (r) $ Determina in modo univoco $ f $ . Ciò rende il test per vedere se un'implementazione particolarmente di $ f $ è quello che ci aspettiamo tribunalmente facile.

per $ n= 2 $ i possibili valori di $ f (3, 7) $ sono il seguente: 0, 1, x= 3, y= 7, xy= 21, 2, 1 + x= 4, 1 + y= 8, 1 + XY= 22, x + x= 6, x + y= 10, X + XY= 24, XY + XY= 42

Quindi se faccio il presupposto che una funzione partiuclar che sto testando ha quanto sopra caratterizzato da $ c $ e $ e $ Quindi ho bisogno solo di un input per testare completamente un'implementazione di $ f $ .

Un buon euristico per la generazione di questi ingressi è iniziare con il primo prime più alto del numero di termini che hai, e quindi prova successivamente PREMS più alti per ciascun input successivo fino a quando non si allenano i pochi nodi che rimangono. L'intuizione è che non ci sono due prodotti saranno gli stessi perché hai scelto PREMES e che ogni prodotto unico sarà distanziato da così tanto che anche le somme saranno anche anche uniche.

Esiste un algoritmo per generare un input a tale funzione che rende tutte le possibili funzioni che tali funzioni comportano valori unici? Cosa succede se siamo disposti ad essere probabilistici in un certo senso come "L'output previsto probabilmente unico per questo input"? Ci sono altre forme di funzioni per le quali è stata studiata questa domanda?

Answer 1

polinomi multilineari

Se sei disposto a utilizzare metodi probabilistici, suggerisco di utilizzare un algoritmo randomizzato per il test dell'identità polinomiale.

Si desidera verificare se $ f (x)= g (x) $ Tiene per tutti $ x $ < / span>, dove $ f, G $ sono ooliiniali multilineari. Questa è un'istanza del test di identità polinomiale problema. Esistono efficaci algoritmi randomizzati per test di identità polinomiale.

Per rendere questa risposta autosufficiente, ti darò una breve panoramica di un algoritmo ragionevole. Innanzitutto, scegli a caso una grande prime $ p $ . Successivo, seleziona casualmente $ x= (x_1, \ dots, x_n) $ , con ciascun elemento $ x_i $ scelto uniformemente a casuale modulo $ p $ . Infine, controlla se $ P (x) \ Equiv G (x) \ PMOD P $ . Se no, allora sai che la tua implementazione è difettosa. Se sì, la tua implementazione ha una buona possibilità di essere bravo. (In particolare, un'implementazione difettosa che calcola alcuni altri polinomi multilineari ha una bassa probabilità di andare in ritardo, grazie al Schwartz-Ziland Lemma .) È possibile ripetere questa procedura più volte per garanzie più forti.

Questa procedura presuppone che tu possa ispezionare il codice dell'algoritmo e verificare che calcola un polinomio multilineo, che sembra essere qualcosa che la tua domanda propone di poter assumere. Se hai una scatola nera completa e non hai conoscenza se calcola un polinomio multilineario o meno, non puoi ottenere forti garanzie che $ f $ sarà corretto ovunque : Ad esempio, la tua implementazione $ f $ potrebbe essere corretto su tutti tranne un ingresso in cui è coperto da un involucro speciale per emette la risposta errata.

Più casi generali

Potresti essere interessato alla teoria degli auto-test, pionieri di Blum, Luby, Rubinfeld e ulteriormente sviluppati da altri. Vedi, ad es., La seguente carta seminale:

Self-test / correzione con applicazioni a problemi numerici . Manuale Blum, Michael Luby, Ronitt Rubinfeld. Journal of Computer e System Sciences, 47 (3), 549-595.

Generalizza la tua idea considerando i tester che richiamano il programma-sottomissione più volte; Consentendo i test probabilistici, dove c'è una possibilità che non avremmo notevoli problemi, ma questa probabilità può essere controllata o limitata; E consentendo l'auto-correzione, dove usiamo il programma possibilmente difettoso come subroutine per costruire un'uscita che sarà corretta con alta probabilità. Nondimeno, nonostante queste generalizzazioni, la classe di funzioni che sappiamo come costruire efficienti autotettrici per è abbastanza limitata, e non sappiamo come farlo per le funzioni arbitrarie.