The Art of Computer Programming: Fundamental Algorithms

https://gyazo.com/e1265764e3e1aa8b2ba5ea649fc2e3d4

タイトル

The Art of Computer Programming

Vol.1 Fundamental Algorithms

Third Edition

著者

年

1998

リソース

ISBN：978-4-04-869402-5

概要

内容

対象読者

目的

このシリーズは，コンピュータにゆきがかり以上の興味をもつ読者を対象としたつもりだが，さりとてコンピュータの専門家だけを対象としたものでもない．

実際，私の主要目標の 1 つは，コンピュータから豊かな成果を得られるはずだが，専門誌に埋め込まれている必要情報をいちいち集めている閑のない他の分野の人々のために，これらのプログラミングテクニックをもっと触れやすいものにすることだったのである．

前提知識

少なくとも 1 つのコンピュータで，4 個のプログラムを書き，テストしたことがあるという 1 つの要件にまとめられる

謎

章の冒頭の引用を読んではならない．(P. 16)

なんで書いたの？

演習問題

どの読者も，レートが 10 以下の問題はすべて解いてみるようにしてほしい(p.19)

高々数分で解けるらしい

Euclidのアルゴリズム

nが十分大きいとき

$ T_n = \frac{12(\ln2)}{\pi^2} \ln n

導出は難しいらしい

アルゴリズムに数学的な背景があることの説明

集合論の基礎知識がないと読めない

第1章——基礎概念

1.1. アルゴリズム

1.2. 数学的な基礎

1.2.1. 数学的帰納法

1.2.2. 整数，指数，対数

1.2.3. 総和と乗積

1.2.4. 整数関数と初等整数論

1.2.5. 置換と階乗

1.2.9. 母関数

1.2.10. アルゴリズムの解析

1.2.11. 漸近的な表現

1.2.11.2. Eulerの総和公式

1.2.11.3. いくつかの漸近計算

1.3. MIX

1.3.1. MIXの解説

1.3.2. MIXアセンブリ言語

1.3.3. 置換への応用

1.4. 基本的プログラム技法

1.4.1. サブルーティン

1.4.2. コルーティン

1.4.3. 通訳系ルーティン

1.4.3.1. MIXシミュレータ

1.4.3.2. トレースルーティン

1.4.4. 入力と出力

1.4.5. 歴史と参考文献

第2章——情報構造

2.1. はじめに

2.2. 線形リスト

2.2.2. 逐次割り当て

2.2.3. リンクによる割り当て

2.2.4. 循環リスト

2.2.5. 双方向リスト

2.2.6. 配列と直交リスト

2.3.1. 二分木をたどる方法

2.3.2. 二分木による木の表現

2.3.3. 木のその他の表現

2.3.4. 木の基本的な数学的性質

2.3.4.1. 自由木

2.3.4.2. 指向木

2.3.4.3. 「無限グラフの補題」

2.3.4.4. 木の数え上げ

2.3.4.5. 路長

2.3.4.6. 研究史と参考文献

2.3.5. リストとごみ集め

2.4. 複数リンク構造

2.5. 動的メモリ配置

2.6. 歴史と参考文献

演習問題の解答

付録A——数表

1. 基本定数(十進)

2. 基本定数(八進)

3. 調和数, Bernoulli数, Fibonacci数