木構造

この記事での学習内容 ITパスポート 基本情報 応用情報

木構造の種類と考え方、木の巡回法、節の追加や削除、ヒープの再構成などを理解する。

用語例:根、葉、枝、二分木、完全二分木、バランス木、順序木、多分木、探索木、深さ優先探索、幅優先探索、先行順、後行順、中間順

木構造

 

木構造はデータ間の階層的な関係、つまり親と子のような関係を表現するのに用いられるデータ構造です。大量の情報を系統的に管理する際に有効です。

木構造は、「節(ノード)」と「枝(ブランチ)」から構成されています。最上位の節は「根(ルート)」といいます。また、最下位の節を「葉(リーフ)」といいます。複数に枝分かれしている場合には、「葉(リーフ)」は複数になります。「枝(ブランチ)」は節と節をつなぐ経路のことです。

また、ある節の上の枝につながる節を親、下の枝につながる節を子といいます。

木構造では、親の節から子の節をたどっていくことでデータを取り出すことができます。

木構造の深さ

木構造では、節や葉の階層を示すため「深さ」という数値が使われます。深さは根の階層を0として、下に行くと1ずつ増えていきます。

部分木

木構造の部分を示す時に「部分木」という言葉が使われます。

ある節に注目した時、その節の左の枝から下の木構造を「左部分木」、節の右の枝から下の木構造を「右部分木」といいます。

二分木と多分木

節から出る枝が2本以下である木を二分木といいます。対して、節から出る枝が2本より多い気を多分木といいます。

二分木では、節の左側に繋がる部分を左の子(左部分木)、右側に繋がる部分を右の子(右部分木)といいます。

二分木の中で、根から葉までの深さが全て同じものを「完全二分木」と呼びます。一般的な二分木は「葉の深さの差が1以内である」、「葉を除く全ての節が左部分木を持っている」という二つの条件を満たすものです。

同じ階層の節に順位があるものを順序木といいます。順序木では一つの節の下の節や葉は左側のほうが高い順位と見なされます。順序木ではデータの格納方法を工夫することにより、データの検索や大小関係での並び替えを効率的に行うことが出来ます。

木の巡回法

木構造からデータを探して読み出すことを「木の巡回」といいます。二分木の巡回法には幅優先探索と深さ優先探索があります。

木の幅優先探索

幅優先探索は、階層が浅いデータを優先して検索する方法です。

幅優先探索を行うと、最初に子のデータを読み出します。子のデータが検索したデータでない場合は、1階層目の節や葉のデータを左から右へと順番に読み出していきます。1階層目のデータが検索したデータでない場合は、次は2階層目と進んでいく、という方法です。

木の深さ優先探索

深さ優先探索は、左部分木を優先して、階層が下のデータを先に読み出す方法です。

葉以外の節のデータと、葉のデータを読み出す順番の違いにより、先行順探索、中間順探索、後行順探索の3種類があります。

先行順探索

先行順は、節、左部分木、右部分木の順番で読み出す方法です。

右の図を例にとって説明すると、最初の節である根のデータ1を読み出し、次に左部分木の節のデータ2を読み出します。
その次は2階層目の左部分木のデータ3を読み出します。
3階層目はないので、2階層目の右部分木のデータ4を読み出します。

中間順探索

中間順は、左部分木、節、右部分木の順番で読み出す方法です。

右の図を例にとって説明すると。根から始めて2階層目の左部分木で左部分旗がなくなるので、データ1を読み出します。
次に、上の階層に戻ってデータ2を読み出します。
その次に2階層目の右部分木のデータ3を読み出します。
2階層目の読み出しが終わると、次は根のデータ4を読み出します。

後行順探索

後行順は、左部分木、右部分木、節の順番で読み出す方法です。

右の図を例にとって説明すると、根から始めて2階層目の左部分木で左部分旗がなくなるので、データ1を読み出します。
次は2階層目の右部分木のデータ2を読み出します。
その次は、上の階層に戻ってデータ3を読み出します。
その次は、1階層目の右部分木ですが、そこからは左部分木が出ているので、左部分木のデータ4を読み出します。

二分探索木の応用

二分木に対して、データを格納するルールを定めることにより、木構造をデータの検索や大小順での並び替えに活用できます。

データの検索に活用する例が「2分探索木」、整列に活用する例が「ヒープ」です。

2分探索木

二分木の中でも、左の木の全てのデータが親よりも小さく、右の木の全てのデータが親よりも大きいという声質を持つ木を「2分探索木」といいます。
なお、2分探索木は完全二分木である必要はありません。

データの探索

2分探索木を用いると、節毎に大小関係を比較することにより、データの探索を効率的に行うことが出来ます。

例えば、9階層の木構造の場合、深さ優先探索や幅優先探索を行うと、最大で1000回を越える比較が行われますが、2分探索木ならば、比較回数は10回未満で済みます。

データの追加

2分探索木にデータを追加する場合は、検索と同じような手順で、追加する場所を探していきます。

データを追加した後も2分探索木になるようにします。

データの削除

2分探索木でデータを削除する場合、削除する節の持つ枝の数により処理が異なります。

  • 枝のない葉の場合: そのまま葉を削除します。
  • 枝が1本の場合: 節を削除して、下の節をつなぎ直します。
  • 枝が2本の場合: 削除する節の左部分木の中で、最も大きな値のデータを削除する節に移動します。

削除をこの手順で行うことにより、削除を行った後も2分探索木になるようにします。

バランス木

木構造は、追加や削除を繰り返していくうちに、葉の深さにばらつきが出て、部分木のバランスが悪くなることがあります。

部分木のバランスが悪くなると、探索の効率が低下してしまうので、一定のルールを定めて、部分木のバランスを取る木構造があります。そのような木構造を「バランス木」といいます。
完全二分木はバランス木の一種です。他のバランス木には「AVL木」や「B木」があります。

AVL木

葉の深さの差が常に1以下の木構造です。完全二分木と異なり、葉でない節が左部分木を持つ必要はありません。

AVL木では、要素の追加や削除が発生する時に、バランスが崩れていないかをチェックしつつ、崩れていればそれを回復する処理(=再構築)を行う必要があります。そのため、追加や削除が発生する場合には、通常の2分探索木より手間がかかるのですが、バランスを取りながら木の深さを浅く保つことで、探索時のコストを抑えることが可能になります。

B木

B木は多分木のバランス木の一つです。一つの節に入れられるデータの個数や分岐の数は、「次数」と呼ばれる数値で決まります。

次数をNとするB木を「N次のB木」といいます。N次のB木は以下の4つの条件を満たす必要があります。

  • 一つの節のデータ数は2×N個以下であること。
  • 根以外の節はN個以上のデータを持つこと。
  • 葉以外の節はデータ数+1個の枝を持つこと。
  • すべての葉は同じ階層であること。

バランス木の実用例

バランス木の実用例としては、データベースの「インデックス(索引)機能」にB木が多く利用されています。(AVL木を使う場合もあります。)

検索の処理を高速に行うことを優先したい場合には、単純な2分探索木よりも、バランス木が用いられます。
単純な2分探索木で最初の木構造の作り方が悪いと、偏った木構造となり、検索のコストがリスト構造と変わらなくなることがあるためです。

スタックとキュー

この記事での学習内容 基本情報 応用情報

スタックとキューの考え方、その操作を理解する。

用語例:FIFO、LIFO、プッシュ、ポップ

スタック(LIFO)

スタックは、最後に入れたものを最初に取り出すデータ構造で、LIFO(Last In, First Out:後入れ先出し)ともいいます。

スタックにデータを追加する動作をプッシュ(push)、データを取り出す動作を(pop)といいます。

スタック構造は、逆ポーランド記法の計算やプログラムにおける提携処理の呼び出しと戻りなどに応用されています。

逆ポーランド記法の説明で「コンピュータと相性が良い」と述べていますが、その特徴とスタックというデータ構造は密接に関連しています。

逆ポーランド記法で記述された式を処理する場合、以下のルールでスタックを使った処理を行っています。

  • 数値が来たら、その数値をスタックにPUSHする。
  • 演算子が来たら・・・
    • スタックからデータをPOPする。(データ1)
    • スタックからデータをPOPする。(データ2)
    • データ1とデータ2を演算し、その結果をスタックにPUSHする。

この処理を行うと、最終的にスタックの一番上に一連の式の結果が保存されています。

キュー(FIFO)

キュートは、最初に入れたデータを最初に取り出すデータ構造で、FIFO(First In, First Out:先入れ先出し)ともいいます。

キューにデータを追加する動作をエンキュー(ENQ)、データを取り出す動作をデキュー(DEQ)といいます。

キューは通信において、タイミング調整に使われることがあります。代表的な例として、送信バッファや受信バッファがあります。バッファとは、一時的にデータを入れる場所のことです。

例えば、コンピュータでのデータ受信の際に、インターネット等伝送路からのデータ量が一定していない場合、そのまま受信してしまうとデータ受信ペースの遅れや、瞬間的に大量のデータを受信した場合などで不都合が生じます。このような場合に受信バッファが用いられ、受信したデータを一時的に格納しておき、できるだけコンピュータが受信するデータ量を一定にするようにします。

スタックやキューをプログラムで実現する場合の違い

スタックやキューをプログラムで実装する場合、データ量や用途に応じて配列構造とリスト構造を使い分けます。

 配列で実現リストで実現
キュー先頭を指すポインタと最後尾を指すポインタが必要
処理が単純で速い
単方向リストで可能
データあふれの心配がない
スタック最新のデータを示すポインタが必要
処理が単純で速い
単方向リストで可能
データあふれの心配がない

リスト

この記事での学習内容 ITパスポート 基本情報 応用情報

リストの考え方、その操作を理解する。

用語例:線形リスト、単方向リスト、双方向リスト、環状リスト、リンク付きリスト

配列のデメリットとリスト

配列では、要素の追加・挿入をする場合に、挿入する位置以降のすべての要素を1つずつずらす処理が必要になるため、要素の数が大量の場合は処理に時間がかかります。
つまり、要素の追加や削除が非効率という欠点があります。

この欠点を踏まえ、追加や削除を効率良く行うことが出来るように工夫されたデータ構造が「リスト」です。

リスト(線形リスト)

リストは同じ型のデータを集めて、それぞれに「自分の次のデータがどれか」という情報(=ポインタ)を持たせて連結したものです。データは物理的に順番に並んでいる必要はありません。

リストの中のデータは、データ部とポインタ部からなります。
データ部には実際のデータが、ポインタ部には次のデータの格納場所が入っています。ポインタ部に入っているメモリ城の格納場所のことをアドレス(番地)といいます。

なお、リスト構造には配列のような添字という概念はありません。そのため、配列のように添え字を使って任意の要素にアクセスする、ということが出来ません。

単方向リストと双方向リスト

リストには、次へのポインタのみを持つ単方向リストと、前後へのポインタを両方持つ双方向リストがあります。

単方向リストは先頭からデータを探すことしか出来ないので、後ろの方のデータを見つけるには時間がかかります。

双方向リストは両方向のポインタを持つため、単方向リストよりもサイズは大きくなりますが、各データの前後、およびリストの先頭、末尾を示すポインタを持っているので、データを後ろから探索することも出来ます。

リスト構造への追加と削除

リスト構造のデータはポインタを保つ必要があるため、配列よりも大きくなりますが、データの挿入や削除をする際、その前後のポインタを書き換えるだけで済むので、データを頻繁に更新する場合に適しています。

環状リスト

単方向リストでは、末尾のデータの「次へのポインタ」は空になります。また、双方向リストでは、先頭のデータの「前へのポインタ」と、末尾のデータの「次へのポインタ」は空になります。
これらを空にせずに、データが環状につながっているようにしたものが環状リストです。

環状リストにはポインタを1つ持つ単方向リストを基にするものと、ポインタを2つ持つ双方向リストを基にするものとがあります。

 

配列

この記事での学習内容 ITパスポート 基本情報 応用情報

配列の考え方を理解し、データの格納方法、取り出し方法などの操作を理解する。

用語例:多次元配列、静的配列、動的配列

配列

コンピュータで大量のデータを高速に処理する場合に、同じ型の変数を、先頭から順番を付けて並べたものを配列といいます。

配列におけるそれぞれの変数は「配列要素」または「要素」と呼ばれます。要素にはそれぞれを区別するために順番に番号が振られています。この番号のことを添字(インデックス)といい、添字を指定すると、配列の中から特定のデータを任意の順番で探し出すことが出来ます。

添字は先頭のデータを1から数える場合と、0から数える場合とがあります。

配列の特徴

配列は構造が単純で、先頭から順に読み込んでいくには便利ですが、データの論理的な順序どおりに物理的にも並んでいるように作られていないといけないので、後からデータを追加したり、削除したりする場合に、そこから後ろのデータを全てずらして書き直さなければならないというデメリットがあります。

あらかじめ配列内の要素の数が決まっているものを「静的配列」といいます。
対して、データの数によって配列の要素の数が変化するものを「動的配列」といいます。

二次元配列

配列には、行が2行以上の多次元配列もあります。2行の場合は二次元配列といいます。

例えば、5名の数学のテスト結果を1行目に、英語のテスト結果を2行目に格納する、といった具合に利用することが出来ます。

二次元配列を使う場合には添字が二つ必要となり、添字の1つ目が行番号、2つ目が列番号となります。

データ構造

この記事での学習内容 ITパスポート 基本情報 応用情報

データ構造の考え方、仕組みや、BNFを使用したデータ構造の定義方法を理解する。

データ構造

「データ構造」とは、コンピュータでデータを系統立てて扱う仕組みをいいます。

プログラミングに際して、データ構造の設計はすべての基礎・土台となるものです。目的とする処理が確実に、迅速に実行できるようなデータ構造となるよう、あらかじめ十分検討し設計しておく必要があります。

変数

プログラムはコンピュータへの操作を指示するもので、コンピュータになにがしかの処理をさせるときに、支持を効率的に与えます。

そのプログラムの内部で、情報を一時的に格納するための「器」として「変数」を用います。変数を定義する際には「変数名」を付与し、他のデータと区別できるようにします。

また、変数では、数値のみならず、文字や文字列、真偽を表す真理値など様々な情報を扱うことが出来ます。その際、変数が扱う情報の種類を「型」と呼びます。

データの型

コンピュータで扱う様々なデータは、用途によって以下のような種類に分けることが出来ます。これをデータの型(属性)といいます。

プログラム内部で扱われる変数には、それぞれ「型」が定義されていて、「型」が異なる変数に情報を入れることは、基本的には出来ません。

数値型整数型小数点がつかない整数値のみ扱える。
実数型小数点以下の数値も扱える。
文字型英字や記号、漢字やひらがな・カタカナなどが扱える。
文字コードによって文字を区別する。
論理型真(True) か偽(False)かの2つの値のみ扱える。

データ構造の種類

コンピュータでたくさんのデータを管理するには、そのデータ構造をなるべく用途に適した形で、コンパクトに収納でき、かつ簡単に探し出せるものにしておくと便利です。

代表的なデータ構造には、レコード、配列、リストがあります。

レコード

プログラムがデータを処理する時の基本単位になるまとまりを、レコードといいます。

1件のレコードには型の異なる幾つかの項目(=フィールド)があるのが一般的です。

例えば「住所録」のデータであれば、一人分のデータを1件のレコードとし、その中に「氏名」「住所」「生年月日」といったフィールドが含まれます。

また、同じフィールドを持つレコードの集まりのことを「ファイル」といいます。

 

データ構造(概要)

情報処理技術者試験での学習内容

【基本情報・応用情報】
・データ構造の考え方、仕組みを習得し、応用する。
・代表的なデータ構造の種類、特徴、操作を習得し応用する。

【ITパスポート】
・データ構造の基本的な考え方を理解する。

(1)データ構造 ITパスポート 基本情報 応用情報

データ構造の考え方、仕組みや、BNFを使用したデータ構造の定義方法を理解する。

(2)データ構造の種類

1.配列 ITパスポート 基本情報  応用情報

配列の考え方を理解し、データの格納方法、取り出し方法などの操作を理解する。

用語例:多次元配列、静的配列、動的配列

2.リスト ITパスポート 基本情報  応用情報

リストの考え方、その操作を理解する。

用語例:線形リスト、単方向リスト、双方向リスト、環状リスト、リンク付きリスト

3.スタックとキュー 基本情報 応用情報

スタックとキューの考え方、その操作を理解する。

用語例:FIFO、LIFO、プッシュ、ポップ

4.木構造 ITパスポート 基本情報 応用情報

木構造の種類と考え方、木の巡回法、節の追加や削除、ヒープの再構成などを理解する。

用語例:根、葉、枝、二分木、完全二分木、バランス木、順序木、多分木、探索木、深さ優先探索、幅優先探索、先行順、後行順、中間順

 

 

基本情報技術者 平成21年秋 問4

産業機器の機器制御に使われるシーケンス制御の説明として、適切なものはどれか。

  • ア: あらかじめ定められた順序又は条件に従って、制御の各段階を逐次進めていく制御方式である。
  • イ: 外乱が予測できる場合に、あらかじめ外乱を想定して前もって必要な修正動作を行う制御方法である。
  • ウ: 制御量を常に検出して制御に反映しているので、予測できないような外乱に強い制御方法である。
  • エ: ”やや多い”、”やや少ない”などあいまい性に基づく制御方法である。

基本情報技術者 平成22年春 問4

フィードバック制御の説明として、適切なものはどれか。

  • ア: 外乱による影響を検知してから修正動作を行う。
  • イ: 外乱に弱く、それらの影響を増幅させてしまう。
  • ウ: 外乱を検知して、その影響が出ないように修正動作を行う。
  • エ: 外乱を予測して修正動作を行う。

制御に関する理論

この記事での学習内容 基本情報 応用情報

制御の考え方、仕組みを理解する。また、フィードバック制御、フィードフォワード制御など、各種制御の考え方、仕組みを理解する。

用語例:リアルタイムOS、MPUアーキテクチャ、オープンループ、応答特性、制御安定性、PWM(Pulse Width Modulation:パルス幅変調)制御

制御

制御とは、計測によって得られた入力値を元に、出力値を調整することです。

入力や出力に使われるものは、電圧、電流、圧力、温度、音量、音程などアナログ信号が使われます。

これに対して、入力された値をコンピュータ処理する際には、デジタル信号で扱われますので、必要に応じてA/D変換、D/A変換が行われます。

制御システム

制御システムとは、「制御」機能により、他の機器やシステムを管理し、制御するシステムです。

例えば、「バケツに水を汲む」という行動を例に取ってみます。

私たちがバケツに水を汲み場合、当然ながらバケツに入って水の量を見ていて、ちょうどよいところで水を止めます。「制御」とはまさしくこのような機能です。制御をせずに水をくんだ場合、単純に一定時間水を出して止めるという処理になってしまうので、出て来る水の量が外的要因で変わってしまった場合、「ちょうどよい量」の水を組めなくなってしまいます。

つまり、制御システムは外的要因にどう対処するか、がポイントになります。

制御システムにはフィードバック制御、フィードフォワード制御、オープンループ制御などがあります。

センサとアクチュエータ

センサは検知・監視装置であり、外的要因を信号に変換する機能を持ちます。電子的な温度計や、湿度計、回転計などが当てはまります。

アクチュエータは信号を動作に変換する機能を持つ機器です。制御可能なモータ、油圧装置、ヒータ、エンジンのガゾリン噴射装置などが当てはまります。

フィードバック制御

フィードバック制御とは、制御した出力の結果を入力側に戻し、目標値と比較して次の制御に反映させる制御方法です。

例えばエアコンの場合、室温と設定温度の差を計測してエアコンから出る風の温度と風量に反映していきます。

フィードバック制御では、常にセンサを用いて対象(エアコンの場合室温)を監視しています。

そのため、エアコンの場合は窓を開けるなどして室温が急に高くなった場合でもその変化を計測し、エアコンの風量などに反映することが出来ます。

フィードバック制御は変化が起きてから制御量の修正をするため、影響が現れてから修正するという後追いの修正となります。

フィードフォワード制御

フィードフォワード制御は、制御を乱す外的要因が発生する場合に、その影響が出る前に必要な修正を行う制御方法です。

例えばエアコンの場合、室内温度に変化はないけれど、外の気温が下がってきたので、冷房を弱める、といった制御を行うことが出来ます。しかし、室内温度と設定温度が等しくなるとは限りません。

通常は、フィードバック制御と組合せて用いられます。

オープンループ制御

制御量の入力値のみを計算する制御方式です。したがって、出力に対してのフィードバックや外乱などのデータは一切考慮しません。

単純に負荷のかかっていないモータの回転数などを入力電圧だけで制御する場合などに適しています。

クローズドループ制御

モータに対する負荷が変化するような場合、負荷により回転数が変化するので、回転数を一定に保つためには、オープンループ制御ではなく、フィードバック制御が必要になります。

このようなフィードバックや外乱を考慮して入力値を制御する方式をクローズドループ制御といいます。

リアルタイムOS

このような制御システムのコンピュータの制御では、リアルタイムOSが利用されることがあります。

リアルタイムOSとは、リアルタイム処理(=処理に対する応答時間が一定の範囲内であること)が保証されているオペレーティングシステムです。

利用者にとっての利便性よりもデータの処理速度を優先しているのが特徴です。

 

信号処理

この記事での学習内容 基本情報 応用情報

アナログ波形を分析して、雑音を除去し、特徴を抽出する信号処理の考え方、仕組みを理解する。

用語例:DFT(Discrete Fourier Transform:離散フーリエ変換)、FFT(Fast Fourier Transform:高速フーリエ変換)、インパルス応答、フィルタ(ローパスフィルタ、ハイパスフィルタ、バンドパスフィルタ、デジタルフィルタ)、サンプリング定理、D/A変換、A/D変換

信号処理

信号処理とは、音声信号や電気信号などに対して、いろいろな処理をして変換する技術です。処理形式は、アナログ信号処理とデジタル信号処理、相互の変換処理の3種類あります。

コンピュータの入力や出力に使われるものは、温度、音声、画像などアナログ信号が使われます。これに対して、入力された値をコンピュータ処理する際には、デジタル信号で扱われます。このアナログ信号からデジタル信号に変換する処理をA/D変換といい、逆にデジタル信号からアナログ信号に変換するのを、D/A変換とよんでいます。

フィルタリング

アナログデータのうち、デジタル化の対象にする必要がない部分を予め削ることをフィルタリングといいます。

例えば、音声の場合には、人間に聞こえない周波数の部分を予めカットする、といった処理が当てはまります。フィルタリングは「標本化」の際に行い、それ以降の手順で扱うデータの量を削減します。

また、A/D変換する際に、アナログ信号にノイズなどが混入していると、そのまま間違った値が入力されてしまうため、ノイズを取り除く必要があり、そのための装置をフィルタとよんでいます。