はじめに
普段仕事で使っている(作っている)プログラムという存在について、そういえばあまり深く理解せずなんとなく使っていることに気がつきました。
一般のサラリーマンならプログラムによって作られたシステムやサービスを使いこなすことができれば、それらがどのように作られているかを意識する必要はありませんが、エンジニアという肩書きで仕事をしていくのであればそうはいきません。
というわけでプログラムを形作る基礎的な知識について学習をしたので記事にまとめます。
プログラミング言語とは
プログラミング言語と種類
プログラミング言語・・・機械語に翻訳しやすく、かつ人間にもわかりやすい中間の言語
↳インタプリタ方式・・・ソースコードに書かれた命令を、１つずつ機械語に翻訳しながら実行する方式。動作を確認しながらの作成が可能。
↳コンパイラ方式・・・ソースコードの内容を最初にすべて翻訳し、機械語のプログラムを作成する方式。1度翻訳した後は高速で動かすことが可能。
コンパイラ方式でのプログラム実行手順
コンパイラ / リンカ / ローダ
コンパイラ・・・プログラム言語を用いて書かれたソースコードを、翻訳して機械語のプログラムファイルにする作業のこと。
リンカ・・・プログラムが使っているモジュールやライブラリなどの関数、共通モジュールなどを全てつなぎ合わせプログラムファイルを作る作業のこと。
ローダ・・・実行可能ファイルを主記憶装置に読み込ませる作業のこと。
構造化プログラミング
構造化プログラミング・・・大まかな流れを決める最上位のメインプログラムから、サブルーチンという形で別のモジュールを切り出し徐々に詳細な内容を決めていく考え方。
原則『順次』『選択』『繰り返し』の３つの制御構造を使ってプログラミングを行う。
↳順次構造・・・上から順番に処理を行う。
↳選択構造・・・何らかの条件によって分岐させ、いずれかの処理を実行する。
↳繰り返し構造・・・ある条件が満たされるまで、特定の処理を繰り返し実行する。
情報を入れられる便利な機能
変数/関数/引数/戻り値/代入
変数・・・数値や文字列などの様々なデータを出し入れすることの出来る箱のこと。
関数・・・機能を部品化して再利用できるようにしたもの。
引数・・・関数により処理を行う際の、元となる数字などの材料のこと。
戻り値・・・関数のよる処理の結果、得られた結果のこと。
代入・・・変数にデータを格納すること。
アルゴリズムとフローチャート
アルゴリズム・・・コンピュータに処理を依頼する際の手順のこと。
フローチャート・・・アルゴリズムを分かりやすく記述するために用いられる、処理の流れをあらわした図。
データの持ち方
データ構造・・・データを効率的に扱うため、特定のルールのもと体系立てて格納する形式のこと。
配列・・・メモリ上の連続した領域に、データを並べて管理するデータ構造。添字（配列内の何番目のデータかを指定できる番号）を用いることで、配列内の各データに直接アクセスすることができる。
リスト・・・データとデータを数珠つなぎにして管理するデータ構造。ポインタを書き換えることでデータの繋ぎ替えが可能で、データの追加や挿入・削除が非常に容易なのが特徴。
↳ポインタ・・・リストで扱うデータに必ずセットになってついている番号。次のデータがメモリ上のどこにあるのかを指し示している。
↳単方向リスト・・・次のデータへのポインタのみを持つリスト。一方通行で先頭から順にたどっていく必要がある。
↳双方向リスト・・・次のデータへのポインタと前のデータへのポインタを持つリスト。前後どちらのリストにもたどっていくことが出来る。
↳循環リスト・・・次のデータへのポインタを持つリスト。最後のデータのみ先頭データへのポインタを持つ。
キュー・・・最初に格納したデータから順に処理を行う、先入れ先出し方式のデータ構造。入力されたデータがその順番通りに処理されなければいけない状況で使われる。
スタック・・・最後に格納したデータから順に処理を行う、後入れ先出し方式のデータ構造。
ツリー構造
ツリー構造・・・階層構造を持つデータを効率よく管理出来る他、データの探索や整列などの用途に使われるデータ構造。
2分木・・・最上位のデータを『根』そこから伸びる分岐を『枝』さらに各節点をつなぎ、末端の『葉』に到達するツリー構造の構成
2分探索木・・・親に対する左部分木と右部分木の関係が、左部分木＞親＞右部分木となる2分木のこと。データの探索を容易に行うことが出来る。
データ探索のアルゴリズム
線形探索法・・・目的のデータを先頭から順番に探索していく方法。
2分探索法・・・データの集合を２つに分けながら対象を絞り込んで行く探索方法。
ハッシュ法・・・ハッシュ関数と呼ばれる一定の計算式を用いて、データの格納位置を算出する探索方法。
データを整列させるアルゴリズム
基本の整列アルゴリズム
基本交換法（バブルソート）・・・隣り合ったデータの大小を比較して、必要に応じて入れ替える方法。
基本選択法（選択ソート）・・・データ群の中から最小値や最大値のデータを取り出し、先頭（末尾）のデータと交換する手順を繰り返す方法。
基本挿入法（挿入ソート）・・・データ群を整列済みと未整列に分け、未整列のデータを１つずつ整列済みの列の中に挿入していく方法。
高度な整列アルゴリズム
シェルソート・・・ある一定間隔おきに取り出した要素で部分列を作り、整列してもとに戻す。その後さらに間隔をつめて取り出しと整列を行う作業を繰り返すことで整列を行う方法。
クイックソート・・・中間的な基準点を決めて、それより小さいグループとそれより大きいグループに分ける。その後各グループ内で同じ処理を繰り返すことで整列を行う方法。
ヒープソート・・・未整列の部分を順序木といわれるツリー構造に構成して、そこから最大値もしくは最小値を取り出して整列済みに移動する。この処理を繰り返すことで未整列部分を縮めて整列を行う方法。
オーダ記法
オーダ記法・・・アルゴリズムの大まかな処理効率をはかるための指標のこと
各アルゴリズムのオーダ
探索アルゴリズム
↳線形探索法 → O(n)
↳2分探索法 → O(log2n)
↳ハッシュ法 → O(１)
整列アルゴリズム
↳基本交換法（バブルソート） → O(n2)
↳基本選択法（選択ソート） → O(n2)
↳基本挿入法（挿入ソート） → O(n2)
↳シェルソート → O(n1.2)
↳クイックソート → O(nlog2n)
↳ヒープソート → O(nlog2n)
オブジェクト指向プログラミング
オブジェクト指向
オブジェクト指向・・・データとそれに対する処理をオブジェクトという概念で捉え、それをモジュール化することで全体を構成する開発方法。
カプセル化・・・データやメソッドなどの複数の要素を１つのカプセルにまとめたようなイメージ。オブジェクト指向の持つ大きな特徴の１つ。
↳情報隠蔽・・・オブジェクト内部の構造を外部から隠すことが出来るという、カプセル化のメリットのこと。
クラス・・・オブジェクトが持っているデータやメソッドなどの性質を定義したもの。オブジェクトの設計図のような役割を持つ。
インスタンス・・・クラスに対して具体的な属性値を与え、メモリ上に生成し実体化させたもの。
クラスの階層構造
クラスの階層化・・・クラスを上位クラス・下位クラスと階層構造に分けること。下位クラスは上位クラスのデータやメソッドなどの構造を受け継ぐことが出来る。
上位クラス ＝ 基底クラス・スーパークラス
下位クラス ＝ 派生クラス・サブクラス
継承（インヘリタンス）・・・サブクラスがスーパークラスの特性を受け継ぐこと。
汎化と特化（is a 関係）
汎化・・・下位クラスの持つ共通の性質を抽出して、上位クラスとして定義すること。
例：下位クラス（軽自動車・スポーツカー・バス） → 上位クラス（車）
特化・・・抽象的な上位クラスを、より具体的なクラスとして定義すること。
例：上位クラス（車） → 下位クラス（軽自動車・バス・トラック）
集約と分解（part of 関係）
分解・・・継承関係のない上位クラス-下位クラスの関係における、下位クラスは上位クラスの１部であると定義したもの。
集約・・・継承関係のない上位クラス-下位クラスの関係における、上位クラスは複数の下位クラスが集まってできたものであると定義したもの。
↳上位クラス（車） 集約↔分解 下位クラス（ハンドル・シート・タイヤ）
多態性（ポリモーフィズム）
多態性・・・同一のメッセージを複数のオブジェクトに送った際に、それぞれ独立した固有の処理を行うこと。
UML（Unified Modeling Language）
UML・・・オブジェクト指向分析・設計において用いられる統一モデリング言語。ダイアグラムと呼ばれる図を用いて作られる。
UMLのダイアグラム
UMLダイアグラム・・・UMLでは１３種類の図を用いる。大きく『構造図』と『振る舞い図』の２つに分かれる。
構造図・・・UMLで用いる図のうち、構造を表す図たちのこと。
↳クラス図・・・クラスの定義や関連付けなど、クラスの構造をあらわす。
↳オブジェクト図・・・クラスを実体化させるインスタンスの具体的な関係をあらわす。
↳パッケージ図・・・クラスなどがどのようにグループ化されているかをあらわす。
↳コンポーネント図・・・処理を構成する複数のクラスをコンポーネントとみなして、その内部構造と相互関係をあらわす。
↳複合構造図・・・複数のクラスを内包するクラスやコンポーネントの内部構造をあらわす。
↳配置図・・・システムを構成する物理的な構造をあらわす。
振る舞い図・・・UMLで用いる図のうち、振る舞いを表す図たちのこと。
↳ユースケース図・・・利用者や外部システムからの要求に対して、システムがどのような振る舞いをするかをあらわす。
↳アクティビティ図・・・システム実行時における一連の処理の流れや状態遷移をあらわす。
↳状態マシン図・・・イベントによって起こる、オブジェクトの状態遷移をあらわす。
↳シーケンス図・・・オブジェクト間のやり取りを、時系列にそってあらわす。
↳コミュニケーション図・・・オブジェクト間の関連と、そこで行われるメッセージのやり取りをあらわす。
↳相互作用概要図・・・ユースケース図やシーケンス図などの構成要素として、より大枠の処理の流れをあらわす。
↳タイミング図・・・オブジェクトの状態遷移を時系列であらわす。
参考文献
この記事は以下の情報を参考にして執筆しました。
キタミ式イラストIT塾 基本情報技術者 令和03年