問題タブ [taocp]

TAOCP Volume 1 を読み始めたばかりで、スタイルを理解するのに苦労しています。

Knuth は計算方法を 4 倍 (Q,I, Omega, f) であると述べていますが、これらのそれぞれが何を意図しているのかを理解するのに苦労しています。彼の最初の例は理解できるが、2 番目の例は理解できない

私は第 3 版の 8 ページを見ています。

章の終わり近くに、文字列のセットについて説明するアルゴリズムがあります。

（ギリシャ語の変数を入力しやすいものに置き換えました-申し訳ありません）

A を文字の有限集合とし、A* を A 上のすべての文字列の集合とします。この考え方は、計算の状態をエンコードして、A* の文字列で表すようにすることです。

(p と w は文字列であることに注意してください) と s が A* の文字列である場合、s が文字列 p と w に対して pTw の形式を持っている場合、T が s に出現すると言います。

文字列のセットを作成するという概念は理解できますが、彼がここで言おうとしていることはすべて理解できません。なぜ Q、I、オメガが必要なのですか? f は実際に何を説明していますか (なぜ f に 3 つの関数が必要なのですか?)??

誰かが光を当てるのを助けることができますか?

TAOCP Volume 1 Edition 3 の演習を行っていますが、次の演習の回答で使用されている構文を理解するのに苦労しています。

第 1 章 演習 8

_{T j} ,s _j ,a _j ,b _jを指定して、正の整数 m & n の最大公約数を計算する

入力を文字列 a ^m b ⁿ (m a の後に n b が続く)で表します。

答え：

A = {a,b,c}、N=5 とします。アルゴリズムは文字列 a ^{gcd(m,n) で終了します}

私が理解に苦しむ部分は、この表をどう解釈するかということです。また、Knuth がこれが文字列 a ^{gcd(m,n) で}終了すると言うとき、 なぜ gcd(m,n) の上付き文字なのですか?

助けてくれてありがとう！

より多くの質問で編集：

T _jとは何ですか -- T = シータであることに注意してください

s _jとは何ですか -- s = phi であることに注意してください

_{列 b j}とa _jをどのように解釈しますか?

なぜクヌースは、ソリューションの新しい表記法を、テキストで説明していない例に切り替えたのですか? ただイライラします。ありがとう！！！

5 ページの下部に「 kをk ⊕ (1 ^{j +1} ) ₂に変更する」というフレーズがあります。2進数でも1の何乗でも1じゃないの？これはタイプミスに違いないと思います。これを報告するためにクヌース博士に電子メールを送信しましたが、何ヶ月も返信が来るとは思っていません。その間、私はこれがどうあるべきかを理解しようとしています。

MIXの除算（TAOCP by Knuth）がバイト単位でどのように機能するかを誰かに説明してもらえますか？

メモリ位置1000には。が含まれます|-|0|0|0|2|0|。

操作を実行するとき

レジスタは

rAこれで、との記号がわかりましたが、塗りつぶされrXたバイトはどのような順序で、rAXどの分割が実行されますか？

DIV 1000がすべてのビットを2で割った値になる場合、私は期待します

ここrAには、除算の結果とrX余り（右側から入力）が含まれています。

私はおそらくここで何かが足りないので、Knuthは私がそれを自分で理解できるはずだと思っているようです（したがって、レベル10の質問ですが、私も得られません）が、誰かがここで私を助けてくれますか？

tacop 2.2.2 シーケンシャル アロケーションの作業中に、247 ページのメモリ セクションを再パックしているときに、いくつかの問題に遭遇しました。

主題は、共通領域の場所 L0 < L < LX を共有する n 個のスタックがあることです。最初に、1 <= j <= n に対して BASE[j] = TOP[j] = L0 を設定します。

目標は、スタック i に関して要素を挿入または削除しているときにオーバーフローが発生した場合、メモリを再パックする方法です。(まだいっぱいになっていないテーブルから一部を取り除いて、スタック i のためのスペースを作ります)。

a)。i < k < n かつ TOP[k] < BASE[k+1] となる最小の k を見つけます (そのような k が存在する場合)。1 ノッチ上に移動、設定 CONTENTS(L+1) -> CONTENTS(L)、 for TOP[k] >= L > BASE[i+1] 最後に、設定 BASE[j] -> BASE[j] + 1 、TOP[j] -> TOP[j] + 1、i < j < k の場合

ここに私の質問があります：

まだ埋まっていないスタックをどのように見つけるのでしょうか? スタックk? そして、なぜ最小のkを選んだのですか?

There is a question in TAOCP vol 1, in "Notes on Exercises" section, which goes something like:

"Prove that 13^3 = 2197. Generalize your answer. (This is a horrible kind of problem that the author has tried to avoid)."

Questions:

1. How would you actually go about proving this ? (Direct multiplication is one way, another way could be using formula of (a+b)^3). Does the solution requires using some method that will allow us to make some kind of generalization ?

2. What is the generalization here ?

3. Why is this a horrible kind of problem ?

4. What are some other kind of similar horrible problems that you are aware of ?

Appreciate any answers.

P.S. I apologize if the statement of problem above makes it look like a homework problem, but its not. Request people to not tag this as a homework problem, so that more people can give answers.

私は、Donald E. Knuth のAlgorithm O (Oriented forests)を実装しようとしています: 'The Art of Computer Programming - Volume 4, Facile 4, Generating All Trees' on page 24.

私のPythonソリューションは次のとおりです。

私の実装は私に与えます：

[0, 1, 2, 3], [0, 1, 2, 2], [0, 1, 2, 1], [0, 1, 2, 0], [0, 1, 1, 1], [0, 1, 1, 0],

[0, 1, 0, 3] ,

[0, 1, 0, 0], [0, 0, 0, 0].

私はすでにバグを探しすぎています。誰かが私のコードを修正する正しい方向に向けてくれることを願っています。私のアルゴリズムの理解は正しいですか？私のpythonスタイルの改善も高く評価されています。ご協力いただきありがとうございます。

ドナルド・クヌースが彼の偉大な本でバラバラなセットをカバーしているかどうか知りたいですか? もしそうなら、それはどの章ですか？

よろしくお願いします、

私は、コンピュータ サイエンスやその他の科学/工学のバックグラウンドではなく、英語の学位を取得してソフトウェア開発のキャリアを積むようになりました。私は独学で長い道のりを歩んできましたが、これを10年以上行った後、特に数学でギャップを埋めたいと思っています.

Comp-Sci 教育を受けるのに最適な場所は、The Art of Computer Programming を学習することです。しかし、私はそれほど多くの数学をとったわけではなく、大学での最後の数学のクラスは 1995 年だったので、TAOCP の数学表記を読めるようになるには、ブラッシュアップと補強が必要です。

私の考えでは、 Khan Academyに行き、TAOCP を読むための前提条件として必要なトピックに取り組みました。ただし、Catch 22 では、準備として実際にどのトピックを実行する必要があるかを把握しようとしています。

それで、私が疑問に思っているのは、誰かが基本的に高校数学しか持っていない場合（私はそれよりも少し多く持っていますが、バックグラウンドとして高校だけでこれにアプローチすることは有効な質問だと思います）、数学の「クラス」は、含まれている数学を読んで理解するために準備されたTAOCPを開始するために、カーンアカデミーのような場所から必要ですか?

こんにちは、最初の質問です。「The Art of Computer Programming」を読み始めました。私はそれが難しいことを知っています。まず、本の言語を学ぶことにしました。まず MIX から始めます。いくつかの演習を行いましたが、本のプログラムで管理できると思います。しかし、問題は私が書いたどこにでもあり、MIXは古い、MMIXを学ぶなどです。OKS、しかしなぜ - これは私の質問ですか? 私は 1 か月 MIX を学習していますが、本の問題を理解し始めましたが、作業を停止して新しい ASM の学習を再開しました。なぜですか? MIX は古いですが、本に書かれているコードはすべて MIX です。時間をかけて MMIX を学習すると、問題をもう一度書き直さなければならず、非常に困難になると思います。MIX は古いので、本当に新しいバージョンを学ばなければなりませんか? TAOCP の経験が豊富な人からアドバイスをもらえますか: MIX の例、問題などの本を読み続けるか、MMIX を学ぶのをやめてください。と、