↓メインコンテンツへスキップ

【応用情報技術者試験】テクノロジ系学習メモ：基礎理論

·
目次

概要
#

応用情報技術者試験のテクノロジ系の基礎理論学習メモを集約する。

参考資料
#

学習メモ
#

基数変換問題で無限小数を素早く判定する方法
#

基数変換問題で無限小数を判定するような問題では分母の素因数分解で判定できる。

手順:

  1. 判定対象の数値を分数に変換
  2. この分数の既約分数(約分してこれ以上割れない形)にする
  3. 分母を因数分解する
  4. このとき、分母が対象の基数のべき乗のみ場合は有限小数。基数のべき乗以外の場合は無限小数と判断できる

具体例:

  1. 0.05
  2. 0.125
  3. 0.5
  • 上記の3つの10進数小数のうち、2進数に変換すると無限小数になるのは?
  • 手順に則ってそれぞれ分母を因数分解すると
    1. 0.05 = 5/100 = 1/20 = 1/2^2*5
    2. 0.125 = 125/1000 = 1/8 = 1/2^3
    3. 0.5 = 5/10 = 1/2 = 1/2^1
  • 「1:0.05」で分母に「5」が紛れていることがわかる。よって、「0.05」が無限小数と判定できる。

リスト
#

順序付けられたデータの並び。主なデータ構造として、配列と連結リストが存在する。

配列
#

個々の要素の位置を固定して、要素が格納されている番地(アドレス)を簡単に計算できるようにしたデータ構造

特徴

  • ダイレクトアクセス(任意の要素への直接参照)が可能
  • 要素の挿入・削除には非効率
    • 当該位置の要素を一つずつ前後に移動させる必要があるため
  • 予め最大データ数に対応した領域を確保する必要がある

連結リスト
#

各要素をポインタでつないだデータ構造

  • ポインタの接続方法で3種類に分類できる

単方向リスト（線形リスト・片方向リンク）
#

各要素は次の要素へのポインタを持つ

双方向リスト（双方向リンク）
#

各要素は前後両方の要素のポインタを持つ。

  • 単方向リストとの違いとして、途中要素への挿入・削除は双方向が容易である。

循環リスト
#

末尾の用が先頭要素へのポインタを持つ単方向リスト

配列と連結リストの違い
#

記憶域: 1つのデータあたりの必要な記憶域は連結リストのほうが大きい

  • 連結リストでは「データ + ポインタ」で管理されるため

追加・削除: 要素の追加・削除においては連結リストのほうが容易

  • 連結レストでは、配列と異なり、番地が固定されていないため、ポインタの値変更のみで済むため

記憶域の変化: 連結リストでは必要な記憶域は動的に変化して、データ数に比例する

  • 連結リストにおける要素の追加・削除
    • 応用情報技術者試験ではHead(先頭要素へのポインタ)・Tail(末尾要素へのポインタ)について出題される
    • Head・Tail・E1～E5のリストを具体例に解説する。

      • 具体例:

              graph LR
      Head --> E1;
      subgraph "Singly Linked List"
          E1 --> E2 --> E3 --> E4 --> E5 --> Null([null]);
      end
      Tail --> E5;

      style Head fill:#f9f,stroke:#333,stroke-width:2px
      style Tail fill:#ccf,stroke:#333,stroke-width:2px
      style Null fill:#eee,stroke:#333,stroke-dasharray: 5 5

      • 要素E0を先頭に追加する場合

          1. E0のポインタ部でE1を設定
          1. HeadでE0のアドレスを設定

      • 要素E6を末尾に追加する場合

          1. TailからたどったE5のポインタ部でE6を設定
          1. TailでE6のアドレスを設定

      • 要素E1を先頭から削除する場合

          1. HeadからたどったE1のポインタ部の値である「E2のアドレス」をHeadに設定

      • 要素E5を末尾から削除する場合

          1. Headから順番にE4までたどる
          1. E4のポインタ部にNULLを設定
          1. TailにE4のアドレスを設定

マージソート
#

データを最小単位(要素が1つ)になるまで半分に分割し、その後、それらを正しい順序で「マージ(併合)」していくことで全体のソートを完成させるソート方法

値呼び出し
#

引数の渡し方において、関数内で変数の値を上書きしても元の変数の値には反映されない。

参照呼出し
#

引数の渡し方において、関数内で変数の値を上書きすると元の変数の値に反映される。

回帰直線
#

散布図にプロットした2組のデータの分布をもとに相関関係を表した近似直線 将来の予定値を求める場合などに利用される

主成分分析
#

複数の要因が相互に関連している場合に、その群の特性を決定づけている主な要因を合成変数として求める統計的な手法 変数を統合した新たな変数を使用して，データがもつ変数の数を減らすことができる