基本情報技術者

基本情報技術者試験のアルゴリズム対策① ~アルゴリズムの例をみてみよう~

こちらの記事は次のような方のニーズに応えるために書いています。

  • 基本情報技術者試験を受けようと思うけど、アルゴリズムについて知りたい!
  • アルゴリズムの基本的な考え方を教えて!
  • アルゴリズムってどういう意味?
まっすーです。中小企業診断士試験他多くの資格に合格した実績をベースに数々の資格試験の合格アドバイスをしています。
アルゴリズムは基本情報技術者試験では必須の知識です。今回はこのアルゴリズムについて解説していきます。

基本情報技術者試験のアルゴリズムとは?

基本情報技術者試験では、アルゴリズムを理解する必要があります。というよりも、理解できていない場合、合格は極めて難しいです。

その理由は、以下の基本情報技術者試験の午後試験科目(15点問題は2問選択)において、擬似言語25点・ソフトウェア開発、プログラミング25点の合計50点が、アルゴリズムを理解できていないとほぼ解答できないため、基本情報技術者試験の合格基準点60点に到達するのが難しくなります。

私が基本情報技術者試験に合格した際の体験記は以下のリンクに掲載しています。

基本情報技術者試験合格体験記 短時間高得点合格の勉強法は、過去問対策+午後アルゴリズムの理解この記事では基本情報技術者試験の合格体験記が読みたい!合格するための勉強法を知りたい!選択科目のアドバイスが欲しい!といった悩みに回答しています。...

アルゴリズムとは?

アルゴリズムの意味

アルゴリズムは下記のような意味があります。

問題を解決するための方法や手順のこと。問題解決の手続きを一般化するもので、プログラミングを作成する基礎となる。アルゴリズムは1つの問題に対し、複数ある場合が多い。たとえば、文字をアルファベット順に並べ替えるには、複数のアルゴリズムが考えられる。アルゴリズム次第で、プログラムのサイズや汎用性などが変わってくるため、効率的と思われるものをプログラムに採用する。アルゴリズムは流れ図(フローチャート)を用いて図式化される。
ASCII.jpデジタル用語辞典より

アルゴリズムの具体例

説明を読むと難しく感じますが、要は手順、と考えておけばいいのかなと思います。
たとえば、下の図でA地点からB地点に行くまでにはどういった方法があって、どれが一番早く到達するかといった検討です。

このくらい単純な図式だと、A→2→3→B地点と行くのが最も時間が短い、というのがわかります。これを算出するには、

  • A地点→1→B地点:  7分+14分=21分
  • A地点→2→B地点:  8分+12分=20分
  • A地点→2→3→B地点:8分+3分+8分=19分
  • A地点→3→B地点:  15分+8分=23分

というように総当りで確認するのが確実です。
情報技術者試験ではおなじみのクリティカルパス法による所要期間の見積もりも同じように計算しますよね。

こうした手順の算出方法がアルゴリズムであり、これを理解することが基本情報技術者試験の鍵になります。なお、ここでいうアルゴリズム(=手順)というのは、計算方法そのものではなくて、考え方です。

もう少し具体的に説明しますと、上の図式では、

  1. A地点からB地点まで行く方法を全て調べる(合計4ルート)
  2. 4ルートすべての所要時間を計算する
  3. 最も早い時間がどれかを選ぶ

という3つの手順を用いていることがわかります。

さらに手順を細分化すると、
「A地点からB地点まで行く方法を全て調べる(合計4ルート)」というのは、

  • A地点からのルートが何通りあるかを調べる
  • A地点から1つ進んだところからのルートが何通りあるかを調べる
  • これをB地点に到達するまで繰り返す

という手順に分かれます。

また、「4ルートすべての所要時間を計算する」というのは、

  • 各ルートを通過するときの所要時間を、B地点に到達するまで合計していく

ということであり、「最も早い時間がどれかを選ぶ」というのは、

  • 最も短い時間のルートのみを残す

ということになります。

つまり、普段ならば頭の中でぱっと計算していることも、手順を判断しているんですね。これを細かく分類して、条件分岐や計算を加えていくのがアルゴリズムの考え方ということになります。

コンピュータになぜアルゴリズムが必要か

なぜ、こういうアルゴリズムの考え方が必要か、というとコンピュータにはこうした手順を教えてあげないと動いてくれないからです。

人間ならば「A地点からB地点まで最も早く到達ルートはどれですか?」と質問するだけで答えを出せますが、コンピュータには先ほど書いたとおり、

  1. A地点からB地点まで行く方法を全て調べて
  2. すべてのルートの所要時間を計算して
  3. 最も早い時間がどれかを選んで

と伝えなければなりません。しかも行く方法の調べ方も、所要時間の計算方法も、最も早い時間の選び方もすべてプログラムという文字で伝えてあげなければなりません。
もし伝えなければ、コンピュータは何もしませんし、自分で考えてはくれません。

このプログラムを考える作業は非常に面倒ですし、頭で色々と考えなければなりません。
この作業ができるかどうかが、基本情報技術者試験に合格できるレベルのアルゴリズムが習得できるかの鍵になります。

もちろん、世間でいうプログラム開発をされている方にとっては簡単すぎる内容なのでしょうが、そうした世界で生きていない場合は、その最初の一歩にたどり着くまでが本当に大変です。

ですので、最初は難しくて当然です。少しずつ慣れていけばいいと思います。

まずは今回ご紹介したような簡単な形で、プログラムの記述は別として、どういうことをコンピュータに教えてあげれば答えを計算してくれるか、ということを考えてみるのがアルゴリズム理解のきっかけになるかと思います。

Excelマクロでアルゴリズムを表現

前置き

今回ご紹介したアルゴリズムは、最も早く到達できるルートをコンピュータに探す命令を出すための手順ですので、プログラム化が可能です。

そして、ExcelマクロはVBAというプログラムを利用したものですのでこうしたアルゴリズムをプログラムとして表現することが可能です。

なお、今回はどういった手順で判断がおこなわれていくのかを追っていくためにも、再帰処理などは使用せずに、そのままコードを羅列して表現しています。

もっと効率的な方法ももちろんあるのですが、アルゴリズムを理解していくには、プログラムのコードを追いながら、変数や条件分岐の流れを追っていくことが大切ですので、この方式をごs

コードのご紹介

まず、Excelに前提条件の準備をします。
プログラム化するにあたり、図で表現されている道順を文字と数値で表現します。

そして、この文字と数値を処理するコードを書きます。

使い方

下記のZIPファイルをダウンロード、解凍してからExcelを開き、マクロを有効にします。

ファイルダウンロード:最短ルート

その後、開発タブ→Visual BasicでVBAの画面を開きます。この操作は、
Alt + F11 または

Alt → E → M →Vでもおこなえます。

開発タブがない場合は、こちらのリンクをご参照の上Excelマクロの初期設定をしてください。

Excelマクロ入門② 初心者向けExcelマクロの使い方と初期設定の方法を解説 自動化を始めようこちらの記事では、17資格全てに一発合格したまっすーがExcelで簡単な自動化をするに何をすればいい?Excelマクロを使うための初期設定方法を教えてほしい!Excelマクロを使おうとしたけど使えない!といった悩みに回答しています。...

VBAの画面では、表示→ローカルウィンドウを選択して、ローカルウィンドウを表示してください。
下記のようにExcelの画面とVBAの画面を並べておくと見やすいです。
ローカルウィンドウが表示されていることを確認したら、再生ボタン(マクロ実行ボタン)を押して開始です。

すぐに結果が出ます。
A→2→3→Bが最短ルート、所要時間は19分です。

これだけだとよくわかりませんね。
今度は、F8 を押してみましょう。

すると、先ほど最初から最後まで実行されたプログラムが、1行ずつ実行されます。
F8 を押し続ければ、続けてプログラムが実行されていきます。

これで、変数の動きを確認しながら、どういった処理がされていくかを確認することができます。プログラムが進むたびに数字が書き換わっていって、答えを導き出していく動きがわかると思います。

アルゴリズムの例の説明は以上です。
いきなりこのプログラムの内容を理解するというよりは、アルゴリズムというのは、こうした動きで結果を出すための手順のことを言うんだ、ということをなんとなく理解してもらえればいいと思います。

ここまでお読みいただきましてありがとうございました。

ABOUT ME
まっすー
中小企業診断士のまっすーです。 社会保険労務士やITストラテジストなど、多くの難関資格に合格した実績をベースとした資格試験の学習方法、ExcelマクロやPythonを活用した自動化の推進、経営に役立つ管理会計の理論解説、ITを活用した経営資源の有効活用などの情報を発信しています。

COMMENT

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA