情報科学の基礎理論

数・情報量の表現

数の表現

コンピュータプログラムにおいて数の表現法は重要です。具体的に直ぐに使うのは、2進数法と10進数法と、あと16進数法などです。また、これらの数の表現が異なるもの同士の基数変換や2進数同士の掛け算・足し算などは覚えておきましょう。

まず、2進数法・10進数法・16進数法の数としての表現法を学びましょう。

2進数法
16進数法
次に、2進数法と10進数法による基数変換や、16進数法と10進数法との基数変換について学びましょう。

情報量の表現

情報量の単位や表現は、コンピュータを理解するときに必須のものになります。メモリやディスクのアクセス時間＆容量を理解するときにも使います。

ビットとバイト。ちなみに、1バイト＝8ビットと覚えておけば十分でしょう。2進数で表現されるビットですが、２種類の情報を持つとも言えます。つまり、4ビットならば16種類の情報が表現できる。すなわち、nビットを用いると、 $2^{n}$ になりますが、1バイトと言うと、その情報量は、256（= $2^{8}$ ）です。
コンピュータで使用する補助単位を確認すると、大体、記憶容量の補助単位とアクセス時間の補助単位という2つに大別できます。

情報科学と統計学

情報科学に特に必要なのは統計学であると思うので、ここでは、統計学の基礎的事項についておさらいしましょう。各項目に重要な事項についての解説が書いてありますので、自分で使いながら覚えましょう。

データ構造とアルゴリズム

データ構造

データ構造（データこうぞう、data structure）とは、計算機科学においてデータを整理、格納、操作するための方法や手法のことです。データ構造は、データの性質や目的に応じて選択され、効率的なアクセスや処理を可能にします。配列、リスト、スタック、キュー、ツリー、グラフなどが代表的なデータ構造であり、それぞれ異なる特性や利点があります。データ構造の選択は、プログラムの効率性や処理速度に大きな影響を与えます。

基本的なデータ構造

基本的なデータ構造には、プログラミングや計算機科学で広く使われるいくつかのものがあります。

主なものを以下に示します：

配列 (Array): 要素が連続したメモリ領域に格納されるデータ構造です。インデックスを使用して要素にアクセスできます。配列は同じ型の要素を保持し、サイズが固定されている場合と可変の場合があります。
リスト (List): 要素が順序付けられ、個々の要素がポインタやリンクを使って連結されるデータ構造です。リストには一方向リスト、双方向リスト、循環リストなどがあります。
スタック (Stack): データを一次元的に積み重ねるデータ構造で、後入れ先出し (LIFO: Last In, First Out) の特性を持ちます。主な操作は push（積む）と pop（取り出す）です。
キュー (Queue): データを一次元的に並べるデータ構造で、先入れ先出し (FIFO: First In, First Out) の特性を持ちます。主な操作は enqueue（追加）とdequeue（取り出し）です。
ツリー (Tree): 階層構造を持つデータ構造で、根から始まり複数の子を持つ節点（ノード）で構成されます。ツリーは木構造を持ち、一般的には親子関係や祖先子孫関係を表現します。二分木、二分探索木、平衡木などがあります。
グラフ (Graph): ノードとそれらを結ぶエッジ（枝）から成るデータ構造で、異なるノード間の関係性を表現します。有向グラフと無向グラフがあり、グラフ内でのパスや経路を見つけるための様々なアルゴリズムが存在します。

これらの基本的なデータ構造は、プログラミングにおいてデータを効率的に操作したり、問題を解決したりするための基盤となります。それぞれのデータ構造は異なる特性を持ち、適切なコンテキストで使用されます。

アルゴリズム

アルゴリズムは、ある問題を解決するための手順や手法のことです。データ構造と同様に、計算機科学やプログラミングにおいて非常に重要です。適切なアルゴリズムを選択することで、問題を効率的に解決できます。

アルゴリズムの種類には多くのものがありますが、以下にいくつかの代表的なものを挙げます：

探索アルゴリズム

線形探索: データの集合から目的の要素を順番に調べて探す方法。
二分探索: ソートされたデータ集合に対して中央の要素と目的の要素を比較し、探索範囲を狭めていく方法。

ソートアルゴリズム

バブルソート: 隣接する要素を比較しながら順番に並べ替える方法。
クイックソート: ピボットを選択し、それより小さい要素をピボットの左側に、大きい要素を右側に分割していく再帰的な方法。

グラフアルゴリズム

幅優先探索 (BFS): グラフ内の全てのノードを同じ深さで探索する方法。
深さ優先探索 (DFS): ある枝から始めて、最も深い部分まで探索し、それができなくなったら戻って探索を続ける方法。

動的計画法:

最適な部分問題の解を組み合わせて、全体の問題の最適解を求める方法。ナップサック問題や最長共通部分列問題などに使用されます。

これらのアルゴリズムは、様々な問題に対する解法を提供します。アルゴリズムの選択は問題の性質や制約によって異なります。そのため、アルゴリズムの理解と適切な選択が重要です。

アルゴリズムと構造化

アルゴリズムと構造化は、プログラミングにおいて密接に関連しています。構造化とは、プログラムを論理的に整理し、理解しやすく、保守しやすくするための手法です。アルゴリズムはそのプログラムの中核を担い、問題の解決方法を定義します。

以下に、アルゴリズムと構造化の関係について説明します：

構造化されたアルゴリズム: アルゴリズムは通常、特定の問題を解決する手順を記述したものです。これらの手順を構造化することは、プログラムの可読性と理解性を向上させます。例えば、手続き型プログラミングでは、手順を関数や手続きに分割することで構造化されたアルゴリズムを作成します。
モジュール化: プログラムを構造化する一つの方法は、モジュール化です。大きな問題を小さな部分問題に分割し、それぞれの部分問題に対して独立したアルゴリズムや手順を適用します。これにより、複雑な問題を解決するための大規模なプログラムを管理しやすくします。
データ構造とアルゴリズムの統合: データ構造とアルゴリズムは密接に結びついています。例えば、特定のデータ構造に対する効率的な操作を提供するアルゴリズムがあります。これらのアルゴリズムを選択することで、プログラムの性能を向上させることができます。また、適切なデータ構造の選択は、アルゴリズムの理解や実装を支援します。
制御構造とアルゴリズム: 制御構造は、アルゴリズムの実行フローを制御します。条件文、繰り返し文、分岐などの制御構造を使用して、アルゴリズムの流れを制御します。これらの制御構造を適切に使用することで、アルゴリズムを構造化し、意図した動作を実現することができます。

結論として、アルゴリズムと構造化はプログラミングにおいて不可分の関係にあります。構造化されたアルゴリズムは、プログラムの保守性、拡張性、および品質を向上させるための重要な手段です。

プログラミング言語とプログラミング

プログラミング言語には数多の種類が存在し、日々改良されている。C言語、COBOL、ＪＡＶＡ言語などは、代表的なプログラミング言語となる。

プログラミング言語

プログラミング言語とは、コンピュータに対する一連の動作（「入力する」、「記憶する」、「計算する」、「出力する」）を指示するための記述をする人工言語の総称。プログラミング言語はプログラムを書くための言語であり、それによってコンピュータは何らかの計算やアルゴリズムを実行し、場合によってはプリンター・ロボットなどの外部装置を制御する。その上で、次のような言語に分類される。

　低水準言語
- 　機械語（マシン語）
- 　アセンブリ言語
　高水準言語

高水準言語の種類

言語プロセッサ

言語プロセッサ（げんご－、language processor）はあるコンピュータ言語を別のコンピュータ言語に翻訳・変換するソフトウェアの総称。コンピュータは機械語によって命令実行するため、それ以外の言語によるプログラムを機械語へ翻訳する必要がある。言語プロセッサによって変換される前のプログラムをソースプログラム（原始プログラム）、変換後のプログラムをオブジェクトプログラム（オブジェクトモジュール）と呼ぶ。

マークアップ言語

マークアップ言語（マークアップげんご。英: markup language）は、テキストの論理構造や修飾情報などに関する仕様を、テキストファイルの中にテキストとともに記述するための言語で、コンピュータ言語の一種である。文章に対するそれらの指定をマークアップ (markup) と呼ぶ。現代において最も有名なマークアップ言語は、World Wide Webの基盤技術の1つであるHTMLであろう。元々、"markup"という語は出版業界で著者、編集者、印刷者の間で指示を伝える方法を意味していた（語源を参照）。

SGMLとSGMLから派生したマークアップ言語は、タグと呼ばれる構文で構造を表現するがが、他のマークアップ言語では独自の文法でマークアップを行う。

ホームページ（Webページ）

ホームページ (homepage) とは、ウェブブラウザを起動した時や、多くのウェブブラウザに存在するホームボタンを押した時に表示されるウェブページ（Webページ）のことである。スタートページともいわれる。Webページを記述するときにはHTML（Hypertext Markup Language）を利用し、その内容を閲覧するときにはブラウザを使用する。

Webページには、文字、静止画、動画、音声などの多様な種類の情報を相互にリンクさせ、そのリンクをたどりながら、関連する情報間を自由に移動できる「ハイパリンク」の機能がある。なお、ハイパリンクを実現しているテキストファイルのことをハイパテキストという。

Webページは、HTML要素、HEAD要素、BODY要素の三つの基本要素で構成されています。

HTML文書の構成

<!DOCTYPE（HTMLの規格）>
<HTML>
 <HEAD>（TITLE要素などのページ内で視覚化されないメタデータが入る）</HEAD>
 <BODY>（内容）</BODY>
</HTML>

主なHTML要素の意味

主なHTML要素の意味
要素名	意味
HTML	マークアップ言語としてHTMLを使用していることを示す。
HEAD	コンテンツのメタデータ
BODY	HTML文書の本文
A	ハイパリンク `<a href="☆">`の☆にリンク先のURLを記述する
IMG	画像イメージ `<img src="★">`の★に画像ファイルのURLを記述する
TABLE, CAPTION, TR, TH, TD	表組み
P, BR, B, I, U	段落、改行、注目付け（強調）、慣用的なテキスト（斜体）、非言語的注釈 (下線)

脚註

^ HTML5は、DTDによる定義ではないので、SGMLではないが、HTML4.01 まではSGMLだったので、便宜上SGML族とした。