今日読んだ本と感想。
プログラムにとってアルゴリズムは、屋台骨となるデータの処理手順を記述するものです。この世にプログラムがあるかぎり、アルゴリズムの改良が続けられます。本書は、アルゴリズムの基礎知識を厳選し、可能なかぎりやさしくまとめました。読むだけで、かならずアルゴリズムのおもしろさに気づいていただけるでしょう。
目次
- 第1章 アルゴリズムってどんなもの？
- 1-01 アルゴリズムは意外と身近にある
- 1-02 アルゴリズムは人類の知恵の結晶
- 1-03 アルゴリズムを知ることでゲームに強くなる？
- 1-04 アルゴリズムに必要な条件は2つ
- 1-05 特に知っておきたい重要なアルゴリズム
- コラム アルゴリズムの基礎となる構造化プログラミングの考え方
- 第2章 変数と配列
- 2-01 「データ」はさまざまな情報のことである
- 2-02 データには型がある
- 2-03 もっとも単純なデータは「値」である
- 2-04 値を入れておく箱を「変数」と呼ぶ
- 2-05 アルゴリズムの記述には「変数」が不可欠
- 2-06 「代入」とは変数にデータを入れること
- 2-07 「変数」には1つひとつ別々の名前がつく
- 2-08 変数名は、扱うデータの内容がわかるようにつける
- 2-09 変数に値を代入する機能をもつ代入文
- 2-10 変数に格納された値を別の変数に代入する
- 2-11 変数にもデータ型がある
- 2-12 同じデータ型の大量の値を扱う「配列」
- 2-13 配列は「配列名」という名前で識別される
- 2-14 配列の要素は「添え字」で管理される
- 2-15 「配列」はどのようなときに利用するのか
- 2-16 「配列」はロッカーのようなもの
- 2-17 「2次元配列」はホテルの客室のようなものである
- 2-18 2次元配列の各要素は2つの添え字により識別される
- 2-19 文字列は文字の連続（配列）で表す
- 2-20 文字列の長さを扱うための2つの方法
- コラム 慣用的に使用される変数名
- 第3章 データ構造
- 3-01 大量のデータを効率よく扱うために
- 3-02 よく利用されるデータ構造は？
- 3-03 「スタック」は机の上に本を積み上げるようなデータ構造
- 3-04 「キュー」はレジの順番待ちのデータ構造
- 3-05 「リスト」はひもでつながっているデータ構造
- 3-06 次のデータしかたどれないのが単方向リスト
- 3-07 前のデータも次のデータもたどれるのが双方向リスト
- 3-08 N番目のデータをすばやく見つけられるのが「配列」
- 3-09 データの挿入・削除をすばやく行えるのが「リスト」
- 3-10 時計のように回って元に戻るのが「リングバッファ」
- 3-11 木の幹と枝、葉の関係のようにデータを管理する「ツリー」
- 3-12 親1人、子ども2人の構造をしているのが「二分木」
- 3-13 ひと筆描きのようにノードとエッジで構成される構造が「グラフ」
- コラム なぜ、配列の先頭要素の添え字は0だったり1だったりするの？
- 第4章 アルゴリズムの基本を学ぼう
- 4-01 繰り返し処理がアルゴリズムの基礎
- 4-02 1～Nの整数値の合計を求めてみよう
- 4-03 配列を使うと大量のデータを効率よく扱うことができる
- 4-04 1年間の総売上を求めてみよう
- 4-05 クラス全員のテストの合計点と平均値を求めてみよう
- 4-06 最高得点を求めてみよう
- 4-07 最低得点を求めてみよう
- 4-08 テストの点数に順位をつけよう
- 4-09 クラス全員の教科別テストの合計点を求めてみよう
- 4-10 「時分秒」形式の時刻の差を求めてみよう
- 4-11 2つの変数の値を入れ替えるにはひと工夫が必要
- 4-12 2つの数値の最大公約数を求めてみよう
- コラム 2000年問題よりも影響が大きい2038年問題
- 第5章 並べ替えのアルゴリズム
- 5-01 並べ替え（ソート）は複数のデータを順番どおりに並べ替える
- 5-02 ソートアルゴリズムのあれこれ
- 5-03 バケツを使ってデータを並べ替える「バケットソート」
- 5-04 いちばん小さい（大きい）値を探して取りだして並べる「単純選択法」
- 5-05 泡が上がるように隣り合ったデータを交換する「単純交換法」
- 5-06 ソート済みデータ列の正しい位置に挿入する「単純挿入法」
- 5-07 ソート済みの複数のデータ列を合体させるのが「マージ（併合）」
- 5-08 マージの考え方を利用して並べ替えを行うのが「マージソート」
- 5-09 並べ替えの効率を上げる工夫をした「シェルソート」
- 5-10 最高速の並べ替えを行える「クイックソート」
- コラム 2のn乗の値を暗記しよう
- 第6章 探索のアルゴリズム
- 6-01 探索（サーチ）とはデータ列の中から目的のデータを探しだすこと
- 6-02 先頭からしらみつぶしに調べる「線形探索（リニアサーチ）」
- 6-03 高速にデータを探しだせる「二分探索（バイナリサーチ）」
- 6-04 ハッシュテーブルで効率のよい探索を実現する
- 6-05 文字列の中の部分文字列を探す「文字列探索」
- 6-06 効率的な文字列探索を行うKMP法
- 6-07 末尾から先頭へ向かって文字比較を行うBM法
- コラム リレーショナルデータベースの利用によるソートや探索
- 第7章 そのほかのアルゴリズム
- 7-01 ニュートン法で高次方程式の解を求める
- 7-02 ガウスの消去法で連立方程式の解を求める
- 7-03 台形の面積の和で定積分の値を求める台形法
- 7-04 素数を求める「エラトステネスのふるい」
- 7-05 処理の中で自分自身を利用する再帰呼びだし
- コラム アルゴリズムとフローチャート（流れ図）
- 第8章 アルゴリズムとコンピュータ
- 8-01 コンピュータのデータは2進数で表現される
- 8-02 2進数を見やすくする（8進数、16進数表現）
- 8-03 2進数から10進数への変換
- 8-04 10進数から2進数への変換
- 8-05 2進数で負の整数を扱えるようにする
- 8-06 どちらか一方が「1」なら「1」となる論理和
- 8-07 両方が「1」なら「1」となる論理積
- 8-08 「1」と「0」なら「1」となる排他的論理和
- 8-09 否定は「0」を「1」に、「1」を「0」にする
- 8-10 ド・モルガンの法則を使うと否定の論理を整理できる
最初の3章のアルゴリズムに入るまでの準備で、特にプログラム言語を定めて話を進めてないので、型や配列などのデータ構造の話がなんか曖昧に感じる部分が多かった。かと思ったら、具体的な言語で説明されていないにもかかわらず、「一般的な言語ではこうだったりする」という説明があったり、混乱のもとになりそうな箇所が多かった。そして、その後にアルゴリズムの話に入っていっても、具体的なプログラミング言語で説明されてないから、そのアルゴリズムについての具体的なコードも出てこないので、確かに図解でイメージしやすいかもしれないけど、本当にソートされたとか、探索してたのが見つかったとかいう事を実感はできない。(情報処理のかなめとなる考え方とあるからあえてコードが無いのかもしれないけど。)
なので、本当にコードを読むのが苦手で、それでもアルゴリズムを知らなければならないという事情等が無い限りは、アルゴリズムについて入門するなら実際にコードが載っていて、そして自分自身のコンピューターで実行できるような、本書以外の入門書(アルゴリズムの本じゃないけど初めてのコンピュータサイエンスが楽しかった)を選択した方がいいと思う。
既に何かプログラミング言語を知っていたり、上記の初めてのコンピュータサイエンスを読み終えて、アルゴリズム、ソートや探索を知っているなら、本書の様々なアルゴリズムの説明を読みながら、そのアルゴリズムのコードを自分自身で書いて実行していけば、本書の図解でイメージしながら自分の書いたコードを実行して実感できて、役立つ1冊になると思う。
ということで、初めてのコンピュータサイエンスである程度アルゴリズムについては入門は出来ていると思うので、本書のアルゴリズムの解説を読んでイメージしながら、それをPythonで書いて実行して、実際に結果を見ながら遊んでみようと思った今日この頃。
0 コメント:
コメントを投稿