Testです

Evernoteとはてなブログが連携できるようになったみたいです。

記念とテストを兼ねて、（特に書く事はないけど）ブログを作成。

 

Evernoteと連携してノベルティをゲット！ Evernoteで保存したノートをブログで活用できる「Evernote貼り付け機能」をリリースしました - はてなブログ開発ブログ http://staff.hatenablog.com/entry/evernote-campaign

 

読んだ本をEvernoteに貼り付けています。

本のあらすじに「一番最初に読むアルゴリズムの本」と紹介されています。

とっても読みやすい本です。

インプレスの公式サイトには掲載されていない詳細な目次を書き出してみました。

 

f:id:kireifish:20121206173550g:plain


http://www.impressjapan.jp/books/3201

アルゴリズムを、はじめよう
伊藤 静香 /2012年05月14日 /256P / amazon


プログラミングの基礎知識から身に付けられるよう、
「プログラムとは何か」「アルゴリズムとは何か」から解説

本書は、アルゴリズムの入門書の中でも、一番最初に読んでいただきたいアルゴリズム超入門書です。
アルゴリズムの定石と呼ばれるものには様々な種類がありますが、プログラマ初心者が
いきなりたくさんのアルゴリズムを学ぼうとしても、途中で挫折してしまう人が多いのではないでしょうか。
 
本書は、アルゴリズムの中でもプログラマが最低限知っておくべきとされるもののみにぎゅっと絞込み、
1つひとつをとにかくていねいに解説しているため、無理なく最後まで読み終えることができます。
 
また、簡単な例でイメージを確認してからフローチャートを
少しずつ完成させていく手順で解説しているため、確実に理解することができます。
はじめに
この本ではデータ構造については、変数と配列以外は、取り上げませんでした。
理由は、アルゴリズムの勉強を始めようとして、データ構造でつまづく人が多いから。

第 1章 アルゴリズムの基本
０１．アルゴリズムとは何か？
０２．アルゴリズムとプログラムの関係
０３．プログラム作成におけるアルゴリズム
０４．いいアルゴリズムとはどういうものか？
０５．なぜアルゴリズムを作る必要があるのか？
０６．手順がアルゴリズムであるための条件
０７．アルゴリズムの３つの基本形
０８．アルゴリズムの記述方法①ー流れ図
０９．アルゴリズムの記述方法②ープログラミング言語
１０．アルゴリズムの記述方法③ー擬似言語
 
第 2章 変数と配列
１．変数について学ぼう
２．配列について学ぼう
 
第 3章 アルゴリズムに慣れよう
１．三角形の面積を計算するアルゴリズム
２．２つのデータの大小を判定するアルゴリズム
３．２つの変数のデータを入れ替えるアルゴリズム
４．合計値を計算するアルゴリズム
５．最大値を探すアルゴリズム
 
第 4章 線形探索法（リニアサーチ）
１．定番アルゴリズムとは？
２．探索アルゴリズムとは？
３．線型探索法のイメージをつかもう
４．線形探索法のアルゴリズム
 
第 5章 二分探索法（バイナリサーチ）
１．二分探索法のイメージをつかもう
２．二分探索法のアルゴリズム
 
第 6章 ハッシュ探索法
１．ハッシュ探索法のイメージをつかもう
２．ハッシュ関数でデータを格納するアルゴリズム
３．ハッシュ探索法でデータを探索するアルゴリズム
 
第 7章 単純選択法（選択ソート）
１．整列アルゴリズムとは？
２．単純選択法のイメージをつかもう
３．単純選択法のアルゴリズム
 
第 8章 単純交換法（バブルソート）
１．単純交換法のイメージをつかもう
２．単純交換法のアルゴリズム
 
第 9章 単純挿入法（挿入ソート）
１．単純挿入法のイメージをつかもう
２．単純挿入法のアルゴリズム
 
第10章 クイックソート
１．クイックソートのイメージをつかもう
２．クイックソートのアルゴリズム
３．基準値を境にしてデータを大小に分ける処理
４．分けたデータに再度同じ処理を実行する処理
 
第11章 エラトステネスのふるい（素数を求めるアルゴリズム）
１．エラトステネスのふるいとは？
２．エラトステネスのふるいのイメージをつかもう
３．アルゴリズムを流れ図で書く
４．アルゴリズムを擬似言語で書く
 
第12章 ユークリッドの互除法（最大公約数を求めるアルゴリズム）
１．ユークリッドの互除法のイメージをつかもう
２．アルゴリズムを流れ図で書く
３．アルゴリズムを擬似言語で書く
 
■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
 
第 1章 アルゴリズムの基本
０１．アルゴリズムとは何か？
・アルゴリズムとは、ひとことで言えば「手順」のこと
・料理のレシピはアルゴリズム
・楽譜もアルゴリズム
・取扱説明書もアルゴリズム
 
０２．アルゴリズムとプログラムの関係
・アルゴリズムをプログラミング言語で書いたものがプログラム
 
０３．プログラム作成におけるアルゴリズム
・プログラム作成の流れ
・プログラミングのはじまりはニーズ
・プログラムを設計する
・プログラミングする
・プログラムをデバッグする
・プログラムのドキュメントを作成する
 
０４．いいアルゴリズムとはどういうものか？
・わかりやすい
・高速である
・効率的である
・再利用しやすい
 
０５．なぜアルゴリズムを作る必要があるのか？
・いいプログラムを作るため
・プログラムの善し悪しを判断するため
・プログラム作成過程全体を効率化するため
・プログラミング技術向上のため
 
０６．手順がアルゴリズムであるための条件
・正しい結果が得られる
・かならず終わる
 
０７．アルゴリズムの３つの基本形
・①順次構造ーー初めから順番に処理する手順
・②選択構造ーー処理を選んで実行する手順
・③反復構造ーー同じ処理を繰り返す手順
 
０８．アルゴリズムの記述方法①ー流れ図
・アルゴリズムを流れ図で表す
 
０９．アルゴリズムの記述方法②ープログラミング言語
・プログラミング言語にはたくさん種類がある
 
１０．アルゴリズムの記述方法③ー擬似言語
・擬似言語はプログラミングには使えない
・擬似言語の記述方法
 
●順次構造の書き方
 
●選択構造の書き方
 
●反復構造の書き方
 
■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
 
第 2章 変数と配列
１．変数について学ぼう
・データはメモリに保存される
・データの保存には変数を使う
・変数を使うときは、まず宣言する
・変数名のつけ方
・データ型とは？
・変数の宣言方法
・変数へデータを代入するには？
・変数のデータを参照するには？
 
２．配列について学ぼう
・変数には限界がある
・配列のしくみ
・配列の宣言方法
・配列の要素へデータを代入するには？
 
■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
 
第 3章 アルゴリズムに慣れよう
１．三角形の面積を計算するアルゴリズム
・処理に分解して手順を考える
 
三角形の面積=底辺の長さ × 高さ÷2
 
この計算過程が、どのようなデータと処理から成り立っているのかを考えよう。
 
まずデータとして必要なのは「底辺の長さ」と「高さ」です。
それぞれ変数を用意して、代入する。データを取り扱うには、とりあえず変数です。
 
次に、実際に計算する処理を考えます。
「底辺の長さ」と「高さ」をかけ合わせて2で割り、「面積」を出します。
ただ計算しただけでは、計算結果がいくらになるのかを確かめることはできません。
計算した結果のデータは、もう一つ別の変数を用意して、代入することにします。
そして、「面積」のデータをコンピュータのディスプレイに表示させます。（標準出力）
 
必要な変数は、「底辺の長さ」「高さ」「面積」を代入する実数型変数が３つ、
処理は順次構造でよさそうだということがわかりました。
 
・アルゴリズムを表す流れ図を作る
変数名を、
 
「底辺の長さ」をbase,
「高さ」をheight,
「面積」をarea
 
とします。
 
次に、baseとheightにデータを入力します。（標準入力）
 
流れ図で言うと、以下のようになる。
開始 →baseとheightを入力する →base*height/2.0=area →areaを出力する →終了
 
・四則演算を表す算術演算子
算数では商を求める機能と余りを求める機能が同居しているが、
プログラミングでは、分離して表す。
 
13/3・・・4（商を表す）
13%3・・・1（余りを表す）
 
 
・アルゴリズムを擬似言語で書く
最初に変数の宣言をする。
変数の宣言は、行頭に「○」をつける。
以後の処理は行頭に「・」を書き、１つの処理を１行ずつに分けて書く。
 
○実数型:base,height,area
・baseとheightを入力する
・area←base*height/2.0
・areaを出力する
 
 
 
２．２つのデータの大小を判定するアルゴリズム
●２つのデータを比較するには、選択構造を使う。
●条件式では関係演算子を使う。
 
・２つのデータのうち、大きいのはどちらか？
 
 
・アルゴリズムを表す流れ図を作る
 
 
・データを比較する関係演算子
 
 
・アルゴリズムを擬似言語で書く
 
 
３．２つの変数のデータを入れ替えるアルゴリズム
●２つの変数のデータを直接入れ替えることはできない
●入れ替え用の変数を使う
 
・２つのデータを入れ替えるなんて、簡単？
 
 
・データ交換用の変数を使う
 
 
・アルゴリズムを擬似言語で書く
 
 
４．合計値を計算するアルゴリズム
●配列の要素を合計するには、反復構造を使う
●合計値を代入する変数sumは、初期化を行う
●変化する添字は、変数i に代入する
●反復構造では、無限ループにならないような処理を忘れずに加える
 
・単純に合計するアルゴリズムもありだけど・・・
 
・反復構造を使ったアルゴリズムを考えてみる
 
 
・アルゴリズムを擬似言語で書く
 
 
５．最大値を探すアルゴリズム
●複雑そうなときは、流れ図を作りながらアルゴリズムを考える
●その時々の最大値を格納する変数maxを使う
●変化する添字を格納する変数iを使う
●繰り返し処理が無限ループにならないような処理を入れる
 
・５つのデータのうち、一番大きいのはどれか？
 
 
・流れ図を作りながら、アルゴリズムを考える
 
 
・アルゴリズムを擬似言語で書く
 
 
■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
 
第 4章 線形探索法（リニアサーチ）
１．定番アルゴリズムとは？
●基本的な処理手順をもっているアルゴリズムのこと
●いいプログラムを作るための考え方やヒントがたくさん詰まっている
●定番アルゴリズムの学習は、プログラミング技術の向上に役立つ
 
・定番アルゴリズムとは何か？
・定番アルゴリズムの種類
 
２．探索アルゴリズムとは？
●検索アルゴリズムとは、目的のデータを探し出すアルゴリズムのこと
●検索エンジンも探索アルゴリズムを使っている
 
・検索エンジンは探索アルゴリズムを使っている
・探索とは目的のデータを探し出すこと
 
３．線型探索法のイメージをつかもう
●線形探索法は、先頭から順番に調べて探す探索アルゴリズム
●アルゴリズムは単純で分かりやすい
●探索効率はそれほどよくない
 
・線形探索法でボールを探し出してみよう
・線形探索法の手順
 
４．線形探索法のアルゴリズム
●配列に保存されたデータを先頭から順番に探索する
●探索処理は反復構造で記述する
●反復構造では終了条件を忘れないこと
 
・配列と要素の設定
・探索処理の流れ
・反復処理にはかならず終了条件をつけること
・アルゴリズムを擬似言語で書く
 
■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
 
第 5章 二分探索法（バイナリサーチ）
１．二分探索法のイメージをつかもう
●二分探索法は、データを探す探索アルゴリズムの一つ
●あらかじめ昇順か降順に整列されているデータが対象
●探索する範囲を半分に絞りながら探索を進める
 
・二分探索法でボールを探してみよう
・①真ん中のボールの数字を見てみる
・②ふたたび真ん中のボールの数字を見てみる
・③みたび真ん中のボールの数字を見てみる
 
２．二分探索法のアルゴリズム
●二分探索法は主に３つの処理からなる
●①真ん中の要素を選ぶ処理
●②真ん中のデータと目的のデータを比較する処理
●③探索の範囲を半分に狭める処理
●目的のデータが存在しない場合の処理も忘れずに書く
 
・配列の設定
・二分探索法のアルゴリズム構成
・①真ん中の要素を選ぶ
・②真ん中の要素と目的のデータを比較する
・③探索の範囲を半分に絞る
・もし目的のデータが存在しなかったら？
・アルゴリズムを擬似言語で書く
 
■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
 
第 6章 ハッシュ探索法
１．ハッシュ探索法のイメージをつかもう
●探索しやすいように、あらかじめ関数を使ってデータを格納しておく
●格納するのに使った関数を使い、一発でデータを探索する
 
・ハッシュ探索法の特徴
・あらかじめ探索しやすいようにボールを格納する
・ハッシュ探索法でボールを探す
 
２．ハッシュ関数でデータを格納するアルゴリズム
●データの格納先の添字を計算するにはハッシュ関数を使う
●格納先の添字がバッティングすることを衝突と言う
●衝突が起こったら、隣の空き要素にデータを格納する
 
・ハッシュ探索法のアルゴリズム構成
・配列を２つ用意する
・arrayD[0]のデータをarrayHに格納する
・arrayD[1]のデータをarrayHに格納する
・arrayD[2]のデータをarrayHに格納する
・arrayD[3]のデータをarrayHに格納する
・arrayD[4]のデータをarrayHに格納する
・arrayD[5]のデータをarrayHに格納する
・arrayD[6]のデータをarrayHに格納する
・アルゴリズムを擬似言語で書く
 
３．ハッシュ探索法でデータを探索するアルゴリズム
●データの探索には、格納に使ったのと同じハッシュ関数を使う
●探索データが存在しない場合の処理を忘れずに書く
 
・探索対象となる配列
・12が格納されている要素を探索する
・36が格納されている要素を探索する
・探索しているデータが配列に存在しない場合
 
■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
 
第 7章 単純選択法（選択ソート）
１．整列アルゴリズムとは？
●整列アルゴリズムとは、データを昇順・降順に並べ替えるアルゴリズムのこと
●検索エンジンやExcelでも整列アルゴリズムは使われている
 
・検索エンジンやExcelでも整列は重要
・整列アルゴリズムの定番４つ
 
 
２．単純選択法のイメージをつかもう
●単純選択法は、データを並べ替える整列アルゴリズムの１つ
●一番小さなデータを選択して、先頭から順に並べ替えていく
 
・単純選択法でボールを並べ変えてみよう
・①数字が一番小さいボールを先頭のデータと交換
・②次に数字の小さいボールを２番目のボールと交換
・③３つのうち一番小さいボールを３番目のボールと交換
・④残った２つを昇順に並べ替え
 
 
３．単純選択法のアルゴリズム
●昇順に整列する単純選択法は、次の２つの手順からできている
●①探索範囲の最小値を探す処理
●②探索範囲の最小値を先頭要素と交換する処理
 
・配列の設定
・探索処理の流れ
・①array[i]からarray[4]の中の最小値を探す
・②最小値とarray[i]のデータを交換する
・３つの処理を組み合わせて流れ図が完成
・アルゴリズムを擬似言語で書く
 
■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
 
第 8章 単純交換法（バブルソート）
１．単純交換法のイメージをつかもう
●単純交換法は、データを並べ替える整列アルゴリズムの1つ
●隣合ったデータを交換する処理を繰り返して、全体を整列する
●単純なアルゴリズムだが、実行速度は遅い
 
・単純交換法でボールを昇順に並べ変えてみよう
・①０番枠に１のボールを持っていく
・②１番枠に２のボールを持っていく
・③２番枠に３のボールを持っていく
・④３番枠に４のボールを持っていく
 
２．単純交換法のアルゴリズム
●昇順に整列させる単純交換法は、2つの手順の組み合わせからなる
●①右端の要素から順に、隣合ったデータを昇順に並べ替える
●②左端の要素から1つずつ順番に、データが昇順に整列していく
 
・配列の設定
・右端から順に、隣り合ったデータを昇順に並べ替える
・左端の要素から順に、入るデータを確定させていく
・アルゴリズムを擬似言語で書く
 
■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
 
第 9章 単純挿入法（挿入ソート）
１．単純挿入法のイメージをつかもう
●単純挿入法は、データを並べ替える整列アルゴリズムの1つ
●正しい順序になるようにデータを挿入していく
●単純挿入法は、挿入ソート、基本挿入法、挿入法とも呼ばれる
 
・単純挿入法でボールを昇順に並べ替えてみよう
・1番目の枠のボールを正しい位置に挿入する
・2番目の枠のボールを正しい位置に挿入する
・3番目の枠のボールを正しい位置に挿入する
・4番目の枠のボールを正しい位置に挿入する
 
２．単純挿入法のアルゴリズム
●挿入したいデータは別に変数を用意して代入しておく
●変数のデータを、整列済みデータと順番に比較していく
●変数のデータより小さいデータが見つかったら、その後ろの要素に変数のデータを代入する
 
・配列の設定
・array[1]のデータを正しい位置に挿入したい
・array[2]のデータを正しい位置に挿入したい
・array[3]のデータを正しい位置に挿入したい
・アルゴリズムを擬似言語で書く
 
■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
 
第10章 クイックソート
１．クイックソートのイメージをつかもう
●クイックソートは、データを並べ替える整列アルゴリズムの1つ
●データを大小のグループ2つに分割しながら全体を整列していくアルゴリズム
●実行速度が速いのが特徴
 
・クイックソートでボールを昇順ニ並べ替えてみよう
・先頭の5を基準にしてボールを大小に分ける
・先頭の3を基準にしてボールを大小に分ける
・先頭の2を基準にしてボールを大小に分ける
・先頭の8を基準にしてボールを大小に分ける
・先頭の7を基準にしてボールを大小に分ける
 
２．クイックソートのアルゴリズム
●クイックソートは、大きく分けて2つの処理から構成されている
 
３．基準値を境にしてデータを大小に分ける処理
●データを大小に分ける処理が、クイックソートの中心的な処理
●配列の左と右から、それぞれ変数を動かして、大小に並べ替えていく
 
・配列の設定
・変数の設定
・変数i を使って、基準値より大きい要素を探す
・変数k を使って、基準値より小さい要素を探す
・大きいデータと小さいデータを交換する
・データを見つけて交換する処理を繰り返す
・基準値を大小データの真ん中に移動する
 
４．分けたデータに再度同じ処理を実行する処理
●「基準値を堺にして、データを大小に分ける」処理を副プログラムにする
●副プログラムの中で副プログラムを使うことで、繰り返し処理を実行する
 
・QuickSortを副プログラムにする
・QuickSortの中でQuickSortを使う
 
 
■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
 
第11章 エラトステネスのふるい（素数を求めるアルゴリズム）
１．エラトステネスのふるいとは？
●エラトステネスのふるいとは、素数を見つけ出すアルゴリズム
●素数とは、2以上の整数で、1とその数自身以外では割り切れない数
●素数は、並んでいる間隔が不規則でランダムで見つけにくい
 
・素数のおさらい
・素数かどうかを見分けるのは案外難しい
・エラトステネスのふるいは素数を発見する方法
 
２．エラトステネスのふるいのイメージをつかもう
・エラトステネスのふるいの構成
・10までの整数データを用意するには？
・要素を使って素数の倍数を取り除く
・ふるわれずに残った数を出力する
 
３．アルゴリズムを流れ図で書く
・配列の設定
・2の倍数を取り除く
・3の倍数を取り除く
・次の素数を探す
・次の素数の倍数を取り除く
・要素が1の添字を出力する
 
４．アルゴリズムを擬似言語で書く
・変数と配列の設定
・本体の処理の部分を書く
 
■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
 
第12章 ユークリッドの互除法（最大公約数を求めるアルゴリズム）
１．ユークリッドの互除法のイメージをつかもう
・最大公約数のおさらい
・最大公約数の求め方
・143と221でユークリッドの互除法を試してみよう
 
２．アルゴリズムを流れ図で書く
・変数の設定
・大きい方の数を小さい方の数で割る
・余りr が ０ かどうか確かめる
・小さい方の数を余りで割る処理を、反復構造にする
 
３．アルゴリズムを擬似言語で書く
・ループ記号を使った前判定型反復構造にする
・後判定型反復構造を使ってみる
・両方のアルゴリズムを擬似言語で書く
 
 
 
 
おわりに
 
最先端の機械を作って製品を作るのは簡単で、しかも楽なことだが、
基本技術を固める前に楽なほうに流れていってしまった。
俺のような基本的なことがきちんとできるローテクが、今、我が世の春を謳歌しているんだ。
 
 
東京生まれ。東京大学文学部卒業。
出版社に勤務の後、テクニカルライターとして独立。
 
著書に
 
「1週間で基本情報技術者の基礎が学べる本」
 
がある。