基礎理論～グラフ理論～
こんにちは。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 が答えになります。
基本情報を受ける方はこのカルノー図は抑えたいところです。
基本情報と応用情報って一体何が違うのか。
こんばんは、明日からの大雨を目の前に左下半身がいつものように使い物にならないこなちゃんです。
さて、 今日は勉強内容ではなく、資格の概要の話です。
基本 と 応用 と何が違うのか。
午前問題の出題範囲
基本情報(以下、FE)は、易しいのもありますが、テクノロジ系統の問題に重点が置かれています。例えば、コンピュータ性能の計算などです。待ち行列の計算も応用情報（以下、AP）より多いのです。
比べてAPは、ストラテジ・マネジメント系統の問題が多い。つまり、SE寄り、設計やマネジメントを行う人を対象にした資格になっています。
計算の難易度
FEに比べてAPは、割り切れない問題が多いんですね。小数点第何位で四捨五入、なんて問題やニアイコールの問題まで出ます。厄介極まりない。
午後の出題方式
一番大きな違いで、一番難易度が高い理由がこれ。
FEは選択式なので、午前同様マークシートで選んでいくだけで良いのだが、APはそうも行かない。全てではないが、午後問題の約半数が記述なのだ。
○○を選択する理由を30文字以内で述べよ、のような問題だ。
必須問題の差異
最近はFEもAPもセキュリティ分野の問題が必須となっている。
それ以外の違いとしては、FEの場合セキュリティ以外にも「アルゴリズム」や「プログラミング言語」問題が必須である。
それに対してAPは、セキュリティ以外全て選択である。
簡単にはこんな感じ。
明日からはまた、技術系のお話を書いていきます。
情報科学について～情報量や情報源～
初めに
数学って好きですか？
私は好きです。
基本情報を始めとした情報処理試験にも数学の知識は必要ですね、集合とか、対数計算とか、指数とか。
今回は数学の対数計算がちょっぴり出てくる 情報量 についてお話したいと思います。
情報量とは？
情報の量って何でしょうね？どうやって表されるんでしょうか。
意外と例は「天気」や「さいころ」、「コイン」を使って表されます。
例えば、 コインで表が出るか裏が出るか って、もちろん答えは「表」か「裏」なんです。
また、サイコロを振って出る数はいくつだろうか というのは「１」～「６」の６通り。
厳密にはそんな単純ではないにしろ、前者は２通り、後者は６通りと、答えの数に差があります。
このように、「何が答えとして出るか」のパターンの量を私は情報量だと解釈しています。
コインの例だと、表 or 裏 の２択なので、0 or 1 の 1bitで表すことができます。
サイコロの例だと、6通りを表すためには、0,1,10,11,100,101 の少なくとも6bitが必要ですね。
つまり、 サイコロで出る目の方が情報量は多い といえます。
これを踏まえて次項に行きましょう。
情報量の計算
ITの資格なので、計算が出てきてしまうのは仕方ないですね。
とはいえ、そんなに難しくはないはずです。数学アレルギーの方はがんばりましょう。
事象Aの生起確率(発生する確率)をP(A)と表すときの情報量をI(A)bit とするとき
となります。
は？とか言わずに思い出してください。
例えば前述のコインの例だと
であるため、
となりますね。1bitで表せることがここでも証明されました。
また、サイコロの例だと
となり、2と少しのbit数、つまり少なくとも3bit必要と証明されました。
情報源
情報量の話や計算をしましたが、続いては情報源の話です。
こちらは至ってシンプルで、情報を発生させる行為を指します。
情報源が、何かしらの情報量を発生させます。例をだすと、「サイコロを投げる」といった情報源が「１が出た！」という情報量を発生させる、ということですね。
平均情報量
名前の通り、情報源に対する情報量の平均です。
サイコロの例だと、
1が出る確率とその情報量を掛けて全て足し合わせたものになります。
情報学ではこの 平均情報量 を H で表します。
k が 1 から mまでの、確率 * 情報量 の合計ですね。
この平均情報量のことを、別名エントロピーとも言います。
マルコフ情報量
コイン、って次に出る面は、前回出た面に影響されないですよね。
じゃんけんも同様に、「さっきグーが出たから次はグーがでない」ということはありません。（心理戦は置いといて。）
このように、 ある事象の生起確率が、それ以前の事象に影響を受けない情報源 を 無記憶情報源やエルゴード情報源といいます。
逆に、天気のように「昨日は曇ってたし、梅雨だから明日はきっと雨が降るだろう」といった影響を受ける情報源を``マルコフ情報源**といいいます。
マルコフ情報源のうち、影響を与えるものが1つの情報源を単純マルコフ情報源といいます。上記のように、今日の天気に影響を与える要因が「昨日雨が降ったから」という、1つだけの場合は単純マルコフ情報源だと言えます。
オートマトンに関係するのは、単純マルコフ情報源なんですね。よく試験に出ます。
なんちゃって情報科学授業終わり。
バランススコアカード
概要
今回はバランススコアカード(Balanced Scorecard)について。
BSCって略されるし、当たり前のように「BSCについて～」なんて問題が始まったりもする。
分類
情報技術者試験にはテクノロジ、ストラテジ、マネジメントと大きく3つに分類されるが、この中のストラテジに分類される。
歴史や経緯
1990年に提唱されたBSC。アメリカのハーバード大学、ノーランノートン研究所で新たに業績評価システムのプロジェクトが発足されたんだ。
キャプラン教授と、ノートン博士が発表した、経営課題を解決する為のフレームワークなんです。
詳細
BSCって？
従来、企業の経営状況や業績を把握するのは「財務のみ」だったんです。お金が指標。稼いでればすごい。
そんな中提唱されたBSCでは「いやいや他にも考えるものあるでしょ」と、非財務評価を加えたんですね。
非財務評価を加えたScore(指標)をバランスの取れた状態(Balanced)にしようという仕組みや働きがBSCなんです。
評価基準
ここが重要。暗記する人は暗記できるだろうけど私はなかなかできないのがこの非財務評価の種類。
経営を、財務＋非財務の「4つの視点」に分類し、整理するのがBSC。その分類は人材、業務、顧客、財務。評価基準になるということは、経営に於いて大切だと判断されるものですね。
この順番で知っておくと記憶ではなく理解になるのではないでしょうか。
詳しくまとめます。
人材
まず、なぜ人材に注力するのか。
人材への注力、すなわち人材育成です。人材育成に力をいれる理由としては業務を活性化したいからです。今時だと「モチベーションアップを図る」というのも理由にありそうですね。
スキルアップによって意識改革や成長ができる企業かどうか、が良い経営かどうかの指標になってるんですね。
業務
次に、なぜ業務を活性化させたいのか。
そりゃもちろん、業務の活性化で、顧客満足度を高めたいからです。人材も育ち、いいアイデアや効率化が進めば、おのずと顧客満足度も高まります。
そのため、業務が活性化しているのか、よい業務プロセスがとられているかが経営指標になっています。
顧客
次に、なぜ顧客満足度を高めたいのか。
これも明白、顧客が満足すれば、もっと関係性がよくなり受注量が増えるからですかね。
財務
最後、なぜ受注量を増やしたいのか。
結局は財務に終始しますね。受注量が増えれば収益性が高まり経営が発展するからなんです。
4つの視点のまとめ
良い財務のためには良い顧客が必要。
良い顧客のためには良い業務が必要。
良い業務のためには良い人材が必要。
こんなつながりになっているんですね。
風が吹けば桶屋が儲かる仕組みなんです。
経営改善の方法
仕組みは把握したかと思いますが、ではこれをどうやって運用していくのか？という話です。
例えば、「具体的にどういった業務プロセスが求められるのか？」など。
売上アップというゴールがあれば、それに対する重要成功要因を考えていく必要があるんですよね。
しれっと登場してきた重要成功要因も試験では重要なキーワードです。Critical Success Factor(CSF)と称されますので知っておきましょう。
ゴールに対して、何をすれば成功するのか、その要因がCSFです。それを見つけるためにSWOT分析を行うんですね。
またまたしれっと登場してきたSWOT分析も重要。企業の強み(Strength)、弱み(Weakness)、機会(Opportunity)、脅威(Threat)を分析する方法。
具体例はまた別記事に。
試験に向けたまとめ
今回出てきた用語などは以下。
BSC
前述の4つの指標は、以下のキーワードとなって試験に出てきます。だいたい穴埋め。
- 財務の視点
- 顧客の視点
- 業務プロセスの視点
- 人材と変革の視点
SWOT分析
これはまた別記事にて。
KPI、KGI
BSCのみならず、情報処理試験で必ず目にしますので、併せて紹介。
KPIはKey Performance Indicatorの略で、重要業績評価指標のことです。KeyとなるPerformanceのIndicatorです。
KGIはKey Goal Indicator。重要目標達成指標のこと。こちらはKeyとなるGoalに対するIndicatorです。
KPIはゴールにどれだけ近づいているかの数値。 KGIはゴールとなる数値です。
例を挙げると、売り上げ1億！がKGIで、売り上げを上げるために毎月集客活動を100回行うぞ！がKPIってことです。今回のメインはBSCなのでこれくらいにします。
なんか用語チックになっていますが、成り立ちや意味を知っておくだけで理解度は増すかと思います。
最後に
試行錯誤して、どんな情報が有用か考えながら項目を増やしていきますね。
1.5hかかりました。疲れた。
情報技術者試験カテゴリについて
このカテゴリについて
あくまで自己満です。
私は学生時代基本情報技術者試験に合格してます。また、それに関しての教鞭を執っています。
応用情報技術者試験にはあと1問、あと数点、というところで数度落ちています。（惜しすぎて萎えてます。いずれ受かります。）
教えることが好きな私が、自分の備忘録を兼ねてこのカテゴリにFE、AP、高度午前共通問題に出るようなものをまとめていこうかと思います。
私が勉強になったものなどをメインに書き連ねるので、基本的には自己満です。
また、私がITについて、プログラミングについて教えるときに心がけていることは 暗記だけで終わらせない ということ。勉強、暗記、という気持ちではなく、開発はゲームのように楽しむようなものだと考えています。 そして私は暗記が苦手なので、暗記ではなく、「理解する」というところから入っていこうと心がけています。
ということで、本カテゴリで紹介する用語についても、歴史・背景や実例を加えて説明していけたらなと思います。
AといったらB！のようなものに終始したくありませんので。
