アルゴリズムとプログラミング
データをどう並べて持つか（データ構造）と、どんな手順で処理するか（アルゴリズム）で、同じ仕事でも手間が大きく変わります。プログラムの書き方の決まりと、言語の種類もここで扱います。
要点
データ構造
- データ構造
- データの並べ方と、追加・削除・探索のやり方の組。処理に合う構造を選ぶと手間が減る。
- 配列
- 同じ型の要素を連続して並べ、添字で直接読み書きする。途中への挿入・削除は後ろをずらす手間がかかる。
- 大きさが決まった静的配列、実行中に変えられる動的配列、表の形の多次元配列。
- リスト
- 各要素が次の要素の位置（ポインタ）を持つ線形リスト。挿入・削除はポインタの付け替えで済む。
- 次だけを指す単方向リスト、前後を指す双方向リスト、末尾が先頭へ戻る環状リスト。
- スタックとキュー
- スタックは最後に入れたものから出すLIFO（後入れ先出し）。入れるのがプッシュ、出すのがポップ。
- キューは最初に入れたものから出すFIFO（先入れ先出し）。待ち行列や印刷の順番待ちに使う。
- 木構造
- 一番上が根、子を持たない節が葉。子が最大2つの2分木、3つ以上持てる多分木。
- 2分探索木は「左の子＜親＜右の子」。偏らないよう高さをそろえるバランス木にAVL木やB木がある。
- 巡回は先行順（根→左→右）、中間順（左→根→右）、後行順（左→右→根）。2分探索木を中間順でたどると昇順。
- ヒープは親が子以上（または以下）の完全2分木。節を追加・削除したら親子を交換して条件を直す（再構成）。
アルゴリズム
- 流れ図
- 処理の順序を記号でつなぐ。端子（開始・終了）、処理、判断（ひし形）、ループ端、定義済み処理、データ、線。
- どんな手順も順次・判定（選択）・繰返しの3つの組み合わせで書ける。
- 整列・併合・探索
- バブルソート（交換法）・選択ソート・挿入ソートは比較が約 n²/2 回で O(n²)。
- クイックソート・マージソート・ヒープソートは平均 O(n log n)。シェルソートは間隔をあけた挿入ソートを繰り返す。
- 線形探索法は先頭から順に比べる。2分探索法は整列済みの列を半分ずつ絞り、最大でも ⌊log₂n⌋＋1 回。
- ハッシュ表探索法はキーから計算した位置を直接見る。違うキーが同じ位置になる衝突（シノニム）の処理が要る。
- 再帰
- 関数の中で自分自身を呼ぶ。n!＝n×(n−1)! のように小さな同じ問題に分け、止まる条件（0!＝1）を必ず書く。
- グラフ
- 行けるところまで進んで戻る深さ優先探索、近い節から順に広げる幅優先探索。
- 最短経路探索は、辺の重みが負でなければダイクストラ法、負の重みもあればベルマンフォード法。
- 文字列処理
- 文字列照合は本文の中から探す語の位置を見つける。1文字ずつずらして全部比べるのが最も単純な方法。
- ファイル処理
- バッチ処理では、キー順に整列し、整列済みの2つのファイルを1つにまとめる（併合）。
- キーの値が変わった所で小計を出すのがコントロールブレーク処理。出力の形に整えるのが編集処理。
- 自然言語処理
- 文を単語に分ける形態素解析→構文解析（係り受け解析）→意味解析→文脈解析の順に進める。
- n文字（n語）ずつ区切るn-gramで索引を作り、単語の出現の似かたで文章間類似度を測る。
- アルゴリズム設計
- 擬似言語・流れ図・決定表（条件と動作の組を表にしたもの）で表す。
- 大きな問題を同じ形の小さな問題に分けて解き、結果をまとめるのが分割統治法（例：マージソート）。
プログラミング
- 作法とコーディング標準
- 字下げ、ネストの深さの上限、命名規則、使用禁止命令をチームで決め、読みやすさと保守性を上げる。
- 守らないと、人によって書き方がばらつき、読み違いや直し忘れが起きやすくなる。
- プログラム構造
- 機能ごとにモジュール分割し、モジュールの独立性を高める。メインルーチンからサブルーチンを呼ぶ。
- データ型と変数
- 整数型・実数型・論理型・文字型・文字列型、複数の値をまとめる構造型、操作ごと定義する抽象データ型。
- 変数は値を入れる名前つきの場所。値を入れることを代入という。
- 演算
- 算術演算（＋−×÷、余り）、比較演算（＝、＜ など）、論理演算（and・or・not）、ビット単位のビット演算。
- 制御構造
- 条件で道を分ける選択処理（if）と、条件を満たす間くり返す繰返し処理（while・for）。
- 手続、関数
- 呼び出し側から渡す値が引数、関数が返す値が戻り値。中だけで使う変数が局所変数。
- オブジェクト指向プログラミング
- クラスはデータ（メンバ変数）と処理（メソッド）の組。生成時に初期化するのがコンストラクタ。
- 親クラスのメソッドを子で書き直すのがオーバーライド、引数の違う同名メソッドを並べるのがオーバーロード。
- Webプログラミング
- サーバ側で HTML を作るサーバサイドプログラミングと、ブラウザで動く JavaScript。Apacheは Webサーバのソフトウェア。
- Ajaxはページを読み直さずに裏で通信して一部を書き換える。リッチクライアントやフロントエンドフレームワークで画面を作る。
- 文法の表記法
- 言語の構文はBNFなどのメタ言語で定義する。例：<数字> ::= 0 | 1 | … | 9。
プログラム言語
- 変遷と分類
- CPUが直接読む機械語、それを記号で書くアセンブラ言語、人に読みやすい高水準言語の順に発展した。
- 手続型言語
- 処理の手順を順に書く。科学技術計算のFortran、事務処理のCOBOL、C、統計解析のR など。
- オブジェクト指向言語
- クラスとオブジェクトでプログラムを組み立てる。Java、C++ など。
- スクリプト言語
- コンパイルせずに手軽に書いて動かせる。Python、Ruby、PHP、Perl、JavaScript の標準仕様のECMAScript。
- 共通言語基盤（CLI）
- 異なる言語で書いたプログラムを共通の中間言語に変え、同じ実行環境で動かすための規格（JIS X 3016）。
その他の言語
- HTML
- 開始タグと終了タグで文書の構造を示す。SGMLをもとにし、使えるタグはDTDで定める。
- XML
- タグを自分で定義でき、データ交換に使う。構造はXML Schemaで定め、DOM（木で扱う）やSAX（順に読む）で処理する。
- XMLで書く応用に、通信のSOAP、図形のSVGがある。
- XHTML
- HTMLをXMLの規則で定義し直したもの。機能をモジュールに分けたXHTML Modularization、小さな端末向けのXHTML Basic。
- スタイルシート
- 文書の構造と見た目を分ける。HTMLにはCSS、XMLの変換と書式にはXSLを使う。
- その他の言語
- UMLはオブジェクト指向設計の図の表記法。クラス図（属性・操作）、シーケンス図、アクティビティ図、ステートマシン図など。
- データを文字で書き表す形式に、括弧と「名前: 値」で書くJSON、字下げで階層を表すYAMLがある。
さわって確かめる
データの出し入れの順と、整列・探索の手間を、次の3つで数えます。擬似言語を1行ずつ動かすのは、下の関連ページの「擬似言語トレーサ」でできます。
1. スタックとキューの取り出し順
A・B・C の順に入れてから3回取り出し、スタックとキューで出てくる順がどう違うか確かめよう。
スタック（LIFO。上が出口）
キュー（FIFO。左が出口、右から入る）
2. 3つの整列法の比較回数と交換回数
5,3,8,1,9,2 を交換法・選択法・挿入法で1手ずつ進め、比較回数と交換回数を比べよう。
数え方：「比較」は2つの値の大小を比べた回数。「交換」は2つの値を入れ替えた回数（挿入法は、左の大きい値と1つずつ入れ替えて差し込む形で数える）。交換法は途中で整列済みになっても最後まで比べる形。
3. 二分探索と線形探索の比較回数
要素数を 10、100、1000 と変えて配列にない 3 を探し、線形探索と二分探索の比較回数の増え方を比べよう。
配列は 2, 4, 6, …, 2n（偶数を小さい順に n 個）。奇数を探すと「見つからない」場合を試せる。1回の比較＝要素1つを調べること。
3問チェック
最初に選んだ答えで採点します。全問正解で、この単元に「済み」の印が付きます。
-
空のスタックに A、B、C の順にプッシュし、ポップを1回、D をプッシュ、ポップを2回行った。取り出された順はどれか。
- C、D、B
- A、B、C
- C、B、D
- A、B、D
答えと解説
正解はア。ポップは最後に入れたものから出す。A B C からCが出て、A B D からDが出て、A B からBが出る。A、B、C はキュー（先入れ先出し）で同じ操作をしたときの順。
-
小さい順に整列済みの1000個のデータから2分探索法で値を探す。見つからない場合も含めて、要素を調べる回数は最大で何回か。
- 9回
- 10回
- 500回
- 1000回
答えと解説
正解はイ。1回調べるごとに候補が半分以下になり、1000→500→250→125→62→31→15→7→3→1 と減るので、最後の1個を調べるまで ⌊log₂1000⌋＋1＝9＋1＝10回。9回は log₂1000≒9.97 を切り捨てたままの値。1000回は線形探索の最大、500回はその平均に近い値。
-
4、3、2、1 を交換法（バブルソート）で昇順に並べ替える。値を入れ替える回数は何回か。
- 2回
- 3回
- 4回
- 6回
答えと解説
正解はエ。交換法は隣どうしの逆順の組を1回ずつ直すので、交換回数は逆順になっている組の数と同じ。4個すべてが逆順なので 4×3÷2＝6回。2回は選択法（4と1、3と2を入れ替える）の回数。3回は1周目だけの交換回数。