問題タブ [proof]

いくつかの文字列変数とリスト変数を含む補題を証明したいというシナリオがあります。おそらく、それは「誘導」を必要としますが、誰かが私が以下に与えられた見出語を証明するのを手伝ってくれるでしょうか。残りのコードが必要な場合は、それも提供できます。

要素の bst への挿入関数の正しさを証明しようとして、一見些細な補題を証明しようとして立ち往生しました。これまでの私の試み：

ツリー内のすべてが よりも小さくn、n <= mすべてが よりも小さい場合は明らかですmが、coq に私を信じさせることはできないようです。どうすれば続行できますか?

おそらくハッキングすることが不可能な、架空のハードウェア+ OSアーキテクチャまたは全体的なソフトウェア設計で行われた作業はありますか？言い換えると、「エクスプロイト」の特定の数学的定義内でエクスプロイトがまったく実行できないように、限られたコード実行のみを許可するアーキテクチャです。したがって、このフレームワークの下でエクスプロイトがもたらす可能性のある潜在的な損害は、おそらく制限されます。

一般的に言って、私はいくつかの合理的な基礎となる仮定に基づいて、「ハッキング可能」アーキテクチャと「ハッキング不可能」アーキテクチャの数学的に動機付けられた理論を探しています。

N^2がc2^Nによって制限されていることははっきりとわかりますが、big-Oの正式な定義を使用してそれを証明するにはどうすればよいですか。MIで簡単に証明できます

これが私の試みです。定義上、任意のn> n0に対して、f（n）<= Cg（n）である定数Cが存在します。ここでf（n）= n ^ 2およびg（n）= 2 ^ n

対数を両側に取り、Cを解く必要がありますか？

フィボナッチ数列についてもう1つ質問がありますが、漸化式を解きます。

方程式は..

そしてもう1つ

それから私は一般的な方程式を形成するために迷子になり始めましたiパターンはどういうわけかパスカルの三角形のようなものですか？

乱数とその発生器に関するさまざまな記事を読んでいます。それらから私が導き出す重要な結論は通常 3 つあります。

• 乱数は本当にランダムではない
• 多くの場合、バイアスがあります (モジュロ バイアス)。
• 人間は、「ランダムに行動」しようとするとき、乱数ジェネレーターになることができません

したがって、これらの観察の後者のほとんどを念頭に置いて、どうすれば

1. 私たちが見ている数列が本当にランダムかどうかを教えてください。さらに重要なことは、
2. 上記のシーケンスが本当にランダムであることを証明できる方法はありますか?

私の証明スクリプトは、矛盾する目標を解決するために使用する必要がある、nat = boolまたは のようなばかげた型の等価性を与えてくれます。nat = list unit

通常の数学では、これは些細なことです。与えられたセットbool := { true, false }と nat := { 0, 1, 2, ... }私はそれを知っていますtrue ∈ boolがtrue ∉ nat、したがってbool ≠ nat. Coqでは、それをどのように述べればよいかさえわかりませんtrue :̸ nat。

質問

これらの等式が偽であることを示す方法はありますか? それとも、それは不可能ですか？

(編集: 失敗した試行の長いリストを削除しましたが、履歴で引き続き表示できます。)

1行のソースコードでタスクを実行するプログラムを作成することは、一般的なプログラマーの趣味です。しかし、それは少し些細なことです。1 000 000行のコードを取得し、すべての改行を削除して、出来上がりです。1行！

したがって、物事を面白くするために、ステートメントを数えることができます。Cスタイルの言語の場合、ステートメントをカウントする簡単な方法はセミコロンをカウントすることです。したがって、100万のif-elsesをネストすることは問題ありません。

n個のステートメントを持つプログラムPがあるとします。一連の状態（変数値） s（sはベクトル）を通過し、出力xを生成します。2つの質問をすることができます：

1. n個未満のステートメントを持つプログラムは出力xを生成できますか？
2. n個未満のステートメントを持つプログラムはsのサブセットを通過できますか？

すぐに、いくつかのことが明らかになります。次のプログラムを受講してください。

これを1つのライナーにリファクタリング（または「デファクタリング」と言うべき）できます。

すべてのプログラムを1行にディファクタリングできますか？このプログラムを受講してください：

それはもう少し挑戦的です。

質問は、 n未満のステートメント、有限の数ですべての可能なプログラムを試すことによって徹底的に答えることができます（理論的には、無限に多くの可能な値を持つ定数を持つことができますが、実際の言語には、それらを格納するための無限のメモリまたは収容するための無限のディスクスペースがありませんソースコード）。

でも：

A. n個のステートメントでx（おそらくsを介して）を生成するプログラムPについて、 m個のステートメントでそれを実行できるQが（効率的な方法で）見つからないことを証明することは可能ですか？

B.最小のnを（効率的な方法で）見つけることができますか？

C.最小nは1であることが保証されていますか？

実際の言語の方が面白いでしょうが、あなたはあなたが望むどんな言語でも仮定することができます。あなたの言語が異常な場合は、あなたの言語での「ステートメント」の定義を提供してください。

私は命令型言語を想定しましたが、関数型言語への問題の適応は大歓迎です。

簡単な解決策があります。任意のPに対して、 Pを実行し、 xを記録します。ここで、 xを単純に出力するプログラムQを記述します。入力のあるプログラムの場合、各入力が正しい出力にマップされた状態で、非常に長いif-elseを作成します。

この解決策は不十分ですが、理由は完全にはわかりません。まず、無限の可能性のある入力の場合、それは不可能です（しかし、実際のプログラムは有限であると言って、私はすでにお尻をカバーしているので、実際の入力は有限であると言えます）。第二に、それは技術的にはsのサブセット、つまり空集合のみを通過します。第三に、それは本当に反気候的です。

この小さな巧妙なトリックを定義するのに役立つこともありがたいです。

PS：私の言葉の価値が何であれ、これは宿題ではありません。私は単に問題に興味を持ち、できるだけ明確に表現しようとしました。もちろん、宿題だったら…

面接でわからない質問があります。サイズ N の配列が与えられた場合、サブセット内の要素が互いに最も離れているようなサイズ k のサブセットを見つけます。つまり、要素間のペアごとの最小距離を最大化します。

ブルートフォースの方法では、実行時に指数関数的であるサイズ k のすべてのサブセットを見つける必要があります。

私が持っていた 1 つのアイデアは、配列から等間隔に値を取得することでした。これが意味することは

1. 最初と最後の要素を取る
2. それらの差（この場合は10-1）を見つけ、それをkで割ります（（10-1）/ 3 = 3）
3. 両端から 2 つのポインターを内側に移動し、前の選択から +/- 3 の要素を選択します。この場合、1 と 10 から始めて、4 と 7 に最も近い要素を見つけます。それは 6 になります。

これは、エレメントをできるだけ均等に配置する必要があるという直感に基づいています。それが機能する/機能しないことを証明する方法がわかりません。誰かが方法を知っているか、より良いアルゴリズムを持っている場合は、共有してください。ありがとう！

前の問題で、私は十分条件（例えば、、そして十分に大きいn）をf(n) = O(g(n))意味することを（うまくいけば正しく）示しました。lg(f(n)) = O(lg(g(n)))lg(g(n)) >= 1, f(n) >= 1

今、私はそれをf(n) = O(g(n))意味することを証明または反証する必要があり2^(f(n)) = O(2^g(n)))ます。直感的には、これは理にかなっているので、前の定理の助けを借りてそれを証明できると思いました。それは次のように書き直すことf(n)ができることに気づきました。それは私を興奮させました...これは私が証明したいことの両側の対数基数2を取り、それは物事を非常に単純化します！lg(2^f(n))g(n)lg(2^g(n))

しかし、これはうまくいかないと確信しています。必ずしもlg(2^f(n)) = O(lg(2^g(n)))それを意味するわけではない2^f(n) = O(2^g(n))からです...それは前の定理（「もしも」ではなく「含意」と言った）から逆になっています。

この証明を別の方法で試す必要がありますか、それとも実際に（少なくともスターターとして）持っているものから離れることができますか？

g(n)**他の方法について言えば、2を「上」に上げると、f(n)それでもそれを高く保つことができるかどうかについて議論することができますか？常識的な議論のように感じますが、何か重要なことが欠けているのかもしれません。

**おっと！私はそれを追加するのを忘れてf(n)おりg(n)、漸近的にポジティブです。私たちの教科書の定義によれば、これはそれらが「十分に大きいすべてのnに対して正である」ことを意味します。

質問：

（5n ^ 2）（ln（n））はn（ln（n）^ 2）のビッグオメガです

私が試したこと：

存在するc>0、n0> 0

（5n ^ 2）（ln（n））> = cn（ln（n）^ 2）for all n> = n0

（5n ^ 2）（ln（n））> = n（ln（n））（n> = 1の場合）> = n（ln（n）^ 2）（n <= 1の場合）

したがって、これは、n = 1 = n0の場合、（5n ^ 2）（ln（n））はn（ln（n）^ 2）のビッグオメガであると結論付けます。ただし、これは（すべてのn> = n0の場合）の要件を満たしていません。

私はここで立ち往生しています、そして誰かが助けることができますか？