基礎理論～誤差～
誤差って何だ
皆さんが知っている誤差、というのは「実際のものと異なる」という認識でしょう。
例えば、私に注がれたジュースとあなたのジュースが違う！的な。
今回は、コンピュータの世界での「誤差」を紹介します。
なぜ誤差が生まれるのか？
コンピュータの世界では、数字や文字などは一定量の桁が確保されます。
なぜ？どこに確保されるの？という話はまた別記事で。
今回は、 数値は有限なんだ という前提のもとお話します。
さて、有限ということは、その桁数を超過してしまったらどうなるのでしょうか。無視されます。スルーされます。なかったコトにされます。
この超過分を「誤差」と言います。誤差には他にも種類があり、特にFEでは説明できる必要があります。
絶対誤差
これが一番シンプルな「誤差」です。
真値 （本当の値）と、有限桁数からはみ出したために真値とずれた観測値との誤差のことです。
例えば、小数点が0桁、すなわち整数のみの桁があります。（PG経験者は整数型の変数と於いてください。）
これに、1234.5という数値を入れます。小数を入れるため、最後の「0.5」が省かれてしまいますね。
この場合の真値は1234.5、測定値は1234.0、0.5が消えてしまったので誤差は「0.5」になります。
意外とシンプル。
相対誤差
相対誤差は、絶対誤差と相対誤差の比率のこと。
なので、
となります。
誤差の発生原因とその種類
丸め誤差
これは一番覚えやすいですね。
四捨五入です。
四捨五入すると末尾の数値が四捨五入する前と当然変化します。
四捨五入する(=丸める）事によって生じるので、丸め誤差と言われます。
桁落ち
ここでは、有効桁数の重要性も感じられます。
例えば、「0.0043」という数値。
この数値にとって重要なもの、有効なものは「43」であり、この桁数（今回でいうと2桁）を有効桁数といいます。
さて、桁落ちとは、この有効桁数が「落ちてしまう」ことを指します。
例えば
有効桁数が7桁 - 7桁 です。この答えこそ先程の「0.0043」です。
有効桁数が7桁から2桁に落ちました。これが「桁落ち」です。
要因
値の近い数値同士の減算
情報落ち
次は「情報が落ちてしまう」誤差です。どういうことでしょうか。
例えば、「小数点以下の有効桁数が4桁」の数値から「小数点以下の有効桁数が8桁」の数値を引いた場合の答えが
小数点以下の有効桁数が4桁しか許容しない場合 に生じます。
ですが！
小数点以下の有効桁数が4桁しか許容しない ため、答えは
となってしまい、正しい答えと異なってしまうんです。
要因
桁の大きい数と、極端に桁の小さい数の加減算。
打切り誤差
これは一言。
有効桁数がとんでもなく大きい数の計算の途中で打ち切ることによって生じる、正確な値との誤差。
出題されること
誤差の発生原因や、回避策が問われます。主に、丸め誤差や桁落ちは頻出です。なんでこの誤差が生まれるのか？知っておきましょう。
以上！今回は誤差についてでした。
基礎理論～誤差～
誤差って何だ
皆さんが知っている誤差、というのは「実際のものと異なる」という認識でしょう。
例えば、私に注がれたジュースとあなたのジュースが違う！的な。
今回は、コンピュータの世界での「誤差」を紹介します。
なぜ誤差が生まれるのか？
コンピュータの世界では、数字や文字などは一定量の桁が確保されます。
なぜ？どこに確保されるの？という話はまた別記事で。
今回は、 数値は有限なんだ という前提のもとお話します。
さて、有限ということは、その桁数を超過してしまったらどうなるのでしょうか。無視されます。スルーされます。なかったコトにされます。
この超過分を「誤差」と言います。誤差には他にも種類があり、特にFEでは説明できる必要があります。
絶対誤差
これが一番シンプルな「誤差」です。
真値 （本当の値）と、有限桁数からはみ出したために真値とずれた観測値との誤差のことです。
例えば、小数点が0桁、すなわち整数のみの桁があります。（PG経験者は整数型の変数と於いてください。）
これに、1234.5という数値を入れます。小数を入れるため、最後の「0.5」が省かれてしまいますね。
この場合の真値は1234.5、測定値は1234.0、0.5が消えてしまったので誤差は「0.5」になります。
意外とシンプル。
相対誤差
相対誤差は、絶対誤差と相対誤差の比率のこと。
なので、
となります。
誤差の発生原因とその種類
丸め誤差
これは一番覚えやすいですね。
四捨五入です。
四捨五入すると末尾の数値が四捨五入する前と当然変化します。
四捨五入する(=丸める）事によって生じるので、丸め誤差と言われます。
桁落ち
ここでは、有効桁数の重要性も感じられます。
例えば、「0.0043」という数値。
この数値にとって重要なもの、有効なものは「43」であり、この桁数（今回でいうと2桁）を有効桁数といいます。
さて、桁落ちとは、この有効桁数が「落ちてしまう」ことを指します。
例えば
有効桁数が7桁 - 7桁 です。この答えこそ先程の「0.0043」です。
有効桁数が7桁から2桁に落ちました。これが「桁落ち」です。
要因
値の近い数値同士の減算
情報落ち
次は「情報が落ちてしまう」誤差です。どういうことでしょうか。
例えば、「小数点以下の有効桁数が4桁」の数値から「小数点以下の有効桁数が8桁」の数値を引いた場合の答えが
小数点以下の有効桁数が4桁しか許容しない場合 に生じます。
ですが！
小数点以下の有効桁数が4桁しか許容しない ため、答えは
となってしまい、正しい答えと異なってしまうんです。
要因
桁の大きい数と、極端に桁の小さい数の加減算。
打切り誤差
これは一言。
有効桁数がとんでもなく大きい数の計算の途中で打ち切ることによって生じる、正確な値との誤差。
出題されること
誤差の発生原因や、回避策が問われます。主に、丸め誤差や桁落ちは頻出です。なんでこの誤差が生まれるのか？知っておきましょう。
以上！今回は誤差についてでした。
基礎理論～浮動小数点数～
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 |
次回
誤差について
基礎理論～オートマトン～
オートマトンとは
一般的には、 状態遷移図 や 状態遷移表 と表されます。
どういったものかと言うと、
こんなもの。
なにこれ？と思うかもしれませんが、個人的にはサービス問題だと思います。詳しく説明していきます。
有限オートマトン（オートマトン基礎）
オートマトンには複数種類がありますが、FEやAPなどで取り上げられるのはこの 有限オートマトンというものです。
簡単に言うと、 状態遷移表 という「地図」と 入力データ という「道順」を与えられるのでゴールまでたどり着いてください、という問題です。
上図は「状態遷移図」です。
- q1
- q2
- q3
という状態（地図で言う建物）があり、矢印を辿って q2 に辿り着こうね、という地図です。
最初のスタート地点(q1)を 初期状態 と言い、◎の q2を 受理状態 といいます。用語です。
さて、この地図と道順を渡されます。
「01101」という順番で行ってね！ という形で入力値が渡されますので、
q1 からスタートして、
q1 -> 0 -> q1 -> 1 -> q2 -> 1 -> q2 -> 0 -> q3 -> 1........あれ？先の道がない。
このように、目的のゴールまでたどり着けない状態を 不受理されなかった 状態といいます。
成功例は、「01」や「011」などですね。
問題では「受理される入力データを選びなさい」という問題が頻出です。
基礎理論～グラフ理論（木構造の巡回）～
初めに
前回の記事では、木構造について紹介しました。
今回は、データの探索方法についてです。
データの探索とは？
木構造なので各節の値を行ったり来たりして、「目的のデータはどこじゃろかい」と探します。
「ここかな？ちがう」「ここも違う」と繰り返して、次の節を見に行くんです。
この次の節の選び方を巡回方法といいます。
巡回方法
巡回方法は「このデータを見つけるまでに、この方法を使用すると何回の巡回で見つかりますか？」という問題にて使用されます。
幅優先順
深さ優先順（先行順）
親が先行します。
深さ優先順（中間順）
親が中間にいます。
深さ優先順（後行順）
親が最後 です。
基礎理論～グラフ理論（木構造）～
初めに
グラフ理論2ということで、何を書くかって言うと、木構造について。
前回は
です。
木構造も、グラフの一種です。点があって、それを結ぶ辺がある。これは立派なグラフの形。
木構造というのは、1つの点からn個の点に対して辺があり、その接続先の点からまたn個の点に向けて辺が結ばれる形です。樹形図が想像しやすいでしょう。
この点の数などによって分類分けがされます。
どんなときにこれが使われるのか？というと、データ探索のときですね。
木構造の一番最上位の点(根やルートと呼ぶ)から、「さーて目的のデータはどこにあるかなー」と、伸びる辺をたどって各点(節やノードと呼ぶ)を探索します。
探索の基本
基本的に、各ノードの中には数値が入っておりその数値を見て次の検索先を決めていきます。
グラフのデータ構造の種類
根からの深さ、各節と親の節の上下関係などによってこのグラフって、名称が変わります。それを紹介します。
参考画像書きました。
（塾の合間だったから字は汚いです）
木構造 pic.twitter.com/1r8lCbxrVR
— こなさん(空瓶)@鬱SE講師 (@sorabin_) 2019年6月29日
ヒープ
子の節と親の節の間に、
子 ＞ 親
もしくは
子 ＜ 親
が存在するものを ヒープ と呼びます。
二分探索木
左の子、親、右の子の節の間に、以下の制約が存在します。
左の子の節の値 ＜ 親の節の値 ＜ 右の節の値
これを 二分探索木 と呼びます。
現在の節より大きい値を探すのか、小さい値を探すのか？で右へ行くのか、左へ行くのか決めるようなものになります。
出題頻度も高く、「こういうデータを探すとき、どういう形で値を探しますか？」って出てきますね。
AVL木
二分探索木のうち、根から最下層の節までの深さの差が、０ or １のものを AVL木 と呼びます。
B木
根以外の節は、同じ数の子を持つ木を B木 といいますね。
基礎理論～グラフ理論～
こんにちは。Twitterでは鬱真っ最中のこなちゃんです。
テーマ
これは、実際にPythonを使用して解説をしたQiitaのサイトもありますが、プログラミング寄りの記事で、FE,APにおける趣旨とは異なってしまうため、プログラムでどう書く？っていう話はしません。
グラフ理論とは
「グラフ」と聞いて、通常は棒グラフや円グラフ、折れ線グラフを想像しますよね。
ですが、情報学で言うグラフ理論の グラフ は別名 ネットワーク とも称され、「点と点を結んだ線」の集合を分析するものになります。
グラフ理論の例
例えば、日本地図の各県庁所在地に点を置き、隣県の点を結びます。
するともちろん、47の点と、隣り合う都道府県への辺が現れます。
それを見て、
「おっ、長野県が一番隣県多いじゃん」
と分析できます。
このように「点と辺の集まりから分析するもの」がグラフ理論です。
以下、グラフというのは「点と辺の集まり」だということを前提に進めていきます。
グラフの種類
無向グラフ
これが一般的なグラフです。
先程の都道府県の例の見たまんま、辺に「向き」なんて存在しないです。
敢えて、「無向グラフ」というからには対になるものがあります。次。
有向グラフ
一般的なグラフ（無向グラフ）と異なり、「方向」が付与されたものです。
？向き？？
そうです、向きです。
先程の都道府県庁を結んだグラフに於いて「さて、日本一周しよう！」としたときに、
出発はここで、次はここで、と番号を振ったり、矢印を引いたりしますね。
この矢印が辺の「向き」です。
つまり、各点や辺に順番のような無向グラフ＋αの意味が付与されたものでした。
途中だよ
元気ないしこれから仕事なので一旦休憩。
また書きます。
