「アルゴリズム」のキホン
「アルゴリズム」のキホン プログラミングの基礎となる「アルゴリズム」の手引き書 (イチバンやさしい理工系)
ソフトバンククリエイティブ
著者：杉浦賢
はじめに
登場キャラクターのご紹介
第1章 アルゴリズムとは
001 料理のレシピはアルゴリズムである
002 アルゴリズムは先人の知恵である
003 アルゴリズムを知ることはゲームに強くなるようなもの
004 アルゴリズムには「正当性」と「停止性」がなければならない
005 アルゴリズムにはたくさんの種類がある
COLUMN アルゴリズムの基礎となる構造化プログラミングの考え方
第2章 変数と配列
006 データとはさまざまな情報である
007 すべてのデータには型がある
008 値とは数値や文字などの具体的な表現である
009 変数とは値を入れておく箱である
010 変数は「変数名」という名前で区別される
011 代入分は変数に値を代入する機能をもつ
012 変数から変数への代入とは、変数に格納された値を別の変数に記憶すること
013 変数にもデータ型がある
014 同じデータ型の連続が配列である
015 配列は「配列名」という名前で区別される
016 配列の各要素は要素番号という番号で識別される
017 配列は関連する値を効率よく格納するためのリッカーである
018 2次元配列はホテルの部屋のようなものである
019 配列の各要素は2つの添字によって識別される
020 文字列は文字データの配列である
021 文字列の文字長は、文字長変数もしくは「番兵」により管理される
COLUMN 慣用的に使用される変数名
第3章 データ構造
022 大量のデータを効率よく管理するためのしくみがデータ構造である
023 データ構造にはたくさんの種類がある
024 本を積み上げるようなデータ構造がスタックである
025 レジに順番に並ぶようなデータ構造が待ち行列(キュー)である
026 ひもでつながれたようにデータを管理するのがリストである
027 一方の端からデータをたどっていくのが単方向リストである
028 両端からデータをたどっていけるのが双方向リストである
029 N番目の要素の参照が速いのは配列で、遅いのはリスト構造である
030 データの挿入・削除が速いのはリスト構造で、遅いのは配列である
031 末尾までいったら先頭に戻ってくるのがリングバッファである
032 親1人、子ども2人の構造をしているのが二分木である
033 親ノードの値が常に子ノードの値より大きくならない二分木がヒープである
034 ハッシュテーブルは配列とリストを組み合わせたデータ構造である
035 節点と辺により項目のつながりを図的に表現したのがグラフである
COLUMN BASE 0なのか、BASE 1なのか
第4章 基本的なアルゴリズム
036 1〜Nの合計値を求めるには繰り返し処理を行う
037 数列の値を保持するには配列を使う
038 配列データの合計値を求めるには合計値を加算する変数を用意する
039 配列データの有効な要素数を求めるにはカウンタを用意する
040 配列データの平均は繰り返し処理で合計値と個数を求めて計算する
041 配列データ内の最大値を求めるには、最大値を保持する変数を用意する
042 配列データ内の最小値を求めるには、最長値を保持する変数を用意する
043 配列データの順位をつけるには、順位を格納する別の配列を用意する
044 時刻の大小比較するには、単位を秒にそろえる
045 時刻の差を求めるには、秒単位で差を求めてから時刻表示に戻す
046 2つの変数の値を入れ替えるには、一時的なワーク変数を利用する
047 2つの数値の最大公約数はユークリッド互除法で求める
COLUMN コードやデータはどこにあるのか？
第5章 並び替えと探索
048 並び替え(ソート)とは、対象をある規則に従って並び替えること
049 ソートアルゴリズムにはさまざまな種類がある
050 別配列(バケツ)にデータを格納して並び替えを行う「バケットソート」
051 数値の下の桁から順にバケットソートを繰り返す「基数ソート」
052 最小値(最大値)を選択し、ソートずみデータの末尾と交換する「単純選択法」
053 隣接するデータを交換していく「単純交換法」(バブルソート)
054 ソートずみデータ中で正しい大小関係の位置にデータを挿入する「単純挿入法」
055 データ列を一定間隔のグループに分けて並び替える「シェルソート」
056 複数のソートずみデータ列を合体させる「併合」(マージ)
057 併合(マージ)のアルゴリズムを利用することでソートを行うマージソート
058 基準データとの大小関係でデータ列を2分割する「クイックソート」
059 ヒープ構造を利用して並び替える操作を行う「ヒープソート」
060 探索とは、複数のデータの中〜目的のデータを探しだすこと
061 先頭からしらみつぶしにデータを比較する「線形探索」(リニアサーチ)
062 ソートずみデータ列から高速にデータを探し出せる「二分探索」(バイナリサーチ)
063 与えられた文字列の中で、指定した部分文字列の位置を調べる「文字列探索」
064 不一致文字位置と部分文字列の構成から文字探索を効率化するKPM法
065 部分文字列の末尾から先頭に向かって文字を比較していくBM法
COLUMN リレーショナルデータベースの利用によるソートや探索
第6章 そのほかのアルゴリズム
066 微分を活用することで高次方程式の解を求めるのがニュートン法
067 連立方程式の解を求めるのがガウスの消去法
068 台形の面積の加算により定積分の値を求めるのが台形法
069 最短時間、最短距離などの最適経路を求めるのがグラフによるダイクストラ法
070 自然数nが素数であるか否かを判定する「エラトステネスのふるい」
071 再帰呼びだしを利用してnの階乗を求める
COLUMN アルゴリズムとフローチャート(流れ図)
第7章 アルゴリズムの計算量
072 アルゴリズムの計算量には、時間計算量と領域計算量がある
073 時間計算量は、「演算」「条件比較」「代入処理」などの操作回数で計測する
074 アルゴリズムの計算量は、「O(オー)記法」で表す
COLUMN プログラムの上達法
参考文献
索引