Formalmente verifica della correttezza di un algoritmo

Question

Prima di tutto, è possibile solo questo su algoritmi che non hanno effetti collaterali?

In secondo luogo, in cui ho potuto conoscere questo processo, qualche buon libro, articoli, etc?

Answer 1

COQ è un assistente di prova che produce un output OCaml corretta. E 'piuttosto complicato però. Non ho mai avuto intorno a guardare, ma il mio collega iniziato e poi smesso di usarlo dopo due mesi. E 'stato in gran parte perché voleva fare le cose più velocemente, ma se avete bisogno di verificare un algoritmo che questo potrebbe essere una buona idea.

Ecco un corso che utilizza COQ e parla di algoritmi comprovanti.
E Ecco un tutorial sulla scrittura di articoli accademici in COQ.

Answer 2

1. E 'generalmente molto più facile per verificare / dimostrare la correttezza quando senza effetti collaterali sono coinvolti, ma non è un requisito assoluto.
2. Si potrebbe desiderare di guardare un po 'della documentazione per un linguaggio di specifica formale come Z . Una specifica formale non è una prova in sé, ma è spesso la base per uno.

Answer 3

Di solito le prove di correttezza sono molto specifici per l'algoritmo a portata di mano.

Tuttavia, ci sono alcuni trucchi ben noti che vengono utilizzati e riutilizzati di nuovo. Ad esempio, con algoritmi ricorsivi è possibile utilizzare invarianti di ciclo .

Un altro trucco comune è ridurre il problema originale di un problema per il quale la prova del vostro algoritmo di correttezza è più facile da dimostrare, allora o generalizzando il problema più facile o mostrando che il problema più semplice può essere tradotto in una soluzione al problema originale. Qui è una descrizione.

Se si dispone di un particolare algoritmo in mente, si può fare meglio nel chiedere come costruire una prova per tale algoritmo piuttosto che una risposta generale.

Answer 4

Compra questi libri: http://www.amazon.com/Science-Programming -Monographs-Computer / DP / 0387964800

Il libro Gries, programmazione scientifica è roba grande. Paziente, accurata, completa.

Answer 5

Credo che verificare la correttezza di un algoritmo sarebbe convalidare la sua conformità ad un disciplinare. V'è una branca della scienza informatica teorica chiamato metodi formali che può essere quello che stai cercando, se è necessario per ottenere il più vicino alla prova come si può. Da wikipedia,

  

I metodi formali sono un tipo particolare   Tecniche di matematicamente-based per   la specifica, lo sviluppo e   la verifica di software e hardware   sistemi

Sarete in grado di trovare molte risorse di apprendimento e gli strumenti dalla moltitudine di link sulla pagina di Wikipedia collegato e dal metodi formali wiki .

Answer 6

Logic in Computer Science, da Huth e Ryan, offre una panoramica abbastanza leggibile di sistemi moderni per i sistemi di verifica. C'era una volta la gente parlava dimostrando programmi corretta - con linguaggi di programmazione che possono o non possono avere effetti collaterali. L'impressione che ricevo da questo libro e altrove è che le applicazioni reali sono diversi - per esempio, dimostrando che un protocollo sia corretto oppure che l'unità in virgola mobile di un chip in grado di dividere correttamente, oppure che una routine senza blocchi per la manipolazione di liste collegate è corretta.

I sondaggi ACM Computing Vol 41 Issue 4 (ottobre 2009) è un numero speciale sulla verifica del software. Sembra che si può arrivare ad almeno uno dei giornali senza un conto ACM per la ricerca di "Metodi formali: pratica e l'esperienza".

Answer 7

Lo strumento Frama-C , per il quale Elazar suggerisce un video demo nei commenti, dà un linguaggio di specifica, ACSL , per la scrittura di contratti di funzione e vari analizzatori per verificare che una funzione C soddisfa le sue proprietà di contratto e di sicurezza come l'assenza di errori run-time.

Un'esercitazione estesa, ACSL per esempio , mostra esempi di attuali algoritmi C saranno specificate e verificati, e separa le funzioni privo di effetti collaterali da quelli effectful (quelle lato-privo di effetti sono considerati più facili e vengono prima nel tutorial). Questo documento è anche interessante in quanto non è stata scritta dai progettisti degli strumenti che descrivono, in modo che dà un aspetto più fresco e più didattico a queste tecniche.

Answer 8

Se si ha familiarità con LISP allora si dovrebbe verificare ACL2: http://www.cs.utexas.edu/~moore/acl2/acl2-doc.html

Answer 9

Dijkstra di Disciplina dei Programmazione e le sue EWDS gettare le basi per la verifica formale come una scienza in programmazione. Un lavoro più semplice è Wirth di Programmazione sistematica , che inizia con l'approccio semplice per utilizzare la verifica. Wirth utilizza pre-ISO Pascal per la lingua; Dijkstra utilizza un formalismo Algol-68-come detto custodito (GCL). verifica formale è maturato dal Dijkstra e Hoare, ma questi testi più anziani può ancora essere un buon punto di partenza.

Answer 10

strumento PVS sviluppato da ragazzi Stanford è un sistema di specifica e verifica. Ho lavorato su di esso e l'ho trovato molto utile per Theoram Proving.

Answer 11

WRT (1), si avrà probabilmente per creare un modello dell'algoritmo in un modo che "cattura" gli effetti collaterali dell'algoritmo in una variabile programma destinato a modellare tali collaterali effetti di stato.