問題タブ [induction]

クラシックなチェッカーボード カバー パズルについて聞いたことがあるかもしれません。L字型のタイルを使用して、コーナーの正方形が1つ欠けているチェッカーボードをどのようにカバーしますか?

「Python 言語で基本的なアルゴリズムをマスターする Python アルゴリズム」という本で説明されているように、これには再帰的なアプローチがあります。

アイデアは、ボードを 4 つの小さな正方形に分割し、L 字型のタイルを大きなボードの中央に配置して、1 つのタイルが欠けている 4 つの小さな正方形を効果的に作成し、再帰を介して続行することです。

概念的には理解しやすいのですが、実装を考えるのは非常に難しいと思います。実装ソリューションの 1 つを次に示します。

コードを実行するには、次を取得します

この実装を理解するのに時間がかかりました。特にオフセットラインの背後にある考えを完全に理解しているかどうかさえわかりません。誰かが実装を簡潔に説明しようとすることができますか? この種の問題の解決策を考えるための直感をどのように発達させるのでしょうか? 特に彼らが行ったようにオフセットラインを設定することで、解決策が非常に巧妙であることがわかりました。誰かがこれを理解するのを手伝ってくれて、おそらくより良くなる方法についての提案をしてくれたら、私はそれを大いに感謝します.

ありがとう！

アルゴリズム入門、第 3 版という本を読んでいます。演習では、帰納的推論を使用して証明するように求められます

ここで、lg は底が 2 の対数です。本は解決策を提供します。

仮定ステップで値 n/2 が使用される理由を誰か説明できますか? 帰納法についての私の理解では、値を使用してから、2 のすべての可能なべき乗をカバーするため2^nに、後でそれをインクリメントしていた2^(n+1)でしょう。なぜ間違っているのか知りたいのです。さらに、誰かが変化する操作を説明できますか?2(n/2)lg(n/2)+n into n(lg n-1) + n?それは私が知っている数学的慣習に準拠していません。

注：これは宿題に関連しています。

私はそれを示そうとしていT(n/3) + T(2n/3) + n >= cn , for all c > 0ます。

私がこれを試みたとき、基本ケースは失敗しました(T(1) = 1 >= cn, for all c > 0、そうではありません）。したがって、これを回避するために、問題の下限が よりも高いことを示すことを考えましたO(n)。これは正しい証拠となりますか？

誰かがこのscalaコードを帰納的に推論する方法を教えてくれますか?

1以降の自然数のリストを生成しますか?

高さ N-1 の N ノードの二分木の形状はいくつありますか? また、帰納法による証明はどのように行いますか?

したがって、ノード n を持つ高さ n-1 のバイナリ ツリーは、すべてのノードが 1 つの子のみを持つことを意味し、一種のチェーンのような構造ですか? したがって、二分木の数は、n である n 個の数の異なる順列になります。私は正しい方向に考えていますか？

型の誘導原理は、命題に関する定理にすぎないと読みましたP。そこでList、正しい (または逆の) リスト コンストラクター に基づいて の誘導原理を構築しました。

誘導原理自体は次のとおりです。

しかし今、私は定理を使うのに苦労しています。induction戦術と同じことを達成するためにそれを呼び出す方法はわかりません。

たとえば、私は試しました：

しかし、最後の行で、私は得ました：

のようなカスタム誘導原理を定義して適用するための正しい手順は何list_ind_rconsですか?

ありがとう

次の問題に興味があり、調査したいと考えています。私が抱えている問題の 1 つは、背景情報を検索するためにどの用語を検索すればよいかさえわからないことです。文法誘導や同様の手法を調べてみましたが、この問題に対処していないようです。

いくつかの小さなドメインで一連の論理ルールを観察するとします。それらから一般的なルールを推測したいと思います。これにより、より小さなドメインと一貫性のある、より大きなドメインに対して同様のルールを生成できるようになります。

例 1

したがって、3 つのインスタンスを観察し、何らかのアルゴリズムを使用して一般的なルールを自動的に推測できるようにしたいと考えています。

別の例として：

この 2 番目の例は、ライン フィッティングによって簡単に解決できることを知っています。

私が望むのは、両方のタイプの問題に適用できる方法です。適用できる一次論理または算術演算の機械学習のようなものはありますか? これを達成するためにパターン学習とパターン生成を使用する方法はありますか? 私はどんなアイデアにもオープンです。

わずかに異なるが十分な解決策は、一般的な規則を生成する代わりに、値 n を入力として与えられ、規則 n に対応する規則を生成するアルゴリズム、文法、または関数を生成することです。

私は帰納法を研究していますが、リスト内の連続した重複を削除する「デスタッター」関数の帰納証明を完了する方法を理解するのにいくつかの問題があります。

そして、これは仮定です：

これは私がこれまでに行ったことです：

基本ケースの証明 (空のリスト)

一般的なケースを証明する:

ここで私はいくつかの問題を抱えています: 仮定を使用して到達する方法がわかりません:

私はさまざまな方法を試しましたが、誰も正しい方法ではないようです。私が行った手順は適切ですか? 私の推論方法は正しいですか？

私は、ほとんど自明に見えるこれらの証明に問題があります。

たとえば、帰納的なケースで、タイトルのプロパティを想定して表示したい場合:

ここからどこへ行けばいいですか？それは明らかに真実ですが、ある種の補題を証明せずにどのような手順を踏むことができるかわかりません。たとえば、私は言うことができます

しかし今、私は次の線に沿って何かを証明しなければなりません

補題を証明する必要があるとき、特にほとんど自明に見える証明では、理解に苦しんでいます。