書籍概要

基本情報技術者【科目B】アルゴリズム×擬似言語 トレーニングブック

著者
発売日
更新日

概要

2023年4月の試験制度の改訂で新設された「科目B」は,従来の午後試験に相当するものですが,長文ではなく,以前の中問程度の分量で20問出題される形に変更されました。このうち16問が「データ構造及びアルゴリズム(擬似言語)」からの出題となりますが,全問必須なので,従来のように言語が苦手という人が表計算等に逃げることもできなくなりました。

IPAが公開したサンプル問題を見ても,1問あたり平均5分で解いていくにはコツや慣れが必要です。本書は,アルゴリズムや擬似言語に慣れていない人を対象として,過去問およびサンプル問題,さらにはそれらを題材としたオリジナル問題を多数用意し,アルゴリズム問題に慣れるためのトレーニングが積める内容となっています。

こんな方におすすめ

  • 基本情報処理技術者試験を受験する方で,特に科目Bのアルゴリズム問題に自信のない方
  • 多くの問題を解きたいと思っている方

サンプル

samplesamplesample

目次

第1章 変数とデータ構造

  • 1.1 アルゴリズムとは
  • 1.2 変数
  • 1.3 配列
  • 1.4 リスト
  • 1.5 スタックとキュー
  • 1.6 木構造
  • COLUMN
    • 円周率3.14を整数型の変数に入れたらどうなる?
    • データ構造とは何か?
    • 双方向リストの場合,ポインタ部は二つ必要!
    • リストを用いたスタックとキューの実現
    • 部分木をもつ節の削除

第2章 擬似言語プログラミング

  • 2.1 手続と関数
  • 2.2 基本制御構造と条件式
  • 2.3 選択処理(if文)
  • 2.4 繰返し処理(while文とdo-while文)
  • 2.5 繰返し処理(for文)
  • 2.6 オブジェクト指向とクラス
  • COLUMN
    • 複合条件の否定はド・モルガンの法則で考える
    • while文の条件式が常に真になる場合は注意!
    • 2分探索法の流れ図
    • クラスStackのインスタンスを二つ作る

第3章 基本例題

  • 3.1 成績評価を行う
  • 3.2 1からNまでの整数の総和を求める
  • 3.3 配列内に格納されているある数値を求める
  • 3.4 二つの配列を連結する
  • 3.5 配列の要素の並びを逆順にする
  • 3.6 配列の要素の値を別の配列の要素番号に使用する
  • 3.7 k番目のデータまでを並べ替える
  • 3.8 二つの正の整数の最大公約数を求める
  • 3.9 リスト要素を探索する
  • 3.10 数字文字列を数値に変換する
  • 3.11 10進整数を8桁の2進数に変換する
  • 3.12 ビット演算の結果を表示する
  • 3.13 再帰的処理を行う関数
  • COLUMN
    • if文の構文を確認しておこう!
    • 変数の初期値に注意!
    • 変数aの初期値として-1を設定する方法もある?!
    • 二つの配列を一つにする処理
    • 問われている処理のみに着目する?!
    • 「配列の領域外を参照する」ってどういうこと?
    • data[1]が最小の値でなかったら…?
    • 最大公約数の求め方
    • 「node+1」で次の要素をアクセスできないの?
    • 16進数の数字文字列を数値に変換する
    • 数字文字列を数値に変換する応用プログラムに挑戦!
    • 問題文にある条件「0<n<100を満たす整数」の意味
    • 配列binの要素数を固定にしない方法
    • maskの値を変えないで同じ処理を行う方法
    • シフト演算を確認しておこう!
    • 試験によく出る再帰関数
    • 二つの正の整数の最大公約数を再帰的に求める

第4章 応用例題

  • 4.1 ゲームの得点を計算する
  • 4.2 自然数nまでの素数を求める
  • 4.3 ハフマン符号化を使ってデータを圧縮する
  • 4.4 整列済の二つの配列を併合する
  • 4.5 文字列を圧縮する
  • 4.6 ハッシュ法でデータを登録する
  • 4.7 スタックを操作する再帰的な手続
  • 4.8 2分探索木からデータを探索する
  • 4.9 逆ポーランド表記法で表された式を計算する
  • 4.10 リストの自己再編成探索
  • 4.11 隣接行列で表されたグラフを探索する
  • 4.12 シフト演算と加算の繰返しで2進数の乗算を行う
  • 4.13 base64におけるエンコード処理
  • 4.14 プログラムの改良
  • 4.15 プログラムのテスト
  • 4.16 非線形方程式の解法(2分法)
  • 4.17 デシジョンツリーを用いた意思決定
  • 4.18 ゲーム木の探索
  • COLUMN
    • 関数numを使うと効率が悪い?
    • ハフマン符号の問題では圧縮率が問われる?
    • 番兵を用いた併合(マージ)
    • プログラムの解読法
    • チェーン方式の処理は「リスト処理」!
    • 条件式が真のときの処理を記述しなくていいの?
    • 関数lookupを再帰版に書き換えてみる
    • 通常の式を逆ポーランド表記にしてみる
    • 2分木を幅優先探索してみる
    • (2)の処理をプログラムで書いてみよう!
    • 時間効率性からみた最適化
    • 判定条件網羅(分岐網羅)
    • 期待値原理を用いた意思決定
    • ゲーム木のミニマックス探索
    • 原始モンテカルロ法

第5章 サンプル問題

  • 5.1 サンプル問題1
  • 5.2 サンプル問題2
  • 5.3 サンプル問題1の解答・解説
  • 5.4 サンプル問題2の解答・解説
  • COLUMN
    • 新たな要素をリストの先頭に追加するプログラム
    • ビットの並びを逆にするもう一つの方法
    • 深さ優先探索(先行順,中間順,後行順)
    • 不具合のある2分探索プログラム

サポート

正誤表

本書の以下の部分に誤りがありました。ここに訂正するとともに,ご迷惑をおかけしたことを深くお詫び申し上げます。

(2024年3月7日最終更新)

P.126 上から1行目

merge({2,4,6,10,15},{6,11,25})として呼び出すと,
merge({2,4,6,10,15},{6,11,17,25})として呼び出すと,

(以下2024年2月5日更新)

P.143 ページ中段にある図の2行上

スタックCの状態は,{1,2,3,1,2,3}となります
スタックBの状態は,{1,2,3,1,2,3}となります

(以下2023年8月2日更新)

P.48 上から3行目,及び4行目

~bが20と等しい」という条件式は~
~bが10と等しい」という条件式は~

(以下2023年6月22日更新)

P.121 脚注※1

「00,01,10,00」の4種類です。
「00,01,10,11」の4種類です。

商品一覧