データ構造の考え方、仕組みを習得し、応用する。・代表的なデータ構造の種類、特徴、操作を習得し応用する。・データ構造の基本的な考え方を理解する。応用情報データ構造の考え方、仕組みや、BNFを使用したデータ構造の定義方法を理解する。配列の考え方を理解し、データの格納方法、取り出し方法などの操作を理解する。応用情報リストの考え方、その操作を理解する。応用情報スタックとキューの考え方、その操作を理解する。木構造の種類と考え方、木の巡回法、節の追加や削除、ヒープの再構成などを理解する。応用情報データ構造の考え方、仕組みや、BNFを使用したデータ構造の定義方法を理解する。「データ構造」とは、コンピュータでデータを系統立てて扱う仕組みをいいます。プログラミングに際して、データ構造の設計はすべての基礎・土台となるものです。目的とする処理が確実に、迅速に実行できるようなデータ構造となるよう、あらかじめ十分検討し設計しておく必要があります。変数プログラムはコンピュータへの操作を指示するもので、コンピュータになにがしかの処理をさせるときに、支持を効率的に与えます。そのプログラムの内部で、情報を一時的に格納するための「器」として「変数」を用います。変数を定義する際には「変数名」を付与し、他のデータと区別できるようにします。変数では、数値のみならず、文字や文字列、真偽を表す真理値など様々な情報を扱うことが出来ます。その際、変数が扱う情報の種類を「型」と呼びます。データの型コンピュータで扱う様々なデータは、用途によって以下のような種類に分けることが出来ます。これをデータの型(属性)といいます。プログラム内部で扱われる変数には、それぞれ「型」が定義されていて、「型」が異なる変数に情報を入れることは、基本的には出来ません。小数点がつかない整数値のみ扱える。小数点以下の数値も扱える。英字や記号、漢字やひらがな・カタカナなどが扱える。文字コードによって文字を区別する。偽(False)かの2つの値のみ扱える。データ構造の種類コンピュータでたくさんのデータを管理するには、そのデータ構造をなるべく用途に適した形で、コンパクトに収納でき、かつ簡単に探し出せるものにしておくと便利です。代表的なデータ構造には、レコード、配列、リストがあります。レコードプログラムがデータを処理する時の基本単位になるまとまりを、レコードといいます。1件のレコードには型の異なる幾つかの項目(=フィールド)があるのが一般的です。いったフィールドが含まれます。同じフィールドを持つレコードの集まりのことを「ファイル」といいます。配列の考え方を理解し、データの格納方法、取り出し方法などの操作を理解する。コンピュータで大量のデータを高速に処理する場合に、同じ型の変数を、先頭から順番を付けて並べたものを配列といいます。配列におけるそれぞれの変数は「配列要素」または「要素」と呼ばれます。要素にはそれぞれを区別するために順番に番号が振られています。この番号のことを添字(インデックス)といい、添字を指定すると、配列の中から特定のデータを任意の順番で探し出すことが出来ます。添字は先頭のデータを1から数える場合と、0から数える場合とがあります。配列は構造が単純で、先頭から順に読み込んでいくには便利ですが、データの論理的な順序どおりに物理的にも並んでいるように作られていないといけないので、後からデータを追加したり、削除したりする場合に、そこから後ろのデータを全てずらして書き直さなければならないというデメリットがあります。配列内の要素の数が決まっているものを「静的配列」といいます。行が2行以上の多次元配列もあります。2行の場合は二次元配列といいます。5名の数学のテスト結果を1行目に、英語のテスト結果を2行目に格納する、といった具合に利用することが出来ます。二次元配列を使う場合には添字が二つ必要となり、添字の1つ目が行番号、2つ目が列番号となります。応用情報リストの考え方、その操作を理解する。用語例:線形リスト、単方向リスト、双方向リスト、環状リスト、リンク付きリスト配列のデメリットとリスト配列では、要素の追加・挿入をする場合に、挿入する位置以降のすべての要素を1つずつずらす処理が必要になるため、要素の数が大量の場合は処理に時間がかかります。要素の追加や削除が非効率という欠点があります。この欠点を踏まえ、追加や削除を効率良く行うことが出来るように工夫されたデータ構造が「リスト」です。リスト(線形リスト)リストは同じ型のデータを集めて、それぞれに「自分の次のデータがどれか」という情報(=ポインタ)を持たせて連結したものです。データは物理的に順番に並んでいる必要はありません。リストの中のデータは、データ部とポインタ部からなります。データ部には実際のデータが、ポインタ部には次のデータの格納場所が入っています。ポインタ部に入っているメモリ城の格納場所のことをアドレス(番地)といいます。リスト構造には配列のような添字という概念はありません。そのため、配列のように添え字を使って任意の要素にアクセスする、ということが出来ません。単方向リストと双方向リストリストには、次へのポインタのみを持つ単方向リストと、前後へのポインタを両方持つ双方向リストがあります。単方向リストは先頭からデータを探すことしか出来ないので、後ろの方のデータを見つけるには時間がかかります。双方向リストは両方向のポインタを持つため、単方向リストよりもサイズは大きくなりますが、各データの前後、およびリストの先頭、末尾を示すポインタを持っているので、データを後ろから探索することも出来ます。リスト構造への追加と削除リスト構造のデータはポインタを保つ必要があるため、配列よりも大きくなりますが、データの挿入や削除をする際、その前後のポインタを書き換えるだけで済むので、データを頻繁に更新する場合に適しています。環状リスト単方向リストでは、末尾のデータの「次へのポインタ」は空になります。双方向リストでは、先頭のデータの「前へのポインタ」と、末尾のデータの「次へのポインタ」は空になります。これらを空にせずに、データが環状につながっているようにしたものが環状リストです。環状リストにはポインタを1つ持つ単方向リストを基にするものと、ポインタを2つ持つ双方向リストを基にするものとがあります。応用情報スタックとキューの考え方、その操作を理解する。Out:後入れ先出し)ともいいます。スタックにデータを追加する動作をプッシュ(push)、データを取り出す動作を(pop)といいます。スタック構造は、逆ポーランド記法の計算やプログラムにおける提携処理の呼び出しと戻りなどに応用されています。逆ポーランド記法の説明で「コンピュータと相性が良い」と述べていますが、その特徴とスタックというデータ構造は密接に関連しています。逆ポーランド記法で記述された式を処理する場合、以下のルールでスタックを使った処理を行っています。数値が来たら、その数値をスタックにPUSHする。演算子が来たら・・・スタックからデータをPOPする。(データ1)スタックからデータをPOPする。(データ2)データ1とデータ2を演算し、その結果をスタックにPUSHする。この処理を行うと、最終的にスタックの一番上に一連の式の結果が保存されています。Out:先入れ先出し)ともいいます。キューにデータを追加する動作をエンキュー(ENQ)、データを取り出す動作をデキュー(DEQ)といいます。キューは通信において、タイミング調整に使われることがあります。代表的な例として、送信バッファや受信バッファがあります。バッファとは、一時的にデータを入れる場所のことです。コンピュータでのデータ受信の際に、インターネット等伝送路からのデータ量が一定していない場合、そのまま受信してしまうとデータ受信ペースの遅れや、瞬間的に大量のデータを受信した場合などで不都合が生じます。このような場合に受信バッファが用いられ、受信したデータを一時的に格納しておき、できるだけコンピュータが受信するデータ量を一定にするようにします。スタックやキューをプログラムで実現する場合の違いスタックやキューをプログラムで実装する場合、データ量や用途に応じて配列構造とリスト構造を使い分けます。木構造の種類と考え方、木の巡回法、節の追加や削除、ヒープの再構成などを理解する。データ間の階層的な関係、つまり親と子のような関係を表現するのに用いられるデータ構造です。大量の情報を系統的に管理する際に有効です。木構造は、「節(ノード)」と「枝(ブランチ)」から構成されています。最上位の節は「根(ルート)」といいます。最下位の節を「葉(リーフ)」といいます。複数に枝分かれしている場合には、「葉(リーフ)」は複数になります。「枝(ブランチ)」は節と節をつなぐ経路のことです。ある節の上の枝につながる節を親、下の枝につながる節を子といいます。木構造では、親の節から子の節をたどっていくことでデータを取り出すことができます。木構造の深さ木構造では、節や葉の階層を示すため「深さ」という数値が使われます。深さは根の階層を0として、下に行くと1ずつ増えていきます。木構造の部分を示す時に「部分木」という言葉が使われます。ある節に注目した時、その節の左の枝から下の木構造を「左部分木」、節の右の枝から下の木構造を「右部分木」といいます。節から出る枝が2本以下である木を二分木といいます。対して、節から出る枝が2本より多い気を多分木といいます。二分木では、節の左側に繋がる部分を左の子(左部分木)、右側に繋がる部分を右の子(右部分木)といいます。二分木の中で、根から葉までの深さが全て同じものを「完全二分木」と呼びます。一般的な二分木は「葉の深さの差が1以内である」、「葉を除く全ての節が左部分木を持っている」という二つの条件を満たすものです。同じ階層の節に順位があるものを順序木といいます。順序木では一つの節の下の節や葉は左側のほうが高い順位と見なされます。順序木ではデータの格納方法を工夫することにより、データの検索や大小関係での並び替えを効率的に行うことが出来ます。木構造からデータを探して読み出すことを「木の巡回」といいます。二分木の巡回法には幅優先探索と深さ優先探索があります。階層が浅いデータを優先して検索する方法です。幅優先探索を行うと、最初に子のデータを読み出します。子のデータが検索したデータでない場合は、1階層目の節や葉のデータを左から右へと順番に読み出していきます。1階層目のデータが検索したデータでない場合は、次は2階層目と進んでいく、という方法です。深さ優先探索は、左部分木を優先して、階層が下のデータを先に読み出す方法です。順番で読み出す方法です。右の図を例にとって説明すると、最初の節である根のデータ1を読み出し、次に左部分木の節のデータ2を読み出します。その次は2階層目の左部分木のデータ3を読み出します。順番で読み出す方法です。右の図を例にとって説明すると。根から始めて2階層目の左部分木で左部分旗がなくなるので、データ1を読み出します。次に、上の階層に戻ってデータ2を読み出します。その次に2階層目の右部分木のデータ3を読み出します。順番で読み出す方法です。右の図を例にとって説明すると、根から始めて2階層目の左部分木で左部分旗がなくなるので、データ1を読み出します。次は2階層目の右部分木のデータ2を読み出します。その次は、上の階層に戻ってデータ3を読み出します。その次は、1階層目の右部分木ですが、そこからは左部分木が出ているので、左部分木のデータ4を読み出します。二分木に対して、データを格納するルールを定めることにより、木構造をデータの検索や大小順での並び替えに活用できます。データの検索に活用する例が「2分探索木」、整列に活用する例が「ヒープ」です。二分木の中でも、左の木の全てのデータが親よりも小さく、右の木の全てのデータが親よりも大きいという声質を持つ木を「2分探索木」といいます。2分探索木は完全二分木である必要はありません。データの探索2分探索木を用いると、節毎に大小関係を比較することにより、データの探索を効率的に行うことが出来ます。9階層の木構造の場合、深さ優先探索や幅優先探索を行うと、最大で1000回を越える比較が行われますが、2分探索木ならば、比較回数は10回未満で済みます。データの追加2分探索木にデータを追加する場合は、検索と同じような手順で、追加する場所を探していきます。データを追加した後も2分探索木になるようにします。データの削除2分探索木でデータを削除する場合、削除する節の持つ枝の数により処理が異なります。そのまま葉を削除します。節を削除して、下の節をつなぎ直します。削除する節の左部分木の中で、最も大きな値のデータを削除する節に移動します。削除をこの手順で行うことにより、削除を行った後も2分探索木になるようにします。木構造は、追加や削除を繰り返していくうちに、葉の深さにばらつきが出て、部分木のバランスが悪くなることがあります。部分木のバランスが悪くなると、探索の効率が低下してしまうので、一定のルールを定めて、部分木のバランスを取る木構造があります。そのような木構造を「バランス木」といいます。完全二分木はバランス木の一種です。他のバランス木には「AVL木」や「B木」があります。葉の深さの差が常に1以下の木構造です。完全二分木と異なり、葉でない節が左部分木を持つ必要はありません。AVL木では、要素の追加や削除が発生する時に、バランスが崩れていないかをチェックしつつ、崩れていればそれを回復する処理(=再構築)を行う必要があります。そのため、追加や削除が発生する場合には、通常の2分探索木より手間がかかるのですが、バランスを取りながら木の深さを浅く保つことで、探索時のコストを抑えることが可能になります。B木B木は多分木のバランス木の一つです。一つの節に入れられるデータの個数や分岐の数は、「次数」と呼ばれる数値で決まります。次数をNとするB木を「N次のB木」といいます。N次のB木は以下の4つの条件を満たす必要があります。一つの節のデータ数は2×N個以下であること。根以外の節はN個以上のデータを持つこと。葉以外の節はデータ数+1個の枝を持つこと。すべての葉は同じ階層であること。バランス木の実用例バランス木の実用例としては、データベースの「インデックス(索引)機能」にB木が多く利用されています。(AVL木を使う場合もあります。)検索の処理を高速に行うことを優先したい場合には、単純な2分探索木よりも、バランス木が用いられます。単純な2分探索木で最初の木構造の作り方が悪いと、偏った木構造となり、検索のコストがリスト構造と変わらなくなることがあるためです。アルゴリズム、流れ図の考え方、表現方法を習得し、応用する。・代表的なアルゴリズムを習得し、応用する。・アルゴリズムの設計方法を習得し、応用する。・アルゴリズムと流れ図の基本的な考え方と表現方法を理解する。返しなど、処理手順の表現方法を理解し、流れ図を描く方法を理解する。整列のアルゴリズム、併合のアルゴリズム、探索のアルゴリズムを理解する。再帰的アルゴリズムの考え方、特徴、実現に適したデータ構造を理解する。応用情報グラフのアルゴリズムを理解する。アルゴリズムを理解する。コントロールブレイク処理、編集処理のアルゴリズムを理解する。近似アルゴリズムを理解する。応用情報モンテカルロ法を例として、確率アルゴリズムを理解する。進化論の適用例であることを理解する。例に、自然言語処理のアルゴリズムを理解する。応用情報データ圧縮のアルゴリズムを理解する。用語例:ランレングス法。応用情報3次元図形処理アルゴリズムを理解する。応用情報OSのメモリ管理の方法について、空きメモリ管理のためのデータ構造、メモリの割当、開放などのアルゴリズムを理解する。応用情報アルゴリズムは、擬似言語、流れ図、決定表(デシジョンテーブル)などを用いて表現することを理解する。アルゴリズムの設計方法を理解する。返しなど、処理手順の表現方法を理解し、流れ図を描く方法を理解する。み処理、判断、ループ端、データ、線アルゴリズムアルゴリズムとは、目的にたどり着くための道筋や処理の手順のことです。同じ結果を出すための処理であっても、より整理されたアルゴリズムで行うほうが、効率よく結果を得ることが出来ます。プログラムを作るときは、特にどんなアルゴリズムを使うかが重要になります。流れ図は「フローチャート」ともいい、処理のアルゴリズムを視覚的に表現できる図解法です。プログラムの設計によく用いられます。流れ図は以下の記号類を使って、上から下に流れていくように描きます。順番に処理を実行していく。流れ図では、上から順に、四角系の中に処理を描いていきます。条件によって異なる処理を実行する。流れ図では、ひし形の中に分岐の条件を書き、矢印を分岐させます。繰り返しを終える条件が満たされるまで、同じ処理を繰り返す。繰り返しを終える条件を、角を切り取った四角形(=ループ端)の中に描き、繰り返す処理を2つのループ端の間に描いていきます。繰り返しの図形を使わずに、右記のように分岐のひし形を使って描く方法もあります。前判定型と後判定型の繰り返し反復型には、先に繰り返しを行うかどうかの条件判定をしてから、一通りの処理を行う「前判定型」と、処理を一通り実行した後で、終了するかどうかの条件判定を行う「後判定型」の2種類があります。反復処理の「1回め」をどのように扱うかで、前判定型と後判定型を使い分けます。前判定型では、1回目の条件判定で終了条件を満たすと、繰り返しの処理は1回も実行されません。対して後判定型では繰り返し処理の後で終了条件を判定するので、少なくとも1回は処理が実行されます。二人で行うゲームを例に、流れ図を見てみましょう。互いにじゃんけんをし、勝ったほうがピコピコハンマーで相手の頭を叩きます。同時に、負けた方はヘルメットで防御します。ハンマーが頭にヒットすれば叩いた方の勝ちとなる、というゲームです。整列のアルゴリズムを理解する。おえういあ数値データは値の大小順に整列され、文字データは文字コードの値の大小順で整列されます。英字はアルファベット順に、ひらがな、カタカナは50音順に文字コードが割り振られているため、英字同士はアルファベット順、ひらがな同士、カタカナ同士は50音順で並び替えが可能になります。処理が単純で実装が容易。処理が単純で実装が容易。処理が単純で実装が容易。アルゴリズムの中では高速。挿入ソートの改良版だが、場合によっては挿入ソートと速度が変わらない。「再帰」の概念の理解が必要。「再帰」の概念の理解が必要。「ヒープ木」の概念の理解が必要。バブルソート代表的な整列のアルゴリズムに、バブルソートがあります。バブルソートは一つとなりと比べては入れ替える、という処理を繰り返していく方法です。隣同士のうち、大きい方が前に並ぶように入れ替えていくと、結果的に全体が降順で並びます。逆に小さいほうが前に並ぶようにすると昇順となります。例:「1・5・7・3・9」の5枚のカードをバブルソートで降順に並び替える。要素[1]と[2]を比較して、大きい方が前になるように入れ替える。続いて[2]と[3]、[3]と[4]、[4]と[5]の順に比較と入れ替えを行う。この時点で、要素[5]が最小値になるので、要素[5]の位置が確定する。要素[1]~[4]について、同様に比較と入れ替えを繰り返し、各要素の位置を確定する。