アルゴリズムイントロダクション1章まとめ

1.1 アルゴリズム

アルゴリズムとは何か？

入力から出力を生成する、計算手続き（入力を出力に変換する計算ステップの系列）。
アルゴリズムは、計算問題を解くための道具と見なせる。
すべての計算問題のインスタンス（具体例）に対して常に停止し、その出力が正しいとき、アルゴリズムは正当である(correctness of an algorithm)という。

アルゴリズムで解くことができる問題

・DNA解析（15章の動的計画法）
・経路探索（24章）、情報検索（11章、32章）
・公開鍵暗号とディジタル署名（31章で扱う数論的アルゴリズムと整数論）
・限られた資源での利益最大化（29章で扱う線形計画法）

本書で扱う具体的な問題

・道路地図上の最短経路の発見（24章）
・2つの記号列の最長共通部分列（15章）
・トポロジカルソート（22章）
・凸包（33章）

データ構造

データ構造(data structure)は、アクセスと更新を容易にする目的のために、データを蓄積し組織化する方法である。どのデータ構造もすべての目的に対して満足に働くことはない。したがって、いくつかのデータ構造についてその長所と限界を理解することが重要である。

アルゴリズムの設計と解析

公表されたアルゴリズムで解決できない問題を解く場合に、自分自身でアルゴリズムを開発し、正当性を証明し、効率を解析する必要がある。本書では、それらの具体的な問題と技法を取り上げる。

計算困難な問題

34章で、NP完全問題について解説する。

並列性

27章（総合版の範囲？）でマルチスレッドアルゴリズムのためのモデルを紹介する。

1.2 科学技術としてのアルゴリズム

計算機の速度もメモリの量も無限ではない。有限の資源を賢く使うために、効率の良いアルゴリズムが役に立つ。

効率

2章で2つのソーティングアルゴリズムを比較する。
挿入ソート：計算時間がn^2に比例する
マージソート：nlgnに比例する
挿入ソートを、何十倍も効率よく実装し、1000倍も速いマシンで実行したとしても、1000万個の値のソートになるとマージソートより10倍以上遅くなる、という例をここでは紹介している。問題のサイズ（ここでは要素数）が大きくなると、差はさらに開く。

アルゴリズムと他の科学技術

上で見たように、システム全体の効率は、アルゴリズムの効率に大きく左右される。つまり、ハードウェアの製造技術のような先端技術と同様に、アルゴリズムは科学技術(technology)である。
ハードウェア設計、GUIの設計、ネットワーク上でのルート選択、コンパイラ、インタプリタ、アセンブラ等、これら全てにアルゴリズムは用いられている。

アルゴリズムに関する知識と技術をしっかりと身につけていることが真の技能をもったプログラマを未熟なプログラマから区別する特徴の1つである。現代の計算技術を用いると、アルゴリズムを知らなくてもいくつかの仕事を達成できる。しかし、アルゴリズムの優れた知識があれば、はるかに多くの仕事が達成できる。