ITの基礎知識|ITパスポート・基本情報

正当性理論

2017.09.19

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

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

用語例: 停止問題

 

プログラムの正当性

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

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

部分正当性

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

停止性

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

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

停止性問題

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

Wikipediaから引用

 

形式言語

2017.09.19
この記事での学習内容 基本情報 応用情報形式言語とは何か、言語の定義、演算、種類、文法を理解する。また、BNF、構文図式などの表記法、正規表現、文脈自由文法を理解する。用語例: 逆ポーランド表記法自然言語と形式言語日本語や英語などの言語は人間が暮らしていく中で自然に発生したため、必ずしも厳密な文法に従っているとは限りません。こういった言語を自然言語といいます。それに対し、特定の...

Read more...

述語論理

2017.09.19
この記事での学習内容 基本情報 応用情報述語論理の考え方、演繹推論と帰納推論の違いを理解する。用語例: 関係データベース述語論理述語論理とは、命題の内部の構造を主語と述語の二つの構成要素に分解し、その中の術後部分を扱う理論です。命題文章や式で表された事象について、それが真であるか偽であるかが明確に決まるもの。命題論理審議の解っている既存の命題をつなげて新しい命題を作...

Read more...

コンピュータで使われている文字コードの説明のうち、適切なものはどれか。 ア: ASCIIコードはアルファベット、数字、特殊文字及び制御文字からなり、漢字に関する規定はない。 イ: EUCは文字コードの世界標準を作成しようとして考案された16ビット以上のコード体系であり、漢字に関する規定はない。 ウ: Unicodeは文字の1バイト目で漢字か分かるようにする目的で制定され、漢字とAS...

Read more...

音声信号をデジタル化する。図の時刻1から時刻5のタイミングで標本化を行い、4段階に量子化(標本点に最も近い段階を選択)を行なった。その後2ビットで符号化を行なった。結果は「11 01 00 10 11」であった。同じ手法でデジタル化を行うと、「01 00 10 11 01」となる音声信号を表す図はどれか。

Read more...

文字の表現

2017.09.14
この記事での学習内容 ITパスポート 基本情報 応用情報代表的な文字コードを理解する。用語例: ASCIIコード、EUC(Extended UNIX Code)、JISコード、シフトJISコード、Unicode、UCS文字コードアルファベットやかな、漢字といった文字データを扱うために、コンピュータ内部ではそれぞれの文字に、0と1からなるコード番号を割り当てています。これを文字コード...

Read more...

符号理論

2017.09.14
この記事での学習内容 ITパスポート 基本情報 応用情報アナログとデジタルの特徴、量子化、標本化、A/D変換などの符号化、符号化の目的、情報伝送における信頼性、効率性、安全性の向上などの効果を理解する。用語例:通信路符号化、ハフマン符号、データ圧縮符号化理論符号化とは、データを数値に変換し、情報量として表現することで、コード化ともいいます。符号化理論とは、情報を符号化し、伝送を...

Read more...