「情報に関する理論」カテゴリーアーカイブ

【基本情報・応用情報】
情報理論、符号理論の考え方、仕組みを習得し、応用する。
コードによる文字の表現を習得し、応用する。
述語論理、形式言語、オートマトンなど、情報に関する理論の考え方、仕組みを習得し、応用する。
正当性理論の考え方、仕組みを習得し、応用する。
AI(人工知能)の考え方、仕組みを習得し、応用する。
コンパイラ理論、プログラム言語論や意味論の考え方、仕組みを習得し、応用する。

【ITパスポート】
情報量の単位を理解する。
情報のデジタル化の基本的な考え方を理解する。

情報に関する理論

 

情報処理技術者試験での学習内容

【基本情報・応用情報】
情報理論、符号理論の考え方、仕組みを習得し、応用する。
コードによる文字の表現を習得し、応用する。
述語論理、形式言語、オートマトンなど、情報に関する理論の考え方、仕組みを習得し、応用する。
正当性理論の考え方、仕組みを習得し、応用する。【応用情報】
AI(人工知能)の考え方、仕組みを習得し、応用する。
コンパイラ理論、プログラム言語論や意味論の考え方、仕組みを習得し、応用する。

【ITパスポート】
情報量の単位を理解する。
情報のデジタル化の基本的な考え方を理解する。

(1)情報理論 ITパスポート 基本情報 応用情報

情報量の概念、事象の生起確率と情報量との関係を理解する。

(2)符号理論 ITパスポート 基本情報  応用情報

アナログとデジタルの特徴、量子化、標本化、A/D変換などの符号化、符号化の目的、情報伝送における信頼性、効率性、安全性の向上などの効果を理解する。

用語例:通信路符号化、ハフマン符号、データ圧縮

(3)文字の表現 ITパスポート 基本情報 応用情報

代表的な文字コードを理解する。

用語例: ASCIIコード、EUC(Extended UNIX Code)、JISコード、シフトJISコード、Unicode、UCS

(4)述語論理 基本情報  応用情報

述語論理の考え方、演繹推論と帰納推論の違いを理解する。

用語例: 関係データベース

(5)形式言語 基本情報  応用情報

形式言語とは何か、言語の定義、演算、種類、文法を理解する。また、BNF、構文図式などの表記法、正規表現、文脈自由文法を理解する。

用語例: 逆ポーランド表記法

(6)オートマトン 基本情報  応用情報

有限オートマトンの概念、形式言語との関係、チューリング機械との関係、状態遷移表、状態遷移図を理解する。

用語例:プッシュダウンオートマトン

(7)正当性理論 応用情報

プログラムの正当性理論とは何か、部分正当性、全正当性の基本的な考え方、仕組みを理解する。

用語例: 停止問題

(8)計算量 基本情報  応用情報

計算量の理論の考え方を理解する。

用語例:時間計算量、領域計算量、オーダ記号、P(Polynomial)問題、NP(Non-deterministic Polynomial)問題、NP完全問題

(9)AI(Artificial Intelligence:人工知能) 基本情報  応用情報

人工知能の基本的な考え方、仕組みを理解する。

用語例:知識工学、学習理論、機械学習、ニューラルネットワーク、ディープラーニング(深層学習)、エキスパートシステム、解析型問題、合成型問題、知識ベース、推論エンジン

(10)コンパイラ理論 基本情報  応用情報

コンパイラの役割、コンパイルの過程、字句解析、構文解析、最適化の基本的な考え方、仕組みを理解する。

用語例:文脈自由文法、意味解析、コード生成、中間言語、目的プログラム、形式言語、オートマトン

(11)プログラム言語論・意味論 基本情報  応用情報

プログラム言語は、処理対象を表現するために構文と意味があること、各言語で構文と意味がどのように定義されるか、データ構造とアルゴリズムがどのように表現されるか、構造化と抽象化がどのように定義されるかなど、基本的な考え方、仕組みを理解する。

用語例:手続型言語、関数型言語、論理型言語、オブジェクト指向言語

 

情報理論

この記事での学習内容 ITパスポート 基本情報 応用情報

情報量の概念、事象の生起確率と情報量との関係を理解する。

情報理論

情報理論とは、ある事象における確率や統計を元に、情報の量を数学的に定義する理論です。

  • 生起確率: ある事象 E が起こる確率。 P(E)
  • 情報量:  事象が起こる確率を P(E) とする時、事象が起こったことを知らされた時に得られる(選択できる)情報の量。

情報量は以下の式で求める。

例)英数字8文字からなるパスワードを1パターン知らされた時に得られる情報量

まずは、生起確率から考える。
英数字は英小文字26文字+英大文字26文字+英数字10文字からなるので、62文字。
パスワード1文字の場合、とある1パターンの確率は 1 / 62 なので、今回の8文字の場合、P= 1 / 628 となる。

よって、公式に当てはめて情報量を求める。

データの単位

コンピュータで扱えるデータ量の最小単位は、2進数の1桁分に当たる、1ビットです。また、8ビットをまとめて1バイトと換算します。通常、データ量はバイトを単位として表します。

更に大きい単位や小さい単位をわかりやすく表記するために、「メガ」や「ミリ」などの補助単位を組み合わせることがあります。

アナログとデジタル

アナログとは、時間の変化に伴って連続的に変化するデータのことです。「連続的」というのは、ある時点の値と別の時点の値の間に異なる値が無限に連続しているような状態です。

対して、デジタルとは、連続して変化する値を離散数(飛び飛びの値)として扱うデータです。離散数として扱うというのは、特定の時点の値を一定の有効桁数の値に当てはめて扱うということです。結果、値は飛び飛びになり、「ある時点とある時点の間」と言うのは存在しなくなります。また、有効桁数で表現できる範囲外の値も存在しません。例えば、有効桁数を小数第一位とした場合、1.5 や -9.9 という値は存在しますが、0.05 と言った値は存在しません。

アナログデータの特徴として、図(グラフ)で表すと波状となります。気温の変化や音の波、光の波などもアナログデータです。
対して、デジタルデータを図(グラフ)で表すと棒グラフ状になります。

A/D変換

コンピュータ内部ではデータは0か1の2進数で表すため、アナログデータをそのまま扱うことは出来ません。そのため、アナログデータは2進数で表すことの出来るデジタルデータに変換して扱います。

このアナログ→デジタルの変換のことを「A/D変換」と言います。A/D変換は以下のような流れで進められます。

  1.  標本化(サンプリング)
    アナログデータから、ある一定間隔ごとに区切って値を抜き出します。このプロセスを「標本化」といいます。
    この段階で、できるだけ細かく区切ることで元のアナログデータに近くなります。
  2.  量子化
    標本化で抜き出した値は、元がアナログデータなので、小数点以下の細かい数値があるため、これをもっとも近い整数値にします。このプロセスを「量子化」といいます。
  3.  符号化(数値を抜き出す)
    区切って量子化した数値を抜き出して、2進数の値とします。このプロセスを「符号化」といいます。

D/A変換

デジタル化したデータは必要に応じて、再度アナログデータに戻す必要があります。(音声データをスピーカーなどで流すなど)

その際の手順をD/A変換といいます。

デジタル→アナログへの変換手順は、A/D変換のサイト逆の手順で行います。

符号理論

この記事での学習内容 ITパスポート 基本情報 応用情報

アナログとデジタルの特徴、量子化、標本化、A/D変換などの符号化、符号化の目的、情報伝送における信頼性、効率性、安全性の向上などの効果を理解する。

用語例:通信路符号化、ハフマン符号、データ圧縮

符号化理論

符号化とは、データを数値に変換し、情報量として表現することで、コード化ともいいます。

符号化理論とは、情報を符号化し、伝送を行う場合の正確性や高速性に関する理論です。

符号化理論には大きく分けて下記の2つがあります。

  • 情報源符号化
  • 通信路符号化

情報源符号化

元のデータに適した形で符号化を行う方法です。

特性として、圧縮率を高めるほど、データサイズは小さくなりますが、負荷が大きくなります。逆に、圧縮率を低くすれば、データサイズは大きくなりますが、負荷は小さくなります。

通信路符号化

符号化されたデータを伝送する際に、伝送路の帯域や雑音、妨害などによって、正しく届かない可能性もあります。
そこで、既に符号化されたデータに冗長なデータを付け加えて再度符号化します。これを通信路符号化と言います。

例えば、データの信頼性を高めるための誤り検出や誤り訂正機能を付け加えます。

ハフマン符号化

データを圧縮する方法の1つで、出現頻度の高いデータには短いビット列を、頻度の低いデータには長いビット列を割り当てて、全体としてデータの圧縮を行う方法です。

例えば、元データが以下の34バイト(1文字1バイト)からなる文字列だったとします。これをハフマン符号化を用いて圧縮してみます。

元データ:AAJABBDBDBFAAAABAABABAFADAAJLAFBAD

・出現する文字は、A, B, D, F, J, L の6文字なので、この6文字に出現頻度に合わせて各文字にハフマン符号を割り当てます。

各文字の登場頻度ハフマン符号データ長
A:16回01ビット
B:8回102ビット
D:4回1103ビット
F:3回11104ビット
J:2回111105ビット
L:1回1111106ビット

表のように出現頻度の高い文字に少ないビットを割り当てるため、ビット列の容量を減らすことが出来ます。
表のハフマン記号に基づいて元データを変換すると、以下のようなビットの並びになります。(便宜上、元の文字の区切りにスペースを入れていますが、実際には空白はありません)

0 0 11110 0 10 10 110 10 110 10 1110 0 0 0 0 10 0 0 10 0 10 0 1110 0 110 0 0 11110 111110 0 1110 10 0 110 

上記のビットの並びで、72ビットになります。元データの34バイトは272ビットになりますので、おおよそ4分の1のデータ量に圧縮できたことになります。

このように元のデータ量を縮小することを「データ圧縮」と呼びます。
その手法には大きく分けると2種類あり、圧縮後のデータから元データが復元できる「可逆圧縮」と、復元不可能な「不可逆圧縮」があります。

 

文字の表現

この記事での学習内容 ITパスポート 基本情報 応用情報

代表的な文字コードを理解する。

用語例: ASCIIコード、EUC(Extended UNIX Code)、JISコード、シフトJISコード、Unicode、UCS

文字コード

アルファベットやかな、漢字といった文字データを扱うために、コンピュータ内部ではそれぞれの文字に、0と1からなるコード番号を割り当てています。これを文字コードといいます。

文字コードには多くの体系があり、体系によって扱える文字種やコードの長さ(ビット数)が異なります。

ASCIIANSI(アメリカ規格協会)が定めた7ビットコード。
英字と数字、記号のみに対応し漢字やかなの規定はない。
Unicode全世界の文字に統一的に対応するための国際規格の標準コード。2~4バイトコード。
文字コードセットとしてUCSが、エンコード方式としてUTFがそれぞれ定められている。
EUCExtended Unix Code(拡張UNIXコード)の略。UNIX上で2バイト文字の漢字・かなを表現できる。
JISコードJIS(日本工業規格)が定めたコード。英数字と半角カナに対応する7又は8ビットのコード体系と、漢字などに対応する2バイト体系がある。
シフトJISJISコードをシフトさせて、ASCIIコードと混在できるようにしたもの。さらに機種ごとの特殊記号などの拡張コードが加えられている。
EBCDICIBMなどの汎用機で用いられているコード。英数字用の文字コード。

日本語の文字コード

ASCIIなどの文字コードでは、基本的に1バイトで1文字を表しますが、1バイトでは最大でも256文字までしか規定することが出来ません。日本語の場合、ひらがな、カタカナ、漢字と種類が多く、特に漢字は「常用漢字」だけでも2,000字近くあり、1バイトで規定することが出来ません。

そこで、1文字2バイトとすることで、表現できる文字数を増やして対応しているのが日本語用の文字コードです。

日本語用の文字コードとしてはUnicode、JISコード、シフトJIS、EUCの4種類が広く用いられています。

文字化け

データを表示した時に、本来の文字列とは異なるでたらめな文字や記号が表示されてしまう現象を「文字化け」といいます。

これは、間違った文字コードが使用された時に起こる現象で、他のシステムからデータを移行・転送した場合にしばしば起こります。また、本来の文字コード体系に含まれていない、ユーザー登録した外字や機種依存文字を含む場合にも発生することがあります。

文字化けを防ぐには、事前に双方で使用している文字コードを確認する必要があります。

述語論理

この記事での学習内容 基本情報 応用情報

述語論理の考え方、演繹推論と帰納推論の違いを理解する。

用語例: 関係データベース

述語論理

述語論理とは、命題の内部の構造を主語と述語の二つの構成要素に分解し、その中の術後部分を扱う理論です。

命題

文章や式で表された事象について、それが真であるか偽であるかが明確に決まるもの。

命題論理

審議の解っている既存の命題をつなげて新しい命題を作ったり、命題を否定したりすること。

推論

ある命題から別の命題を導くこと。
元の命題を「前提」または「過程」といい、導かれた命題のことを結論といいます。
述語論理における推論には、「演繹推論」と「帰納推論」の二種類があります。

演繹推論

複数の前提条件から結論を導く推論方法。代表的なものに、一般的な大前提と個別の小前提から結論を導く三段論法があります。

三段論法の例
大前提:「塩水は塩辛い」
小前提:「海の水は塩水である」
結論 :「海の水は塩辛い」

帰納推論

与えられた事例から一般的法則を導き出す推論方法で、予測や仮説を導くのにも使う推論方法です。

例「海の水は塩辛い」
事例:沖縄の海の水は塩辛い
   三陸沖の海の水は塩辛い
   ハワイの海の水は塩辛い
推論:海の水は塩辛い

 

述語論理や命題、推論といったキーワードは『論理学』の中で用いられる用語です。論理学とは、論理を成り立たせる論証の後世やその体型を研究する学問です。
ここでいう論理とは、思考の法則、思考のつながり、推理の仕方や論証のつながり方のことを言います。

よく言われる『論理的に話す、書く』ということの意味は、つながりを明確に、論証を的確に話し、書く、ということです。

形式言語

この記事での学習内容 基本情報 応用情報

形式言語とは何か、言語の定義、演算、種類、文法を理解する。また、BNF、構文図式などの表記法、正規表現、文脈自由文法を理解する。

用語例: 逆ポーランド表記法

自然言語と形式言語

日本語や英語などの言語は人間が暮らしていく中で自然に発生したため、必ずしも厳密な文法に従っているとは限りません。こういった言語を自然言語といいます。

それに対し、特定の目的のために作られ、厳格な文法に則った言語を形式言語といいます。
コンピュータに指示を与えるためには、プログラミング言語と呼ばれる言語を用いたプログラムを作成します。
このプログラミング言語も形式言語の一つです。

文脈自由文法

言語に関するルールを定めたものが『文法』で、制限の強さの異なる4つの分類があります。ここでいう文法は文の形式を定めるだけで意味についての解釈は行いません。

  • 句構造文法
  • 文脈依存文法
  • 文脈自由文法
  • 正規文法

句構造文法が制限が最も弱く、正規文法が最も制限が強い文法です。形式言語では、文脈自由文法が用いられます。

文脈自由文法は、プログラミング言語を正確に記述するための厳密な形式を定めることが出来る文法です。

例えば、文脈自由文法で『直角とは90度である』と定義する場合、定義が必要なもの(この場合は「直角」)を「非終端記号」といい、それ以上他のものに置き換えることが出来ずに定義が必要でないもの(この場合は「90度」)を「終端記号」といいます。

BNF記法(バッカス・ナウア記法)

BNF(Backus-Naur Form)は、文脈自由文法の文法自体を定義するための記法で、一般的には、バッカス・ナウア記法と呼びます。
プログラミング言語 algol60の文法定義に初めて用いられた記法です。

記号意味
<変数名><非終端記号>(=メタ変数名)
::=左辺が右辺に分解できることを表す。(○○とは▲▲であるの部分を表す)
「または」を表す

メタ変数名

非終端記号のことを「メタ変数名」と呼ぶこともあります。「メタ」というキーワードは情報処理の分野ではよくつかわれるキーワードで、「メタ情報」「メタデータ」という使われ方をします。意味としては、「情報のための情報」「そのデータが持つ、データ自身についての抽象度の高い付加的データ」という意味でつかわれます。

現在では、ヴィルド博士がBNFを拡張して作成したEBNF(拡張バッカス・ナウア記法)も一般的です。
BNFとEBNFの相違は、EBNFでは繰り返し部分を中かっこで囲んだり、終端記号をダブルクォーテーションやシングルクォーテーションで囲んだり、といった違いがあります。

例:

  • <a> ::= <b>  aはbである。
  • <a> ::= 1|2  aは1または2である。

例2(数値の表現をBNF記法で表した例)

  • <数値>::= <数字列>|<符号><数字列>|<数字列>.<数字列>
  • <数字列>::=<数字>|<数字列><数字>
  • <数字>::=0|1|2|3|4|5|6|7|8|9
  • <符号>::= +|-

この例の<数字列>の定義のように、自身の定義の中で自らを定義するような書き方が、情報処理の分野ではよく用いられます。このような定義の仕方を「再帰(的)」と呼びます。

構文図式

構文図式は、BNFで定義した文法の構造、「構文」を視覚的に表現する方法の一つです。

以下に、BNFのと構文図式の例を示します。

<算術式>のBNF表記

  • <算術式>::=<項>|<加減演算子><項>
  • <加減演算子>::= +|-

なお、点線で囲っている部分は0回以上の繰り返しを表します。

正規表現

正規表現とは、いくつかの文字をパターン化して一つの形式で表現する表記法です。BNFを記述するときにも使われます。

正規表現を用いることで、個別の文字列を指定しなくても、また表記にゆれがあっても検索することが可能です。

例えば、以下のようなケースで正規表現を用いて、文字列を検索します。

  • 数値のみで構成されている任意の文字列を検索したい
  • 「ユーザ」と「ユーザー」といった、調音の有無を無視して検索したい

例)メールアドレスの表記ルールを正規表現で表す

正規表現: [\w\d_-]+@[\w\d_-]+\.[\w\d\._-]+

正規表現で用いられる記号の例

  • \w 半角英字(a~z、A~Z)
  • \d 半角数字(0~9)
  • \. 半角ピリオド
  • _ 半角アンダースコア
  • - 半角ハイフン
  • [\w\d_-] []内のいずれか1文字
  • + 直前の正規表現の1回以上の繰り返し
  • . 任意の1文字
  • * 直前の正規表現の0回以上の繰り返し

逆ポーランド記法

演算方法の表記法の一つに「逆ポーランド記法(Reverse Polish Notation : RPN)」があります。
数式を記述する際、演算子を演算対象の後ろに置く方法です。

逆ポーランド記法はコンピュータと相性の良い数式の書き方です。なぜなら、コンピュータは人間と違って与えられた情報を俯瞰的に眺めることは苦手であり、基本的には「右から来た情報を左に受け流す」というのがコンピュータの情報の扱い方なので、逆ポーランド記法のように、情報を流れてきた順序に沿って処理できる方法と相性が良いからです。
また、コンピュータが持つ「スタック」というデータの管理機構で数式を処理しやすい、という面もあります。

スタックは「積み重ねる」という意味で、最後に入れたものを最初に取り出すデータ構造です。

実際に、逆ポーランド記法で書かれた、「135×82÷++」という計算式を、スタックを用いて計算してみましょう。
基本的な動作は、以下の2つです。

  • 数値が来たら、スタックに投入する。
  • + や – などの演算子が来たら、スタックから数値を2個取り出して計算し、その結果をスタックに投入する。

 

正当性理論

この記事での学習内容 応用情報

プログラムの正当性理論とは何か、部分正当性、全正当性の基本的な考え方、仕組みを理解する。

用語例: 停止問題

 

プログラムの正当性

プログラム開発においては、不具合(=バグ)の発生はなかなか避けられないものです。このバグの除去のために作成するプログラムに対して、テストや検証を行いますが、「検証」を行うことで、プログラムの正当性を証明することができます。

ここでいう「プログラムの正当性」とは、「入力条件を満たしたプログラムを実行すると、そのプログラムは確実に停止するとともに出力条件を満たした結果が得られる」ということを指します。完全正当性とも言います。

部分正当性

正当性のうち、「入力条件を満たしたプログラムを実行すると、そのプログラムは出力条件を満たした結果が得られる」ことを部分正当性といいます。

停止性

正当性のうち、「そのプログラムは確実に停止する」ことを停止性といいます。

プログラムの検証において、停止性を証明するためには、特にプログラム内の繰り返し(ループ)部分に着目します。繰り返しの条件が不適切な場合、プログラムが永久に終了しない(=無限ループ)状態となってしまい、停止性を満たすことができません。

停止性問題

計算可能性理論において停止(性)問題(ていしせいもんだい・ていしもんだい、halting problem)は、あるチューリング機械(≒コンピュータプログラムアルゴリズム)が、そのテープのある初期状態(≒入力)に対し、有限時間で停止するか、という問題。アラン・チューリングが1936年、停止性問題を解くチューリング機械が存在しない事をある種の対角線論法のようにして証明した。すなわち、そのようなチューリング機械の存在を仮定すると「自身が停止すると判定したならば無限ループを行い、停止しないと判定したならば停止する」ような別のチューリング機械が構成でき、矛盾となる。

Wikipediaから引用

 

オートマトン

この記事での学習内容 基本情報 応用情報

有限オートマトンの概念、形式言語との関係、チューリング機械との関係、状態遷移表、状態遷移図を理解する。

用語例:プッシュダウンオートマトン

オートマトン

プログラミング言語などの形式言語で記述された分を解釈するための仮想的な機械概念をオートマトンといいます。
コンピュータそのものを数学的な観点からモデル化し、アルゴリズム(=問題解決のための処理手順)を定型化したものです。

元々は「自動人形」を意味している言葉で、現代のコンピュータ技術の基礎原理の一つとして、様々な場面で応用されています。

オートマトンのモデルでは、コンピュータを外部からの入力に応じて内部の状態が変化し外部に出力を行うものとして扱います。

なお、オートマトンとコラム「コンピュータの歴史」で紹介した「チューリング機械」というのは非常に似たものとなっていて、オートマトンの定義を拡張したものがチューリング機械となっています。

チューリング機械は無限の記憶領域を持つとされているが、0と1という記号の並びを入力として、順次処理を行い、後戻りしない、という共通点があります。

有限オートマトン

オートマトンの中で有限個の状態を扱うものを、特に「有限オートマトン」と呼びます。有限オートマトンでは、開始時点の状態(=初期状態)が決まっています。そして、入力によって他の状態へ変化(=遷移)します。最後に成功して終了する状態(=受容状態)のどれかに遷移すれば終了とします。

以下に有限オートマトンの特徴をまとめました。

  • 一つの初期状態を取る。
  • 有限な記憶領域を持つ。
  • 記号列を入力とし、一度に1つずつ読み込む。
  • 後戻りしない。
  • 入力に応じて、他の状態の遷移する。
  • 特定の状態のどれかで終わっていれば成功。受容状態となる。

例えば、「ノートパソコンの電源投入状態」を有限オートマトンで考えてみましょう。
このノートパソコンは、閉じると休止状態となり、開くと休止状態から復帰するものとします。

  • 初期状態は、電源が入っていない「停止」状態です。
  • 「電源スイッチON」という入力によって、状態は「動作」に遷移します。
  • 「動作」状態でパソコンを閉じると「休止」に遷移します。
  • 「休止」状態でパソコンを開くと「動作」に遷移します。
  • 「シャットダウン」という入力によって、「停止」に遷移し、終了します。

他に身近な例では、有限オートマトンの考え方で表現できるものとしては、「自動販売機」があります。

状態遷移表と状態遷移図

オートマトンの状態を表すものには、「状態遷移表」と「状態遷移図」があります。

どの状態の時に、どの入力があると、どの状態に変化(遷移)するのかを示す規則を、表にしたものが状態遷移表、図にしたものが状態遷移図です。

先述のノートパソコンの例を元に、状態遷移表と状態遷移図を確認してみましょう。

まずは、状態遷移表を示します。

縦が遷移前の状態、横が入力、表の中は遷移後の状態を表しています。なお、標柱の横棒は遷移がないことを示します。

次に状態遷移図を見てみましょう。

状態を楕円形で、入力を矢印によって、状態の遷移を視覚的に分かりやすいように表現しています。

プッシュダウンオートマトン

有限オートマトンの「状態」と「入力」に加えて、無限の容量の「スタック」を持っているのが、プッシュダウンオートマトンと呼ばれるものです。

スタックを持つことに加え、以下の点で有限オートマトンとは異なっています。

  • スタックのトップ(=最上位の要素)でなすべき状態遷移を判断する。
  • 遷移実行の一部として、スタック操作を行うことが出来る。

 

計算量

この記事での学習内容 基本情報 応用情報

計算量の理論の考え方を理解する。

用語例:時間計算量、領域計算量、オーダ記号、P(Polynomial)問題、NP(Non-deterministic Polynomial)問題、NP完全問題

計算量

ある問題を解く場合に、問題を解く手順(=アルゴリズム)は複数存在します。例えば、以下のような単純な掛け算を取ってみても、複数の計算方法があります。
例)3×1977

  • 3を1977回足す
  • 1977を3回足す

この例の場合、明らかに1977を3回足すほうが計算の回数が少なく、優れた解法といえます。

この例のように、問題を解くためのアルゴリズムは一つとは限らず、いくつかあるアルゴリズムから最良のものを選ぶためには、アルゴリズムを定量的に評価する指標が必要となります。この指標が「計算量」と言われるものです。
アルゴリズムに基づいて処理するデータ量によって、プログラムの実行時間がどのように変化するかを表し、アルゴリズムの複雑さをはかることが出来ます。
時間計算量はあるアルゴリズム手順(=処理手順)の数と繰り返し回数の最大数で表すことが出来ます。

解く問題の種類によっては、計算量が一定でない場合があります。例えば検索処理です。

検索処理では場合によっては、処理開始直後に見つけられることもあれば、最後の最後で見つかることもあります。このような一定でない計算量を表現するために、最大計算量と平均計算量という考え方もあります。それぞれ、計算量の最大値と平均値を示すものです。
計算量の代表値としては、平均計算量のほうが適切ですが、平均計算量は算出が難しい場合があり、最大計算量で評価することも多くあります。

時間計算量の他に、「領域計算量」も評価指標として使うことがあります。この場合は使用するメモリの容量を指標とし、より使用メモリの少ないアルゴリズムを良いアルゴリズムとしてみなすものです。
但し、現在はメモリが大容量化、かつ低価格化しているので、時間計算量がより優先される傾向にあります。

オーダ記法

良いアルゴリズムを考える場合に、「実行速度が早い」という点は大変重要ですが、実際の速度というのはコンピュータの性能によって異なってきます。
そこで、実行にかかる時間の目安を「時間計算量」として計算して評価します。その際に時間計算量は「O(オーダ)」という記号を使って表します。この表記法を「オーダ記法」といいます。

AI(Artificial Intelligence:人工知能)

この記事での学習内容 基本情報 応用情報

人工知能の基本的な考え方、仕組みを理解する。

用語例:知識工学、学習理論、機械学習、ニューラルネットワーク、ディープラーニング(深層学習)、エキスパートシステム、解析型問題、合成型問題、知識ベース、推論エンジン

人工知能

人間の知的活動をコンピュータに行わせるための技術を「人工知能」と呼びます。英語表記の「Artificial Intelligence」を略してAI(エーアイ)とも呼ばれます。

人工知能は基盤となる技術によって、三種類に分類されます。

知識ベース型

「知識ベース」とは、専門家の知識や経験をデータベース化したものです。知識ベース型人工知能は、この知識ベースを活用して問題の解決方法を見つけ出すものです。

代表的な知識ベース型人工知能には、エキスパートシステムがあります。

エキスパートシステムとは、知識ベースとあわせて、推論エンジンを使います。推論エンジンは状況に合わせて推論を行なっていく機能を持つもので、知識ベースと推論エンジンを組み合わせることでエキスパート(=人間の専門家)と同じような応答をするものです。

ファジィ型

「ファジィ」とは「ぼやけた」という意味です。ファジィ型人口では、真と偽の教会が「ぼやけた」もの、つまり曖昧な値を扱います。
例えば「安全」か「危険」かという二者択一だけではなく、「やや危険」といった中間的な状況も扱い、最適な答えを導き出していきます。

「安全」や「危険」であれば、安全度もしくは危険度と言うかたちで数値化することができれば、人工知能を用いなくても答えを導くことが出来ますが、ファジィ型人工知能を使うことで負荷の大きな数値計算をすることなく、効率的に判断を行うことが出来ます。

学習型

学習型人工知能とは、入力されたデータに応じて、答えを導く論理構造を変化させていくものです。

代表的な学習型人工知能にはニューロコンピュータシステムがあります。
ニューロコンピュータコンピュータシステムは、人間の脳の構造をモデル化した、ニューロネットワークモデルに基づくものです。

身近な例としては、迷惑メールフィルタなどに用いられている「機械学習」や、囲碁や将棋のソフトなどで注目を浴びた「ディープラーニング」などが上げられる。

 

コンパイラ理論

この記事での学習内容 基本情報 応用情報

コンパイラの役割、コンパイルの過程、字句解析、構文解析、最適化の基本的な考え方、仕組みを理解する。

用語例:文脈自由文法、意味解析、コード生成、中間言語、目的プログラム、形式言語、オートマトン

言語プロセッサ

コンピュータが直接実行できるプログラムは「機械語」のプログラムです。
機械語のプログラムは、人間がみると単なる数値(2進数)の並びで、人間が作成したり呼んだりするのには不向きです。

そのため、人間がプログラムを扱いやすくするために、プログラミング言語が存在します。プログラミング言語で書かれたプログラムのことを「ソースコード」あるいは「原始プログラム」と呼びます。

「ソースコード」はそのままではコンピュータ上で実行することは出来ません。実行可能な機械語のプログラムに変換することが必要になります。この変換処理を行うのが「言語プロセッサ」と呼ばれるものです。

言語プロセッサにはいくつかの種類があります。

  • アセンブラ: 機械語と1対1に対応したアセンブラ言語を機械語に変換するプログラム
  • コンパイラ: ソースコードを一括して機械語に変換するプログラム
  • インタプリタ: ソースコードを機械語に変換しながら実行するプログラム
  • ジェネレータ: 必要な条件をパラメータで支持することで、目的に応じたプログラムを自動生成するプログラム

コンパイラ理論

コンパイラで実行可能なプログラムを生成する場合、直接実行可能なプログラムを生成するわけではありません。これは、大規模なプログラムになると、一つのプログラムのソースコードを複数に分けて扱う必要が出てくるからです。

実行可能なプログラムを生成する第一段階は、ソースコードを変換して「オブジェクトコード」または「目的プログラム」を生成することです。
この「オブジェクトコード」はソースコード単位で作られます。

第二段階として、オブジェクトコードをつなげて実行可能なプログラムを生成します。
この段階では、ライブラリと呼ばれるオブジェクトコードの集合体が使われることもあります。
ライブラリは多くのプログラムで使われるであろう、ファイル入出力などの機能をあらかじめオブジェクトコードとして用意しておいたものです。

なお、第二段階で使われるプログラムのことを「リンカ」または「リンケージエディタ」とも呼びます。

コンパイラの処理手順

コンパイラがソースコードからオブジェクトコードを生成する時、いくつかの段階を経て処理が行われます。

典型的な流れは、字句解析→構文解析→意味解析→最適化→コード生成、となっています。

  1. 字句解析: ソースコードを最小の単位の語句(トークン)に分解
  2. 構文解析: トークンの並びを、定められた文法に従って解析
  3. 意味解析: トークンの意味を考慮した解析
  4. 最適化&コード生成: プログラムの高速化、サイズの縮小

 

プログラム言語論・意味論

この記事での学習内容 基本情報 応用情報

プログラム言語は、処理対象を表現するために構文と意味があること、各言語で構文と意味がどのように定義されるか、データ構造とアルゴリズムがどのように表現されるか、構造化と抽象化がどのように定義されるかなど、基本的な考え方、仕組みを理解する。

用語例:手続型言語、関数型言語、論理型言語、オブジェクト指向言語

プログラミング言語の種類

プログラミング言語には多くの種類があり、処理の手順などによって分類することが出来ます。

代表的なプログラミング言語の分類

言語の種類概要代表的な言語
低水準言語機械語コンピュータが直接実行できる言語
アセンブラ言語機械語と1対1に対応した命令語からなる言語CASLⅡ
高水準言語手続型言語処理内容を記述した命令を、順を追って実行する言語FORTRAN
COBOL
C言語
BASIC
非手続型言語関数型言語関数と呼ばれる式を組合せた後世の言語LISP
論理型言語論理式で記述していく言語Prolog
オブジェクト指向言語すべての事象をオブジェクト(モノ)として扱う言語Java
C++
Objective-C