アルゴリズムとプログラミング（データ構造・アルゴリズム・プログラミング・プログラム言語・その他の言語）

テクノロジ系／基礎理論

---

この単元の範囲

大分類1「基礎理論」の中分類2「アルゴリズムとプログラミング」は、1.データ構造 2.アルゴリズム 3.プログラミング 4.プログラム言語 5.その他の言語という5つの小分類で構成される。データをどう格納するか（データ構造）、格納したデータをどう処理するか（アルゴリズム）、その処理をどう記述するか（プログラミング／プログラム言語／その他の言語）という一連の流れとして捉えると理解しやすい。

なお、この中分類は基本情報技術者試験の科目Bの出題範囲の中心（想定出題割合で約8割）を占める。科目Bは「アルゴリズムとプログラミング」（擬似言語による出題、想定出題割合約8割）と「情報セキュリティ」（同約2割）の2分野で構成されており、後者はこの中分類の範囲外である点に注意したい。科目Bでは、IPA公式の擬似言語（プログラム的な記述形式）で書かれたコードを読み、変数の値や処理結果をトレースする問題が中心になる。したがって、ここで扱う内容は暗記科目ではなく「実際にコードを読み書きできるか」を問う実技寄りの分野だと意識しておきたい。

1. データ構造

配列はデータを連続した領域に並べて格納する最も基本的な構造で、多次元配列（表形式のデータなど）や、確保サイズを実行時に変えられる動的配列もある。リストは要素同士をポインタで数珠つなぎにする構造で、一方向にしか辿れない単方向リスト、前後どちらにも辿れる双方向リスト、末尾が先頭に戻る環状リストがある。配列は途中への挿入・削除が重く、リストは要素へのランダムアクセスが遅い、というトレードオフを押さえておくとよい。

スタックは最後に入れたものを最初に取り出すLIFO（Last In First Out）構造で、格納操作をプッシュ、取り出し操作をポップと呼ぶ。ブラウザの「戻る」ボタンや関数呼び出しの管理（コールスタック）が身近な例である。キューは先に入れたものから先に取り出すFIFO（First In First Out）構造で、印刷待ち行列や窓口の順番待ちに相当する。

木構造は根（ルート）から葉（リーフ）へと枝分かれする階層構造で、各節点が高々2つの子を持つ2分木、全ての節点の子の数が揃った完全2分木、左右の高さの差が小さく保たれるバランス木（代表例がAVL木）、多数の子を持てる多分木、探索に特化した探索木（代表例が2分探索木、大量データのディスク管理に向くB木）がある。木の巡り方には、根を先に処理する先行順、子を先に処理する後行順、左の子→根→右の子の順で処理する中間順があり、探索方針としては深く潜ってから戻る深さ優先探索と、階層ごとに広く探す幅優先探索がある。

2. アルゴリズム

処理の流れを図で表す流れ図（フローチャート）では、開始・終了を表す端子、処理を表す長方形、条件分岐を表す判断（ひし形）、繰り返しの範囲を示すループ端などの記号を使う。

代表的なアルゴリズムのうち、整列（ソート）では、隣接要素を比較して並べ替えるバブルソート、未整列部分から最小値を選んで確定させる選択ソート、適切な位置に挿入していく挿入ソート、基準値（ピボット）で分割を繰り返す高速なクイックソート、木構造を利用するヒープソート、整列済みの部分列を統合していくマージソートがよく問われる。探索では、先頭から順に調べる線形探索法、整列済みデータを半分ずつ絞り込む2分探索法、キーからハッシュ関数で格納位置を計算するハッシュ表探索法がある。グラフアルゴリズムでは、重み付きグラフの最短経路を求めるダイクストラ法やベルマンフォード法が代表例である。近年は文章を単語に分割する形態素解析、係り受け解析やn-gramなどの自然言語処理関連の用語もシラバスに含まれる。処理を自分自身の呼び出しで表す再帰、問題を小さく分割して解く分割統治法は、アルゴリズム設計の考え方として整列・探索の両方に登場する。

3. プログラミング

プログラムを書く際の作法として、字下げ（インデンテーション）やネストの深さ、命名規則を統一することが保守性・可読性を高める。制御構造は、条件によって処理を分岐させる選択処理（if文など）と、条件が満たされる間処理を繰り返す繰返し処理（while文・for文など）に大別される。データ型には整数型・実数型・論理型・文字列型などがあり、演算には四則演算などの算術演算、大小を比べる比較演算、真偽値を組み合わせる論理演算、ビット単位で処理するビット演算がある。手続や関数では、呼び出し元から渡す引数と、処理結果として返す戻り値、関数内だけで有効な局所変数の関係を理解しておく必要がある。

オブジェクト指向プログラミングでは、データと処理をひとまとめにした「クラス」からインスタンス（実体）を生成する際に呼ばれるコンストラクタ、クラス内の変数であるメンバ変数、親クラスのメソッドを子クラスで上書きするオーバーライド、同名メソッドを引数の型・数で使い分けるオーバーロードが基本用語である。Webプログラミングでは、Webサーバ側で動作するサーバサイドプログラミング、ページ全体を再読み込みせず非同期通信で部分更新するAjaxなどが問われる。また、プログラムの文法をBNF（バッカス・ナウア記法）のようなメタ言語で厳密に表記する方法もこの小分類の範囲に含まれる。

4. プログラム言語

プログラム言語は大きく3系統に分類される。処理手順を順番に記述する手続型言語（Fortran, COBOL, Pascal, BASIC, C, R など）、データと処理をオブジェクトとしてまとめるオブジェクト指向言語（Java, C++, Julia, Go など）、コンパイルせずに逐次実行できるスクリプト言語（Python, Ruby, PHP, Perl など）である。用途に応じて、業務システムはCOBOLや Java、統計処理はR、Webアプリのバックエンドは Python や PHP といった向き不向きがある。

異なるプログラム言語で書かれたコードを共通の実行基盤上で動かす仕組みとして共通言語基盤（CLI：Common Language Infrastructure）があり、JIS X 3016（国際規格 ISO/IEC 23271 に対応）として標準化されている。これにより、例えばC#で書いたモジュールとF#で書いたモジュールを同じ実行環境上で連携させることができる。

5. その他の言語

Webページの構造を記述するマークアップ言語の代表がHTMLで、<開始タグ> と </終了タグ> で要素を囲んで表現し、文書の構造ルールを DTD（文書型定義）で定義できる。汎用的にデータ構造を記述できるXMLでは、文書構造をオブジェクトとして扱う DOM、ベクター画像を表す SVG、XML文書の構造を検証する XML Schema などが関連する。HTMLとXMLの文法を統合した XHTML、見た目（デザイン）を文書構造から分離して指定するスタイルシート（CSS：Cascading Style Sheets、XSL：Extensible Stylesheet Language）も範囲に含まれる。

ソフトウェアの設計図を描くUML（Unified Modeling Language）では、クラス同士の関係を表すクラス図、処理の流れを表すアクティビティ図、オブジェクト間のやり取りを時系列で表すシーケンス図などの図の種類を区別できることが求められる。データ交換用の軽量な記法として、キーと値の組でデータを表す JSON（JavaScript Object Notation）、インデントで階層を表す YAML もこの小分類に含まれる。

6. 科目Bとの関係と擬似言語の記法

科目Bで使われるIPA公式の擬似言語は、次のような記述ルールに従う。代入は ←、配列の要素番号は1から始まる（data[1] が先頭要素）。条件分岐は次の形で書く。

if (条件式)
    処理1
elseif (条件式)
    処理2
else
    処理3
endif

繰り返しには、条件を先に判定する while (条件式) 〜 endwhile、条件を後で判定する do 〜 while (条件式)、回数を指定する for (変数を初期値から終値まで増分ずつ増やす) 〜 endfor の3種類がある。関数・手続の定義は「○戻り値の型: 関数名（引数の型: 引数名）」の形で書き、return で値を返す。この記法に慣れておくと、後述の演習問題や実際の科目B問題を読み進めやすくなる。

---

参考文献

IPA「基本情報技術者試験シラバス Ver.9.2」大分類1「基礎理論」中分類2「アルゴリズムとプログラミング」（p.7-10）: https://www.ipa.go.jp/shiken/syllabus/omgdg50000005kpe-att/syllabus_fe_ver9_2.pdf

---

本資料は IPA（独立行政法人情報処理推進機構）が公表する「基本情報技術者試験シラバス Ver.9.2」（大分類1「基礎理論」中分類2「アルゴリズムとプログラミング」、p.7-10）に基づく自作の解説テキストである。

シラバス本文の小分類構成（データ構造／アルゴリズム／プログラミング／プログラム言語／その他の言語）・用語例を参照しつつ、解説文・具体例は本資料著者（nomuraya-dojo）の独自作成である
末尾の「オリジナル演習問題」は IPA 過去問を模倣・転記せず、本資料著者が独自に作成したものである。擬似言語によるプログラムトレース問題も、IPA公式の擬似言語記述形式（if/elseif/else/endif、while/endwhile、for/endfor、配列の要素番号は1始まりなど）に準拠した独自コードであり、IPA公表の科目Bサンプル問題・過去問のコードそのものを転記したものではない
シラバスそのものの著作権は IPA に帰属する。原文は IPA公式シラバスPDF を参照すること
本資料の利用にあたっては、IPAのウェブサイトのご利用について（著作権・利用規約）に従うこと

考えてみよう

既定では正解・不正解の判定はしません。自分のペースで「答えを見る」を。採点してほしい場合だけ「採点してほしい」を押してください。

問1

データを格納する際、後から入れたデータを先に取り出す方式（LIFO）を採用しているデータ構造はどれか。

ア　キュー

イ　スタック

ウ　単方向リスト

エ　2分探索木

解答：イ

解説： 後入れ先出し（LIFO：Last In First Out）を実現するのはスタックであり、格納操作をプッシュ、取り出し操作をポップと呼ぶ。キューは先入れ先出し（FIFO）であり、両者は取り出す順序が逆である。単方向リストは要素の連結方法を表す用語、2分探索木は探索に特化した木構造であり、いずれもLIFOそのものを指す語ではない。

問2

オブジェクト指向プログラミングにおいて、親クラスで定義されたメソッドと同じ名前・同じ引数構成のメソッドを子クラスで再定義し、子クラスのインスタンスから呼び出したときに子クラス側の処理が実行されるようにする仕組みを何と呼ぶか。

ア　オーバーロード

イ　オーバーライド

ウ　コンストラクタ

エ　カプセル化

解答：イ

解説： 親クラスのメソッドを子クラスで上書き（再定義）する仕組みはオーバーライドである。オーバーロードは同一クラス内で引数の型や数が異なる同名メソッドを複数定義する仕組みであり、オーバーライドとは異なる概念なので混同しないこと。コンストラクタはインスタンス生成時に呼ばれる初期化用のメソッド、カプセル化はデータと処理をまとめて外部から隠蔽する考え方である。

問3（擬似言語プログラムトレース）

次の擬似言語で記述された手続 整列 は、配列 data を選択ソートで昇順に並べ替えるものである。この手続を 整列({5, 2, 4, 1, 3}) として呼び出したとき、外側の繰返し for (i を 1 から (dataの要素数－ 1) まで 1 ずつ増やす) が i = 1 の処理を終えた直後の配列 data の中身として正しいものはどれか。

○整数型の配列: 整列(整数型の配列: data)
    整数型: i, j, minIdx
    整数型: tmp
    for (i を 1 から (dataの要素数 － 1) まで 1 ずつ増やす)
        minIdx ← i
        for (j を i ＋ 1 から dataの要素数 まで 1 ずつ増やす)
            if (data[j] ＜ data[minIdx])
                minIdx ← j
            endif
        endfor
        tmp ← data[i]
        data[i] ← data[minIdx]
        data[minIdx] ← tmp
    endfor
    return data

ア　{1, 2, 4, 5, 3}

イ　{2, 5, 4, 1, 3}

ウ　{1, 5, 4, 2, 3}

エ　{5, 2, 4, 1, 3}

解答：ア

解説： 選択ソートは「未確定部分から最小値を探して先頭と交換する」動作を繰り返す。i = 1 のとき、内側の繰返し（j = 2〜5）で未確定部分 {5, 2, 4, 1, 3} の最小値 1（添字4）を探し当て、minIdx ← 4 となる。ループ終了後に data[1] と data[4] を交換するので、配列は {1, 2, 4, 5, 3} となる。以降 i = 2, 3, 4 でも同様の処理を繰り返すことで最終的に {1, 2, 3, 4, 5} に整列される。

問4（擬似言語空欄補充）

次の擬似言語で記述された関数 2分探索 は、昇順に整列済みの配列 data から target の位置（添字）を2分探索で求め、見つからない場合は －1 を返す。プログラム中の空欄 a、b に入れる字句の組合せとして適切なものはどれか。

○整数型: 2分探索(整数型の配列: data, 整数型: target)
    整数型: low, high, mid
    low ← 1
    high ← dataの要素数
    while (low ≦ high)
        mid ← (low ＋ high) ÷ 2    // 小数点以下切り捨て
        if (data[mid] ＝ target)
            return mid
        elseif (data[mid] ＜ target)
            low ← [ a ]
        else
            high ← [ b ]
        endif
    endwhile
    return －1

ア　a: mid，b: mid

イ　a: mid ＋ 1，b: mid － 1

ウ　a: mid － 1，b: mid ＋ 1

エ　a: high，b: low

解答：イ

解説： 2分探索は、探索範囲の中央 mid の値と目的の値 target を比較し、範囲を半分に絞り込みながら探す。data[mid] ＜ target のときは目的の値が mid より右側（後方）にあるはずなので、探索範囲の下限を mid ＋ 1 に更新する（low ← mid ＋ 1）。逆に data[mid] ＞ target（else側）のときは目的の値が mid より左側にあるはずなので、上限を mid － 1 に更新する（high ← mid － 1）。境界に mid 自身を含めてしまうと、探索範囲が縮まらず無限ループになる点に注意する。

問5

手続型言語・オブジェクト指向言語・スクリプト言語の分類に関する記述のうち、適切なものはどれか。

ア　COBOLはオブジェクト指向言語に、Javaは手続型言語に分類される

イ　Pythonはスクリプト言語に、C++はオブジェクト指向言語に分類される

ウ　共通言語基盤（CLI）は特定の1つのプログラム言語の名称である

エ　スクリプト言語はコンパイルを行わなければ一切実行できない言語の総称である

解答：イ

解説： Pythonはコンパイルせず逐次実行できるスクリプト言語、C++はクラスによってデータと処理をまとめるオブジェクト指向言語に分類され、イは正しい。COBOLは業務処理を手順どおりに記述する手続型言語、Javaはオブジェクト指向言語であり、アの対応は逆である。共通言語基盤（CLI）は特定言語の名称ではなく、異なるプログラム言語で書かれたコードを共通の実行基盤上で動かすための仕組み（JIS X 3016 = ISO/IEC 23271 として標準化）であり、ウは誤り。スクリプト言語は一般に逐次実行（インタプリタ方式）されるが、これは「コンパイルなしでは一切実行できない」という意味ではなく、実装によってはバイトコードへの変換等が行われる場合もあるため、エのような断定は不適切である。

力試ししたい方はクイズ形式の演習（任意）もあります。読むだけでも十分です。