基礎理論～オートマトン～
オートマトンとは
一般的には、 状態遷移図 や 状態遷移表 と表されます。
どういったものかと言うと、
こんなもの。
なにこれ？と思うかもしれませんが、個人的にはサービス問題だと思います。詳しく説明していきます。
有限オートマトン（オートマトン基礎）
オートマトンには複数種類がありますが、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の点と、隣り合う都道府県への辺が現れます。
それを見て、
「おっ、長野県が一番隣県多いじゃん」
と分析できます。
このように「点と辺の集まりから分析するもの」がグラフ理論です。
以下、グラフというのは「点と辺の集まり」だということを前提に進めていきます。
グラフの種類
無向グラフ
これが一般的なグラフです。
先程の都道府県の例の見たまんま、辺に「向き」なんて存在しないです。
敢えて、「無向グラフ」というからには対になるものがあります。次。
有向グラフ
一般的なグラフ（無向グラフ）と異なり、「方向」が付与されたものです。
？向き？？
そうです、向きです。
先程の都道府県庁を結んだグラフに於いて「さて、日本一周しよう！」としたときに、
出発はここで、次はここで、と番号を振ったり、矢印を引いたりしますね。
この矢印が辺の「向き」です。
つまり、各点や辺に順番のような無向グラフ＋αの意味が付与されたものでした。
途中だよ
元気ないしこれから仕事なので一旦休憩。
また書きます。
基礎理論～集合と論理～
論理演算
今回は集合と論理です。
集合って高校の時習いましたね、数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は、セキュリティ以外全て選択である。
簡単にはこんな感じ。
明日からはまた、技術系のお話を書いていきます。
