アルゴリズムの分類～その他の言語（2024.05.21）
参考書
アルゴリズムの分類
基本情報では、以下のアルゴリズムが出題される
整列アルゴリズム
データを並べるためのアルゴリズム探索アルゴリズム
データを見つけ出すためのアルゴリズム再帰的アルゴリズム
処理の途中で自分自身を呼び出すアルゴリズム
整列アルゴリズム
データを特定の順番に並べるアルゴリズム
ソートアルゴリズムと呼ばれることもある
主な整列アルゴリズム
バブルソート
配列の先頭から順に、隣り合ったデータを比較して、順序が違っていたら交換することを繰り返すアルゴリズム選択ソート
配列の先頭から順に、データを比較して最小値を選択し、選択した最小値を先頭のデータと交換することを繰り返すアルゴリズム
未整列データから最小値のデータを取り出し、最小値と確定データの右隣と入れ替えることで整列させていく方法挿入ソート
整列済みの要素を持つ配列に対して、未整列のデータを適切な場所に挿入するアルゴリズム
データを整列済と未整列の2つに分類し、未整列データの先頭の要素を正しい場所に挿入していくことで整列済にしていく方法クイックソート
「基準値よりも小さいグループ」と「基準値よりも大きいグループ」の2つに分け、分けたグループに対しても同じ手順を繰り返すアルゴリズム
基本情報ではほとんどこれが出題される。参考
クイックソート
データ全体を「基準値よりも小さいグループ」と「基準値よりも大きいグループ」の2つに分けるという作業を繰り返すことで、データの並べ替えを行うアルゴリズム
もっとも高速なアルゴリズム
最初に基準値を選び、それよりも小さな値のグループと大きな値のグループにデータを分割する。
探索アルゴリズム
特定のデータを見つけ出すアルゴリズム
主な探索アルゴリズム
線形探索法
先頭のデータから順番に1つずつ照合することで、目的のデータを見つける単純な探索アルゴリズムハッシュ法
ハッシュ表を使って、目的のデータを見つける探索アルゴリズム2分探索法
調べる範囲を半分に切り分けながら目的のデータを見つける探索アルゴリズム
基本情報では、「ハッシュ法」と「2分探索法」が頻繁に出題される
ハッシュ法
探索対象のデータをハッシュ値に変換し、このハッシュ値を使って目的のデータを見つける探索アルゴリズム
ハッシュ表探索法とも呼ばれる
ハッシュ表の作成方法
①ハッシュ関数を使ってデータをハッシュ値に変換
②ハッシュ値を添字とした、配列の要素にデータを格納する。ハッシュ法による探索方法
①ハッシュ関数を使って、探索対象となるデータをハッシュ値に変換
②ハッシュ表で変換したハッシュ値を指定することで、目的のデータの格納場所（添字）に一度の探索でアクセス可能代表的なハッシュ関数に、「剰余」がある。
ハッシュ法の弱点
入力値が異なるのに、ハッシュ値が同じ値になってしまうケースが存在すること
上記のことを「衝突」という。
試験に出る場所
ハッシュ法では、ハッシュ値によって格納場所を決める
ハッシュ法のデメリットは、衝突が起こる可能性があること
2分探索法
調べる範囲を半分に分割することで目的のデータを見つけるアルゴリズム
特徴
①データをあらかじめ整列させておく必要がある
②データを2つに分けながら探索する非常に効率のよい探索アルゴリズムだが、データをあらかじめ昇順か降順で整列させておくことが必要
探索方法
①列の中から中央の要素を見つける（中央の要素は先頭の添字と末尾の添字の合計を2で割ることで求められる。）
②探しているデータと１で取り出したデータを比較する
③－１．「探しているデータと１で取り出したデータが同じ」だったら、それが探しているデータ
③－２．「探しているデータの方が１で取り出したデータよりも大きい」だったら１で取り出したデータとそれよりも小さいデータを全部消す
③－３．「探しているデータの方が１で取り出したデータよりも小さい」だったら１で取り出したデータとそれよりも大きいデータを全部消す
④．残っているデータの中から真ん中のデータを取り出す
を繰り返す
再帰的アルゴリズム
処理の途中で自分自身を呼び出すアルゴリズム
再帰関数に関連する用語
再帰
繰り返しという意味再帰呼び出し
処理の途中で自分自身を呼び出すこと再帰関数
処理の途中で自分自身を呼び出す関数のこと
基本情報では、再帰的アルゴリズムは、主に「総和」、「剰余」、「階乗」の3つを求める際に出題される。
用途
総和
与えられた数すべての合計。数式では「Σ」（シグマ）と呼ばれる記号を用いて表す剰余
割り算の余り。数式では「mod」（モッド）と呼ばれる記号を用いて表す。階乗
1からｎまでの整数をかけ算した数
試験に出る部分
再帰呼び出しとは関数の中で自分自身を呼び出して処理を実行すること
再帰的アルゴリズムとは「総和」、「剰余」、「階乗」を求めるアルゴリズムとして出題される
再帰的アルゴリズムの問題では、実際に再帰関数に引数を代入し、結果を算出すり練習をしておくことが必要
再帰的アルゴリズムによる総和の求め方
再帰的アルゴリズムの4つの表現方法（文章、流れ図、数式、プログラム言語）は、基本情報でも頻繁に出題される。
それぞれの表現例については参考書を参照
アルゴリズムの計算量を算出する問題
最適なアルゴリズムが何であるかを調べるために、アルゴリズムの計算量を算出する。
最適なアルゴリズムとは、実行時間が短く、メモリの使用量が少ないアルゴリズム
オーダー（計算量）
アルゴリズムを完了するために必要な計算量のこと
オーダーは「これ以上は大きくならない」という「最大の計算量」を表す
オーダー記法
データ数と計算量の関係を表す記法のことオーダー記法の例
Ｏ（計算量）
データの数が2倍、3倍になった際に、計算量が2倍、3倍になる場合
→Ｏ（n）データの数が2倍、3倍になった際に、計算量が4倍、9倍になる場合
→Ｏ（n^2）1回の比較や探索で処理が完了する場合
→Ｏ（1）
2分探索法のオーダーの求め方
Ｏ（log2 n）
対数の2つの表記方法
オーダー記法では、底の違いは無視できるため2とおりの表記方法あり
log2 n
log n
その他のアルゴリズムのオーダー
ハッシュ法
Ｏ（1）
n（データ数）に関わらず、計算量は常に1回線形探索法
Ｏ（ｎ）
最大ですべてのデータ（ｎ）を探索する必要があるクイックソート
Ｏ（ｎ log n）
プログラムの性質と種類
プログラム
コンピュータに対する命令書のこと
基本情報でよく出題される内容
性質
再帰（リカーシブ）
再入可能（リエントラント）
プログラム言語
Java Beans
Javaアプレット
Javaサーブレット
プログラムの性質
再帰（リカーシブ）
プログラムの実行中に自分自身を呼び出すことができる性質
この性質を持つプログラムのことを「再帰プログラム」という
再入可能（リエントラント）
複数のプログラムから同時に呼び出されても、正しく動作する性質
この性質を持つプログラムのことを「再入可能プログラム」という
再配置可能（リロケータブル）
プログラムを主記憶装置のどこに配置しても実行できる性質
この性質を持つプログラムのことを「再配置可能プログラム」という
再使用可能（リユーザブル）
一度プログラムを主記憶装置に格納すれば、あとは主記憶装置から何度でも繰り返し実行できる性質
この性質を持つプログラムを「再使用可能プログラム」という
通常のプログラムでは、処理の実行後に再度処理を実行したい場合は、補助記憶装置から主記憶装置にプログラムを再度格納する必要がある。（これをリロード）という
再使用可能プログラムはリロードが必要ない。
名称にJavaが含まれる用語
Java
コンピュータの種類やOSに依存しない、ソフトウェアを開発できるプログラム言語Javaアプリケーション
Javaで書かれたアプリケーションソフトウェアJavaアプレット
サーバーからダウンロードして、クライアント側のWebブラウザ上で実行されるJavaで書かれたプログラム。クライアント側へ転送されて実行されるプログラムのことを「アプレット」というJavaサーブレット
サーバ上で実行される動的なWebページを作るためのJavaで書かれたプログラム。動的処理（ユーザーの要求に合わせてその都度異なるWebページを表示する処理）を実現する際に利用する。JavaBeans
Javaのプログラムにおいて、よく使われる機能を部品化し、再利用できるようにコンポーネント化するための仕様JavaScript
動的なWebページを作るためのプログラム言語。「Java」と名前は似ているがまったく別物のプログラム言語試験に出る部分
Javaアプレットとは、サーバからダウンロードして、クライアント側のWebブラウザ上で実行されるJavaで書かれたプログラム
Javaサーブレットとは、サーバ上で実行される、動的なWebページを作るためのJavaで書かれたプログラム
その他の言語
基本情報で出題頻度が高いもの
ＸＭＬ
ＣＳＳ
Ａｊａｘ
ＨＴＭＬ
Hyper Text Markup Language
Ｗｅｂページを作成する際に利用されているマークアップ言語
タグと呼ばれる要素を使ってＷｅｂページの論理構造や文字要素を指定する
用途は、Webページの作成
論理構造
そのＷｅｂページにどのような要素があり、またそれがどのような関係性を持っているかを示すものマークアップ言語
タグ（＜＞で囲まれた文字）を使ってデータを記述するマークアップ言語
マークアップとは、「タグをつける」という意味の英語
ＸＭＬ
eXtensible Markup Language
ユーザー自身が定義したタグを使ってデータを記述するマークアップ言語
用途は、Web上でデータを交換すること
メリットは、人間とコンピュータの両方が読みやすい形式であること
ＨＴＭＬとＸＭＬの親
ＳＧＭＬ
ＣＳＳ
Cascading Style Sheets
ＨＴＭＬ文書の文字の大きさ、文字の色、行間などのデザイン（視覚表現）を指定する言語
Ａｊａｘ
Asynchronous JavaScript and XML
Webページ上で画面を切り替えることなく、動的なユーザーインターフェースを実現する技術
従来のWebページ
ブラウザに表示するWebページを切り替えるために画面遷移を必要としていた。流れは下記のとおりサーバと通信して次のWebページを取得する
取得したWebページをブラウザ上に表示する。
同期通信と非同期通信
同期通信
サーバの処理が完了するまで次の処理に進まない方式非同期通信
サーバの処理が終わるのを待たずに次の処理に進む方式のこと
代表例）グーグルマップ
進捗
２５ ／ ９７ （２５％）
この記事が気に入ったらサポートをしてみませんか？