問題タブ [proof]

（非公式に）意味的には同等ですが、構文的には異なる2つの言語があります。1つはxmlで、もう1つはスクリプトベースです。両方の言語が実際に同等であることを正式に証明するにはどうすればよいですか。スクリプトアプローチは、xmlで書くのが面倒な同じプログラムを書くための便利な方法です。

ありがとうケタン

RWH の読み取りに失敗しました。やめる人ではなく、Haskell: The Craft of Functional Programmingを注文しました。今、146 ページのこれらの機能証明に興味があります。具体的には、 8.5.1 を証明しようとしていsum (reverse xs) = sum xsます。私はいくつかの誘導証明を行うことができますが、行き詰まります..

ハイプ:

ベース：

誘導：

だから今、私はLeft sum ( reverse xs ++ [x] )が に等しいことを証明しようとRight x + sum xsしていますが、それは私が始めたところからそれほど離れていませんsum ( reverse (x:xs) ) = sum (x:xs)。

なぜこれを証明する必要があるのか​​ よくわかりませんが、（defnによる）の記号証明を使用することは完全に合理的reverse x:y:z = z:y:xであり、 + は可換（arth）であるため、reverse 1+2+3 = 3+2+1、

最近、HP研究所のVinay Deolalikarが、P！=NPであることを証明したと主張する論文が浮かんできました。

誰かがこの証明が数学的にあまり傾いていない私たちのためにどのように機能するかを説明できますか？

私がcpythonについて読んだことから、相互に指しているオブジェクトを検出/解放するための参照カウント+何か余分なものがあるようです（間違っている場合は訂正してください）。誰かが何か特別なことを説明できますか？また、これはサイクルリークがないことを保証しますか？そうでない場合は、参照カウントに追加してリークしないようにすることが証明されているアルゴリズムの研究はありますか？これは、非参照カウントトレースgcを頻繁に実行しているだけでしょうか？

*外部関数インターフェイスを使用したモジュールのバグと問題の割引

n = Big-O(1) という関係が間違っていることはわかっています。しかし、Big-O を含む帰納法を使えば証明できます。しかし、Big-O を導入することはできないという誤りがあります。しかし、私の質問は、定数を使用して関係を反証する方法です。

偽の証明はこちらです。定数を使って偽であることの証明をお願いします。定数について混乱しています。証明で使用されている各関係が異なる定数を持っているのか、同じものを持っているのかわかりません。トピックについて啓発してください。

帰納仮説 : 真だとしましょう : n-1 = O(1) n = O(1) であることを証明します

誤って証明された.. Big-O の基本的な定義にある <= と定数に関する誤謬の明確化が必要です。

私は現在アルゴリズムの本を読んでいて、安定結婚問題に出くわしました。そして、気になる質問が思い浮かびましたが、本は答えません。すべてのSMPで、それぞれがもう一方を最も優先する1つのペアを常に持つことは可能ですか？古典的な結婚の例のように。1人の女性と1人の男性がいて、どちらも好みの上位にランク付けされているペアは常にありますか？

次の例を証明したいと思います。

多項式関数が指数関数よりも速く成長することは注目に値します。条件を満たす k0 > 0 を見つけようとします。

よりも

したがって、k0 > 0、正で十分に小さいですが、c の値は関係ありません... OK ですか?

私のアルゴリズム分析コースでは、アルゴリズムから関数 f(n) = n^2 - n + 2 を導き出しました。ここで、f(n) ∈ O(n)を証明または反証する必要があります。明らかにそうではないので、私はそれを数時間反証しようとしてきましたが、それを行う方法がわかりません.

それを反証するには、否定を証明する必要があります。

私は前後に作業しようとしましたが、どこにも行けないようです。また、私の判断に反して、f(n) ∈ O(n) であることを証明しようとしました。

...成功しませんでした。私は何がそんなにひどく間違っているのですか？

長さ n のすべてのシーケンスについて、任意の 0 の文字列の 2 の補数が常に 0 になることを帰納法によって証明することは可能ですか?

値式を使用してこれを実行しようとしています。

値 = -a_n-1 x 2^(n-1) + summation{i=0 to n} (a_i x 2^i)、n = 文字列のビット数

私は帰納法によって次のことを証明しようとしています:

これはアルゴリズム クラスの問題です。私は通常、合計に対して行うことを行うことができると考えていました。つまり、それがいくつかの P(m) で機能すると仮定し、次に P(m+1) の合計をインクリメントし、右側に何を追加するかによって逆方向に作業します。左辺の総和が生成します。

しかし、H + 1 を代入すると総和内の各項が変わるため、この問題は異なります...そのため、その手法は機能しないと思います。

これは宿題なので、完全な解決策は期待できません。しかし、どこで合計を取るべきかよくわからないので、誘導を行う他の方法を探しています。