ドナルド・クヌース 彼はコンピュータ科学者であり、自分の本の正確さを非常に気にしているので、彼は次のように述べています。 166ドル 見つかった「エラー」に対して ($2,56、0x$1,00)。エラーとは、「技術的、歴史的、活字的、または政治的に正しくない」ものと定義されます。私はどうしてもクヌースから小切手をもらいたかったので、彼の最高傑作の間違いを探すことにしました。 「プログラミングの芸術」 (TAOCP)。なんとか3つ見つけることができました。その言葉通り、クヌートは小切手を送りました。 0x$3,00.
ご覧のとおり、これは実際の小切手ではありません。 Knuth は以前は本物の小切手を送っていたが、2008 年に停止した。 。彼は現在、「個人預金証明書」を次の人に送っている。 （ボス）。彼は、必要に応じて実際のお金を送金するつもりだと言っていますが、それはあまりにも面倒なようです。
タイプミスが 2 つと歴史上の誤りが 1 つ見つかりました。重要度が低い順にリストします。
タイプミス #1
最初のタイプミスは、第 392 巻「並べ替えと検索」の XNUMX ページ、下から XNUMX 行目にあります。「検索が失敗した後、次のレコードを含むテーブルに新しいレコードを入力することが望ましい場合があります。 K;これを行う方法は、検索および挿入アルゴリズムと呼ばれます。間違いはその代わりに いつか 〜でなければならない 時々.
もちろん、そのような間違いは驚くべきことではありません。この記事だけでも、いくつかのタイプミスがあるはずです (タイプミスを見つけても報酬はありません)。本当に驚くべきことは、それが長い間気づかれなかったことです。 392 ページは数学セクションの奥深くに埋もれているのではなく、 一番最初のページ 第6章「探索」！おそらくこの本の中で最も読まれているセクションの 1 つです。理論的には、タイプミスは最も少ないはずですが、そうではありません。
ちなみに、TAOCPを読んでみようと思ったことがあるなら、ぜひ読んでみてください。多くの人はこう言うだろう ディレクトリ、直接読むことを目的としていませんが、これは真実ではありません。著者は明確な視点と独特のスタイルを持っています。読みやすさを妨げる唯一のものは、数学の複雑さです。ただし、簡単な解決策があります。理解できない数学が出てくるまで読み、スキップして、理解できる次のセクションに進みます。こうやって読むと、この本の少なくとも 80% は懐かしいですが、残りの 20% は素晴らしいです。
TAOCPとも言われています。 無関係な、時代遅れであるか、「実際のプログラミング」には適用できません。これも真実ではありません。たとえば、導入後の最初のセクションでは、ソートされていない配列内の要素の検索について説明します。最も単純なアルゴリズムは、すべてのプログラマーによく知られています。配列の先頭からポインターを開始し、ループ内で次の操作を実行します。
- 現在の要素が目的の要素であるかどうかを確認します。そうであれば、それを返します。さもないと
- ポインタが配列境界の外側にあるかどうかを確認します。その場合は、エラーを返します。さもないと
- ズームインして続行します。
ここで考えてみましょう: このアルゴリズムでは平均して何回の境界チェックが必要でしょうか?配列に要素が含まれていない最悪の場合、リスト内の各要素は 1 回のチェックを必要とし、平均すると次のようになります。 
。より賢い検索アルゴリズムであれば、境界チェックを 1 回だけ行うだけで済む可能性があります。目的の要素を配列の末尾にアタッチし、配列の先頭からポインタを開始して、ループ内で次の操作を実行します。
- 現在の要素が目的の要素であるかどうかを確認します。その場合、ポインタが配列内にある場合は応答を返し、配列内にない場合はエラーを返します。さもないと
- ズームインして続行します。
いずれにせよ、要素が見つかることが保証されており、この場合、境界チェックは 1 回だけ実行されます。これは奥深いアイデアですが、初心者のプログラマーにとっても十分に簡単です。私はおそらく、その作業の関連性について他の人に話すことはできませんが、この知恵を個人的なコードと職業的なコードの両方にすぐに適用することができました。 TAOCP の本には、そのような珠玉の本がたくさんあります (公平を期すために、そこには、次のような奇妙な内容もたくさんあります) ).
「探せ、探せ
さよなら
検索、検索
ただ踊りたかっただけです」
— ルーサー・ヴァンドロス、「ザ・サーチ」（1980）
タイプミス #2
4 番目のタイプミスは、第 1A 巻、組み合わせアルゴリズム、パート 60 にあります。882 ページには、さまざまなカジノでコメディアンのパフォーマンスを行うスケジュールを設定する際の問題が説明されています。リリー・トムリン、ウィアード・アル・ヤンコビッチ、そして本が出版された時点ではまだ存命だったロビン・ウィリアムズなど、実在のコメディアンが例として挙げられている。クヌースは常にフルネームを索引に記載しているため、ウィリアムズは XNUMX ページに「ウィリアムズ、ロビン・マクロリム」として記載されています。しかし、彼のミドルネームは「m」ではなく「n」で終わります、つまりマクローリンです。
マクローリンは母親の旧姓でした。彼女は第 34 代ミシシッピ州知事アンセルム・ジョセフ・マクローリンの曾孫娘でした。彼の治世は明らかに何も良いことでは記憶されていなかった。本から :
「マクローリン政権における最も重要な出来事は、1898 年春の米国のスペインに対する宣戦布告でした。残念なことに、戦争は一部の政府高官に贈収賄の機会を与えたかもしれません。マクローリンは、縁故主義や恩赦権限の過度の使用など、さまざまな問題のある行為で告発された。禁酒運動中、批評家らは知事を大酒飲みだと非難したが、知事はそれを公に認めた。」
歴史的間違い
検討する 従来の乗算アルゴリズム 学校のカリキュラムから。 1桁の乗算は何回必要ですか?掛け算するとします 
-桁の数字 
на 
-少し 
。まず最初の桁を掛けます 
各桁ごとに 
一つずつ。次に2桁目を掛けます 
各桁ごとに 
すべての番号を確認するまで、1 つずつ続けます 
。したがって、従来の乗算には次のことが必要です。 
原始的な乗算。特に、2 つの数値を乗算する場合、 
ランクが必要です 
一桁の乗算。
これは悪いことですが、ソビエトの数学者アナトリー・アレクセーヴィチ・カラツバによって開発された方法を使用してプロセスを最適化することは可能です。そのふりをしてみましょう 
и 
- 2 桁の 10 進数。つまり数字がある 
, 
, 
, 
そのような 
и 
(このアルゴリズムをより大きな数に一般化するには、ある程度の操作が必要です。それほど難しいことではありませんが、細部で間違いを犯さないように、単純な例に固執することをお勧めします)。それから 
, 
, 
。二項式を乗算すると、 
。現時点ではまだ残っています 
1桁の乗算: 
, 
, 
, 
。では足し算と引き算をしてみましょう 
。読者のための演習として残しておきますが、いくつかの再構成の後、次のようになります。 
- 1 桁の掛け算は 3 つだけです。 (一定の係数がいくつかありますが、それらは桁を加算およびシフトすることによってのみ計算できます)。
証拠は求めないでくださいが、 カラツバアルゴリズム (上記の例から再帰的に一般化された) は、従来の乗算方法を改善します。 
前の操作 
。これはアルゴリズムの実際の改善であり、暗算の最適化ではないことに注意してください。実際、このアルゴリズムは再帰的な操作に多大なオーバーヘッド コストが必要となるため、暗算には適していません。さらに、数値が十分に大きくなるまで効果は完全には現れません (幸いなことに、Karatsuba のアルゴリズムはさらに高速な方法に置き換えられました。2019 年 XNUMX 月には、 掛け算;加速は想像を絶するほど大きな数値にのみ適用されます)。
このアルゴリズムは、第 295 巻「半数値アルゴリズム」の XNUMX ページで説明されています。そこでクヌースは次のように書いている。 1962 年』にカラツバのアルゴリズムを解説した記事が掲載されました。しかし！ 1995 年にカラツバは「計算の複雑さ」という論文を発表しましたが、その中でいくつかのことが述べられています: 1) 1956 年頃、コルモゴロフは、乗算は XNUMX 秒未満では実行できないと示唆しました。 
ステップ。 2) で 1960 年、カラツバはコルモゴロフが仮説 n² を発表したセミナーに出席した。 3) カラツバ氏は「ちょうど 4 週間で」「分割統治」アルゴリズムを開発しました。 1962) XNUMX 年にコルモゴロフは論文を書き、発表しました。 カラツバを代表して アルゴリズムの説明付き。 「この記事のことを知ったのは、再掲載された後でした。」
したがって、エラーは代わりに 1962 指定する必要があります 1960 年。それだけです。
の分析
間違いを見つけるのに特別なスキルは必要ありませんでした。
- 最初のエラーは可能な限り些細なもので、比較的目立つ場所 (章の冒頭) にありました。馬鹿なら誰でも見つけただろう。私があのバカだと判明しただけだ。
- 66 番目のタイプミスを見つけるには、スキルではなく、運と勤勉さが必要でした。 「ウィリアムズ」の索引は巻の最後から XNUMX 番目のページ、つまり本のかなり目立つ部分にあります。私はただ索引をめくっていました（クヌースの索引にはイースターエッグが隠されているので、思っているほど情けないことではありません。たとえば、アラビア語とヘブライ語の項目があり、両方とも XNUMX ページを指しています。しかし、そのページには言及されていません）どちらの言語も指しますが、代わりに「右から左に読む言語」を指します。そして、二つ目の名前が私の注意を引きました。私は普段ウィキペディアを読んでいるので、ロビン・ウィリアムズをチェックして、矛盾に気づきました。
- 歴史的な間違いを見つけるために真剣に調査したと言いたいところですが、実際にはただ調べただけです 。一番最初の行には次のように書かれています。「Karatsuba アルゴリズムは高速な乗算アルゴリズムです。 1960 年にアナトリー カラツバによって発見され、1962 年に出版されました。」あとはXNUMXつ、XNUMXつ足すだけだ。
将来的には、特に Knuth のコードで、より重大なバグを見つけたいと考えています。また、『基本アルゴリズム』の上巻のバグを見つけたいと思っています。たぶん見つけたかもしれないが、どういうわけか地元の図書館には2、3、4A巻しかありません。
財務上の事実:
- 合計すると、私の TAOCP への貢献は 3 文字だけで構成されています。 s、 交換 m на n и 2 на 0。 2,56 ドルで、これらはかなり儲かるシンボルです。もしそのような金額を支払われたとしたら、1000 ワード (平均 XNUMX 文字) の記事で XNUMX グラントを稼げることになります。
- 29 進数 69 ドルを持っている私は、他の 1 人の国民とともに、サンセリフ銀行の最も裕福な預金者リストで 2019 位タイに入っています (XNUMX 年 XNUMX 月 XNUMX 日現在)。
Knuth からの小切手に関するその他のディスカッション
クヌースの本の間違いを見つけるための一般的な推奨事項。ほとんどの場合、技術的なエラーに関するものですが、私にはそのようなエラーはありません。そこで私が真剣に受け止めた提案が 1 つあります。
送信するエラーのセットを収集するまで待つことをお勧めします。実際にはあるがあまり価値のないエラーをいくつか組み合わせると、そのうちの 1 つが実際には間違いまたはアドバイスとみなされる可能性が高くなります。一度に 1 つずつエラーを送信すると、それぞれが個別に拒否される可能性があります。
私は意味のないタイプミスだけを送りたくはなかったが、アドバイスに従い、十分に重大と思われる歴史的間違いを見つけた場合にのみ手紙を送った。
Ashutosh Mehra はサンセリフで 0 番目に裕福な投資家で、BoSS で 207x$0.fXNUMX という途方もない資産を持っています。
- その他：
出所： habr.com
