7.プログラミング言語とアルゴリズム
7.1. プログラミング言語
7.1.1. 代表的な言語とその特徴
C言語
OSやアプリケーションなど広範囲で用いられる言語。ハードウェアに近いレベルの記述もできる。
BASIC
古くから使われていた言語です。インタプリタ方式で主流である特徴を持つ、動作確認しながら開発を進められる。
COBOL
事務処理用に古くから使われている。システム改修などでまだ使われている言語。
Java
オブジェクト指向やネットワーク機能が想定されて設計されています。Java仮想マシンという環境を用いることでOSやコンピュータによらず作成したプログラムを動かすことができます。
7.1.2. インタプリタとコンパイラ
インタプリタ方式
ソースコードに書かれた命令を１つずつ機械語に翻訳しながら実行する。逐次翻訳するため動作を確認しながら作っていくことが容易に行えます。
コンパイラ方式
ソースコードの内容を最初に全て機械語に翻訳する。作成途中で確認のため動かすと言った手法は用いれません。
7.2. コンパイラ方式でのプログラムの実行手順
コンパイラ方式のプログラムの場合、その過程でコンパイラ以外にリンカとローダが使われます。
コンパイラの仕事
リンカの仕事
プログラムは自分で分割したモジュールやライブラリとしてあらかじめ提供されている関数や共通モジュールなどすべてつなぎ合わせる作業はリンク(連係編集) と呼ばれます。これがリンカの仕事です。
あらかじめリンクさせておく手法は静的リンキングと呼ばれます。またこの時点ではリンクさせず、プログラムの実行時にロードしてリンクする手法は動的リンキングと呼ばれます。
ローダの仕事
ロードモジュールを主記憶装置に読み込ませる作業はロードと呼ばれます。これを担当するプログラムがローダである。
7.3. 構造化プログラミング
構造化プログラミングはプログラムを機能単位の部品に分けて、その組み合わせで全体を形作るプログラミングです。
制御構造として用いる3つの原則
構造化プログラミングでは原則的に3つの制御構造を使ってプログラミングを行う。
- 順次構造 ・・・ 上から順番に処理を実行する
- 選択構造 ・・・ 何らかの条件によって分岐させいずれかの処理を実行させる
- 繰返し構造 ・・・ ある条件が満たされるまで一定の処理を繰り返する
7.4. 変数
変数はメモリの許す限りいくらでも使うことができ、変数は名前を付けて管理する。
7.5. アルゴリズムとフローチャート
コンピュータはプログラムに書かれたアルゴリズム(作業手順) にのっとり動作する。 アルゴリズムをわかりやすく記述するために用いるのがフローチャートである。
フローチャートの記号
7.6. データの持ち方
配列
メモリの連続した領域にデータを並べて管理するのが配列です。 配列は固定サイズでまとめて領域を確保するため、データの削除や挿入は苦手です。
リスト
データ同士を数珠つなぎにして管理するのがリストです。 リストの扱うデータはポインタと呼ばれる番号がセットになっています。これはメモリ上の位置を表す番号で次のデータがメモリのどこにあるかを指し示する。
リストの特徴として、ポインタ順にデータをたどるため、配列のように添え字を使い各データに直接アクセスする使い方はできない。
単方向リスト
リストの一般的構造です。一方通行です。
双方向リスト
次のデータと前のデータのポインタを持つリストです、前後どちらにもリストをたどれます。
循環リスト
最後尾データは先頭データのポインタを持つリストです。
キュー
キュー(待ち行列)は最初に格納したデータから順に処理を行うFIFO方式のデータ構造である。
スタック
スタックはキューの逆で最後に入れたデータから処理を行うLIFO方式のデータ構造である。
7.7. ツリー構造
2分木のデータ構造
ツリー構造のうち節から延びる枝が2本以上のものは2分木と呼ばれます。 また2分木は左右の子にポインタを付加すると次のような配列構造になります。
完全2分木
葉以外の節がすべて2つの子を持ち、根から葉までの深さが等しい2分木は完全2分木と呼ばれます。
2分探索木
ツリーの左分木と右分木の関係が「左<親<右」となる2分木は2分探索木と呼ばれます。 このツリー構造ではデータ探索を節の中身と比較して簡単に行えます。
7.8. データ探索のアルゴリズム
探索のアルゴリズムには主に以下のようなものがある。
線形探索法
先頭から順に探索していく方法は線形探索法(リニアサーチ)と呼ばれます。 線形探索法では番兵と呼ばれる目的のデータを配列最後尾につけることでフロー処理の簡素化を行えます。
2分探索法
探索対象のデータ列が昇順か降順の場合、2分探索法(バイナリサーチ)を実施することで効率よくデータを求められます。 流れは次のようになります。
- データ構造の真ん中のデータを求めているデータと比較する
- 求めているデータに近い方の範囲(右か左)を絞り込みます
- 絞り込んだ範囲の真ん中のデータと求めているデータを比較する
- 1から3を繰り返すと求めたいデータが求まります。
フローチャートは以下のようになります。
ハッシュ法
ハッシュ関数と呼ばれる「一定の計算式」を用いてデータの格納位置を算出する方法です。 なおデータの登録もハッシュ関数を用いて行われる必要がある。 シノニムが発生する場合オープンアドレス法やチェイン法でデータを追加する。
各アルゴリズムにおける探索回数
線形探索法
先頭にあるときと末尾にあるときの平均なので、平均探索回数は (0+n)/2 :nはデータ範囲の最大値
2分探索法
半分ずつに絞り込みを行うので対数logを使うと、平均探索回数はlog2n :nはデータ範囲の最大値
ハッシュ法
シノニム(コリジョン)の発生確率が無視できるほど小さい場合、平均探索回数は1回
7.9. データを整列させるアルゴリズム
基本交換法(バブルソート)
隣接するデータの大小を比較し、必要に応じて入れ替えることで全体を整列させるのがバブルソートである。
基本選択法(選択ソート)
対象とするデータの中から最小値(or最大値)のデータを取り出し、先頭データと交換しこれを1つずつずらして繰り返すことで整列させるのが選択ソートである。
基本挿入法(挿入ソート)
データ列を「整列済みのもの」と「未整列なもの」に分け、未整列の側からひとつずつ整列済みの列の適切な位置に挿入し、全体を整列させる手法が挿入ソートである。
高度な整列アルゴリズム
シェルソート
ある一定間隔沖に取り出した要素からなる部分列を整列しさらに間隔を詰めて同様の操作を行い、間隔が1になるまで繰り返して整列させる手法
クイックソート
中間的な基準値を決めてそれよりも大きな値を集めた区分と小さな値を集めた区分に要素を振り分けてこれを繰り返すことで整列する手法
ヒープソート
未整列データを順序木に構成し、そこから最大値(or最小値)を取り出して既整列に移す。これを繰り返して未整列部分をなくしていって整列する手法
7.10. オーダ記法
オーダ記法はアルゴリズムの計算量(実行時間)をO(式) の形で表すこと。
各アルゴリズムのオーダ
平均計算時間≒オーダ
7.11. オブジェクト指向プログラミング
処理の対象をオブジェクトという概念でとらえ、オブジェクトの集まりとしてシステムの設計開発を行うことはオブジェクト指向プログラミングと呼ばれる。
詳細に説明するとオブジェクトはデータ(属性)とそれに対するメソッド(手続き)を一つにまとめた概念である。
オブジェクト指向でプログラムを設計するとモジュールの独立性が高く保守しやすいプログラムの作成が可能。
オブジェクト指向のカプセル化
オブジェクト指向プログラミングではカプセル化できることが大きな特徴。 カプセル化することでオブジェクト内部の構造は外部から知ることができなくなる。つまり、情報隠蔽ができることがカプセル化の利点である。
カプセル化を用いるとオブジェクトの実装方法に修正を加えてもその影響を最小限にとどめることができる。
クラスとインスタンス
オブジェクトはデータとメソッドを定義したものでした。この「オブジェクトがもつ性質」を定義したものはクラスと呼ばれる。
言い換えると、オブジェクトの設計図がクラスであり、データやメソッドを持っている。
この設計図に対して具体的な属性値を与えメモリ上に実体化させたものはインスタンスと呼ばれる。
クラスの階層構造
クラスの基本的な考え方はオブジェクトを抽象化し定義することです。 クラスの階層化というのはクラスに上位、下位の階層を持たせることができるというものです。
下位クラスは上位クラスのデータやメソッドの構造を受け継ぐことができます。 上位クラスはスーパクラス(基底クラス) 、下位クラスはサブクラス(派生クラス) と呼ばれます。 サブクラスがスーパクラスの特性を引き継ぐことは継承(インヘリタンス) と呼ばれる。
汎化と特化
汎化は下位クラスが持つ共通性質を抽出し上位クラスとして定義することをさす。 特化は抽象的な上位クラスをより具体的なクラスとして定義すること。 それぞれの関係は下記図のようになる。
集約と分解
下位クラスは上位クラスの特性を分化して定義したもの。上位クラスは下位クラスを集約して定義したものという関係。
多態性(ポリモーフィズム)
多態性は同じメッセージを複数のオブジェクトに送ると、それぞれが独立した固有の処理を行うというものです。
7.11. UML(Unified Modeling Language)
UMLはオブジェクト指向分析・設計において用いられる統一モデリング言語である。
またこれは複数人で設計モデルを共有してコミュニケーションをとるための手段。 UMLでは13種類の図が規定されています。これらはダイヤグラムと呼ばれる。
UMLのダイヤグラム
UMLの図は構造図と振る舞い図に分類できます。
クラス図
クラスの定義や関連付けを示す図である。 クラス内の属性と操作を記述し、クラス同士を線でつないで互いの関係を表する。
ユースケース図
利用者視点でシステムが要求に対してどう振る舞うかを示す図である。
アクティビティ図
業務や処理のフローを表す図である。
シーケンス図
オブジェクト間のやり取りをし系列に沿って表す図である。オブジェクト同士の相互作用を表すもので、オブジェクト下の点線で生成から消滅までを表しそこで行われるメッセージのやり取りを矢印で表す。
