問題タブ [proof]

アルゴリズムの正当性を証明するためのルール/スキームが存在するかどうか疑問に思っていますか？たとえば、自然数で定義され、以下で定義されている関数$F$があります。

ここで、$ n \ \ text {div} \ 2 = \ left \ lfloor \ frac {n} {2} \ right \ rfloor $

タスクは、$ F（n、k）= \ begin {cases} 1 \ Leftrightarrow {n \ choice k} \ \ text {mod} \ 2 = 1 \ 0 \text{それ以外の場合は}\end{cases}であることを証明することです。 $

それほど複雑には見えませんが（私は間違っていますか？）、この種の証明をどのように構成する必要があるのか​​わかりません。助けていただければ幸いです。

与えられたのは、黒または白の最大 30 個の石の列です。ゲームの開始時に隙間は許されませんが、30 個未満の石が存在する可能性があります。目標は、すべての石を取り除くことです。黒い石のみを取り除くことができます。石を取り除くと、その隣の石の色が変わります。取り除かれた石が真ん中にあった場合、これ以上埋めることができないギャップが生じます。その石の隣人は、石が取り除かれた後、隣人とは見なされません。

今、このゲームを力ずくで解くプログラムを作成しました。私は、ゲームが解けるのは、(明らかに) 黒い石がまったくなく、黒い石の数が奇数である場合のみであると結論付けました。また、黒石の数が奇数の場合は、列の最初の黒石を再帰的に取り除くことでゲームを解決できます。

私の問題は、黒い石の数が奇数でなければならず、最初の石を取り除くとゲームが解決するというこの条件を証明できないことです。このアルゴリズムを正しく証明するにはどうすればよいですか?

私はすでに誘導を使用しようとしましたが、私は立ち往生しています:

行 (a,b) = a*黒 + b*白

RemoveFirstBlack(Row(1, b)) = RemoveFirstBlack(black + b*white) = 0 (a=1 または n = 0 の場合、a=2n+1 および n は整数)

RemoveFirstBlack(Row(k*a, b)) = RemoveFirstBlack(k*a*black + b*white) = 0、k = 2p + 1、p を整数と仮定します。

RemoveFirstBlack(Row((k+1)*a, b)) = RemoveFirstBlack((k+1)*a*black + b*white) = RemoveFirstBlack((2(p+1)(2n+1))*black + b*白) = RemoveFirstBlack(2(p+1)*a*黒 + b*白) = 0?

あらゆる指針を前もって感謝します！

ウィキペディアの並べ替えアルゴリズムのリストを調べていると、 （最悪の場合）時間計算量と（最悪の場合）空間計算量を持つ安定した比較並べ替えがないことに気付きました。これは確かに理論上の境界のように見えますが、私はそれについてのより多くの情報を見つけることができませんでした。O(n*log(n))O(1)

これをどのように証明しますか？

O(n*log(n))注：比較ソートの最悪の場合の時間計算量の下限について知っています。

質問は：

このルールは有効ですか?

このようなことに取り組むにはどうすればよいでしょうか。私が考えることができるのは、それが偽になる例を見つけようとすることだけです.

P1 && P2 の組み合わせが Q1 と Q2 の両方を偽にするように考えてみましたが、何も考えられません。したがって、これが有効であることに傾いていますが、それを証明する場所がわかりません...このクラスのテキストは絶対にゴミであり、正しさのステートメントの組み合わせに関するリソースをオンラインで見つけることができません...

コンピューター ビジョンの研究について、いくつか抽象的な質問をしたいと思います。Web を検索したり論文を読んだりしても、これらの質問に答えることができませんでした。

1. コンピュータ ビジョン アルゴリズムが正しいかどうかは、どうすればわかりますか?
2. コンピュータ ビジョンのコンテキストで「正しい」をどのように定義するのでしょうか?
3. 正式な証明は、コンピューター ビジョン アルゴリズムの正しさを理解する上で役割を果たしますか?

ちょっとした背景: 私はコンピューター サイエンスの博士号を取得しようとしています。高速な並列アルゴリズムを設計し、これらのアルゴリズムの正確性を証明することを楽しんでいます。また、いくつかのクラス プロジェクトで OpenCV を使用しましたが、コンピューター ビジョンに関する正式なトレーニングはあまり受けていません。

私は、コンピューター ビジョン用のより高速でスケーラブルなアルゴリズム (高速画像セグメンテーションなど) の設計に取り組んでいる潜在的な論文アドバイザーからアプローチを受けました。コンピュータ ビジョンの問題を解決する際の一般的な方法を理解しようとしています。

L をアルファベット {0,1} の文字列で構成される言語とし、1 と 0 を同数含む。

例えば：

L が正規言語ではないことをどのように証明できますか?

誰かがこの質問に答えるのを手伝ってくれるかどうか疑問に思っていました. これは以前の試験用紙からのものであり、今年の試験の準備ができている答えを知っていればできることです。

この質問は非常に単純に思えて、完全に道に迷ってしまいます。正確には何を求めているのでしょうか?

整数変数を含むコードの次のセクションを検討してください。

適切な出力条件を記述し、コード片の正確性を検証することにより、実行後に m が i と j の最小値に等しいことを証明します。

私は投稿条件を次のように持っています: {m = i ∧ i < j ∨ m = j ∧ j < i}

これは正しいです？そして、これをどのように確認しますか？

ビッグオーと漸近解析を学び始めたばかりで、私はこの特定の証拠に固執しています：

2 ^ nがO（n！）であることをどのように証明できますか？ありがとう

stringsここでgperfを使用するという回答を見てきましたが、固定長のドメインに対して作成した証明に基づいて自分でロールしたいと思います<= 200 。wolframからの計算に基づいて、~7.9 x 10^374完全な順列を取得します。したがって、私の考え方は、2048ビットハッシュ関数（3.2 x 10^616）があれば、処理する必要のある文字列のユニバース全体を処理できるはずです。私の質問は、長さが200以下のすべての文字列のユニバースの制約を考慮して、最終的に生成するハッシュ実装が完全であることをどのように証明できるかということです。

以下の補題を証明したい。戦術「破壊」を使用しようとしていますが、それを証明できません。そのような補題をどのように証明できるか教えてください。EmptyString については証明できますが、変数 s1 と s2 については証明できません。ありがとう