「アルゴリズムとプログラミング」カテゴリーアーカイブ

データ構造(概要)

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

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

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

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

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

(2)データ構造の種類

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

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

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

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

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

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

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

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

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

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

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

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

 

 

データ構造

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

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

データ構造

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

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

変数

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

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

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

データの型

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

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

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

データ構造の種類

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

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

レコード

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

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

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

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

 

配列

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

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

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

配列

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

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

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

配列の特徴

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

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

二次元配列

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

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

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

リスト

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

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

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

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

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

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

リスト(線形リスト)

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

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

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

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

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

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

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

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

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

環状リスト

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

環状リストにはポインタを1つ持つ単方向リストを基にするものと、ポインタを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パスポート 基本情報 応用情報

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

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

木構造

 

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

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

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

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

木構造の深さ

木構造では、節や葉の階層を示すため「深さ」という数値が使われます。深さは根の階層を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分探索木で最初の木構造の作り方が悪いと、偏った木構造となり、検索のコストがリスト構造と変わらなくなることがあるためです。

アルゴリズム(概要)

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

【基本情報・応用情報】
・アルゴリズム、流れ図の考え方、表現方法を習得し、応用する。
・代表的なアルゴリズムを習得し、応用する。
・アルゴリズムの設計方法を習得し、応用する。

【ITパスポート】
・アルゴリズムと流れ図の基本的な考え方と表現方法を理解する。

(1)アルゴリズムと流れ図 ITパスポート 基本情報 応用情報

アルゴリズムや流れ図(フローチャート)の考え方、記号、順次、判定、繰り返しなど、処理手順の表現方法を理解し、流れ図を描く方法を理解する。

用語例:端子、処理、定義済み処理、判断、ループ端、データ、線

(2)代表的なアルゴリズム

1.整列、併合、探索のアルゴリズム ITパスポート 基本情報  応用情報

整列のアルゴリズム、併合のアルゴリズム、探索のアルゴリズムを理解する。

用語例:選択ソート、バブルソート、マージソート、挿入ソート、シェルソート、クイックソート、ヒープソート、線形探索法、二分探索法、ハッシュ表探索法、シノニム対策

2.再帰のアルゴリズム 基本情報  応用情報

再帰的アルゴリズムの考え方、特徴、実現に適したデータ構造を理解する。

3.グラフのアルゴリズム 基本情報 応用情報

グラフのアルゴリズムを理解する。

用語例:深さ優先探索、幅優先探索、最短経路探索

4.文字列処理のアルゴリズム 基本情報 応用情報

文字列処理のアルゴリズムを理解する。

用語例:文字列照合、KMP法(クヌース・モリス・プラット法)、BM法(ボイヤ・ムーア法)

5.ファイル処理のアルゴリズム 基本情報 応用情報

バッチ処理などで使用される整列処理、併合処理、コントロールブレイク処理、編集処理のアルゴリズムを理解する。

6.近似アルゴリズム 応用情報

近似アルゴリズムを理解する。

用語例:近似計算

7.確率アルゴリズム 応用情報

モンテカルロ法を例として、確率アルゴリズムを理解する。

8.遺伝的アルゴリズム 応用情報

最適化問題への進化論の適用例であることを理解する。

9.自然言語処理のアルゴリズム 応用情報

情報検索、機械翻訳などを例に、自然言語処理のアルゴリズムを理解する。

10.データ圧縮のアルゴリズム 応用情報

データ圧縮のアルゴリズムを理解する。

用語例:ランレングス法。ハフマン法

11.図形に関するアルゴリズム 応用情報

3次元図形処理アルゴリズムを理解する。

用語例:Zバッファ法、スキャンライン法、レイトレーシング法

12.記憶域管理アルゴリズム 応用情報

OSのメモリ管理の方法について、空きメモリ管理のためのデータ構造、メモリの割当、開放などのアルゴリズムを理解する。

(3)アルゴリズム設計 基本情報 応用情報

アルゴリズムは、擬似言語、流れ図、決定表(デシジョンテーブル)などを用いて表現することを理解する。また。アルゴリズムの設計方法を理解する。

用語例:再帰、分割統治法

 

アルゴリズムと流れ図

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

アルゴリズムや流れ図(フローチャート)の考え方、記号、順次、判定、繰り返しなど、処理手順の表現方法を理解し、流れ図を描く方法を理解する。

用語例:端子、処理、定義済み処理、判断、ループ端、データ、線

アルゴリズム

アルゴリズムとは、目的にたどり着くための道筋や処理の手順のことです。

同じ結果を出すための処理であっても、より整理されたアルゴリズムで行うほうが、効率よく結果を得ることが出来ます。プログラムを作るときは、特にどんなアルゴリズムを使うかが重要になります。

流れ図

流れ図は「フローチャート」ともいい、処理のアルゴリズムを視覚的に表現できる図解法です。プログラムの設計によく用いられます。

流れ図は以下の記号類を使って、上から下に流れていくように描きます。

アルゴリズムの基本構造

アルゴリズムの基本構造には、順次型、分岐型、反復型があります。

  • 順次型: 順番に処理を実行していく。

    流れ図では、上から順に、四角系の中に処理を描いていきます。

  • 分岐型: 条件によって異なる処理を実行する。

    流れ図では、ひし形の中に分岐の条件を書き、矢印を分岐させます。

  • 反復型: 繰り返しを終える条件が満たされるまで、同じ処理を繰り返す。

    繰り返しを終える条件を、角を切り取った四角形(=ループ端)の中に描き、繰り返す処理を2つのループ端の間に描いていきます。


    繰り返しの図形を使わずに、右記のように分岐のひし形を使って描く方法もあります。

前判定型と後判定型の繰り返し

反復型には、先に繰り返しを行うかどうかの条件判定をしてから、一通りの処理を行う「前判定型」と、処理を一通り実行した後で、終了するかどうかの条件判定を行う「後判定型」の2種類があります。

反復処理の「1回め」をどのように扱うかで、前判定型と後判定型を使い分けます。

前判定型では、1回目の条件判定で終了条件を満たすと、繰り返しの処理は1回も実行されません。
対して後判定型では繰り返し処理の後で終了条件を判定するので、少なくとも1回は処理が実行されます。

流れ図を使った例

二人で行うゲームを例に、流れ図を見てみましょう。

互いにじゃんけんをし、勝ったほうがピコピコハンマーで相手の頭を叩きます。同時に、負けた方はヘルメットで防御します。
ハンマーが頭にヒットすれば叩いた方の勝ちとなる、というゲームです。(いわゆる「たたいてかぶってジャンケンポン」)

 

整列-代表的なアルゴリズム1

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

整列のアルゴリズムを理解する。

用語例:選択ソート、バブルソート、マージソート、挿入ソート、シェルソート、クイックソート、ヒープソート

整列(ソート)

整列とは、データを大きい順(降順)または小さい順(昇順)になるように並び替えることです。

 昇順降順
数値「32514」1234554321
英字「BDAEC」ABCDEEDCBA
かな「いあえおう」あいうえおおえういあ

数値データは値の大小順に整列され、文字データは文字コードの値の大小順で整列されます。
英字はアルファベット順に、ひらがな、カタカナは50音順に文字コードが割り振られているため、英字同士はアルファベット順、ひらがな同士、カタカナ同士は50音順で並び替えが可能になります。

代表的なソートアルゴリズムと計算量・速度の比較
名称オーダー(計算量)処理速度備考
バブルソートO(n2)遅い処理が単純で実装が容易。
選択ソートO(n2)遅い処理が単純で実装が容易。
挿入ソートO(n2)遅い処理が単純で実装が容易。
O(n2) のアルゴリズムの中では高速。
シェルソートO(n1.2)~O(n2)程度やや遅い挿入ソートの改良版だが、場合によっては挿入ソートと速度が変わらない。
マージソートO(n log2n)高速「再帰」の概念の理解が必要。
クイックソートO(n log2n)高速「再帰」の概念の理解が必要。
ヒープソートO(n log2n)やや高速「ヒープ木」の概念の理解が必要。

バブルソート

代表的な整列のアルゴリズムに、バブルソートがあります。バブルソートは一つとなりと比べては入れ替える、という処理を繰り返していく方法です。
隣同士のうち、大きい方が前に並ぶように入れ替えていくと、結果的に全体が降順で並びます。逆に小さいほうが前に並ぶようにすると昇順となります。

例:「1・5・7・3・9」の5枚のカードをバブルソートで降順に並び替える。

  1. 要素[1]と[2]を比較して、大きい方が前になるように入れ替える。
  2. 続いて[2]と[3]、[3]と[4]、[4]と[5]の順に比較と入れ替えを行う。
    この時点で、要素[5]が最小値になるので、要素[5]の位置が確定する。
  3. 要素[1]~[4]について、同様に比較と入れ替えを繰り返し、各要素の位置を確定する。
バブルソートの計算量

n個の要素をバブルソートで整列する時の比較の回数は、 ( n ( n - 1 ) ) ÷ 2 であり、n の2乗に比例します。。
オーダ記号で表すと、O(n2) となります。

選択ソート

選択ソートは、最小値の要素を選択して、先頭の要素と置き換える整列アルゴリズムで、基本選択法ともいいます。
処理効率は、バブルソートと変わらず、計算量はO(n2) となります。

例:「1・5・7・3・9」の5枚のカードを選択ソートで昇順に並び替える。

  1. 要素[1]~[5]の値を調べて、最小値を求める。
  2. 1.で求めた最小値を先頭の要素と交換する。
  3. 残りの要素について、1と2を繰り返す。

挿入ソート

挿入ソートは、前の方の整列済みの並びの途中へ、直後の要素を挿入する整列アルゴリズムで、基本挿入法ともいいます。
計算量はO(n2) となります。

例:「1・5・7・3・9」の5枚のカードを挿入ソートで昇順に並び替える。

  1. 先頭の要素を1要素だけの整列済みの並びと見立てる。
  2. 整列済みの並びの要素と、その直後の要素を比較して、バブルソートと同じ要領で並び替えを行う。
  3. 最後の要素を処理するまで、2を繰り返す。

マージソート

マージソートは、並びを2等分しながら、分割された部分同士を併合(マージ)することによって、全体を整列させるアルゴリズムです。

例:「2・7・5・3・8・1・4・6」の8枚のカードをマージソートで昇順に並び替える。

  1. 並びを2等分することを、整列済みの部分並びが見つかるまで反復する。(要素が1つになれば整列済みとみなすので、反復は必ず終了する。)
  2. 整列済みの部分並び同士を、整列状態を保つように併合して、1つの部分並びにする。
  3. 全体が1つの部分並びになるまで、2を反復する。

シェルソート

シェルソートは、シェル氏によって考案された挿入ソートの改良版の整列アルゴリズムです。

  1. 適当な間隔を決めて、等間隔の飛び飛びの要素で作った部分的な並びに対して挿入ソートを適用する。
  2. 間隔を狭めながら、間隔が1になるまで1を繰り返す。

例:「2・7・5・3・8・1・4・6」の8枚のカードをシェルソートで昇順に並び替える。

挿入ソートは、元々の並びが整列状態に近いほど高速になる性質があるため、間隔を空けて部分的な並びを作って徐々に整列させることで速度の向上を図っています。

クイックソート

クイックソートはその名の通り、特に高速な整列アルゴリズムです。

  1. 適当な基準値を定めて、その値より小さい要素を前の方に移し、その値以上の要素を後の方へ移す。
  2. 分割したそれぞれのグループへ、1の処理を反復して、全てのグループに属する要素数が1になるまで繰り返す。

例:「9・2・7・5・3・8・1・4・6」の9枚のカードをクイックソートで昇順に並び替える。

反復する毎に、分割されたグループの数は2倍、4倍、8倍というペースで増えていくので、各グループに含まれる要素の数は急激に減っていきます。
基準値と要素の値を比較する回数が急速に減っていくことが、クイックソートが特に高速である理由です。

ヒープソート

ヒープソートは、ヒープを経由する整列アルゴリズムです。

ヒープは「小さい山」という意味の言葉であり、親の値が必ず子の値以上であることを保つ二分木です。

  1. 要素の並びを元にして、ヒープを構築します。子の処理には、木構造アルゴリズムの一種である、ヒープ構築アルゴリズムを用います。
  2. 根に当たる要素を取り出して、並びの端へ移します。
  3. ヒープに残った要素に対して、ヒープ再構築アルゴリズムを適用します。
  4. 2と3をヒープの要素がなくなるまで繰り返します。

例:「2・7・5・3・1・4・6」の7枚のカードをヒープソートで降順に並び替える。

二分木は木の階層ごとに、部分木の数が2倍、4倍、8倍と増えていきます。値の大小比較の回数は2つの部分木の根を比較するだけなので、ヒープソートは特に高速とされています。

 

探索、併合、再帰-代表的なアルゴリズム2

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

探索、併合のアルゴリズムを理解する。
再帰的アルゴリズムの考え方、特徴、実現に適したデータ構造を理解する。

用語例:線形探索法、二分探索法、ハッシュ表探索法、シノニム対策

探索

「探索」とは配列などに格納されたデータの集まりから、特定のデータを探すことです。その値が見つかる場合と、見つからない場合があり、複数ある場合には最初の一つを見つければ良い場合と、全てを見つける必要がある場合があります。

つまり、探索の結果も見つかったかどうかだけではなく、何番目に見つかったか、いくつあったか、という情報を帰す場合があります。

線形探索法(リニアサーチ)

線形探索法とは、配列の先頭から1つずつ調べてゆき、求めるデータが見つかるか、又は配列の最後まで探し終わったとき探索を終了する方法です。

以下に、線形探索法の場合の流れ図を示します。ここでは、4つの数が入った配列の中から、「5」を探すものとします。

探索する数「5」を変数 x とし、探索対象の数を n [ i ] と表します。
先頭の n [ i ] から順に x と比較していき、同じものが見つかったら、その添字 i を表示して探索を終了、最後まで探して見つからなかった場合は、「無し」と表示して終了します。

なお、線形探索法を行なった場合の探索回数は以下の通りとなり、オーダ記号で表すと O(n) となります。(データは n 個とする)

  • 最小探索回数: 1回
  • 最大探索回数: n回
  • 平均探索回数: (n+1)÷2回

番兵を使った線形探索法

線形探索をより簡単にするために、配列の最後に「番兵」と呼ばれるデータを追加する方法があります。

探すデータと同じ値を、配列の最後尾の次に追加しておくことで、反復の終了条件として、添字の範囲を毎回チェックする必要がなくなります。

但し、配列を拡張できないケースではこの方法は使用できません。

二分探索法

二分探索法は、整列済みのデータの並びを二等分しながら、目的のデータを探す探索アルゴリズムです。

例えば、昇順に整列済みの配列であれば、以下のような流れとなります。

  1. 並び全体の中央のデータと目的のデータを比較する。一致すれば終了。
  2. 目的のデータが中央のデータより小さければ、前半の部分並びにを対象にして、大きければ後半の部分並びを対象にして、1を繰り返す。
  3. 最終的に部分並びの要素が1つになったら、見つからなかったことになる。

なお、二分探索法を行なった場合の探索回数は以下の通りとなり、オーダ記号で表すと O(log2n) となります。(データは n 個とする)

  • 最小探索回数: 1回
  • 最大探索回数: ( log2n)+1回
  • 平均探索回数:  log2n 回

例えば、要素の数が65,536個(216)であった場合、線形探索法なら、最大で65,536回、平均でも32,768回かかります。
対して、二分探索法の場合、比較を行うたびに、部分並びの数が、216、215、214、・・・22、21、20 と減っていき、最大でも17回で済みますので、二分探索法の方がはるかに高速なアルゴリズムです。

ハッシュ表探索

ハッシュ表探索法は、データの格納位置をデータの値から決めることで、目的のデータを直接得られる方法です。
ハッシュ表という配列の複数の要素に、探索対象の部分並びを所属させておき、目的のデータの値に対してある種の計算を行い、一つの部分並びだけを探索対象として選択する探索アルゴリズムです。

例えば、目的のデータを100で割った余りは、必ず0~99の数になります。この値を100個の要素の配列の索引として、一つの部分並びを選択することが出来ます。
この例の「目的のデータを100で割った余り」といったような、目的のデータを範囲内の値に換算する関数のことを「ハッシュ関数」といいます。

ハッシュ表探索では、最初の1回目の検索で多くの部分並びの中から1つを選択することで、初めの時期の検索回数を減らしています。

ハッシュ関数と衝突

ハッシュ関数を適用した結果、値が重複してしまうことを衝突(シノニム)といいます。

ハッシュ表を使う場合、ハッシュ関数を検討する際に極力シノニムが発生しないようにすることも重要ですが、余りハッシュ表を大きくすると無駄も多いので、シノニム発生時の対処法もあわせて検討しておく必要があります。
例えば、データの件数が1万件だからといって、1万件のハッシュ表を作るのでは、メモリをムダに消費してしまいます。

シノニム対策としては、以下のようなパターンが主流です。

  • ハッシュ表の隣接する要素を使う。
  • シノニム用の領域を別途用意する。

併合のアルゴリズム

併合のアルゴリズムは、二つの整列済みのデータの並びを一つの整列されたデータの並びにするアルゴリズムです。

  1. 二つの配列のそれぞれ先頭の要素を比較して、値の小さい要素を併合先の配列の先頭に移す。
  2. 残りの配列について、それぞれの配列の最後の要素を移し終わるまで1の処理を繰り返す。

再帰のアルゴリズム(リカーシブ)

再帰とは、定義自身の一部にその定義が含まれるという性質です。

再帰のアルゴリズムは、反復を含むアルゴリズムと似ていますが、それよりも簡潔になります。

例えば、1からnまでの自然数の和を表す関数を f( n ) とします。
・n=1のときは、f(1) は値として「1」を返す。
・n>1のときは、f( n )は値として「n+f( n-1 )」を返す。

この関数を使って、1から4までの和を計算する場合、以下のように再帰が進行していきます。

f(4) = 4+f(3)
 =4+3+f(2)
 =4+3+2+f(1)
 =4+3+2+1
 =10

再帰のアルゴリズムは、これまでに紹介した整列や探索のアルゴリズム(マージソート、クイックソート、二分探索法)でも活用されているアルゴリズムです。

グラフのアルゴリズム-代表的なアルゴリズム3

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

グラフのアルゴリズムを理解する。

用語例:深さ優先探索、幅優先探索、最短経路探索

グラフのアルゴリズム

グラフは節(ノード)とそれらを連結する結線(リンク)で結ばれた一つの図です。通信網、木構造、あるいは流れ図がその例です。(木構造の場合は、結線のことを枝とも呼ぶ)

これらのグラフを扱うアルゴリズムをグラフのアルゴリズムといいます。

木の巡回法(再掲)

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

木の幅優先探索

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

幅優先探索を行うと、最初に子のデータを読み出します。子のデータが検索したデータでない場合は、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を読み出します。

最短経路探索

最短経路とは、グラフのある出発点の節から終着点の節へ到達するのに、結線ごとに要する時間や距離の合計が最短である結線の並びです。この最短経路をたどることを「最短経路探索」といいます。
結線ごとに要する時間や距離を総称して「コスト」といいます。

例:ダイクストラのアルゴリズム

  1. 出発点から各説へのコストの表は、出発点の節だけゼロとし、それ以外の節へのコストは初期値として無限大とする。
  2. 出発点の節から、結線の一つをたどって、節のデータを調べる。
    1. その節へのコストの記録が、今回の経路のコストより大きいなら、今回の経路のほうが短いので、今回の経路のコストを記録し、直前の節の記号をその節に関するデータとして記録する。(その節へのコストが初期値の無限大だったのなら必ずこちらの処理)
    2. その節へのコストの記録が、今回の経路のコスト以下なら、今回の結線は最短経路に含まれないので、それ以降の処理対象から除外する印を記録する。
  3. 以上の処理を、処理していない結線について反復する。
  4. すべての処理が終わったら、終着点の節から最短のコストを回答する。また、直前の節を次々と逆行して、出発点から終着点までの節の順序を経路として回答する。

 

文字列処理のアルゴリズム-代表的なアルゴリズム4

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

文字列処理のアルゴリズムを理解する。

用語例:文字列照合、KMP法(クヌース・モリス・プラット法)、BM法(ボイヤ・ムーア法)

文字列処理のアルゴリズム

文字列処理のアルゴリズムは、一連の文字の並びを処理するアルゴリズムです。

  • 連結: 一つの文字列の後へ別の文字列を追加して、一つの文字列にします。
  • 挿入: 文字列の途中に別の文字列を挿入して、一つの文字列にします。
  • 削除: 文字列の一部の文字を取り除いて、残りを一連の文字列にします。
  • 照合: 文字列が別の文字列の中に含まれるか、有無を調べて位置を特定します。

順次探索法

  1. 対象の文字列の先頭の文字から、特定の文字列を一文字ずつ照合する。
    すべての文字が一致したら、全体の処理を終了して対象の文字列の位置を返す。
  2. 対象の文字列の1文字後ろから1の処理を反復する。対象の文字列の最後を越えたら、探索失敗として終了する。

ボイヤ・ムーア法(BM法)

ボイヤとムーアによって考案された、高速の文字列照合アルゴリズムです。特定の文字列の後尾から前の方へ照合することと、一致しない場合には、複数の文字をスキップすることが特徴です。

  1. 特定の文字列を前処理して、「特定の文字が何文字目に出現するかを表す表」「一致した文字のパターンと、その場合にスキップしていい文字数を対応付ける表」の2表を作成する。
  2. 対象の文字列の先頭部分を特定の文字列の後尾から前方向へ、文字の比較をすすめる。
    一致したら全体の処理を終了して、対象の文字列の位置を返す。
  3. 一致しなかったら、比較時に得られた情報と1で作った表を元にして、文字をスキップし、2の処理に戻る。

 

ファイル処理のアルゴリズム-代表的なアルゴリズム5

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

バッチ処理などで使用される整列処理、併合処理、コントロールブレイク処理、編集処理のアルゴリズムを理解する。

ファイル処理のアルゴリズム

ファイル処理とは、入力装置や外部記憶装置から読み取ったファイルを処理することです。処理対象のデータが主記憶装置の中にないため、以下のような手順が基本となります。

  1. 前処理: ファイルを開き、内容を主記憶装置の中に展開します。
  2. 主処理: 開いたファイルに対して、1レコードずつ所定の処理を行います。
  3. 後処理: ファイルを閉じます。

なお、ここでいうファイルは以下の定義となります。

  • レコード: 型の異なる幾つかの項目(=フィールド)を持つ
  • ファイル: 同じフィールドを持つレコードの集まり

ファイルの性質として、データ件数が膨大になることがあるため、ハードディスクなどの外部記憶装置に作業ファイルを作成し、中間結果を一時退避しながら処理をすすめることもある。その場合、外部記憶装置に十分な空き容量が必要となる。

ファイルの併合処理

ファイルの併合処理は、二つの整列済みのレコードの並びで構成されるファイルを、一つの整列されたレコードのファイルにする処理です。

例:ファイルAとBから、ファイルCを作成する

  1. 前処理: ファイルA、B、Cをそれぞれ開く。
  2. 主処理: ファイルA、Bを1レコードずつ読み込み、値の小さい方のレコードをファイルCに出力し、出力した方のファイルの次のレコードを読み込む。
    これを両ファイルの終端まで繰り返す。
  3. 後処理: ファイルA、B、Cをそれぞれ閉じる。

コントロールブレイク処理

コントロールブレイクとは、同じキー値を持つレコード軍の切れ目のことです。

コントロールブレイク処理とは、コントロールブレイクに出会ったらそのレコード群の処理を終了し、複数のレコード群の処理を反復することです。レコード群の中のレコードごとの処理の反復とあわせて、二重の反復になります。

例:社員の給与の部署ごとの合計

  1. 社員の給与一覧ファイルをあらかじめ部署で整列
  2. 部署が同じである間、社員毎の給与を計算用変数に加算していく。
  3. 違い部署コードが出現したら「コントロールブレイク」
    部署名と計算用変数の値を中間ファイルに出力し、計算用変数0で初期化。
  4. 2と3をファイルの終端まで繰り返す。
  5. ファイル終端まで来たら、部署名と計算用変数の値を中間ファイルに出力。中間ファイルの内容を処理の最終結果として書き出す。

ファイルの編集処理

ファイルの編集処理は、既存のファイルのデータを修正する処理です。

  1. 前処理: マスターファイルM、トランザクションファイルT、新マスターファイルNを開く。
  2. 主処理: ファイルMとファイルTからから1レコードずつ読み込み、キー値を比較して以下の処理を行う。これをファイル終端まで繰り返す。
    1. Tのキー値=Mのキー値なら、ファイルTのレコードをファイルNに出力し、ファイルMとファイルTの次のレコードを読み込む。(データの更新)
    2. Tのキー値>Mのキー値なら、ファイルMのレコードをファイルNに出力し、ファイルMの次のレコードを読み込む。
    3. Tのキー値<Mのキー値なら、ファイルTのレコードをファイルNに出力し、ファイルTの次のレコードを読み込む。(レコードの追加)
  3. 後処理: ファイルM、ファイルT、ファイルNを閉じる。

アルゴリズム設計

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

アルゴリズムは、擬似言語、流れ図、決定表(デシジョンテーブル)などを用いて表現することを理解する。また。アルゴリズムの設計方法を理解する。

用語例:再帰、分割統治法

アルゴリズム設計

アルゴリズムとは、目的にたどり着くための道筋や処理の手順のことです。アルゴリズムを考える、設計する目的は、単に問題を解く方法を見つけるだけではなく、より効率的に、より速く、より簡単に問題を解くアルゴリズムを探す事が重要です。

同じ結果を出すための処理であっても、そのアルゴリズムが異なると、処理にかかる時間や、必要となるメモリの容量などが異なってきます。効率の良いアルゴリズムほど、処理時間が短くなり、メモリの消費量が少なく済むものなのです。

アルゴリズムの表現

プログラムを設計するときには、アルゴリズムを何らかの形式で表現します。

アルゴリズムの表現には、流れ図(フローチャート)、擬似言語、決定表(デシジョンテーブル)などの表現があります。

擬似言語

擬似言語は、人間が用いる自然言語とプログラム言語を混合した言語です。

アルゴリズムをできるだけ人間向きに自然言語で表現しつつ、反復や選択のように微妙な部分にプログラム言語を混用したりします。

プログラム言語と同様にテキストエディタで描くことが出来、図形を用いた表現に比べて修正が容易なのが特徴です。

テキストのみで表現した例

if a[mi] が a[i] より小なら then
   a[mi] と a[i] の値を交換する

図形処理の発達に伴い、情報処理技術者試験の分野では、以下のような簡易な図記号を混用したものを擬似言語と称しています。
(実際に情報処理技術者試験で使われたものを紹介します。)

擬似言語の仕様の例
実際に出題された擬似言語の記述例

決定表(デシジョンテーブル)

決定表(デシジョンテーブル)は、条件とその条件に対する処理の関係を4つの部分からなる表にして表現する技法です。

  1. 条件表題欄: 問題を処理するための条件を表します。
  2. 行動表題欄: 条件によって取りうる行動を表します。
  3. 条件記入欄: 条件表題欄の各条件について、当てはまる場合は[Y]、当てはまらない場合は[N]と記載します。条件判断を必要としない場合は[-]と記載します。
  4. 行動記入欄: 行動表題欄の各行動について、当てはまる場合に[X]と記載します。当てはまらない場合は空欄か[-]と記載します。

大きなプログラムの場合、「行動」の単位で「サブルーチン」化することがよく行われています。(=後述:分割統治法)

また、決定表を作成するときは、取りうる条件の組み合わせを網羅し、なおかつ全てのパターンに対して、必要な処理が行われるように設計することが重要です。

分割統治法

分割統治法とは、大きな問題を小さな問題に分割して、それぞれの問題ごとに解決に集中する方法です。

再帰のアルゴリズム、モジュール分割、オブジェクト指向設計などが分割統治法の具体的な例です。

また、ソートのアルゴリズムの中でも、マージソートやクイックソートは分割統治法に基づいて設計がなされています。

例えば、1からnまでの自然数の和を求めるアルゴリズムの場合、分割統治法を使わない場合と使った場合とでは、以下のように違った流れ図となります。

プログラミング(概要)

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

【基本情報・応用情報】
・プログラミング作法、コーディング基準を習得し、応用する。
・プログラム言語の文法の表記法を習得し、応用する。

【ITパスポート】
・プログラム言語とプログラミングの役割を理解する。

(1)プログラミング

1.プログラミング作法とコーディング基準 ITパスポート 基本情報 応用情報

プログラミング作法とコーディング基準の目的、効果、種類を理解する。また、プログラミング作法とコーディング基準を守らない場合に起こる弊害を理解する。

用語例:字下げ(インデンテーション)、ネストの深さ、命名基準、仕様禁止命令、プログラムの機能性・効率性・使用性・保守性の向上

2.プログラム構造 基本情報 応用情報

プログラムの信頼性、保守性の観点からプログラム構造を理解する。

用語例:モジュール分割、独立性、メインルーチン、サブルーチン、DLL

3.データ型 基本情報 応用情報

プログラム言語で使用される代表的なデータ型を理解する。

用語例:整数型、実数型、論理型、文字型、抽象データ型、構造型

4.Webプログラミング 基本情報 応用情報

WebサーバとWebクライアントの仕組みを理解し、Webサーバ、Webクライアントにおけるプログラムの役割と作成方法、Webアプリケーションプログラムを開発する環境を理解する。

用語例:サーバサイドプログラミング、リッチクライアント、Ajax、Apache、JSP(Java Server Pages)、HTML5技術(canvas、WebSocket、Geolocation APIほか)

(2)文法の表記法 基本情報 応用情報

プログラム言語の構文を定義するために、BNF等のメタ言語を使用することを理解する。

用語例:EBNF(拡張バッカス記法:Extended Backus Naur Form)

 

プログラミング作法とコーディング基準

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

プログラミング作法とコーディング基準の目的、効果、種類を理解する。また、プログラミング作法とコーディング基準を守らない場合に起こる弊害を理解する。

用語例:字下げ(インデンテーション)、ネストの深さ、命名基準、仕様禁止命令、プログラムの機能性・効率性・使用性・保守性の向上

プログラミング

プログラミングは、コンピュータを使って実行する作業手順を、前もって作っておく作業です。プログラムとは、コンピュータ用の作業手順書を、コンピュータに分かることが出書き出したもの、といえます。

人間が何かの仕事をこなすときは、まず段取りを考えて計画を立て、それに従って実際に仕事を進めます。これと同じように、コンピュータに仕事をさせるための段取りを書いたものがプログラムであり、プログラムを作成する作業がプログラミングです。コンピュータはプログラムに従って運用を行います。

プログラミング作法とコーディング基準の目的・効果

プログラミング作法は、プログラムを読む人にとって適切であろうと、一般的に指示された流儀のことです。対して、コーディング基準とは、チームや組織が定めたプログラムの書き方の基準です。いずれもプログラムの保守性を改善することが目的であり、読む人の労力や読み間違いを減らす効果があります。

同じ処理をするプログラムであっても、書き方の流儀や個人差が発生してしまいます。例えば、C言語で「変数aに1を加算する」という処理でも、以下のように異なる書き方が可能です。

  •  a++
  •  a = a + 1

専門家の間では、前者のほうが簡潔で、読み間違いが少ないとして支持されている、というのがプログラミング作法の例です。

また、コーディング基準は以下のような事項に関して定められることが多いです。

インデンテーション文の書き出し位置のインデンテーション(字下げ)の指針。
ネスト(入れ子)データ構造や制御構造の階層状態。ネストの深さを規制。
命名基準変数やモジュールの名前の付け方の指針。
使用禁止命令使用を推奨しない命令。(Goto文の禁止など)

インデンテーション

インデンテーション(字下げ)とは、プログラムの文の書き出し位置を、何文字分か右の方へ下げることです。これは、一般的なビジネス文書でも当てはまる事柄で、文章を読む時の人間の視線が左から右、上から下と流れることを踏まえたものです。

プログラムのインデンテーションは、例えば次のようにします。

  1. データ構造のネストを字下げで表す。
  2. 反復や選択などの制御構造のネストを字下げで表す。
  3. ラベルよりそれ以外の部分を字下げする。
  4. 字下げは半角文字4文字分ずつとする。
インデンテーションの例

label1:
    i=0;
    repeat
        a=b+c;
        ~~

このような字下げは、処理には関係ない表現なので、人間にとっての読みやすさを目的として、コーディング基準で規定するのが一般的です。

ネスト

データ構造や制御構造の階層状態をネスト(入れ子)といいます。ネストが深すぎると人間は把握することが難しくなります。

例えば、コーディング基準でネストの深さを4までに規制します。それを越えようとする場合は、一部を他のモジュール呼び出しや関数参照にしてネストが深くなるのを回避します。

命名基準

命名基準とは、変数、モジュール、関数、ラベルなどの名前の付け方の指針です。以下に、命名基準の例を示します。

  1. 元になっている業務や学術の用語と一致する名前を用いる。
  2. 配列の索引には、i,j,kを用いる。
  3. カウンタにはn,mを用いる。
  4. 長さを表す変数には、l,mを用いる。
  5. ポインタ変数には、p,qを用いる。
  6. 合計には、sを用いる。
  7. 一時的な変数には、t,wを用いる。

使用禁止命令

使用禁止命令とは、仕様が推奨されていない命令や文のことです。

例えば、goto文を禁止して、代わりに反復や選択の文で代替するほうが、読み手には読みやすくなります。

プログラム構造

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

プログラムの信頼性、保守性の観点からプログラム構造を理解する。

用語例:モジュール分割、独立性、メインルーチン、サブルーチン、DLL

プログラム構造

一つのプログラムは、いくつかの要素で構成されます。複数の要素で構成されるプログラムの形を、プログラム構造といいます。

モジュール

一つのプログラムを構成する要素を「モジュール」といいます。モジュールは、メインルーチン、サブルーチン、コンパイル単位などを総称する一般的な用語です。

モジュール構成にすることで、次のような効果が生まれます。

  • 人間の行っている作業の分解単位にモジュールを対応させることによって、わかりやすくなります。例えば、ATMを例に取ると、預入モジュール、引出しモジュール、残高照会モジュールといった対応をさせます。
  • 共通部分を「共通モジュール」とすることによって、プログラム全体の規模を減らすことが出来ます。
  • 分割統治法といって、モジュール単位に分割することで、モジュールごとの設計や試験、保守に集中することが出来ます。

メインルーチン

いくつかのモジュールで構成されるプログラムにおいて、最初に起動されるモジュールをメインルーチンといいます。「ルーチン」とは、「決められた仕事」という意味の言葉です。

メインルーチンの内容は、全体の処理の流れの概要を表す役割をはたすことが多いです。

サブルーチン

サブルーチンは、メインルーチンや他のサブルーチンから呼び出されるモジュールです。サブルーチンは2ヶ所以上から利用する共通ルーチンにすることが出来ます。また、別のプログラムで再利用することも出来ます。

Webプログラミング

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

WebサーバとWebクライアントの仕組みを理解し、Webサーバ、Webクライアントにおけるプログラムの役割と作成方法、Webアプリケーションプログラムを開発する環境を理解する。

用語例:サーバサイドプログラミング、リッチクライアント、Ajax、Apache、JSP(Java Server Pages)、HTML5技術(canvas、WebSocket、Geolocation APIほか)

Webプログラミング

Webプログラミングは、WWW(ワールドワイドウェブ)を閲覧する一環として利用するプログラムのプログラミング作業です。HTMLなどのマークアップ言語の機能や部品を用いたり、プログラム言語で書かれたモジュールを呼び出したりする形でプログラミングします。

初期のWWWは、資料を世界的に共用するという、静的な表現の役割をはたすものでしたが、次第に旅行業やインターネット通販などの動的な処理をすることが出来て、現在に至っています。

Webプログラミングには、閲覧者側のクライアントコンピュータ側で動作するプログラムを作ることと、提供者側のWebサーバ側で動作するプログラムを作ることがあります。

具体的な例としては、各種の会員制Webサイトや通販サイト、インターネットバンキングなどがあります。また、スマートフォンのアプリもある種のWebプログラムと言えるでしょう。

Webプログラミングにおけるサーバの役割

Webプログラミングにおける、サーバの役割は次のようなものがあります。

  • クライアントコンピュータへ送信するコンテンツの量を減らすために、大規模な処理はサーバ側で担当する。
  • プログラム言語で書かれたモジュールをアクセスする部分をサーバ側に置く。
  • サーバ側にあるファイルやデータベースにアクセスする部分をサーバ側に置く。

その他、サーバ側のプログラムは、アクセスが集中した場合の負荷や、セキュリティなどを意識して設計・プログラミングします。

Webプログラミングにおけるクライアントの役割

Webプログラミングにおける、クライアントの役割は次のとおりです。

  • HTMLなどのマークアップ言語や、小さな部品を用いてプログラミングします。
  • 閲覧者との対話の部分を担当します。

クライアント側のプログラムは、閲覧用に提供する文章や画像のを用いて、閲覧者にとって分かりやすくて手間の掛からない操作性になるように設計・プログラミングします。

 

プログラム言語(概要)

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

【応用情報】
・プログラム言語の種類、特徴、記述方法を修得し、応用する。
・プログラム言語の制御構造を修得し、応用する。
・プログラムの実行に必要な記憶域の考え方、利用法を修得し、応用する。
・プログラム言語が持つ構文規則、意味規則を修得し、応用する。

【基本情報】
・プログラム言語の種類、特徴、基本的な記述方法を修得し、適用する。
・C、COBOL、Java、アセンブラ言語のプログラム作成方法を修得し、適用する。
・表計算ソフトの活用方法を修得し、適用する。

【ITパスポート】
・プログラム言語とプログラミングの役割を理解する。

(1)プログラム言語の種類と特徴

1.プログラム言語の変遷と分類 ITパスポート 基本情報 応用情報

プログラム言語は、機械語、アセンブラ言語、高水準言語と発展してきたこと、プログラム言語の分類を理解する。

用語例:手続型言語、関数型言語、論理型言語、オブジェクト指向言語、スクリプト言語

2.手続型言語 基本情報 応用情報

代表的な手続き型言語の特徴、記述方法を理解する。

用語例:Fortran、COBOL、PL/Ⅰ、Pascal、BASIC、C

3.オブジェクト指向言語 基本情報 応用情報

代表的なオブジェクト言語指向言語の特徴、記述方法を理解する。

用語例:Java、C++

4.スクリプト言語 基本情報 応用情報

代表的なスクリプト言語の特徴、記述方法を理解する。

用語例:ECMAScript、Perl、PHP、Python、Ruby

5.共通言語基盤(CLI:Common Language Infrastructure) 基本情報 応用情報

JIS X 3016(ISO/IEC 23271)で標準化されている、共通言語基盤の特徴、利用法を理解する。

用語例:共通言語基盤(CLI)

(2)プログラム言語の制御構造 応用情報

プログラム言語の基本的な制御構造、手続きと関数、逐次制御と並列制御を理解する。

用語例:連接、選択、繰り返し、手続き呼び出し、パラメータ、仮引数、実引数、値呼び出し、参照呼び出し、制御の流れ、再帰呼び出し、プロセス、疑似並列制御

(3)プログラム言語の記憶域 応用情報

プログラムの実行に必要な記憶域の考え方、利用法を理解する。

用語例:目的プログラムテキスト、定数、静的変数、自動変数、ヒープ、ガベージコレクション、ブロック、スコープ

(4)プログラム言語の記述 応用情報

プログラム言語が持つ構文規則、形式的意味論を中心とした意味規則を理解する。

用語例:プログラムの構成単位、文脈自由文法、BNF

(5)Cの知識と技術 基本情報

  • Cのプログラムの作成方法の基本を修得し、適用する。
  • 演算処理、制御処理、文字処理などを行うプログラムの作成方法を修得し、適用する。
  • ライブラリ関数の利用方法を収録し、適用する。
  • ファイル処理を行うプログラムの作成方法を修得し、適用する。

(6)COBOLの知識と技術 基本情報

  • COBOLのプログラムの作成方法の基本を修得し、適用する。
  • 演算処理、制御処理、文字処理、表操作を行うプログラムの作成方法を修得し、適用する。
  • ファイル処理を行うプログラムの作成方法を修得し、適用する。

(7)Javaの知識と技術 基本情報

  • Javaのプログラムの作成方法の基本を修得し、適用する。
  • 演算処理、制御処理などを行うプログラムの作成方法を修得し、適用する。
  • クラスの宣言方法、クラスをインスタンス化して利用する方法を修得し、適用する。
  • 継承、インタフェースを利用し、効率よくプログラミングを行う方法を修得し、適用する。
  • 例外処理、並列処理などの作成方法を修得し、適用する。

(8)アセンブラ言語(CASLⅡ)の知識と技術 基本情報

  • コンピュータシステムCOMETⅡの仕様を理解する。
  • CASLⅡのプログラムの作成方法の基本を修得し、適用する。
  • 演算処理、制御処理を行うプログラムの作成方法を修得し、適用する。
  • 表を使った処理、入出力処理を行うプログラムの作成方法を修得し、適用する。
  • スタック、およびスタックを用いたサブルーチンコールの仕組みと用法を修得し、適用する。

(9)表計算ソフト 基本情報

  • 表計算ソフトが持つ計算、集計などの機能を修得し、適用する。
  • 関数の種類、使い方を修得し、適用する。
  • マクロの作成方法を修得し、適用する。
  • 業務処理における表計算ソフトの活用方法を修得し、適用する。

 

プログラム言語の分類と概要

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

プログラム言語は、機械語、アセンブラ言語、高水準言語と発展してきたこと、プログラム言語の分類を理解する。

用語例:手続型言語、関数型言語、論理型言語、オブジェクト指向言語、スクリプト言語

プログラム言語

コンピュータに処理をさせるには、処理の手順を司令として与える必要があります。この指示書をプログラムといい、プログラム言語によって書かれています。

以下に、代表的なプログラミング言語をいくつか紹介します。なお、「基本情報」アイコンがついているものは、基本情報技術者試験の午後の問題で出題されるプログラム言語です。

C  基本情報
パソコンやワークステーションのアプリケーションソフト、デジタル家電やIoT機器など、いわゆる「組み込み系」の開発で用い要られています。
C++
C言語をベースとして、オブジェクト指向の概念を取り入れた言語です。UNIXやLinuxのサーバ内部のプログラムや、Windowsアプリケーションで用いられています。
COBOL  基本情報
10進数の扱いを得意とするプログラミング言語で、金融分野などの汎用コンピュータで利用されている、事務処理用のプログラム言語です。
Java 基本情報
C++をベースとして開発され、インターネット環境などで利用される言語です。「Java仮想マシン」という仕組みを使い、OSや機種といったプラットフォームの違いにかかわらず動作できるという特徴があります。
Visual Basic
GUI環境でのWindowsアプリケーションソフト開発に用いられる言語です。
C#
主にWindowsアプリケーションソフト開発に用いられる言語です。.Net Frameworkという、共通言語基盤(CLI)上で動作するプログラム言語です。
Fortran
主に科学技術系の計算処理で用いられるプログラム言語です。

機械語と言語プロセッサ

コンピュータが直接理解できる命令は、2進数で表現された機械語です。しかし、機械語は機種によって異なり、かつ機械語は人の手で記述するのは難しいので、より人間の言葉に近いプログラム言語で記述したもの(ソースコード)を機械語に翻訳してから動作させます。

このソースコードを機械語に翻訳する機能を「言語プロセッサ」といいます。翻訳の方法には、機械語と1対1に対応する疑似命令を機械語に変更する「アセンブラ」、ソースコード全文を一括で機械語に翻訳する「コンパイラ」、1行ずつ逐次翻訳しながらプログラムを実行する「インタプリタ」があります。

コンパイラ

コンパイラは、プログラム言語で書かれたソースコードを、一括して機械語のオブジェクトやプログラムに作り変えるソフトウェアです。

CやCOBOL等の高水準言語はコンパイラで変換されます。

インタプリタ

ソースコードを1行ずつ解析しては機械語に変換し、実行するという動作を繰り返すもので、逐次変換ともいいます。

以前のVisual Basicはインタプリタで実行されていました。

スクリプト言語

コードを記述するだけで、コンパイルの必要なく動作させることが出来る、スクリプトと呼ばれるプログラムがあります。これを記述するプログラム言語を、スクリプト言語と言います。

代表的なものには、PerlやPHP、JavaScriptなどがあります。これらはWebページに動きを加えたり、Webサーバ上でデータを計算してWebブラウザに送るなどの機能を作る時に用いられています。

以下に、いくつかスクリプト言語の特徴を紹介します。

Perl(パール)
Perlは、テキスト処理から機能を拡大してきた、スクリプト言語です。実用性を重視していて、C言語などの各種の言語を参考にして、多様な機能を持ちます。
Perlを処理するためのソフトウェア、”perl”はフリーソフトウェアとして提供されています。 
記述されたスクリプトの提供形態は、Webページに動的な性質を持たせる、CGI(Common Gateway Interface)という機能の形をとることが多いです。
PHP(Hypertext Preprocessor)
Webページに動的な機能を持たせるためのスクリプト言語および言語処理ソフトウェアの名称です。
PHPで書かれたスクリプトはWebサーバ側でHTML形式のマークアップ言語表現に変換されるので、閲覧するクライアントコンピュータ側には、PHPのソフトウェアは必要ありません。
Python(パイソン)
オブジェクト指向型のスクリプト言語です。Perlとは対象的に、言語そのものの機能は少なめに限定されています。そのかわり、多様な標準ライブラリを提供してカバーしています。
見た目のブロック構造と、実際の制御が同じで、視覚に訴えるソースコードが強制されている言語です。
Ruby(ルビー)
日本人が発案したオブジェクト指向型のスクリプト言語です。テキスト処理や機能の多様性という性質はPerlに近く、オブジェクト指向型という点でPythonと比較されます。

 

その他の言語(概要)

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

【応用情報・基本情報】
・代表的なマークアップ言語の種類、特徴、記述方法を修得し、応用する。
・コンピュータで使用されるその他の言語を修得し、応用する。

【ITパスポート】
・代表的なマークアップ言語の種類とその基本的な使い方を理解する。

(1)マークアップ言語 ITパスポート 基本情報 応用情報

1.HTML

Webページの作成に利用されるHTMLの特徴、基本的な記述方法を理解する。

用語例:開始タグ、終了タグ、DTD(文書型定義:Document Type Definition)、SGML

2.XML

HTMLの機能に加えて、独自にタグを定義できる機能を備え、主にインターネットを介したデータ交換に利用されているXMLの特徴、基本的な記述方法を理解する。

用語例:DOM(Document Object Model)、SOAP(Simple Object Access Protocol)、SVG(Scalable Vector Graphics)、SAX(Simple API for XML)、XML Schema

3.XHTML

HTMLをXMLで再定義したマークアップ言語であるXHTMLの特徴、基本的な記述方法を理解する。

用語例:XHTML Basic、XHTML Modulation

4.スタイルシート

HTMLやXMLなどマークアップ言語の構造と表示形式を分離するための仕様である、スタイルシートを理解する。

用語例:CSS(Cascading Style Sheets:段階スタイルシート)、XSL(Extensible Stylesheet Language:拡張可能なスタイルシート言語)

(2)その他の言語 基本情報 応用情報

オブジェクト指向設計のための表記法である、UMLやその他の言語を理解する。

用語例:クラス図、シーケンス図、オブジェクト図、コラボレーション図、ステートチャート図、操作、属性、ロール名、ユースケース図、SDL(Specification and Description Language)、ADL(Architecture Description Language:アーキテクチャ記述言語)、データ定義言語(DDL:Data Definition Language)

 

その他の言語

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

・代表的なマークアップ言語の種類、特徴、記述方法を修得し、応用する。
・コンピュータで使用されるその他の言語を修得し、応用する。

 

 HTML

HTML(HyperText Markup Language)はインターネットのWebページの記述に使われる言語です。言語といっても、プログラムを組むものではなく、文章の中に編集用の指定を織り交ぜて記述できる、マークアップ言語の一種です。

HTMLでテキスト文書を描くときには、ページの構造や書式、レイアウトに関する指定を、タグという形式で挿入することが出来ます。

HTMLで記述したテキストは、HTMLファイルとして保存します。ファイル名の末尾には、”.html”などの拡張子をつけます。

HTMLのタグ

HTML文書の基本構造は、ヘッダ部とボディ部からなります。ヘッダ部には文書のタイトルなどを、ボディ部には文書の内容を記述します。

HTMLでは、編集したいテキストの前後に”<>”で囲んだタグを挿入します。開始タグ(<タグ名>)から終了タグ(</タグ名>)までが、そのタグの有効範囲です。

タグ名概要
<html>~<html>HTML文書であることを宣言するタグ
<head>~<head>文書のヘッダ部を示す。ヘッダ部はタイトルなどを記述する場所で、本文には含まれない。
<body>~<body>文書のボディ部を示す。ボディ部は、ブラウザ上で実際にWebページとして表示される本文を記述するところ。
<img>画像を表示する。<img src="~~">のように、src属性を使って表示する画像ファイルのURLを指定する。
<a>~<a>他の文書ファイルへのリンクを示す。href属性に参照先ファイルのURLを指定する。
Webページ上で、このタグに囲まれた部分をクリックすることで、参照先に移動することが出来る。
<br>文章の改行を指定する。

タグのネスト

タグを入れ子にすると、階層的に書式を指定することが出来ます。内側のタグほど指定が優先されます。

以下に<font>というタグを使って3段階の入れ子の形で指定した例を示します。

ハイパーリンク

<a>タグや<img>タグのような、他のHTML文書や画像ファイルを参照して表示するタグを挿入すると、文書の中から関連のある別のファイルを直接開いてみることが出来るようになります。これをハイパーリンクといいます。

こういったハイパーリンクを含むテキストをハイパーテキストといいます。

ブラウザ

HTML文書を閲覧するためのソフトウェアとブラウザ(Webブラウザ)といいます。HTMLのタグが指定するレイアウトにしたがい、画像などを含む文書として表示します。

Google ChromeやInternet Explorer、Firefoxなどの製品が代表的です。

なお、HTMLの仕様は、WWWコンソーシアム(W3C)で標準化されていますが、タグの中にはブラウザ側が独自に拡張したものもあり、それらのタグをHTML文書内で使うと、表示結果がブラウザの種類によって違ってしまう場合があります。

SGML

SGML(Standard Generalized Markup Language)は論理構造を持つ文書を記述するために、ISOで制定されたマークアップ言語です。SGML文書同士の参照関係と階層構造を、文書中に定義する機能があります。

このSGMLを元にして、HTMLやXMLが作られました。

XML

XML(Extensible Markup Language)は、HTMLのような使い勝手の良さだけでなく、SGMLのような拡張性も備えたマークアップ言語です。汎用性が高く、ユーザが独自にタグを定義して使用することが出来るのが特徴です。

複雑なデータをインターネット経由で交換することが出来るため、企業間の電子商取引などに欠かせない技術となっています。

XHTML

HTMLをXMLの仕様に準拠した形で再定義したマークアップ言語です。HTMLの言語仕様が拡張によってXMLと整合しきれない部分があるのを修正したものです。

言語としてはHTMLとほぼ同じですが、改めて書式を幻覚に規定し、各ブラウザによる表示の差などを減らしました。

スタイルシート

スタイルシートは、スタイル言語で記述された文書の内容以外の様式の定義です。HTMLなどのマークアップ言語や組版系のソフトウェアとともに利用されます。

マークアップ言語や組版系のソフトウェアは、文書の内容も様式も指定できますが、スタイルシートを用いて文書の内容・構造と様式・デザインを分離することによって、作業を分業したり、保守性を向上させたり、様式・デザインを再利用したりするのに役立ちます。

CSS

CSS(Cascading Style Sheets)は、スタイルシートを記述するための代表的なスタイル言語です。

以前は、文字の色や大きさ、フォントといった見栄えに関する記述も全てHTMLで行っていました。しかし、文書構造と見栄えを分離することにより、保守性が向上し、開発も分担しやすくなります。

現在では、文書の内容はHTML、見栄えに関してはCSSで定義するのが一般的です。

XSL

XSL(Extensible Stylesheet Language)はマークアップ言語XMLに準拠したスタイル言語です。

UML(Unified Modeling Language)

その他の言語としては、UMLがあります。「言語」と名前はついていますが、他の言語とは大きく異なり、UMLはモデリング技法・表記法と考えるべきものです。

UMLはオブジェクト指向のソフトウェアを設計・開発するための統一表記法です。オブジェクト指向に基づいてシステムを図解したり、モデル化したりする際の表記法が定められています。

UMLで定義されている図解法は、大きく次の3種類にわけられます。

構造図システムの静的な構造を表すクラス図など
振る舞い図システムの動的な変化や相互作用を表すユースケース図など
実装図ソフトウェア実装時の構成や配置を表す配置図など

C言語の知識と技術(概要)

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

【基本情報】

  • Cのプログラムの作成方法の基本を修得し、適用する。
  • 演算処理、制御処理、文字処理などを行うプログラムの作成方法を修得し、適用する。
  • ライブラリ関数の利用方法を収録し、適用する。
  • ファイル処理を行うプログラムの作成方法を修得し、適用する。

1. C の基本的なプログラム

C の基本的なプログラムを作成する。

修得項目: main 関数,printf 関数,標準出力,注釈,ヘッダ など

2.数値の計算

四則演算を使ったプログラムを作成する。

修得項目:四則演算子,変数,式,整数の計算,型変換(キャスト),実数の計算,データ型のビット幅,増分演算子,減分演算子,比較演算子 など

3.選択型のプログラム

条件式を使って条件分岐するプログラムを作成する。

修得項目:等価演算子,関係演算子,論理演算子,代入演算子,if 文,switch 文 など

4.反復型のプログラム

繰返し文を使ったプログラムを作成する。

修得項目: while 文,do 文,for 文 など

5.ビット演算

ビット単位の演算子を使ったプログラムを作成する。

修得項目: 符号なし整数型,ビットシフト など

6.入力処理

標準入力を使ったプログラムを作成する。

修得項目:scanf 関数,空白類文字,アドレス演算子 など

7.配列

配列を使ったプログラムを作成する。

修得項目: 1 次元配列,2 次元配列 など

8.文字処理

文字列を処理するプログラムを作成する。

修得項目: putchar 関数,puts 関数,getchar 関数,gets 関数,文字の入出力,文字列の入出力,文字列リテラル,ナル文字 など

9.ポインタ

ポインタを使ったプログラムを作成する。

修得項目: ポインタの配列,アドレスの加減算 など

10.関数

関数を作成し,関数を使ったプログラムを作成する。

修得項目: 関数原型,void 型,再帰呼出し など

11.ライブラリ関数

ライブラリ関数を使ったプログラムを作成する。

修得項目:プリプロセッサ,#include,#define,前処理指令 など

12.記憶域クラス指定

記憶域クラス指定子を使ったプログラムを作成する。

修得項目:自動記憶域期間をもつ変数,静的記憶域期間をもつ変数,register,typedef,記憶域期間,外部定義 など

13.構造体

構造体を使ったプログラムを作成する。

修得項目:構造体の配列,自己参照する構造体,共用体 など

14.ファイル処理

ファイル処理を行うプログラムを作成する。

修得項目:シーケンシャルなファイル処理,ランダムなファイル処理,ストリーム,バッファリング など

 

 

COBOLの知識と技術(概要)

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

【基本情報】

  • COBOLのプログラムの作成方法の基本を修得し、適用する。
  • 演算処理、制御処理、文字処理、表操作を行うプログラムの作成方法を修得し、適用する。
  • ファイル処理を行うプログラムの作成方法を修得し、適用する。

1. COBOL の基本的なプログラム

COBOL の基本的なプログラムを作成する。

修得項目: 部(DIVISION),節(SECTION),見出し部,環境部,データ部,手続部,ACCEPT文,DISPLAY 文,データの構造,データ項目,データの転記,データの編集,正規法,注釈 など

2.数値の計算

四則演算を使ったプログラムを作成する。

修得項目:計算文,算術式,作業場所節 など

3.選択型のプログラム

条件式を使って条件分岐するプログラムを作成する。

修得項目:IF 文,比較演算子,正負条件,字類条件,論理演算子,入れ子になった分岐,多分岐,GO TO 文,STOP 文 など

4.反復型のプログラム

反復型の制御文を使ったプログラムを作成する。

修得項目: 回数を指定する反復実行,条件を指定する反復実行,入れ子になった反復実行,PERFORM 文 など

5.文字処理

文字処理を行うプログラムを作成する。

修得項目:文字列の部分参照,文字列の検査,文字列の置換,文字列の連結,文字列の分解 など

6.表操作

表操作を行うプログラムを作成する。

修得項目:表の概念,1 次元の表,多次元の表,指標,初期値の設定,逐次探索,非逐次探索,OCCURS 句,SEARCH 文 など

7.ファイル処理の基本

順ファイルの入出力操作を行うプログラムを作成する。

修得項目: ファイルの入出力,帳票の出力,データの集計,コントロールブレーク,マッチング など

8.ファイル処理の応用

相対ファイル,索引ファイルを使ったプログラムを作成する。

修得項目: レコードの書換え,レコードの削除,レコードの位置づけ,整列,併合 など

 

 

Javaの知識と技術(概要)

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

【基本情報】

  • Javaのプログラムの作成方法の基本を修得し、適用する。
  • 演算処理、制御処理などを行うプログラムの作成方法を修得し、適用する。
  • クラスの宣言方法、クラスをインスタンス化して利用する方法を修得し、適用する。
  • 継承、インタフェースを利用し、効率よくプログラミングを行う方法を修得し、適用する。
  • 例外処理、並列処理などの作成方法を修得し、適用する。

1. Java の基本的なプログラム

Java の基本的なプログラムを作成する。

修得項目: クラス,メソッド,main メソッド,標準出力,注釈,javadoc コメント など

2.数値の計算

四則演算を使ったプログラムを作成する。

修得項目:データ型,型変換(キャスト),変数,配列,四則演算子,式,代入演算子,比較演算子,増分演算子,減分演算子,シフト演算子 など

3.選択型のプログラム

条件式を使って条件分岐するプログラムを作成する。

修得項目:if 文,switch 文 など

4.反復型のプログラム

反復型の制御文を使ったプログラムを作成する。

修得項目: while 文,do 文,for 文,拡張for 文 など

5.クラスとインスタンス

クラスを定義し,インスタンス化して使用するプログラムを作成する。

修得項目: インスタンス変数,インスタンスメソッド,アクセス修飾子,参照型変数,隠蔽(いんぺい),コンストラクタ,オーバロード,this,クラス変数,クラスメソッド,文字列クラス,パッケージ,完全限定名,super,単純名,import 宣言,クラス修飾子 など

6.差分プログラミング

既存のクラスの機能を拡張するプログラム,インタフェースを利用して機能を追加するプログラムを作成する。

修得項目:継承,final,extends,スーパクラス,サブクラス,Object,implements,キャスト,アップキャスト,ダウンキャスト,instanceof,オーバライド,ダイナミックバインド,クラスライブラリ,抽象クラス,抽象メソッド,基底クラス,派生クラス など

7.例外処理

例外処理を行うプログラムを作成する。

修得項目:try 文,throw 文 など

8.並列処理

並列処理を行うプログラムを作成する。

修得項目: スレッド,synchronized 修飾子,wait( ),notify( ) など

9.コレクションと総称

コレクションを使ったプログラムを作成する。

修得項目: add( ),remove( ),List,Set,Map,Stack,型引数 など

10.入れ子クラス

入れ子クラスを使ったプログラムを作成する。

修得項目: メンバクラス,メンバインタフェース,局所クラス,匿名クラス など

11.列挙

列挙型を使ったプログラムを作成する。

修得項目:列挙定数,final 変数 など

 

 

アセンブラ言語(CASLⅡ)の知識と技術(概要)

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

【基本情報】

  • コンピュータシステムCOMETⅡの仕様を理解する。
  • CASLⅡのプログラムの作成方法の基本を修得し、適用する。
  • 演算処理、制御処理を行うプログラムの作成方法を修得し、適用する。
  • 表を使った処理、入出力処理を行うプログラムの作成方法を修得し、適用する。
  • スタック、およびスタックを用いたサブルーチンコールの仕組みと用法を修得し、適用する。

1. COMETⅡ

COMETⅡを構成するレジスタ,命令形式を理解する。

修得項目: GR0~GR7,SP,PR,FR,OF,SF,ZF,注釈

2.CASLⅡの基本的なプログラム

CASLⅡの基本的なプログラムを作成する。

修得項目:START,END,DS,DC,LD,ST,LAD,実効アドレス

3.算術演算,論理演算

算術演算命令,論理演算命令を使ったプログラムを作成する。

修得項目:ADDA,ADDL,SUBA,SUBL,AND,OR,XOR

4.選択と反復処理

比較演算命令,分岐命令を使って選択型,反復型のプログラムを作成する。

修得項目: CPA,CPL,JPL,JMI,JNZ,JZE,JOV,JUMP

5.シフト演算

シフト演算命令を使ったプログラムを作成する。

修得項目: SLA,SRA,SLL,SRL

6.表を使った処理

表(配列)を使ったプログラムを作成する。

修得項目:GR1~GR7,指標レジスタ

7.入出力処理

マクロ命令IN,OUT を使って入出力処理を行うプログラムを作成する。

修得項目: IN,OUT

8.スタック

スタック操作を行うプログラムを作成する。

修得項目: PUSH,POP,RPUSH,RPOP,CALL,RET

 

表計算ソフト(概要)

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

【基本情報】

  • 表計算ソフトが持つ計算、集計などの機能を修得し、適用する。
  • 関数の種類、使い方を修得し、適用する。
  • マクロの作成方法を修得し、適用する。
  • 業務処理における表計算ソフトの活用方法を修得し、適用する。

1. ワークシート

基本的なワークシートを作成する。複数のワークシート間での参照,集計を行う。

修得項目: セル,空白セル,セル番地,セル範囲,ワークシート参照,相対参照,絶対参照 など

2.式

定数,セル,演算子,関数などを組み合わせて式を作成する。

修得項目:算術式,文字式,論理式,単項演算子(+,-),算術演算子(+,-,*,/,^),比較演算子(=,≠,>,<,≧,≦) など

3.関数

関数と数値,関数とセル,関数と関数などを組み合わせて式を作成する。

修得項目:引数,関数の入れ子,合計,平均,標本標準偏差,母標準偏差,最大,最小,IF,個数,条件付個数,整数部,剰余,平方根,論理積,論理和,否定,切上げ,四捨五入,切捨て,結合,順位,乱数,表引き,垂直照合,水平照合,照合検索,照合一致,条件付合計 など

4.マクロ

変数,セル変数,配列,演算子,関数を使ってマクロを作成する。

修得項目: 変数,セル変数,絶対表現,相対表現,配列,宣言,注釈,代入,選択処理,繰返し処理 など

5.表計算ソフトの応用

会計処理,成績処理などの業務処理に表計算ソフトを適用する。具体的には,対象業務を把握し,業務処理のアルゴリズムを表計算ソフトで実装する。