3-3.情報に関する理論

(4)述語論理

★関係データベース

データベースの形式の一つで、関係モデルと呼ばれる概念に基づいてデータを扱うデータベースのこと
データには必ずカラム(列)とレコード(行)が与えられ、テーブル(表)の中に配置して整理されている。
データの集合をいくつかの2次元の表によって表現する

(5)形式言語
★逆ポーランド表記法
A+BをAB+で表すこと。これと一回使った演算子は2度使わず、普通の計算式を解くのと同じ要領で行っていくことで逆ポーランド表記法の式となる。
例:E=(A+B)×(C-D)
①カッコ内の式から処理をする。
E=(AB+)×(CD-)
②「×」の左側と右側を整理する。()を一つの記号として考える。
E=AB+CD-×
③「=」を最後に持ってくる。
EAB+CD-×=

(6)オートマトン

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

内部状態として任意容量のスタックを持つ有限状態機械である。
※画像で説明したいところですが、wikiのアップロードがうまくいかず割愛

(7)正当性理論

★停止問題

あるチューリング機械がそのテープのある初期状態に対し、有限時間で停止するのか?という問題。
停止問題を解くチューリングは存在しない。なぜなら自身が停止すると判定したなら無限ループを行い、停止しないと判定したならば停止するといった別のチューリング機械が構成できてしまい、それが矛盾となってしまうからである。


(8)計算量

★時間計算量

コンピュータが特定の手順に従って与えられた問題を解くときに必要とする時間のこと。これは実行ステップ数により表記される。


★領域計算量

空間計算量ともいわれ、コンピュータが特定の手順に従って与えられた問題を解く際に必要とする記憶容量のこと。これが少ないと少ないメモリ容量で解くことができることを示す。


★オーダ記号

ランダウの記号ともいわれ、無限大でのふるまいや0付近での振る舞いを大雑把に評価するのに用いられる。記号オー(O)で表記される

★P(Polynomial)問題

計算複雑性理論などといわれ、多項式時間で解ける判定問題の集合である。


★NP(Non-deterministic Polynomial)問題

複雑性クラスの一つで非決定性多項式時間のこと


★NP完全問題

NPに属する決定問題で、NPに属する問題から多項式時間還元可能なもののこと


  • 最終更新:2017-08-18 16:00:51

このWIKIを編集するにはパスワード入力が必要です

認証パスワード