まとめ 基本情報技術者 アルゴリズムとプログラミングについて

データ構造

データ構造の種類

• スタック

  • 最後に格納したデータを最初に取り出すデータ構造

  • push （データの格納）

  • pop（データの取り出し）

  • 後に入れたデータを先に出すアルゴリズム

    後入れ先出し（LIFO：Last In First Out）

• キュー

  • 最初に格納したデータを最初に取り出すデータ構造

  • enqueue（データの格納）

  • dequeue（データの取り出し）

  • 先に入れたデータを先に取り出すアルゴリズム

    先入れ先出し（FIFO：First In First Out）

• 配列

  • 配列は参照、更新が早い
    • 値を直接指定できるので、参照や更新が早い
    • 挿入、更新時は他のデータの値の添字が変わるので遅い
  • 添字（0~）
  • 要素（中身）
  • 多次元配列
    • 行と列でデータを格納
    • 配列名(行, 列)で取り出す

• 連結リスト

  • 数珠繋ぎでデータを格納する方法
    データとポインタ（次のデータのアドレス値）が一纏めで格納されている
  • 連結リストは挿入、削除が早い
    • 挿入、削除時は次の前後のポインタの値を書き換えるだけで行える
    • 逆に参照や更新時は、対象データを追わないといけないので遅い。

• 二分探索木

  • 左の子孫＜親＜右の子孫
  • データを見つけるのに便利

アルゴリズムの分類

整列アルゴリズム（データを並べるためのアルゴリズム）

※クイックソートが出る可能性大

• バブルソート

  • バブルソートは単純な比較ソートアルゴリズムで、隣接する要素を比較して必要に応じて交換します。
  • リストを一巡りすると、最大の要素が一番後ろに移動します。
  • このプロセスを要素が整列するまで繰り返します。

• 選択ソート

  • 選択ソートは簡単なソートアルゴリズムで、リストから最小の要素を選択し、先頭に配置します。
  • 残りの要素から次に最小の要素を選んで、次の位置に配置する作業を繰り返します。
  • リスト全体が整列するまで続けます。

• 挿入ソート

  • 挿入ソートは、要素を適切な位置に挿入していくアルゴリズムです。
  • リストを整列済みの部分と未整列の部分に分け、未整列の要素を適切な位置に挿入します。
  • リストの先頭から順に要素を取り出し、挿入操作を行って整列します。

• クイックソート

  1. クイックソートは分割統治法を使用する高速なソートアルゴリズムです。リストを適切な基準値（ピボット）を選び、それを中心に小さい要素と大きい要素に分割します。それぞれの部分リストを再帰的にソートし、結合してソート済みのリストを得ます。
  2. バブルソート (Bubble Sort):

探索アルゴリズム（特定のデータを見つけ出すアルゴリズム）

※ハッシュ法と二分探索法が出る可能性大

• 線形探索法

  • 線形探索法は、データを順番に検索するアルゴリズムです。
  • リストや配列内の各要素を順番に調べ、目的の要素が見つかるか、リストの終端まで探索します。
  • 線形探索はソートされていないデータにも適用できますが、大規模なデータ構造では効率が低いことがあります。

• ハッシュ値

  • ハッシュ法は、データを高速に検索するためのアルゴリズムです。
  • ハッシュ関数を使用して、データのキーをハッシュ値に変換します。
  • ハッシュ値を使って、データを格納した配列やハッシュテーブルなどのデータ構造にアクセスし、データを効率的に取得します。
  • ハッシュ法は平均的に高速な検索を提供しますが、ハッシュ関数の選択が重要で、衝突（複数のキーが同じハッシュ値を持つ状況）の処理が必要です。

• 二分探索法

  • 二分探索法は、データがソート済みのリストや配列内で検索するアルゴリズムです。
  • リストの中央の要素を調べ、目的の要素が中央より小さいか大きいかを比較します。
  • 目的の要素が中央より小さい場合、探索範囲を前半に絞り込み、大きい場合は後半に絞り込みます。
  • このプロセスを繰り返して、目的の要素が見つかるまで続けます。

再起アルゴリズム

• とは
  • 再起呼び出しアルゴリズムは、関数が自身を呼び出す再起性を持つアルゴリズムです。
  • 再帰的な関数は、問題を小さな部分問題に分割し、それを解決するために同じ関数を再帰的に呼び出します。

オーダー（アリゴリズムの計算量）

• オーダーとは

  • アルゴリズムを完了するための計算量

  • オーダー記法
    O(計算量)

  • データの量が2倍、3倍になると、計算量も2倍、3倍になる > O(n)

  • データの量が2倍、3倍になると、計算量も4倍、9倍になる > O(n2)

  • 二分探索法のオーダー

    O (log n)

    • logとは対数。何等倍かを表す
    • 2の3乗＝8の場合
      log 8 = 3 (2を何回かけたら8になるか)

プログラミングの性質

※出るのはリカーシブとリエントラント

• 再起（リカーシブ）

  • プログラミングの実行中に自分自身を呼び出すことができる性質
  • 再起プログラミング

• 再入可能（リエントラント）

  • 複数のプログラムから同時に呼び出されても正しく動作する性質
  • 再入可能プログラミング

• 再配置可能（リロケータブル）

  プログラムを主記憶装置のどの部分においても実行できる性質

• 再使用可能（リユーザブル）

  一度主記憶装置に格納すれば、何度でも繰り返し実行できる性質

Javaが含まれる用語

• Javaアプレット

  クライアントのWebブラウザ上で実行されるプログラム

• Javaサーブレット

  サーバー上で実行される、動的Webページを作るためのプログラム

• Java Beans

  機能を部品化、再利用できるようコンポーネント化するための仕様

その他の言語

• マークアップ言語

  ※タグを定義しる言語

  • HTML（タグで論理構造や文字要素を定義）
  • XML（任意のタグを定義）

• Ajax

  Webページ上で画面推移なしで動的インターフェースを実現する技術（非同期処理）