問題タブ [invariants]

このトピックをグーグルで検索しましたが、ウィキペディア以外に役立つドキュメントや記事は見つかりませんでした。

誰かが私にそれが何を意味するのかを簡単な言葉で説明したり、素敵で理解しやすいドキュメントを紹介してくれませんか?

私はいくつかのホーア論理に取り組んでいますが、私のアプローチが正しいかどうか疑問に思っています。

私は次のプログラムPを持っています：

これは、hoare triple {n> = 0} P {s = n *（n + 1）/ 2}を満たす必要があります（したがって、合計が必要です）。さて、最初は| s = i *（i-1）/2|でした 私の不変条件として、これはうまく機能します。しかし、ループの最後から希望の事後条件に至るまで、問題が発生しました。含意のために

保持するには、iがn + 1であり、nより大きいiだけではないことを証明する必要があります。だから私が考えたのは、不変量に（i <= n + 1）を追加して、次のようにすることです。

そうすれば、プログラムを証明できるので、正しいはずだと思います。

それにもかかわらず、私は不変条件が少し、「不変条件」ではないことを発見しました:)。そして、これまでのコースや演習で見たものとは違うので、ここにもっとエレガントな解決策があるのだろうかと思いました。

トリプルパワーの合計の不変量が何であるかは100％わかりません。

注：nは常に非負の値です。

擬似コード：

私はその厄介なことを知っており、はるかに簡単な方法で行うことができますが、これは私が期待していることです（主にアルゴリズム分析の練習のために）。

私は3つのループ不変条件を考え出すことになっています。LI1、LI2、およびLI3。
LI1の場合、不変量はtot =（i ^ 2（i + 1）^ 2）/ 4（0からiまでの立方体の合計の方程式）
と関係があると思います。ただし、LI2またはLI3に対して行います。LI2でのループはi^3を作成し、LI3はi ^ 2を作成しますが、それらをループ不変条件として定義する方法が完全にはわかりません。

whileループ本体のそれぞれに3つの別々の合計変数がある場合、不変条件を定義するのは簡単でしょうか？

あなたが与えることができるどんな助けにも感謝します。

また、この関数の成長の順序は次のとおりです：Θ（n ^ 3）？

トリプルパワーの合計の不変量が何であるかは100％わかりません。

注：nは常に非負の値です。

擬似コード：

私はその厄介なことを知っており、はるかに簡単な方法で行うことができますが、これは私が期待していることです（主にアルゴリズム分析の練習のために）。

私は3つのループ不変条件を考え出すことになっています。LI1、LI2、およびLI3。
LI1の場合、不変量はtot =（i ^ 2（i + 1）^ 2）/ 4（0からiまでの立方体の合計の方程式）
と関係があると思います。ただし、LI2またはLI3に対して行います。LI2でのループはi^3を作成し、LI3はi ^ 2を作成しますが、それらをループ不変条件として定義する方法が完全にはわかりません。

最初のループのi++の直前にメインの合計に追加されたwhileループ本体のそれぞれに3つの別々の合計変数がある場合、不変条件を定義するのは簡単でしょうか？

あなたが与えることができるどんな助けにも感謝します。

これらは、配列 b[hk] の最小値を見つけるアルゴリズムのアサーションです。

これは、この不変式の正しいループですか?

不変: b[x] は b[h...t] の最小値です

事後条件 b [0...h] <= 9 および b[k+1..] > 9 が true になるように、配列 b の値を交換して k に値を格納しようとしています。

私はこれまでのところこれを持っています：

アルゴリズムを書くとき、私は通常コメントに不変条件を書き留めます。

たとえば、1つの関数が順序付きリストを返し、もう1つの関数がリストが順序付けられることを期待する場合があります。
定理証明が存在することは知っていますが、使用した経験はありません。

また、スマートコンパイラ[sic！]は、それらを利用してプログラムを最適化できると思います。
それで、不変条件を書き留めて、コンパイラーにそれらをチェックさせることは可能ですか？

すべての構築が、不変条件を保持できるモジュール メンバーを通過するように型を定義したいと考えていますが、パターン マッチングのための分解は可能です。

私はちょうどOCamlを学んでいますが、以下は、左が厳密に右よりも小さくなければならないという不変条件を持つintペアに対してほとんど機能します

このように機能する

そして、破壊はファッションの後に機能します

構築中に失敗する

しかし、私が本当にやりたいのは、タプルを分解するという構文上の利便性を実現することです。以下は機能しません。

しかし、タプルパターンを使用してそれを分解することはできません:

タイプをに変更することもできますが、type t = R of (int * int)これらは可能な限り軽量でメモリ的にする必要があります。何か案は？

加速されたc++を読んでいるときに、不変条件がfalseになる理由についての説明に混乱しました（以下のコードを参照）。

不変条件は、作成者（この場合）によって次のように定義されています。

whileの不変条件は、これまでにr行の出力を書き込んだことです。rを定義するときは、初期値0を指定します。この時点では、何も記述していません。rを0に設定すると、明らかに不変条件が真になるため、最初の要件を満たしています。

その後、説明します...

出力の行を書き込むと、rが書き込んだ行の数ではなくなるため、不変条件がfalseになります。

定義を考えると、私は2つの間の接続を形成することはできません。

出力の行が書き込んでいるときに不変条件がfalseになるのはなぜですか？

私はデータ構造とアルゴリズムの初歩的なコースを取っています。私たちが使用する本は、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] は並べ替えられた順序ではありませんが、繰り返しが終了すると並べ替えられます。

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