Scrivere una prova per un algoritmo

Question

Ciao ragazzi sto cercando di confrontare 2 algoritmi e ho pensato di provare a scrivere una prova per loro !!! (I miei matematica succhia in modo da qui la domanda)

Normalmente nella nostra lezione di matematica lo scorso anno ci sarebbe stata data una domanda come

dimostrare: (2r + 3) = n (n + 4)

poi Vorrei fare le 4 fasi necessarie e ottenere la risposta alla fine

Dove sono bloccato sta dimostrando prims e Kruskals - come posso ottenere questi algoritmi in una forma come quella matematica sopra così posso procedere per dimostrare

nota: non sto chiedendo alla gente wer per me - solo aiutarmi in una forma dove posso avere un andare io stesso

grazie

Answer 1

Non si danno molti dettagli, ma c'è una comunità di matematici (matematica Knowledge Management MKM) che hanno sviluppato strumenti per supportare prove informatiche di matematica. Si veda ad esempio:

http://imps.mcmaster.ca/

e l'ultima conferenza

http://www.orcca.on.ca/conferences/cicm09/mkm09/

Answer 2

Dalle mie lezioni di matematica a Uni I (vagamente) ricordate dimostrando Prims e algoritmi Kruskals - e non si attacca scrivendolo in forma matematica. Invece, prendi teorie comprovate per i grafici e combinali per es. http://en.wikipedia.org/wiki/Prim%27s_algorithm#Proof_of_correctness per costruire la prova.

Se stai cercando di dimostrare la complessità, allora semplicemente con il funzionamento dell'algoritmo è O (n^2). Esistono alcune ottimizzazioni per il caso speciale in cui il grafico è scarso e può ridurlo a O (nlogn).

Answer 3

dove mi trovo bloccato si sta rivelando prims e Kruskals - come posso ottenere questi algoritmi in una forma simile a quella di cui sopra mathmatical modo che io possa procedere per dimostrare

Io non credo che si può direttamente. Invece, prova che entrambi generano un MST, quindi prova che i due MST sono uguali (o equivalenti, dal momento che puoi avere più di un MST per alcuni grafici). Se entrambi gli algoritmi generano MST che sono mostrati come equivalenti, allora gli algoritmi sono equivalenti.

Answer 4

Per dimostrare la correttezza di un algoritmo, in genere è necessario mostrare (a) che termina e (b) che il suo output soddisfa le specifiche di ciò che si sta tentando di fare. Queste due prove saranno piuttosto diverse dalle prove algebriche che hai menzionato nella tua domanda. Il concetto chiave di cui hai bisogno è mathematical induction. (È il recursion per le prove.)

Prendiamo come esempio quicksort.

Per dimostrare che il Quicksort termina sempre, si dovrebbe prima dimostrare che termina per l'ingresso di lunghezza 1. (Questo è banalmente vero.) Poi mostrare che se termina per input di lunghezza fino a n, allora sarà terminare per immissione di lunghezza n + 1. Grazie all'induzione, questo è sufficiente per dimostrare che l'algoritmo termina per tutti gli input.

Per dimostrare che quicksort è corretto, è necessario convertire le specifiche dell'ordinamento confronto in un preciso linguaggio matematico. Vogliamo che l'uscita sia un permutation dell'ingresso tale che se i ≤ j poi un _i ≤ un _j. Dimostrare che l'output di quicksort è una permutazione dell'input è facile, dal momento che inizia con gli elementi input e swap. Dimostrare la seconda proprietà è un po 'più complicato, ma di nuovo puoi usare l'induzione.

Answer 5

La maggior parte delle volte la prova dipende dal problema che si ha in mano. L'argomento semplice può essere sufficiente a volte, in alcune altre occasioni è possibile che richieda una prova rigorosa. Una volta ho usato un corollario e la dimostrazione di un teorema già provato per giustificare il mio algoritmo è giusto. Ma questo è per un progetto universitario.

Answer 6

Forse si desidera provare un metodo di prova semiautomatico. Per esempio, se si dispone di una specifica Java degli algoritmi di Prim e Kruskal, che si basa in modo ottimale sullo stesso modello di grafico, è possibile utilizzare lo KeY Prover per dimostrare l'equivalenza dell'algoritmo.

La parte cruciale è formalizzare l'obbligo di prova in Dynamic Logic (questa è un'estensione della logica del primo ordine con tipi e mezzi di esecuzione simbolica dei programmi Java). La formula per dimostrare potrebbe corrispondere il seguente (discutibile) modello:

\forall Graph g. \exists Tree t. 
    (<{KRUSKAL_CODE_HERE}>resultVar1=t) <-> (<{PRIM_CODE_HERE}>resultVar2=t) 

Ciò esprime che per tutti i grafici, entrambi gli algoritmi terminano e il risultato è lo stesso albero.

Se sei fortunato e la tua formula (e le implementazioni algoritmiche) sono corrette, allora KeY può dimostrarlo automaticamente per te. In caso contrario, potrebbe essere necessario istanziare alcune variabili quantificate che rendono necessario ispezionare l'albero delle prove precedente.

Dopo aver provato la cosa con KeY, puoi essere felice di aver imparato qualcosa o provare a ricostruire una prova manuale dalla prova KeY - questo può essere un compito noioso dal momento che KeY conosce un sacco di regole specifiche per Java che non sono facili da comprendere Tuttavia, forse si può fare qualcosa come estrarre una disgiunzione Herbrand dai termini che KeY ha usato per istanziare i quantificatori esistenziali sul lato destro delle sequenze nella dimostrazione.

Beh, penso che Key è uno strumento interessante e sempre più persone devono abituarsi a dimostrare codice Java critica utilizzando strumenti come questo;)