2019-07-04

基礎理論～PERT図～

今回のテーマ

プロジェクト管理技法の1つで、日程管理に用いられる PERT図 について。

参考図

f:id:cresta522:20190704200525p:plain — PERT図

コンナノ。

PERT図って？

図の味方を説明します。

AやらBやら書かれていますが、これらは「作業の名前」と「それにかかる日数」を指します。

作業Aは、開始から終了まで5日かかり、作業Bは作業終了までに10日かかります。

次に、この矢印の意味ですが、前提作業を指します。

作業Fは作業Bが終わっていないと作業開始ができない。
作業Hは作業G,D,E...とすべてが終わっていないと開始できない

といったことが読み取れます。

さて、一番最初の○がすべてのスタートで、一番右の○がすべてのゴール。

これで何が分かるんでしょうね。

読み取れること（最も早く開始できる日程）

作業Cの前提に、作業A,作業Bがあるが、Aは5日かかり、Bは10日掛かるのでCに着手開始することができるのはプロジェクト開始から10日後である。

この「最も早く開始できる日程」を最早結合点時刻という。

このように、次々と 最早結合点時刻を求められるようになるのも必要なスキルである。

以下に、この図から読み取れる最早結合点時刻を挙げる。

Aは5日、Bは10日掛かるため、Cの着手開始は10日後
FはBの完了後開始できるため、10日後。
Gは、Cが20日掛かるため30日後。
Dは、C同様10日後。
Hは、F,Eの終了が20日後、Dの終了が40日後、Gの終了が50日後なので、最も早く前提作業が終わり、開始できるのは50日後。

作業Hは10日掛かるため、このプロジェクトは早くとも60日掛かることがわかりました。

読み取れること（最も遅く開始できる日程）

最も遅く開始する日ってなんだろう？とお思いかもしれませんが、

「ここまでに開始してくれればプロジェクト終了には間に合うよ」という余裕をもった日程のことです。

最早結合点時刻はスタートからゴールまで計算しましたが、今度はゴールからスタートまで追うことで、余裕日数を求めます。

個人的にはこの逆算が難しいかなって思ってましたが、言葉で説明すると簡単で

このプロジェクトには最短60日掛かる
Hは50日目までには開始していないといけない
すなわち、作業F、Eは50日目までに終わっていないと行けない。
とすると、作業Fは少なくとも40日めまでには開始していないと行けない

とわかってきます。

今回求めた最も遅く開始できる日程を 最遅結合点時刻 といいます。

クリティカルパス

さて、ここまで最早と最遅を求めてきましたが、

この日数が同じになる作業というのが存在します。それらは「開始及び終了日がずれたらPJに影響が出る」ことを指すため、重要視されます。

この、 最早結合点時刻と最遅結合点時刻が等しい作業を結んだ線 をクリティカルパスと言います。

今回を例に取ると、B→C→G→Hがクリティカルパスとなり、重要視しなければならない作業ということになります。

計算は要練習です。

頻出ですので慣れましょう。

以上！

2019-07-03

基礎理論～エンディアン～

こんばんは、本日二度目の記事です。

雨が強くなり早々に切り上げます。

今回はコラム的な意味合いで エンディアン についてご紹介。地味にFEだと求められる知識です。

物資の運搬（データの運搬）

例えば、Amazonから大量に10箱届いたら、「これはここ、これはこっち」と分けますよね。

玄関にどかどかと積まれるのも大変ですし、積み方も様々です。

コンピュータにおけるデータの保存や転送も同じように「方法」があるんです。その方法をエンディアンといいます。

エンディアン

2バイト以上の数値データを転送、記録する順番のことです。

これは結果のみ見せたほうが早いですね。

転送は、1バイトずつ行われるのが通常です。00000001で一区切り、11101100でまた一区切り、と。

今回は例として、16進数の 1234ABCD を転送してみます。皆さんは是非2進数に変換してみてください。

1バイト = 8bit = 16進数の2桁 ずつ転送しますが、そこに違いが現れます。

それは、「最上位バイトから転送するのか、最下位バイトから転送するのか」。

前者をビッグエンディアン,後者をリトルエンディアンと言います。

具体的にどうなるかというと、

ビッグエンディアン

0	1	2	3
12	34	AB	CD

リトルエンディアン

0	1	2	3
CD	AB	12	34

です。あくまで8bitずつというところに注意しましょう。

余談

当初、メールなどのデータ転送にも「リトルエンディアンで送るよ！」というのを明記しないと行けなかったんですよね。

でないと、12345678円、と送りたかったのに78563412円と送られてくることになってしまいますからね。

今は、統一されています。

2019-07-03

基礎理論～誤差～

誤差って何だ

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

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

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

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

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

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

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

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

この超過分を「誤差」と言います。誤差には他にも種類があり、特に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 }$

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

要因

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

打切り誤差

これは一言。

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

出題されること

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

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

2019-07-03

基礎理論～誤差～

情報処理技術者試験

誤差って何だ

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

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

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

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

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

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

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

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

この超過分を「誤差」と言います。誤差には他にも種類があり、特に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 }$

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

要因

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

打切り誤差

これは一言。

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

出題されること

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

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

2019-07-02

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

情報処理技術者試験

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

次回

誤差について

2019-07-01

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

情報処理技術者試験

オートマトンとは

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

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

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

こんなもの。

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

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

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

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

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

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

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

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

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

q1 からスタートして、

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

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

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

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

2019-06-30

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

情報処理技術者試験

初めに
- データの探索とは？
巡回方法

初めに

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

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

データの探索とは？

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

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

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

巡回方法

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

幅優先順

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

深さ優先順（先行順）

親が先行します。

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

深さ優先順（中間順）

親が中間にいます。

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

深さ優先順（後行順）

親が最後 です。

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