問題タブ [loop-invariant]

私は自分自身の些細な小さな関数 (便宜上 php) を書きましたが、誰かがその帰納法によって証明を構築するのを手伝ってくれることを望んでいました。

その結果、a[0] が 0 に初期化されたため、各インデックスの値はインデックス自体と同じになります。

目標は、不変式 (それ自体が疑わしいかもしれませんが、うまくいけば要点がわかる) が k+1 に対して成立することを証明することです (または証明する必要があります)。

ありがとう

編集: 例: http://homepages.ius.edu/rwisman/C455/html/notes/Chapter2/LoopInvariantProof.htm

私はデータ構造とアルゴリズムの初歩的なコースを取っています。私たちが使用する本は、CLRS による独創的な作品です。章 2.1: 挿入ソートで説明されているように、ループ不変式を理解するのに苦労しています。

その本は次のように述べています。

行 1 ～ 8 の for ループの各反復の開始時に、部分配列 A[1..j -1] は、元は A[1..j-1] の要素で構成されますが、並べ替えられた順序になっています。

今、これは私を困惑させます。最初の反復が開始されたときにこれが保持されるのはなぜですか? ソートされる配列が { 5, 2, 4, 6, 1, 3 } のように見えるとします。for ループの最初の繰り返しが開始されると、 A[1.. j-1] は並べ替えられた順序ではありませんが、繰り返しが終了すると並べ替えられます。

ここで何が欠けていますか？

これは過去の試験問題からの問題です。

i<=nループ テストで と表示されているのに、なぜループ不変条件が表示されるのですかi<n。

適切な答えは次のとおりです。while ループの失敗条件でi<=nas iwill equals と表示されます。nしたがって、 の 6 回目の繰り返しは、失敗した状態でiは値 6 に等しくなります。nただし、while ループ自体はi<n、i0 から開始しi、5 に等しい 1 回ループを終了すると述べています。

ループ不変式について知りたいです。アルゴリズム（主にソートアルゴリズム）にはループ不変条件があり、ループ不変条件はアルゴリズムの正しさを示していることを知りました。

これはどのように作動しますか？誰かがこれを理解するのを手伝ってくれますか?

ループ不変条件を取得し、次のアルゴリズムでそれを証明するにはどうすればよいですか。

2つのループ不変条件を証明するのに問題があります：

\atが期待どおりに配列に対して機能していないと思います。

ACSL by Example（68ページ、swap_ranges）にも同様の関数があり、これを使用していますが、前述のように、WPプラグインでこの特定の関数を証明することはできませんでした。私は自分のマシンでそれを試しましたが、実際に同じ不変条件を証明することはできません。

完全なコード

編集

Frama-C Oxygenリリースを使用しており、alt-ergo（0.94）およびcvc3（2.4.1）を使用して自動証明を試しました

frama-cからの出力：

cvc3：

alt-ergo：

私は不変式に少し精通しており、小さなループについて多かれ少なかれ見つけることができます。次のJavaの疑似コードの不変式を解くときに、私はとても混乱しています。誰でも助けてください：