talosのプログラミング教室

【基本・応用情報技術者】論理回路

こんにちは。たろすです。

今回は論理回路について説明します。

論理式の知識が前提になるので、論理式がわかっていない方はこちらから押さえておきましょう。

talosta.hatenablog.com

論理ゲートの種類

論理ゲートは6種類あります。

基本情報技術者試験応用情報技術者試験ではMIL記号と呼ばれる表記で論理回路が書かれているのですが、それぞれの記号がなにを表しているのかは提示されるため必ずしも覚える必要はありません。

ただ時間をかけないためにも覚えることを推奨します。

AND

f:id:talosta:20210607154658p:plain

 X = A \cdot Bを表しています。

OR

f:id:talosta:20210607154933p:plain

 X = A + Bを表しています。

NOT

f:id:talosta:20210607155110p:plain

 X = \overline{A}を表しています。

NAND

f:id:talosta:20210607155327p:plain

 X = \overline{A \cdot B}を表しています。

NOR

f:id:talosta:20210607155432p:plain

 X = \overline{A + B}を表しています。

XOR

f:id:talosta:20210607155537p:plain

 X = A \oplus Bを表しています。

例題

論理回路図を使った問題を解いてみましょう。

問題

図に示すディジタル回路と等価な論理式はどれか。ここで,論理式中の"・"は論理積,"+"は論理和,XはXの否定を表す。

f:id:talosta:20210607160836p:plain

ア. X = A \cdot B + \overline{A \cdot B}
イ. X = A \cdot B + \overline{A} \cdot \overline{B}
ウ. X = A \cdot \overline{B} + \overline{A} \cdot B
エ. X = (\overline{A} + B) \cdot (A + \overline{B})

(出典:平成29年度 秋期 基本情報技術者試験 午前 問23)

解説

各ゲートの入力と出力を見ていきましょう。

二つのNOTゲートにはそれぞれ A Bが入力され、 \overline{A} \overline{B}が出力されます。

f:id:talosta:20210607162019p:plain


一つ目のORゲートには \overline{A} \overline{B}が入力され、 \overline{A} + \overline{B}が出力されます。

f:id:talosta:20210607162857p:plain

上側のANDゲートには A \overline{A} + \overline{B}が入力され、 A(\overline{A} + \overline{B})が出力されます。

下側のANDゲートには B \overline{A} + \overline{B}が入力され、 B(\overline{A} + \overline{B})が出力されます。

f:id:talosta:20210607162932p:plain


最後のORゲートには A(\overline{A} + \overline{B}) B(\overline{A} + \overline{B})が入力され、 A(\overline{A} + \overline{B}) + B(\overline{A} + \overline{B})が出力されます。

f:id:talosta:20210607163019p:plain

もちろん選択肢にこの回答はないため、変形する必要があります。


\begin{eqnarray}
 A(\overline{A} + \overline{B}) + B(\overline{A} + \overline{B}) &=& A \cdot \overline{A} + A \cdot \overline{B} + \overline{A} \cdot B + B \cdot \overline{B} \\
&=& 0 + A \cdot \overline{B} + \overline{A} \cdot B + 0 \\
&=& A \cdot \overline{B} + \overline{A} \cdot B
\end{eqnarray}

したがって答えはウになります。

おわりに

今回は論理回路について説明しました。

毎回1問は出るのでできるようにしておきましょう。

【基本・応用情報技術者】ラウンドロビン方式

こんにちは。たろすです。

今回はスケジューリングの方式のひとつ、ラウンドロビン方式について説明をします。

スケジューリングの説明は以下の記事でしています。

https://talosta.hatenablog.com/entry/schedulingtalosta.hatenablog.com

ラウンドロビン方式

プロセスにCPUを割り当てられる時間(=タイムクォンタム)が決められており、タイムクォンタム分実行したら待ち行列の最後尾に並べる方式です。

ラウンドロビン方式は基本情報技術者試験応用情報技術者試験でよく問われます。

なぜかというと、他の方式と比べると複雑だからです。

なので例題を解きながら詳しく見ていきましょう。

例題

問題

タイムクウォンタムが2秒のラウンドロビン方式で処理されるタイムシェアリングシステムにおいて,プロセス1~3が逐次生成されるとき,プロセス2が終了するのはプロセス2の生成時刻から何秒後か。ここで,各プロセスはCPU処理だけで構成され,OSのオーバヘッドは考慮しないものとする。また,新しいプロセスの生成と中断されたプロセスの再開が同時に生じた場合には,新しく生成されたプロセスを優先するものとする。


プロセス 生成時刻 単独で処理された場合の時間
1 0秒後 5秒
2 3秒後 7秒
3 6秒後 5秒

ア.12
イ.14
ウ.16
エ.17

(出典:平成28年度 秋期 応用情報技術者試験 午前 問19)

解説

まず最初に生成時刻が0秒後のプロセス1が実行されます。

タイムクォンタムは2秒なので2秒間だけ実行されます。

f:id:talosta:20210529111525p:plain
待ち行列:プロセス1


しかし、プロセス1がタイムクォンタムを使い切った時点で他のプロセスはまだ生成されていません。

したがって、もう一度プロセス1が実行されます。

プロセス1を実行している間にプロセス2も生成されます。

f:id:talosta:20210529111841p:plain
待ち行列:プロセス2、プロセス1


プロセス2が生成されて待ち行列の先頭に並んでいるため、次はプロセス2が実行されます。

さらに、プロセス2がタイムクォンタムを使い切ると同時にプロセス3が生成されます。

f:id:talosta:20210529112623p:plain
待ち行列:プロセス1、プロセス2(、プロセス3)


問題文に「新しいプロセスの生成と中断されたプロセスの再開が同時に生じた場合には,新しく生成されたプロセスを優先するものとする」

とあるので、次はプロセス3が実行され、タイムクォンタムを使い切ると待ち行列の最後尾に並びます。

f:id:talosta:20210529113106p:plain
待ち行列:プロセス1、プロセス2、プロセス3


続いて、待ち行列の先頭のプロセス1が実行されます。

ただし、プロセス1の残り時間は1秒なので、1秒だけ実行されます。

f:id:talosta:20210529113735p:plain
待ち行列:プロセス2、プロセス3


後はプロセス2とプロセス3を交互に繰り返していきます。

f:id:talosta:20210529114039p:plain
待ち行列:プロセス3、プロセス2


f:id:talosta:20210529114417p:plain
待ち行列:プロセス2、プロセス3


f:id:talosta:20210529114542p:plain
待ち行列:プロセス3、プロセス2


f:id:talosta:20210529114704p:plain
待ち行列:プロセス2


f:id:talosta:20210529114831p:plain
待ち行列:なし


プロセス2の生成時刻は3、終了時刻は17なので答えは「イ.14」になります。

おわりに

今回はラウンドロビン方式について説明しました。

スケジューリング方式の中でも比較的問われやすいので覚えておきましょう。

【基本・応用情報技術者】スケジューリング

こんにちは。たろすです。

今回はスケジューリングの説明をします。

プロセス

スケジューリングの説明する前にプロセスについて説明します。

プロセスはプログラムを実行する際に、CPUが処理する実行単位です。

プロセスは以下の状態をとります。


待ち状態:CPUが割り当てられても実行できない状態

実行可能状態:CPUが割り当てられれば実行できる状態

実行状態:CPUが割り当てられていて実行中の状態


これらの状態は図のような関係性にあります。

f:id:talosta:20210529100605p:plain

スケジューリング

プロセスをどのような順番で処理するかを決めることです。

スケジューリングにはいくつか種類があるので、それぞれ説明していきます。

到着順方式

名前の通り、到着順(=実行可能状態になった順)に実行していく方式です。

優先度順方式

各プロセスに予め優先度を設定しておき、優先度が高いものから実行していく方式です。

優先度順方式には静的優先度順方式と動的優先度順方式があります。

静的優先度順方式は優先度が一度決められたら変わることはありません。

動的優先度順方式は実行可能状態の時間が長いほど、プロセスの優先度を高く設定し直します。

処理時間順方式

所持時間が短いものから実行していく方式です。

ラウンドロビン方式

プロセスにCPUを割り当てられる時間(=タイムクォンタム)が決められており、タイムクォンタム分実行したら待ち行列の最後尾に並べる方式です。

おわりに

今回はスケジューリングの説明をしました。

ラウンドロビン方式はよく問われるので、次回詳しく説明します。

【基本・応用情報技術者】直列接続システムと並列接続システムの稼働率

こんにちは。たろすです。

今回は直列接続システムと並列接続システムの稼働率の説明をします。

稼働率とは?という方はこちらからご覧ください。

https://talosta.hatenablog.com/entry/rasistalosta.hatenablog.com

直列接続システムの稼働率

図のように機器Aと機器Bが直列接続になっている場合、機器Aと機器Bはどちらも稼働していないとシステムとして稼働しているとは言えません。

f:id:talosta:20210522102700p:plain

したがって、システム全体としての稼働率は以下のように求められます。

 システムの稼働率 = 機器Aの稼働率 \times 機器Bの稼働率

機器が3つ、4つと直列で接続されている場合もすべての稼働率を掛け合わせることでシステム全体の稼働率を算出できます。

並列接続システムの稼働率

図のように機器Aと機器Bが並列接続になっている場合、機器Aと機器Bのどちらかが稼働していればシステムは稼働していると言えます。

f:id:talosta:20210522103504p:plain

つまり、システム全体の稼働率は機器Aと機器Bの両方が稼働していない確率を1から引くことで算出できます。

機器が稼働していない確率は(1 - 機器の稼働率)で求められるので、システムの稼働率は以下の式で求められます。

 システムの稼働率 = 1- (1 - 機器Aの稼働率) \times (1 - 機器Bの稼働率)

機器が3つ、4つと並列で接続されている場合もすべての機器の稼働していない確率(1 - 機器の稼働率)を掛け合わせて1から引くことで全体の稼働率を算出できます。

例題

基本情報技術者試験応用情報技術者試験で実際に出てくるような問題を解いてみます。

問題

機器AのMTBFは990時間、MTTRは10時間である。また、機器BのBTBFは980時間、MTTRは20時間である。機器Aと機器Bを用いて以下の図のようなシステムを構成したときのシステム全体の稼働率を求めよ。

f:id:talosta:20210522104517p:plain

解答

まず、機器Aと機器Bのそれぞれの稼働率を求めます。

 \begin{eqnarray}
機器Aの稼働率 &=& \frac{990}{990 + 10} \\
&=& 0.99
\end{eqnarray}

 \begin{eqnarray}
機器Bの稼働率 &=& \frac{980}{980 + 20} \\
&=& 0.98
\end{eqnarray}

次に並列部分の稼働率を求めます。

 \begin{eqnarray}
並列部分の稼働率 &=& 1 - (1 - 0.99) \times (1 - 0.98) \\
&=& 1 - 0.01 \times 0.02 \\
&=& 0.9998
\end{eqnarray}

続いて、機器Aと機器Bの並列部分を一つの機器とみなして機器Cとします。

f:id:talosta:20210522105302p:plain

するとこのシステムは稼働率0.9998の機器Cと稼働率0.99の機器Aが直列接続されていると考えることができます。

したがって、システム全体の稼働率

 \begin{eqnarray}
システム全体の稼働率 &=& 0.9998 \times 0.99 \\
&=& 0.989802
\end{eqnarray}

となります。

おわりに

今回は応用的な稼働率の計算を行いました。

よく出るのでしっかり覚えておきましょう。

【基本・応用情報技術者】システムの信頼性評価

こんにちは。たろすです。

今回はシステムの信頼性評価について説明します。

信頼性評価指標

システムの信頼性評価の指標としてよく使われるものを二つ挙げます。

MTBF(Mean Time Btween Failures:平均故障間隔

故障してから次に故障するまでの時間の平均値です。

MTBFが大きければ大きいほど故障しにくいと言えます。

つまり大きいほど良いです。

MTTR(Mean Time To Repair:平均修理時間

故障してから復旧するまでの時間の平均値です。

MTTRが大きければ大きいほど復旧に時間がかかると言えます。

つまり小さいほど良いです。

稼働率の計算

基本情報技術者試験応用情報技術者試験では稼働率の計算問題がよく出てきます。

稼働率は以下の式で求められます。

 稼働率 = \frac{MTBF}{MTBF + MTTR}

式を言語化すると「全体の時間に占めるMTBF(稼働している時間)の割合」です。

それでは例題を解いてみましょう。

例題

問題

故障してから次に故障するまでの平均時間が990時間の機器がある。故障をすると復旧するまでに平均で10時間かかる。この機器の稼働率を答えよ。

解答

先程挙げた式に当てはめると以下のようになります。

 \begin{eqnarray}
\frac{MTBF}{MTBF + MTTR} &=& \frac{990}{990 + 10} \\
&=& 0.99
\end{eqnarray}

したがって答えは0.99です。

おわりに

今回はシステムの信頼性評価について説明し、簡単な稼働率の計算を行いました。

実際に出てくる問題はもう少しひねった問題になるので、それは次回説明します。

【基本・応用情報技術者】ハミング符号による誤り訂正

こんにちは。たろすです。

今回はハミング符号による誤り訂正について説明します。

ハミング符号とは

ハミング符号とは、データの伝送時に付加し、誤りを検知・訂正できる誤り訂正符号の一つ。

ハミング符号(Hamming code)とは - IT用語辞典 e-Words

とのことです。

誤り制御には検知しかできないものと訂正もできるものがあります。

ハミング符号は1ビットまでの誤りなら訂正もできます。

このような知識もよく問われるので覚えておきましょう。

例題

問題

さっそくですが例題を解いていきます。

応用情報技術者試験からの出題です。

ハミング符号とは,データに冗長ビットを付加して, 1ビットの誤りを訂正できるようにしたものである。ここでは,X1,X2,X3,X4の4ビットから成るデータに,3ビットの冗長ビットP3,P2,P1を付加したハミング符号 X1X2X3P3X4P2P1 を考える。付加ビットP1,P2,P3は,それぞれ
   X1 \oplus X3 \oplus X4 \oplus P1=0
   X1 \oplus X2 \oplus X4 \oplus P2=0
   X1 \oplus X2 \oplus X3 \oplus P3=0
となるように決める。ここで⊕は排他的論理和を表す。
ハミング符号 1110011 には1ビットの誤りが存在する。誤りビットを訂正したハミング符号はどれか。

ア.0110011
イ.1010011
ウ.1100011
エ.1110111

(出典:平成30年度 春期 応用情報技術者試験 午前 問3)

解答

ハミング符号 X1X2X3P3X4P2P1 を考える」とあり、ハミング符号は「1110011 」であることから、

X1=1
X2=1
X3=1
P3=0
X4=0
P2=1
P1=1

であることがわかります。

それでは3つの式に具体的な数字を入れていきます。

一番目の式は、

 X1 \oplus X3 \oplus X4 \oplus P1=1 \oplus 1 \oplus 0 \oplus 1

となります。

演算結果は1となり0になっていないので、X1かX3かX4が誤っていることがわかります。


二番目の式は

 X1 \oplus X2 \oplus X4 \oplus P2=1 \oplus 1 \oplus 0 \oplus 1

となります。

こちらも演算結果は1となり0になっていないので、X1かX2かX4が誤っていることがわかります。


三番目の式は

 X1 \oplus X2 \oplus X3 \oplus P3=1 \oplus 1 \oplus 0 \oplus 1

となります。

こちらも演算結果は1となり0になっていないので、X1かX2かX3が誤っていることがわかります。


三つの式すべてに誤っているビットが含まれていることがわかりました。

したがって、三つの式すべてに含まれているビットが誤っているビットであると断定できます。

つまり、誤っているビットはX1です。

以上より、答えは「1110011 」から先頭のビットを反転した「ア.0110011 」となります。

おわりに

今回はハミング符号による誤り訂正について説明しました。

難しくはないので確実に正解できるようにしておきましょう。

【基本・応用情報技術者】オートマトンと状態遷移図

こんにちは。たろすです。

今回はオートマトンと状態遷移図について説明します。

オートマトンとは

オートマトンは一定の規則に従って複数の内部状態の間を遷移する仮想的な機械で、現在の状態と入力の組み合わせを規則の中から探し出し、指定された次の状態へ遷移する。規則に該当する組み合わせがなければ同じ状態を維持する。規則は状態遷移表や状態遷移図として書き表すことができる。

オートマトン(状態機械)とは - IT用語辞典 e-Words

つまり、現在の状態にある入力を与えると特定の状態へ遷移する機械のことです。

オートマトンの問題では状態遷移図がよく使われます。

状態遷移図の読み方

次のような状態遷移図があります。

f:id:talosta:20210508100730p:plain

丸が状態で、矢印が遷移、矢印の横にある値が入力を表しています。

まず最初に確認するのが初期状態と終了状態です。

なにもないところから矢印が入ってきているq0が初期状態、二重丸のq2が終了状態です。

f:id:talosta:20210508100848p:plain

問題としては選択肢としてビット列が与えられて、「次の状態遷移図で表現されるオートマトンで受理されるビット列はどれか」などと問われます。

「受理される」とは入力をすべて入れたときに終了状態になるものを指します。

具体的な読み方は例題を解きながら見ていきましょう。

例題

次の状態遷移図で表現されるオートマトンで受理されるビット列はどれか。

f:id:talosta:20210508101432p:plain

ア.00100
イ.10110
ウ.11110
エ.00111

ア(00100)の解説

初期状態はq0です。

f:id:talosta:20210508101943p:plain

アの最初の入力は0なのでq1に移ります。

f:id:talosta:20210508102113p:plain

次の入力も0なので自己遷移します。

f:id:talosta:20210508103028p:plain

次の入力は1なのでq2に遷移します。

f:id:talosta:20210508103108p:plain

ここで終了状態に到達しましたが、入力がまだあるので続きます。

次の入力は0なのでq0に遷移します。

f:id:talosta:20210508103206p:plain

さらに次の入力も0なのでq1に遷移します。

f:id:talosta:20210508103310p:plain

すべての入力を終えて到達した状態はq1なのでアのビット列は受理されません。

イ(10110)の解説

解き方はアと同様なので詳しい解説は省略します。

f:id:talosta:20210508103438p:plain

f:id:talosta:20210508103600p:plain

f:id:talosta:20210508103616p:plain

f:id:talosta:20210508103629p:plain

f:id:talosta:20210508103644p:plain

f:id:talosta:20210508103701p:plain

ウ(11110)の解説

解き方はアと同様なので詳しい解説は省略します。

f:id:talosta:20210508101943p:plain

f:id:talosta:20210508103600p:plain

f:id:talosta:20210508103644p:plain

f:id:talosta:20210508103108p:plain

f:id:talosta:20210508103644p:plain

f:id:talosta:20210508103701p:plain

エ(00111)の解説

解き方はアと同様なので詳しい解説は省略します。

f:id:talosta:20210508101943p:plain

f:id:talosta:20210508103310p:plain

f:id:talosta:20210508103028p:plain

f:id:talosta:20210508103108p:plain

f:id:talosta:20210508103644p:plain

f:id:talosta:20210508103108p:plain

最後に到達した状態が終了状態となりました。

したがって答えはエになります。

おわりに

今回はオートマトンと状態遷移図について説明しました。

難しくはないので確実に正解できるようにしておきましょう。