プログラムPがC++で書かれている場合、プログラムPが特定のアルゴリズムを実装しているかどうかを調べるアルゴリズムを書くことはできますか？この問題を解決するアルゴリズムはありますか？この問題は解決可能ですか？与えられたプログラムが与えられたアルゴリズムを実装しているかどうかをチェックするベリファイアを書くことはできますか？
は、例えば、私はクイックソートアルゴリズムを実装するために、人を尋ねると、今私は、人が実際にクイックソートアルゴリズムを実装していることを確認したい場合。人は実際に他のソートアルゴリズムを実装することができ、正しい出力を生成し、すべてのテストケースを通過させます（ブラックボックステスト）。私がこれを行う方法の1つは、ソースコードを調べることです。私はこの手作業を避け、この仕事をすることができるプログラムを書こうと思っています。問題は「それは可能ですか？」です。
Rice's Theoremから、あなたも、一般的にコードの一部は、コードを調べることによってソート機能であるかどうかを判断することはできません。もちろん、それらの入力で実行して結果を調べることで、有限の入力セットをソートする効果があるかどうかを調べることができます。
ソート中にソートされている配列を調べ、ターゲットアルゴリズムの特徴である不変量を調べることで、特定のターゲットソートアルゴリズムの特定のケースで何かできることがあります。たとえば、再帰的なクイックソートの実装では、呼び出しごとにサブアレイがソートされます。
============================================== ===================
のコメントに続いて、私はAhmad Taherkhani's home pageを見てお勧めします。彼はこのトピックに関する2012年の論文を含め、この分野での研究を継続しています。
本当に助けてくれてありがとう。アルゴリズムを実装しているサンプルプログラムを使用し、プログラムを分類しようとするとうまくいくのだろうかと思います。彼らは機械学習の問題のように。 – Aryaveer
@Aryaveerこれを行うための鍵は、テキストから抽出できる特徴を見つけることです。そのようにして、特徴空間内で近接する点が類似のアルゴリズムを表すようになります。私はいくつかのウェブ検索を行い、[ソートアルゴリズムを認識するための静的プログラム分析]（www.cs.hut.fi/~ahmad/mastersthesis.pdf）が見つかりました。それは2008年の論文ですが、最先端の技術を見つけるための引用検索の出発点になるかもしれません。 –
私は考えて、まだ（あなたにも最適なソリューションに対してテストを与えられた）、スタック/ヒープチェックを考えていました。
時間の複雑さと全体的なメモリの複雑さを確認することで、結果を絞り込むことができます。時間：O（n lg n）の場合でも、マージとクイックソートが可能です。それらは順番にN、Lg（n）であるため、それらをメモリ割り当てと区別することができます。
元のアレイ外乱などのことを確認することもできますが、これは決定的な重みではありません。人はそのような要素とスワッピングへのアクセスなど、低レベルな操作の抽象インタフェースを使用することについて
方法。その後、呼び出し元がクイックソートが行うような操作を呼び出していることを確認する具体的なオブジェクトを渡します。 –