こなさんち

しがないフリーランスエンジニアの備忘録。

基礎理論～誤差～

情報処理技術者試験

誤差って何だ

皆さんが知っている誤差、というのは「実際のものと異なる」という認識でしょう。

例えば、私に注がれたジュースとあなたのジュースが違う！的な。

今回は、コンピュータの世界での「誤差」を紹介します。

なぜ誤差が生まれるのか？

コンピュータの世界では、数字や文字などは一定量の桁が確保されます。

なぜ？どこに確保されるの？という話はまた別記事で。

今回は、 数値は有限なんだ という前提のもとお話します。

さて、有限ということは、その桁数を超過してしまったらどうなるのでしょうか。無視されます。スルーされます。なかったコトにされます。

この超過分を「誤差」と言います。誤差には他にも種類があり、特にFEでは説明できる必要があります。

絶対誤差

これが一番シンプルな「誤差」です。

真値 （本当の値）と、有限桁数からはみ出したために真値とずれた観測値との誤差のことです。

例えば、小数点が0桁、すなわち整数のみの桁があります。（PG経験者は整数型の変数と於いてください。）

これに、1234.5という数値を入れます。小数を入れるため、最後の「0.5」が省かれてしまいますね。

この場合の真値は1234.5、測定値は1234.0、0.5が消えてしまったので誤差は「0.5」になります。

意外とシンプル。

相対誤差

相対誤差は、絶対誤差と相対誤差の比率のこと。

なので、

{ \displaystyle 絶対誤差/真値 = 0.5 / 1234.5 = 5/12345 = 1/2469 }

となります。

誤差の発生原因とその種類

丸め誤差

これは一番覚えやすいですね。

四捨五入です。

四捨五入すると末尾の数値が四捨五入する前と当然変化します。

四捨五入する(=丸める）事によって生じるので、丸め誤差と言われます。

桁落ち

ここでは、有効桁数の重要性も感じられます。

例えば、「0.0043」という数値。

この数値にとって重要なもの、有効なものは「43」であり、この桁数（今回でいうと2桁）を有効桁数といいます。

さて、桁落ちとは、この有効桁数が「落ちてしまう」ことを指します。

例えば

{ \displaystyle 356.3622 - 356.3579 }

有効桁数が7桁 - 7桁 です。この答えこそ先程の「0.0043」です。

有効桁数が7桁から2桁に落ちました。これが「桁落ち」です。

要因

値の近い数値同士の減算

情報落ち

次は「情報が落ちてしまう」誤差です。どういうことでしょうか。

例えば、「小数点以下の有効桁数が4桁」の数値から「小数点以下の有効桁数が8桁」の数値を引いた場合の答えが

小数点以下の有効桁数が4桁しか許容しない場合 に生じます。

{ \displaystyle 356.3622 - 0.00000015 = 356.36219985 }

ですが！

小数点以下の有効桁数が4桁しか許容しない ため、答えは { \displaystyle 356.3622 - 0.00000015 = 356.3621 }

となってしまい、正しい答えと異なってしまうんです。

要因

桁の大きい数と、極端に桁の小さい数の加減算。

打切り誤差

これは一言。

有効桁数がとんでもなく大きい数の計算の途中で打ち切ることによって生じる、正確な値との誤差。

出題されること

誤差の発生原因や、回避策が問われます。主に、丸め誤差や桁落ちは頻出です。なんでこの誤差が生まれるのか？知っておきましょう。

以上！今回は誤差についてでした。

基礎理論～浮動小数点数～

情報処理技術者試験

2進数での小数

小数って、10進数だと「1.24」のようなものですね、当たり前です。

さて、2進数だと？という話です。

固定小数点

例えば2進数の「101.01」（10進数でいう5.25）を8ビットの固定小数点数で表現するときに、4桁目の後を小数点の場所と決めると、次のようになります。

0101.0100

小数点の位置が固定されているため、固定小数点数といいます。

ですが、これはあまり出題しません。

浮動小数点

これが本題。

IEEE754

これは知っておきたい IEEE 。IEEEは、標準化機構。ITのみならず、様々な事柄を標準化する機構です。

このIEEEは、決まりごとに番号がつきますが、その中で、浮動小数点数に関する規定を IEEE754 といいます。

表現方法

IEEE754では、小数を32bitで表されます。

左から1bit、8bit、23bitと分割されます。

符号部 指数部 仮数部
1bit 8bit 23bit
別名:S 別名:E 別名:M

符号部

プラスの小数なら0、マイナスの小数なら1です。

指数部

これは、正規化を行います。正規化については以下説明します。

0.375(10進数) -> 0.011(2進数) -> 0.11 * 2^-1 (正規化)

小数点以下を1から始まるようにすることを正規化といいます。具体的には、累乗で位置を調整するんです。

IEEE754では、この指数(今回の場合 -1 )に 127を足します。->126

この127をバイアス値と言います。バイアス値を足した8bitを指数部とします。

よって、「01111110」が指数部です。

仮数部

0.375(10進数) -> 0.011(2進数) -> 0.11 * 2^-1 (正規化)

正規化後の 0.11 の小数点以下部分を仮数部と言います。

つまり、「11」を23bitにした「11000000000000000000000」が仮数部です。

符号部 指数部 仮数部
1bit 8bit 23bit
別名:S 別名:E 別名:M
0 01111110 11000000000000000000000

次回

誤差について

基礎理論～オートマトン～

情報処理技術者試験

オートマトンとは

一般的には、 状態遷移図 や 状態遷移表 と表されます。

どういったものかと言うと、

f:id:cresta522:20190701195856p:plain
オートマトン

こんなもの。

なにこれ？と思うかもしれませんが、個人的にはサービス問題だと思います。詳しく説明していきます。

有限オートマトン（オートマトン基礎）

オートマトンには複数種類がありますが、FEやAPなどで取り上げられるのはこの 有限オートマトンというものです。

簡単に言うと、 状態遷移表 という「地図」と 入力データ という「道順」を与えられるのでゴールまでたどり着いてください、という問題です。

上図は「状態遷移図」です。

  • q1
  • q2
  • q3

という状態（地図で言う建物）があり、矢印を辿って q2 に辿り着こうね、という地図です。

最初のスタート地点(q1)を 初期状態 と言い、◎の q2を 受理状態 といいます。用語です。

さて、この地図と道順を渡されます。

「01101」という順番で行ってね！ という形で入力値が渡されますので、

q1 からスタートして、

q1 -> 0 -> q1 -> 1 -> q2 -> 1 -> q2 -> 0 -> q3 -> 1........あれ？先の道がない。

このように、目的のゴールまでたどり着けない状態を 不受理されなかった 状態といいます。

成功例は、「01」や「011」などですね。

問題では「受理される入力データを選びなさい」という問題が頻出です。

基礎理論～グラフ理論（木構造の巡回）～

情報処理技術者試験

初めに

前回の記事では、木構造について紹介しました。

今回は、データの探索方法についてです。

データの探索とは？

木構造なので各節の値を行ったり来たりして、「目的のデータはどこじゃろかい」と探します。

「ここかな？ちがう」「ここも違う」と繰り返して、次の節を見に行くんです。

この次の節の選び方を巡回方法といいます。

巡回方法

巡回方法は「このデータを見つけるまでに、この方法を使用すると何回の巡回で見つかりますか？」という問題にて使用されます。

幅優先順

f:id:cresta522:20190630225137p:plain
幅優先順

深さ優先順（先行順）

親が先行します。

f:id:cresta522:20190630230330p:plain
先行順

深さ優先順（中間順）

親が中間にいます。

f:id:cresta522:20190630230442p:plain
中間順

深さ優先順（後行順）

親が最後 です。

f:id:cresta522:20190630230643p:plain
後行順

基礎理論～グラフ理論（木構造）～

情報処理技術者試験

初めに

グラフ理論2ということで、何を書くかって言うと、木構造について。

前回は

cresta522.hateblo.jp

です。

木構造も、グラフの一種です。点があって、それを結ぶ辺がある。これは立派なグラフの形。

木構造というのは、1つの点からn個の点に対して辺があり、その接続先の点からまたn個の点に向けて辺が結ばれる形です。樹形図が想像しやすいでしょう。

この点の数などによって分類分けがされます。

どんなときにこれが使われるのか？というと、データ探索のときですね。

木構造の一番最上位の点(根やルートと呼ぶ)から、「さーて目的のデータはどこにあるかなー」と、伸びる辺をたどって各点(節やノードと呼ぶ)を探索します。

探索の基本

基本的に、各ノードの中には数値が入っておりその数値を見て次の検索先を決めていきます。

グラフのデータ構造の種類

根からの深さ、各節と親の節の上下関係などによってこのグラフって、名称が変わります。それを紹介します。

参考画像書きました。

（塾の合間だったから字は汚いです）

ヒープ

子の節と親の節の間に、

子 ＞ 親

もしくは

子 ＜ 親

が存在するものを ヒープ と呼びます。

二分探索木

左の子、親、右の子の節の間に、以下の制約が存在します。

左の子の節の値 ＜ 親の節の値 ＜ 右の節の値

これを 二分探索木 と呼びます。

現在の節より大きい値を探すのか、小さい値を探すのか？で右へ行くのか、左へ行くのか決めるようなものになります。

出題頻度も高く、「こういうデータを探すとき、どういう形で値を探しますか？」って出てきますね。

AVL木

二分探索木のうち、根から最下層の節までの深さの差が、０ or １のものを AVL木 と呼びます。

B木

根以外の節は、同じ数の子を持つ木を B木 といいますね。

基礎理論～グラフ理論～

情報処理技術者試験

こんにちは。Twitterでは鬱真っ最中のこなちゃんです。

テーマ

グラフ理論。

これは、実際にPythonを使用して解説をしたQiitaのサイトもありますが、プログラミング寄りの記事で、FE,APにおける趣旨とは異なってしまうため、プログラムでどう書く？っていう話はしません。

グラフ理論とは

「グラフ」と聞いて、通常は棒グラフや円グラフ、折れ線グラフを想像しますよね。

ですが、情報学で言うグラフ理論の グラフ は別名 ネットワーク とも称され、「点と点を結んだ線」の集合を分析するものになります。

グラフ理論の例

例えば、日本地図の各県庁所在地に点を置き、隣県の点を結びます。

するともちろん、47の点と、隣り合う都道府県への辺が現れます。

それを見て、

「おっ、長野県が一番隣県多いじゃん」

と分析できます。

このように「点と辺の集まりから分析するもの」がグラフ理論です。

以下、グラフというのは「点と辺の集まり」だということを前提に進めていきます。

グラフの種類

無向グラフ

これが一般的なグラフです。

先程の都道府県の例の見たまんま、辺に「向き」なんて存在しないです。

敢えて、「無向グラフ」というからには対になるものがあります。次。

有向グラフ

一般的なグラフ（無向グラフ）と異なり、「方向」が付与されたものです。

？向き？？

そうです、向きです。

先程の都道府県庁を結んだグラフに於いて「さて、日本一周しよう！」としたときに、

出発はここで、次はここで、と番号を振ったり、矢印を引いたりしますね。

この矢印が辺の「向き」です。

つまり、各点や辺に順番のような無向グラフ＋αの意味が付与されたものでした。

途中だよ

元気ないしこれから仕事なので一旦休憩。

また書きます。

基礎理論～集合と論理～

情報処理技術者試験

論理演算

今回は集合と論理です。

集合って高校の時習いましたね、数Aでした。

プログラマはできて当然？

実はエンジニアでプログラムをごりごり書いてる方は無意識に得意になっているはずです。

条件分岐の if で書いているからです。

では改めて今回はそんなifの中身である 集合と論理 に触れていきましょう。

論理演算

論理演算 (別名 ブール演算 )は、 0 or 1、 YES or No など、二値の判定をする計算です。

ブール と聞いて、扱う言語によってはピンと来る方もいるかと思います。Boolean または bool のことです。わからない方はプログラムを書いていくと学べます。

さて、 論理演算 って難しいワードを出されると「ふええ」ってなるかもしれませんが、前述したとおり結局は「二値の判定」です。どんな難しい計算も、砕いて砕いて砕けばこの「YES or NO」の二値に収束します。

論理和

A または B のとき 「YES」 となるお話です。

例えば、「晴れまたは曇のときに洗濯物を干す」という日常生活の話を、論理演算チックに書くと

「晴れ」または「曇り」ならば「洗濯物を干す」というふうになります。

この「または」を OR と表します。

論理積

A かつ B のとき「YES」 となるお話。

例えば、「15時以降に洗濯物が乾いていたら取り込む」という日常生活を論理演算チックに書くと…

「15時以降」かつ「洗濯物が乾いている」ならば「取り込む」という条件を示します。

論理積と論理和

論理積と論理和は日常生活でも割と言い表すことができます。

これが、プログラムになると

YesはTrueや1と訳されて、NoはFalseや0と訳されます。表現が難しいだけですね。

大事なのは、 条件となるもの両方がYESかNOかで結果が変わる ことを理解すること。

この2点をあえて少し難しくまとめますね。

x y 論理和 論理積
0 0 0 0
0 1 1 0
1 0 1 0
1 1 1 1

数値で表されていますが、1を「YES」、0を「NO」と読み替えてください。

論理積が1すなわち「YES」となっているのは事象X、事象Yともに1すなわち「YES」となっている場合のみなのです。

論理和は、事象X、事象Yのどちらかが「YES」ならば答えも「YES」となっています。

論理積と論理和以外

排他的論理和

論理積が「AND」、論理和が「OR」表された次、　 排他的論理和 です。記号は XOR または EOR です。

これは日常生活に言い換えることは難しく、唯一つ 事象X と 事象Y の答えが同一ならば0 という論理演算なんです。

否定論理積

論理積の逆ですね。 NOT AND の略で NAND と表されます。

否定論理和

論理和の逆です。 NOT OR の略で NOR と表されます。

論理演算まとめの表

x y 論理和 論理積 排他的論理和 否定論理和 否定論理積
X Y OR AND XOR NOR NAND
0 0 0 0 0 1 1
0 1 1 0 1 0 1
1 0 1 0 1 0 1
1 1 1 1 0 0 0

ド・モルガンの法則

懐かしい方もいらしゃいませんか？

AND の否定 = OR ( =NAND)

OR の否定 = AND ( =NOR)

と、入れ替わることを把握しておこう。

カルノー図

カルノー図は 論理式、論理演算を簡略化するために用いる表 です。カルノー図はAPよりFEが出題率高めです。

ですが、私は勉強していた当初はちんぷんかんぷんでした。
AB\CD 00 01 10 11
00 1 0 0 1
01 0 1 1 0
10 0 1 1 0
11 1 0 0 1

論理演算の01の関係性が理解できている前提ではありますが、このカルノー図から論理式を導出する問題が頻出です。

表の見方

一番左の列は、 ABの組み合わせ 、一番上の行が CDの組み合わせ です。

ABが00の行とCDが00の列が1であることが見て取れます。
AB\CD 00 01 10 11
00 1 0 0 1
01 0 1 1 0
10 0 1 1 0
11 1 0 0 1

導出方法

※ 否定を ¬ 記号で表します。

※ 論理積を AND でなく 「・」で表します。

※ 論理和を OR でなく 「＋」で表します。

結果が「１」となる行列を抽出します。

例)A = 0, B = 0, C = 0, D = 0 の場合1 => ¬A ･ ¬B ･ ¬C ･ ¬D = 1

すると、

  • ¬A ･ ¬B ･ ¬C ･ ¬D
  • ¬A ･ ¬B ･ C ･ ¬D
  • ¬A ･ B ･ ¬C ･ D
  • ¬A ･ B ･ C ･ D
  • A ･ B ･ ¬C ･ D
  • A ･ B ･ C ･ D

の6通りが挙げられます。

次に、その中で1が隣り合うものを同じグループとして、グループ分けを行います。

グループA

  • ¬A ･ ¬B ･ ¬C ･ ¬D
  • ¬A ･ ¬B ･ C ･ ¬D

グループB

  • ¬A ･ B ･ ¬C ･ D
  • ¬A ･ B ･ C ･ D
  • A ･ B ･ ¬C ･ D
  • A ･ B ･ C ･ D

このグループA と グループBの論理和が答えです。グループ内の論理式は論理積です。

グループA

  • ¬A ･ ¬B ･ ¬C ･ ¬D
  • ¬A ･ ¬B ･ C ･ ¬D

の論理積（共通項）なので

  • ¬A ･ ¬B ･ ¬D

グループB

  • ¬A ･ B ･ ¬C ･ D
  • ¬A ･ B ･ C ･ D
  • A ･ B ･ ¬C ･ D
  • A ･ B ･ C ･ D

の論理積（共通項）なので

  • B ･ D

となります。

最後に、グループAとグループBの論理和なので、 ¬A ･ ¬B ･ ¬D + B ･ D が答えになります。

基本情報を受ける方はこのカルノー図は抑えたいところです。