È possibile scrivere un verificatore che controlli se un determinato programma implementa un determinato algoritmo?

Dato un programma P, scritto in C++, posso scrivere un algoritmo che trovi se il programma P implementa un particolare algoritmo? C'è qualche algoritmo che risolve questo problema. Questo problema è risolvibile?È possibile scrivere un verificatore che controlli se un determinato programma implementa un determinato algoritmo?

Ad esempio, chiedo a una persona di implementare un algoritmo di ordinamento rapido e ora se voglio accertarmi che la persona abbia effettivamente implementato un algoritmo di ordinamento rapido. La persona può effettivamente implementare un altro algoritmo di ordinamento e produrrà l'output corretto e passerà tutti i testicoli (test black box). Un modo per farlo è guardare nel codice sorgente. Voglio evitare questo sforzo manuale e voglio scrivere un programma che possa fare questo lavoro. La domanda è "È possibile?".

fonte

2013-02-24 Aryaveer

Che ne diresti se la persona utilizza un'interfaccia astratta per alcune operazioni di basso livello, come l'accesso agli elementi e lo scambio. Poi passa loro un oggetto concreto che si assicura che il chiamante chiami quelle operazioni nel modo in cui Quicksort farebbe. –

Da Rice's Theorem, non è nemmeno possibile in generale decidere se una parte di codice è una funzione di ordinamento o meno esaminando il codice. Ovviamente, è possibile scoprire se ha l'effetto di ordinare determinati set di input finiti eseguendoli con tali input ed esaminando i risultati.

Potrebbe essere possibile fare qualcosa per il caso specifico di un determinato algoritmo di ordinamento di destinazione, esaminando la matrice che viene ordinata durante l'ordinamento, controllando gli invarianti che sono caratteristici dell'algoritmo di destinazione. Ad esempio, ogni chiamata in un'implementazione di ordinamento rapido ricorsivo comporterà l'ordinamento di un sottoarray.

========================================= ===================

In seguito ai commenti, suggerisco di guardare Ahmad Taherkhani's home page. Ha continuato la ricerca in questo settore, tra cui un documento del 2012 sull'argomento.

fonte

2013-02-24 15:08:49

grazie davvero aiutato. Mi chiedo se funzionerà se usiamo alcuni set di programmi di esempio che implementano l'algoritmo e quindi proviamo a classificare un programma. Come fanno nei problemi di apprendimento automatico. – Aryaveer

@Aryaveer La chiave per farlo sarebbe trovare le caratteristiche che è possibile estrarre dal testo in modo tale che i punti vicini nello spazio delle funzioni rappresentino algoritmi simili. Ho fatto alcune ricerche sul Web e ho trovato [Analisi del programma statico per il riconoscimento degli algoritmi di ordinamento] (www.cs.hut.fi/~ahmad/mastersthesis.pdf). È un documento del 2008, ma potrebbe essere un utile punto di partenza per la ricerca delle citazioni per trovare lo stato dell'arte. –

Stavo pensando, e sto ancora pensando ai controlli stack/heap (dato che testate anche con soluzioni ottimizzate).
È possibile verificare la complessità del tempo e la complessità complessiva della memoria che restringerà i risultati. anche per il tempo: O (n lg n) per l'unione e le ordinazioni rapide. puoi distinguerli con l'allocazione di memoria dato che sono N, Lg (n) in ordine.
puoi anche controllare cose come il disturbo dell'array originale ... ma questo non è un peso decisivo.

fonte

2013-02-24 15:14:21 blackmath

È possibile scrivere un verificatore che controlli se un determinato programma implementa un determinato algoritmo?

risposta

Problemi correlati