某試験に向けてのメモ的な何か6

平衡二分探索木
データ構造の1つである二部探索木のうち、根ノードから子を持たない末端の葉ノードまでの深さがなるべく均等になるように構築されたもの。
二部探索木は各ノードの値よりも左の子ノードの値の方が小さく、右の子ノードの値の方が大きくなるように値を挿入した二分木である。値を探索するには、根ノードから出発して、各ノードの値が探索している値より大きければ左の子に、小さければ右の子に移っていき、末端のノードまで辿れば探索が終了する。このとき、根から葉までの距離がなるべく均等な方が探索効率が良いため、平衡二分探索木では値の挿入や削除の際に高さが均等になるような処理を行う。


平衡木
データ構造の一種であるツリー構造のうち、根ノードから子を持たない末端の葉ノードまでの深さがなるべく等しくなるように構築されたもの。
根からどの葉までたどってもほぼ同じ数のノードを経由するため、探索などの処理する際に平均の計算時間を短縮することができる。ツリーを平衡木に保つには、ノードの挿入や削除が行われる際に、再構築して高さが等しく保たれるようにする処理が必要となる。


分割統治法(divide and conquer algorithm)
大規模な問題を効率的に解くアルゴリズムの1つで、そのままでは解決することが難しい大きな問題を、いくつかの小さな問題に分割して個別に解決していくことで、最終的に大きな問題を解決する方式。

クイックソート - データの比較・交換回数を極力少なくして効率的にソートする

マージソート - 並べ替えたい配列を再帰的に分割していった後、それらを比較、交換しながら再び併合していく

メイン処理では大まかな流れを記述して、細かい処理をサブルーチンと呼ばれる単位で分割していく「構造化プログラミング」もこの考え方に基づくものである。


ブロック暗号
データを一定の長さのブロックごとに区切り、ブロック単位で暗号化を行なう暗号のこと。
鍵の長さが大きいほど複雑な暗号を作成できる。
これに対するは、ストリーム暗号 - 1ビットまたは1バイト単位で逐次暗号化


平文
暗号化されていないデータのこと。「暗号文」の対義語で、本来暗号化されていることが望ましいパスワードのデータが、暗号化されないままネットワークを流れている状態を強調するためなどに用いられる。
POP、FTP、telnetなどが平文でパスワードを送信するプロトコルとして知られている。


秘密暗号鍵(共通鍵暗号)
暗号化と復号に同じ鍵を用いる暗号方式。暗号文の送信者と受信者で同じ鍵を共有する必要があり、暗号文を送受信する前にあらかじめ安全な経路を使って秘密の鍵を共有する必要がある。
対になる2つの鍵を暗号化と復号に使う公開鍵暗号が発明されるまでは、暗号といえば秘密鍵暗号のことであった。


秘密鍵
公開鍵暗号方式で使用される一対の鍵の組のうち、一般に公開されない鍵。


バックトラック法
コンピュータで数学的な問題の解を探索するアルゴリズムの一種で、もっともポピュラーなものの1つ。
ある解を求めるときに、可能性のある手順を順に試していき、その手順では解が求められないと判明した時点で1つ前の状態に戻って別の手順を試す、という手法。
すべての可能性をしらみつぶしに試していく方法に近いが、計算途中で絶対に解が出ないとわかった可能性は最後まで計算せずにその場で諦めて引き返すため、純粋な総当りよりは効率がよい。
解を求めるのにかかる時間はばらつきが大きく一定しないが、もっとも単純で記述しやすい方法であるため、広く用いられている。


ハッシュ関数
与えられた原文から固定長の擬似乱数を生成する演算手法。生成した値は「ハッシュ値」と呼ばれる。不可逆な一方向関数を含むため、ハッシュ値から原文を再現することはできず、また同じハッシュ値を持つ異なるデータを作成することは際めて困難である。
通信の暗号化の補助や、ユーザ認証やデジタル署名などに応用されている。


ハフマン符号化
可逆圧縮の代表的なアルゴリズム。
一定ビットごとに文字列を区切り、区切られた後の文字列を統計的に処理して、出現確率がより高いパターンに対してより短い符号を与える方式。
各パターンの出現数を比較して、最も出現数の低いパターン2つに「0」と「1」の符号を付与し、次の比較においては両者を合算して扱うことにより、一意な情報を維持することを可能にしている。


FIFO(First-In First-Out)
ある場所に格納したデータを、古く格納した順に取り出すようにする方式。
一番新しく格納されたデータが一番最後に取り出される。
キュー(queue)と呼ばれるデータ構造はこの方式でデータを扱う。


キュー(待ち行列)
先に入力したデータが先に出力される特徴をもつ、データ構造の一種。
何かの処理を待たせる際によく使われる構造。


LIFO
ある場所に格納したデータを、新しく格納した順に取り出すようにする方式。
一番古く格納したデータが一番最後に取り出される。
スタック(stack)と呼ばれるデータ構造はこの方式でデータを扱う。


スタック
最後に入力したデータが先に出力されるという特徴をもつ、データ構造の一種。
本を机の上に積み上げるような構造になっており、データを入れるときは新しいデータが一番上に追加され、データを出すときは一番上にある新しいデータが優先して出てくる。
サブルーチンや関数を呼び出す際に、処理中のデータや戻りアドレスなどを一時的に退避する場合に使うことが多い。


情報科学・工学用語辞典 : IT用語辞典


情報エントロピー
情報量の定義指標として情報理論に導入したもの。
情報科学の分野では、このエントロピーを「事象の不確かさ」として考え、ある情報による不確かさの減少分が、その情報の「情報量」であると考える。情報を受け取る前後の不確かさの相対値を「情報エントロピー」という。


LFU(Least Frequently Used)
広さの限られた一時的な保管場所に何を残して何を捨てるか決定するための計算手順(アルゴリズム)の1つ。
キャッシュメモリの管理やOSの仮想記憶(仮想メモリ)システムなどで利用される。
保存されているデータなどの中で一定の期間のうち使用頻度が最も低いものを探し出して破棄し、新しいものに入れ替える方式である。


ウォーターフォールモデル
システムの開発手順を示すモデルの1つ。システム開発モデルとしては古典的なものである。システム全体を一括して管理し、分析・設計・実装・テスト・運用をこの順に行っていく。各工程が完了する際に、前の工程への逆戻りが起こらないよう、綿密なチェックを行なう。


ソート
複数の要素からなるデータの列を、ある特定の規則に従って並べ替えること。整列とも言う。


挿入ソート
もっとも基本的なソートアルゴリズムの1つ。
まず、並んだ要素のうち最初の2つを取り出し比較し、望みの順序に並べる。
次に、3つ目の値を整列した2つと順に比較し、適切な位置に挿入する。4つ目以降も同様にして、整列済みの列の適切な位置に1つずつ挿入していく。
与えられた要素がソート済み状態に近ければ比較的高速だが、要素が逆順に並んでいるととてつもない時間を要する。l
人間が最も簡単に行えるソート方法。


シェルソート
ソートアルゴリズムの1つで、挿入ソートを改良したもの。
要素を数個飛びに拾い集めて挿入ソートをかけ、次第にソートする要素の間隔を詰めていき、最後に単純な挿入ソートで完全に整列される。
大幅に離れた2つの要素を一気に交換することで交換回数を減らし、高速化をはかったアルゴリズムであるが、クイックソートなどに比べると若干速度は落ちる。


選択ソート
もっとも基本的なソートアルゴリズムの1つ。
要素の列を端から順に調べ、一番小さい値を持つ要素を抜き出して最初の要素と交換し、さらに未整列の部分から一番小さい値を持つ要素を抜き出して2番目の要素と交換するという操作を繰り返してソートする。
比較回数はバブルソートと同様だが、要素の数が同じなら交換回数は常に同じという、安定性の高いアルゴリズムである。


クイックソート
データ列を順番に並べ替えるソートアルゴリズムの1つ。データの集合を基準値より大きいものと小さいものとのグループに分け、それぞれのグループの中でも新しい基準値を使って同様の作業を行なう、という手順を再帰的に繰り返す方式。
単純かつ高速なソート方式として、特に要素数の多い集合のソートによく用いられている。


総当り攻撃(ブルートフォース攻撃)
暗号解読手法の1つ。考えられる全ての鍵をリストアップし、片っ端から解読を試みる方式。
暗号文の一部を復号プログラムにしたがって変換し、意味のある文章になるか調べる。
鍵の長さが増えると考えられる鍵のパターンの数は幾何級数的に増大するため、「効率の悪い」攻撃手法である。


ストリーム
ITの分野では連続したデータの流れや、データの送受信や処理を連続的に行なうことなどを意味する。
プログラミングの分野では、データの入出力全般を扱う抽象的なオブジェクトやデータ型を意味する場合が多い。
ネットワーク通信の分野では、データを送受信する際にデータ全体の受信完了を待たずに受信したデータから順番に処理を行なう送受信方式(ストリーミング)や、そのように扱うデータ列のことをストリームという。


真理値
論理学で、ある命題が真(true)であるか偽(false)であるかを示す値のこと。転じて、論理回路やプログラミング言語において、条件式などが真であるか偽であるかを表す値やデータ型のこと。
ブール値。


参照渡し
プログラム中で関数やサブルーチンなどに引数を渡すときに、変数への参照(メモリ中のアドレス)を渡す方式。関数などの中で値を変更すると元の変数も同じように変更される。
これに対し、変数の値のみを渡し、渡された関数などの中で値を変更しても呼び出し元の変数の内容が変わらない方式を「値渡し」という。


コンテキスト
「文脈」という意味の英語で、様々な用例があるが、特に、実行中のプログラムが処理内容を選択する際の判断の材料となる、プログラムの内部状態や置かれた状況、与えられた条件などを指すことが多い。


グローバル変数
プログラムの中のもっとも外側のブロックで宣言された変数で、すべてのブロックで有効なもの。大域変数とも呼ばれる。プログラム全体に対して定義される変数で、プログラムのどこからでも参照・更新することができる。


逆ポーランド記法
コンピュータで数式を扱う際に用いる記法の1つで、演算子を被演算子のうしろに置く記法。
通常われわれが使う書式(中置記法)で「a+b」と書く方式を、逆ポーランド記法では「ab+」のように記す。括弧で処理の順序を指定しなくても一意に順序を決めることができ、プログラムで自動処理するときに扱いやすい。



オーバーフロー
コンピュータが数値演算を行った結果が、扱える数値の最大値を超えること


オーバーライド
オブジェクト指向プログラミング(OOP)で、スーバークラスで定義されたメソッドや関数を、そのクラスを継承したサブクラスで独自に定義しなおして上書きすること。サブクラスで機能を追加する必要がある場合などに利用する。引数の型や数を元の関数などに揃えなければならないなどの製薬を課している言語もある。


インスタンス
オブジェクト指向プログラミングで、クラスを基にした実際の値としてのデータのこと。クラスと対比して用いられることが多く、クラスを「型」、インスタンスを「実体」として説明されることもある。
「オブジェクト」とほぼ同義語のように用いられることが多いが、実際にメモリ上に配置されたデータの集合という意味合いが強く、データの実体をより具体的・直接的に捕らえた用語。


暗号化
インターネットなどのネットワークを通じて文書や画像などのデジタルデータをやり取りする際に、通信途中で第3者に盗み見られたり改ざんされたりされないよう、決まった規則に従ってデータを変換すること。暗号化、復号には暗号表に当たる「鍵」を使う。


暗号鍵
データの暗号化を行なう際に、暗号方式の定めた計算手順に与えるパラメータのこと。


アロケーション
割り当て、配当などの意味を持つ英単語。


多重継承
オブジェクト指向プログラミングで、あるクラスを複数のクラスの性質を受け継ぐ形で定義すること。



もう方向性がわからない