ドナルドクヌースのプログラミングの最初のステップ：女の子とではなく、コンピューターで夏を過ごした方法（19,20,21,22 / 97）

「一番下の行は、このIBM Model 650の取扱説明書はかなり馬鹿だったということです。 プログラミングに追い込まれました。」



コンピューターにどのように興味がありますか？ 私はキーソフ工科大学で勉強する奨学金を持っていましたが、それは訓練の全費用をカバーしていませんでしたが、一部だけなので、アルバイトをしなければなりませんでした。 私の両親にはお金がなく、私は統計局の仕事に行きました。 私の責務の1つは、パンチカードをソートするためのIBM機械であるソーティングマシンを管理することでした。 パンチカードを取り出してマシンに配置し、別のポケットに送り、特定の順序でパンチカードを取得し、結果を確認してチャートを描画する必要がありました。 それで、私は統計学部の図を描きました。

翻訳：ジュリア・ハイトワ
この出版物は、支部の仕事を調整するために 、オークと悪魔 、 CRMシステムを使用した ジオロケーションゲームを開発するエジソンによってサポートされています 。

グラフへの興味とコンピューターの最初の経験

思考が逃れる前に、グラフについて何か追加すべきことがあると思います。 高校では、私は夏の間ずっと過ごしました...私は数学のグラフに情熱を傾けていました、引数xと関数yがあり、軸よりもy単位セグメント高いグラフを描画する必要があり、実際に関数のグラフを取得します。 その瞬間から私はビジュアルが好きです。

私は最終的に取得したい画像から始めて、それを可能にするグラフを持つ方程式をピックアップできるという考えに非常に熱心でした。 だから、夏を過ごしてグラフを整理しました。 一度に何百ものグラフを描きました。 方程式として、例えば、x ^ 3 + 5xの平方根から他の数を引いたものを取り、それをプロットします。

私の父には、根を計算できる小さな計算機がありました。 彼女も結果を印刷しました。 父は会計士だったので、機械は結果を印刷しさえしました。 乗算などの算術演算に使用しました。 次に、x ^ 3 + 5xをx ^ 3 + 4xに変更し、異なるグラフがどのように見えるかを覚えて新しいグラフを描きました。

私は学校で数学的分析を持っていませんでしたが、これを認識していませんでしたが、方程式グラフをプロットすることができました。 これは私を魅了しました。 私はこれに一生懸命取り組み、オレンジ色のグラフ用紙にグラフを作成し、頭を痛めました。 この時期に眼鏡をかけ始めたのは、スケジュールのせいだと思います。 しかし、私は少なくとも建設の経験があり、高校の時でもこの数学のセクションが好きでした。

それから、Keysov Institute of Technologyで私の最初のアルバイトを得ました。そこでは統計学者のためにグラフを描く必要がありました。 それは素晴らしく、仕分け機からそれほど遠くない新しいコンピューター、または「人工知能」と呼ばれたIBM Model 650でした。

これは最初の大量生産されたコンピューターモデルであり、1000台以上が生産されましたが、それ以前は、30を超えるコピーがあるコンピューターはバッチで生産されていませんでした。 そして、このコンピューターが持ち込まれたとき、研究所での最初の1年の真ん中にあり、私が働いていたオフィスの下の階の部屋に設置されていました。 オフィスの窓からコンピューターを見ることさえできました。

ある日、従業員が私がコンピューターを見ているのに気づき、私を招待しました。 彼はこのデバイスがどのように機能するか説明してくれました。 父が見せてくれたコンピューターとは異なり、このコンピューターは非常に多くのことができるので、私は感銘を受けたので、取扱説明書に精通することにしました。

彼はすぐに、コンピューター用に設計されたパンチカードに穴を開けることを許可しました。 ソーティングマシンの制御方法は知っていましたが、その瞬間、コンピュータープログラムでパンチカードを作成していました。 そして、私はこのデバイスの中に何があるかを知り始めました。

プログラミングに興味を持ったきっかけ

IBMの取扱説明書を読みましたが、プログラムの例が含まれており、プログラムの作成プロセスを改善する方法について考えました。 「そうですね、これらのプログラムは動作しますが、何かを変更すると、さらに良くなるでしょう。」 プログラミングの才能があるのではないかという自信を与えてくれました。

マニュアルに失敗した例が含まれていなかった場合、私は自分自身にそれほど自信がなく、恐ろしく、ただ振っただけだったので、おそらくプログラムを書くことに興味さえありませんでした： "ああ、私はそのようなことを考えたことがなかった「。 しかし、一番下の行は、この取扱説明書はかなり愚かだったということです。 私は、これで成功することができたので、プログラミングに追い込まれました。

それで、私は研究所での研究の最初の年の間にコンピューターに興味を持ち始めました。 そして、私が友愛会に参加したとき、参加者の1人は、彼が緊急に解決しなければならない課題に問題を抱えていました。次数5の方程式の根を見つけてください。 私はすでに「Bell Interpretive System」と呼ばれるプログラムについて知っていました。 彼は、自分でそれをやりたくなかったのです。

それで、私は彼のために彼の仕事の一つをする「兄弟」のためのプログラムを書きました。 そして、プログラムは機能しました。 信じるのは大変でしたが、そうでした。 それで彼はとても幸せでした。 さらに、夜間にこのIBMマシンを使用できるようになったとき、Computer Centerの人々ともっと話し始めました。

そして、1年目から2年目の間のどこかで、コンピューターセンターでパートタイムで働いていました。 彼らは実際、他の人、他の学生が使用するソフトウェアを書くことを許可しました。

私が書いた最初のコンピュータープログラムは次のとおりでした：数の素因数分解。 コンソールを介して番号を入力します。つまり、100などの番号に移動できるロータリースイッチを入力すると、次のデータが出力されました。100= 2 * 2 * 5 * 5。 そのため、コンソールから入力された数値の素因数を計算することができました。

私はまだこのプログラムのコピーを持っています。 最初は、プログラムの約60または70のチームから始まり、2週間後にようやく正常に機能し、130になりました。この間に約200のエラーを修正したと思います。

つまり、プログラミングだけでなく、エラー修正も学びました。 あなたがちょうど何がうまくいかないのか...まあ、私はプログラミングについてあまり知りませんでしたが、私はこの練習から多くのことを学び、数の素因数を計算するプログラムを書きました。

IBM 650でのプログラミング方法の学習

また、いくつかのことも理解しました。たとえば、バイナリシステムではなく10進数で動作する10進数のコンピューターがありました。 そして、最終的には、10桁の数字さえ取得できました。 私はそのようなコンピューターの使い方を学ぶことができましたが、非常に遅いものでした。

分割のプロセスには約4ミリ秒かかりましたが、コンピューターは数百万倍高速に動作しています。 今日の標準では、非常に遅いコンピューターであり、同時に複数の部門プロセスを生成することさえできませんでした。

そして、要因を見つけることは次の通りでした：最初に、この数を2つに分けることは適切ではありません。 三？ いや 4時？ いや そして、うまくいくまで続けます。 これで、最大の10桁の素数を簡単に選択できるようになりましたが、時間がかかりましたので、プログラムを少なくともわずかに高速化する必要がありました。

最初に2、3、4、5で除算するべきではありませんでしたが、元の数値が2と4で割り切れない場合、すべての偶数をスキップすることができました。そして、プロセスを高速化するためにこのようなことをしなければなりませんでした。 最初は、すべての可能な数値で除算する必要がないことを理解していませんでした。数値に係数がある場合、最小の係数はこの数値の平方根よりも小さいか、ほぼ同じ値になるためです。 これが、プログラムのアルゴリズムをわずかに変更する必要があることを認識した方法です。

プログラムで最も暗黙的なエラーの1つは、修正に多くの時間を要しましたが、突然その数に多くの素因があることですか？ 判明したように、パンチカードの9つの要因のみを突破することができました。数値は30を超える要因があるため、プログラムをやり直す必要がありました。 そして、答えが1つのマップではなく、4つのマップに反映されるように変更しました。

それでも、それは...この乗数プログラムが当時私にとって非常に有用だった理由を説明したいだけです。 そして結局、私は最初の年の終わりにそれを書きました。私はこの装置に座って、レバーを切り替え、ボタンを押すことを許されました。 教師は、私たちが自分でコンピューターを使用し、夜間に仕事をし、教室で寝入り、他の生徒が使用するプログラムを書くことを許可しました。

スタンフォード大学では、すべてが異なっていました。 スタンフォードでは、後でわかったように、マシンに直接渡すために作業を引き継がなければならなかったIBMの従業員がいたため、翌日だけ結果を得ることができました。

Keysov Instituteでは、自分ですべてを行うことが許可されていました。彼らは何かを壊すことさえ心配しませんでしたが、紙やカードが詰まったらパネルを開きました。 そして、私たちは新入生でした！ 当時、ケースとダートマスは、学生に対して非常に寛大で、自分で技術を使用することを許可された唯一の大学だったと思います。

三目並べプログラムの作成

夏には、コンピューターセンターで働いていたので、ミルウォーキーの家にいなかったのは、数日だけでした。 そして、それは私がすでに話したそれらの2年目の女の子に会う前でした。 それで、私は夏の間ずっとコンピューターで過ごしました。 2番目のプログラムは10進数から他の数値システムへの変換でしたが、かなり高速でした。 私がもっと時間を費やした3番目のプログラムは、ゲーム「三目並べ」でした。

後に、多くの科学者がこのゲームに取り組んでいることを知りました。 1800年代にTic Tac Toeをプレイする最初のマシンを発明した英国の数学者、Charles Babbage。 ダニー・ヒリスは、ティンカートイズの子供デザイナーから三目並べのスロットマシンを製作しました。これは現在ボストン科学博物館に展示されています。 それにもかかわらず、私はこのゲームのためにコンピュータープログラムを書くことにしました。 かなり問題がありました。

私はTinkertoysを使用しませんでしたが、IBM 650には別の興味深い機能がありました。10桁の数字を使用する10進数システムだけでなく、2000だけしか機能しませんでした。 彼の一般的な記憶は、どれくらいですか？ 5バイト？ したがって、わずか10 KBのメモリです。 そして今、10 GB、または少なくとも10 MBがなければ、これで終わりです。 数百MBを持っていない場合は、Microsoft Windowsをダウンロードすることもできません。共有メモリは10 KBしかありません。

そして、マシンが私に対して三目並べを再生できるようにしたかったのです。 そして、私は3つの難易度を書きました。 最初のレベルは、私が確信していた戦略を持つ「専門家」です。

二番目は何でしたか？ 覚えていませんが、3番目が最も面白かったです。 これは「学習版」でした。マシンは何も知らずにゲームを開始し、彼女はゲーム中にフィールド上のすべての可能な位置を覚えて学習しました。

これを10 KBに収めることはほとんど不可能でした。 ゲーム中に負けるたびに、彼女は次のようなことを言いました：「私はミスをし、相手の動きは良かった」、そして勝ったとき：「私の動きは良かったが、相手の動きは良かった」。 彼女は調整できました。

難易度の各レベルは特定の数に対応し、ゲームは4から始まり、勝った場合は次のゲームは5になり、負けた場合は3になります。異なる戦略を使い始めた場合、彼女は最も適切と思われる動きを選択しました。

このプログラムを書くのに1か月かかりました...この間に多くのことを学び、その後、「エキスパート」バージョンを使用してゲームの「トレーニングバージョン」を教えようとしました。 「エキスパート」は「トレーニングバージョン」で何回プレイしましたか？ 私は120について考え、それから「訓練版」は「専門家」に負けなくなった。

三目並べはかなり退屈なゲームです。なぜなら、あなたはそのプレイ方法を知っていて、各ゲームは引き分けに終わったからです：誰も勝ちません-誰も負けません。 しかし、あなたが間違っているとき-それは運び去る。 そして、私は2つの「学習バージョン」を作成し、それらが互いに遊ぶことを決定しました。最初はゲームについて何も知らず、最初の動きは盲目的にランダムに行われました。

もちろん、彼らは間違いを犯しますが、最終的には、そのうちの1人が勝ち、一部は敗北し、彼らの戦略は少し変わります。 そして、私が知ったように、ゲームがプレイされた後、彼らはかなり保守的にプレイし始め、ゲームは退屈になりました。 慎重で危険な動きをする代わりに、彼らは非常に慎重にプレーしました。 それにもかかわらず、このプログラムを書くことはやりがいのある経験になりました。

続きを読む

• ドナルドクヌース：私はバックデスクに座って冗談を言ったが、先生たちは我慢しなかった。
  
• ドナルド・クヌース：「若者への私のアドバイス」（93/97）および「自分を主張する必要性を感じている」（9/97）
  
• 「超現実的な数字」：私は6日間働き、7日目に休みました（40,41,42 / 97）
  
• ドナルド・クヌース：プログラミングの芸術はどのように作られたのか（33.38.39 / 97）
  
• Donald Knuth：第4巻がついにリリースされるのはいつですか
• Donald Knuth：女の子とではなく、コンピューターで夏を過ごした方法（19,20,21,22 / 97）