ITの基礎知識|ITパスポート・基本情報

【アルゴリズム】の記事一覧

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

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

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

アルゴリズム設計

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

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

アルゴリズムの表現

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

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

擬似言語

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

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

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

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

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

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

擬似言語の仕様の例

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

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

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

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

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

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

分割統治法

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

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

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

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

この記事での学習内容 基本情報 応用情報バッチ処理などで使用される整列処理、併合処理、コントロールブレイク処理、編集処理のアルゴリズムを理解する。ファイル処理のアルゴリズムファイル処理とは、入力装置や外部記憶装置から読み取ったファイルを処理することです。処理対象のデータが主記憶装置の中にないため、以下のような手順が基本となります。 前処理: ファイルを開き、内容を主記憶装置の中...

Read more...

この記事での学習内容 基本情報 応用情報文字列処理のアルゴリズムを理解する。用語例:文字列照合、KMP法(クヌース・モリス・プラット法)、BM法(ボイヤ・ムーア法)文字列処理のアルゴリズム文字列処理のアルゴリズムは、一連の文字の並びを処理するアルゴリズムです。 連結: 一つの文字列の後へ別の文字列を追加して、一つの文字列にします。 挿入: 文字列の途中に別の文字列を挿入...

Read more...

この記事での学習内容 基本情報 応用情報グラフのアルゴリズムを理解する。用語例:深さ優先探索、幅優先探索、最短経路探索グラフのアルゴリズムグラフは節(ノード)とそれらを連結する結線(リンク)で結ばれた一つの図です。通信網、木構造、あるいは流れ図がその例です。(木構造の場合は、結線のことを枝とも呼ぶ)これらのグラフを扱うアルゴリズムをグラフのアルゴリズムといいます。木の巡回法...

Read more...

この記事での学習内容 ITパスポート 基本情報 応用情報探索、併合のアルゴリズムを理解する。再帰的アルゴリズムの考え方、特徴、実現に適したデータ構造を理解する。用語例:線形探索法、二分探索法、ハッシュ表探索法、シノニム対策探索「探索」とは配列などに格納されたデータの集まりから、特定のデータを探すことです。その値が見つかる場合と、見つからない場合があり、複数ある場合には最初の一つ...

Read more...

この記事での学習内容 ITパスポート 基本情報 応用情報整列のアルゴリズムを理解する。用語例:選択ソート、バブルソート、マージソート、挿入ソート、シェルソート、クイックソート、ヒープソート整列(ソート)整列とは、データを大きい順(降順)または小さい順(昇順)になるように並び替えることです。 昇順降順 数値「32514」1234554321 英字「BDAE...

Read more...

この記事での学習内容 ITパスポート 基本情報 応用情報アルゴリズムや流れ図(フローチャート)の考え方、記号、順次、判定、繰り返しなど、処理手順の表現方法を理解し、流れ図を描く方法を理解する。用語例:端子、処理、定義済み処理、判断、ループ端、データ、線アルゴリズムアルゴリズムとは、目的にたどり着くための道筋や処理の手順のことです。同じ結果を出すための処理であっても、より整理され...

Read more...

情報処理技術者試験での学習内容【基本情報・応用情報】 ・アルゴリズム、流れ図の考え方、表現方法を習得し、応用する。 ・代表的なアルゴリズムを習得し、応用する。 ・アルゴリズムの設計方法を習得し、応用する。【ITパスポート】 ・アルゴリズムと流れ図の基本的な考え方と表現方法を理解する。(1)アルゴリズムと流れ図 ITパスポート 基本情報 応用情報アルゴリズムや流れ図(...

Read more...