基本理論(2)

アルゴリズムとプログラミング

データ構造

データおよびデータ構造

「データ」すなわちコンピュータで取り扱われる情報は、系統立った「データ構造」を持っている

変数

プログラムの中で扱われるデータを一時的に記憶する領域を「変数」と呼ぶ。変数は、プログラムを実行するたびにデータを代入する箱のようなもので、変数に名前を付け、必要に応じて使いたい値を代入することで実行結果を変化させるため、プログラム自体を書き換える必要はない

フィールドのタイプ

格納するデータの種類を「フィールドのタイプ」と呼ぶ。ほかに「データ型」という呼び方もあり、プログラム中で扱われるデータに対して、数値や文字列を定義する。定義することにより、適切なデータだけが代入されるため、プログラムの精度が向上する

配列

配列とはオブジェクトの並びをいう
その要素（成分）が何番目か？というインデックス（添字）を用いて、どのデータにも直接アクセス（参照）できる
インデックスの範囲（配列の大きさ）に注意する必要がある

散在する複数のデータを数珠つなぎにするデータ構造。データが連続的に配置されていなくてもOK。データとともに、次のデータの格納場所を示す「ポインタ」と呼ばれる情報を持っている。実際には列で並んだデータが複数の列となり「ファイル」としてまとめられています。この列ひとつひとつの行は「レコード」と呼ばれている
リストの特徴：
　・サイズは固定ではなく、データの大きさに柔軟に対応できる
　・ポインタの付け替えだけで並び替えが可能
　・データの挿入や削除を行っても、他のデータを動かす必要がない

スタックとキュー

リストにデータの挿入や削除を行う考え方は次の2つ

スタック

スタックは、後に入れたデータが先に取り出される
スタックにデータを入れることをPush（プッシュ）、データを取り出すことをPop（ポップ）という

キュー

キューは、先に入れたデータが先に取り出される
キューにデータを入れることをEnqueue（エンキュー）、データを取り出すことをDequeue（デキュー）という

スタック・キュー
　　スタック：後入れ先出し
　　　　　　　PUSH：データ挿入
　　　　　　　POP：最後のデータ削除
　　キュー：先入れ先出し
　　　　　　　ENQUEUE：データ挿入
　　　　　　　DEQUEUE：最初のデータ削除

流れ図（フローチャート）

アルゴリズムを分かりやすく図で表したもの

流れ図の記号

流れ図には、日本工業規格（JIS規格）によって定められた記号が用いられ、プログラム手順だけでなくデータの経路や制御を示すことも可能

アルゴリズムの基本構造

アルゴリズムの基本構造には「順次構造」、「選択構造」、「繰返し構造」がある

順次構造

順番に流れを示したもの

選択構造

条件によって処理が選択される

繰り返し構造

条件によって同一の処理が繰り返される

代表的なアルゴリズム

代表的なアルゴリズムとして「合計」、「探索」、「併合」、「整列」などがある

合計

足し算のこと。足す回数が1回から数回程度の場合は順次構造で記述し、複数回のものは選択構造や繰返し構造で記述する。最も基本的なアルゴリズム

探索（サーチ）

与えられた条件に合致するデータを見つけるためのアルゴリズム。探索、あるいは検索とも呼ばれる。探索には「線形探索法」や「2分探索法」などの手法が知られている

線形探査法（リニアサーチ）

先頭のデータと条件が合致するかどうかを確認し、違っていれば2番目のデータと照合し、という形で、データの先頭から末尾まで、条件に合うものが見つかるまで順番に検索してゆく手法

2分探査法（バイナリサーチ）

対象が、データ群の中央にあるデータより前にあるか、後ろにあるかを判断し、2分したデータ群を取捨選択する。更に、残ったデータ群の中央から前後のどちらにあるかを判断し、取捨選択を繰り返して絞り込んでいく。データを昇順に整列させておく必要がある

併合（マージ）

「併合」とか「結合」という意味。複数あるものを１つにまとめること

整列（ソート）

データの並び順をルールに従って整えること。最も基本的な手法として「バブルソート」がある

バブルソート

バブルソートは、隣接するデータの値を比較して、並べ替えるべきかどうかを判断し、必要に応じて並べ替える動作を繰り返す手法。逐次比較することで、最終的にはデータの先頭から末尾までを順番に整列することができる

比較ソート

2つのデータを比較し、順番に並べ替える方法。バブルソートは比較ソートの一種

挿入ソート

2つのデータを比較し、間に挿入して並べ替える方法

マージソート

整列した後で併合する方法

プログラミング・プログラム言語

アルゴリズムをコンピュータに指示するための文書のことを「プログラム」という。プログラムを記述するには、規則や文法をまとめた「プログラム言語」を用いる。また、さまざまなプログラム言語を用いてアルゴリズムを記述することを「プログラミング」と呼んでいる

プログラム言語の種類

プログラム言語は大きく分けて「低水準言語」（低級言語）と「高水準言語」（高級言語）に分類される。また、観点や特徴によってさらに細かく区分することもできる

低水準言語

低水準言語は、言語仕様がよりコンピュータの解釈方法に近いプログラム言語の総称。CPUが直接解釈できる、2進数の命令コードで記述された「機械語」や、機械語の命令部分を人間でも読めるように記号に変換した「アセンブラ言語」などがある
低水準言語はコンピュータの処理に適した構造をしていますが、人間がプログラミングのために用いることは困難

高水準言語

高水準言語は、人間がプログラミングを行うために、より人間が理解しやすい構造や形式をもったプログラム言語の総称。それぞれ特徴をもった多彩な種類の高水準言語が存在する

代表的なプログラム言語の種類
種　類		特　徴
低水準言語	機械語	CPUが理解できる2進数の命令コードで記述する言語
低水準言語	アセンブラ語	人間が読みやすいように機械の命令部分を記号にした言語
高水準言語	C言語	OS「UNIX」の開発にも用いられている、代表的な構造化言語。アプリケーションソフトウェアから組み込みシステムまで、多様な分野で汎用的に利用されている
	C++	C言語にオブジェクト指向の概念を取り入れた拡張版
	Java	インターネット関連技術や分散システム環境で広く利用されている、オブジェクト指向言語。C++をモデルとして作られている。Javaは「Javaアプリケーション」、「Javaアプレット」、「Javaサープレット」など細分化されている
	COBOL	主に事務処理を目的として開発された言語。汎用コンピュータなどで利用される
	FORTRAN	科学技術に関する計算処理に適するとされる言語。世界初のプログラム言語
	BASIC	比較的初心者向けの、パソコン用プログラム言語。派生形の、Windows上でアプリケーション開発ができる「Visual Basic」が特に有名。インタプリタ型言語

言語プロセッサ

高水準言語で記述されたプログラムは、そのままではCPUが解釈することはできない。そのため、「コンパイラ」や「インタプリタ」などのソフトウェアによって、機械語へと変換、あるいは逐次翻訳されてから、実行される
高水準言語プログラム(ソースプログラム)を機械語プログラム(オブジェクトプログラム)へ変換する、コンパイラやインタプリタのようなソフトウェアは、「言語プロセッサ」と総称される

代表的な言語プロセッサ
種　類	特　徴
コンパイラ	ソースプログラムをまとめてオブジェクトプログラムに変換する。コンパイラを使ってオブジェクトプログラムに変換することをコンパイルという。実行速度は、翻訳する必要がないので速い
インタプリンタ	ソースプログラムを一命令ずつ翻訳と実行をおこなう。実行速度は、実行時に翻訳するためコンパイラに比べて遅い。プログラムがすべてできていなくても実行が可能である。このためデバッグなどは容易

マークアップ言語

指定した箇所に表示方法などの命令を割り当てる特殊文字列や記号を用いる「タグ」を使って、文書の論理構造を記述することができる言語。論理構造には文章や図形のレイアウト、文字の装飾といったものがあり、タグを用いることでこれらを表現する。マークアップ言語の多くは「SGML（Standard Generalized Markup Language）」をベースとしており、現在利用されている代表的なマークアップ言語としては「HTML」や「XML」などがある

HTML (Hyper Text Markup Language)

SGMLを基に開発された、WWW（World Wide Web）上で表示される文書（Webページ）の構造を定義するための言語。テキストや画像に対して、ハイパーリンクやレイアウト、装飾的用語などを追加できる

XML (eXtensible Markup Language)

HTMLの拡張仕様で、目的に応じてタグを定義して拡張できるマークアップ言語。独自の仕様を追加して利用することができる