○スケジューリングアルゴリズム
実行可能状態にあるプロセスの内、どのプロセスを実行するか
・到着順方式
先に起動したプロセスを先に実行する方法
先に到着したプロセスがCPUを長く利用するプロセスの場合、システムの応答性が低くなる
・処理時間方式
プロセスが必要とする処理時間の短い順に実行する
・ラウンドロビン方式
処理を一定時間行い、時間切れになったら実行可能状態に戻して列の最後に
・優先度順方式
プロセスに優先度をつけ、優先度の高いプロセスから順に実行する
優先度が低いプロセスがなかなか実行されない
・多重待ち行列方式
ラウンドロビン方式に優先度順方式を取り入れたもの
最初は高い優先順位と短いCPU時間を割り当て、その後は優先度を低くしてCPU時間を長くしていく
○排他制御
・デッドロック
複数のプロセスがお互いにロック解除を待ち、先に進まない状態
・セフォマ
排他制御を実行するための変数
0ならロック状態、1ならロック取得可能
・P操作
セフォマが0より大きければ1減らしてロック取得。0なら待機
・V操作
セフォマを1増やし、ロック解除
○データ構造
・リスト
・LIFO（スタック）
逆ポーランド記法で使う
・FIFO
○木
・２分木
親の持つ子要素が２つ以下で左右の子を区別する木
・２分探索木
各接点が持つデータについて、『左部分木の値＜親＜右部分木の値』が成り立つ』木
親が削除された場合、左部分木の最大値か右部分木の最小値を親にする
・ヒープ
各接点について、『親≦子』または『親≧子』の関係が成り立っている２分木
左右の子の大小は問わない
・AVL木
各接点について左部分木と右部分木の高さの差が±１までに収まる２分探索木
挿入や削除の後に最適化を行う必要あり
・Ｂ木
子の最大数がm、最少数がm/2となるタ分木
データは葉に格納
○探索
・線形探索法
前から順にデータをデータを調べていく。データ右端に番兵と呼ばれる目的のデータを入れて終了判定
O(n)
・２分探索法
ソート済みのデータに対し、真ん中の値を調べ、調べる範囲を半分にしていく
O(log n)
・ハッシュ表
データをハッシュ関数（データを配列の長さで割った余り）で求めた場所に格納する
値によって衝突が起こる。衝突時の処理として、オープンアドレス法とチェイン法がある
・オープンアドレス法
衝突が発生した時、別の関数でサイド計算し、そのアドレスに格納する
・チェイン法
衝突が発生した時、その場所にリストを作り、リストに格納する
・ハッシュ法
O(1)で追加、削除、嘆息を行えるが、衝突が多いとこの限りではない
○ソート
・選択整列法
先頭から順に最小値を探し、先頭を交換
比較回数O(n^2)
・交換法（バブルソート）
隣り合わせになっているデータの大小を正していく
比較回数O(n^2)
・挿入整列法
整列部分にデータを挿入する方法。前から順位整列していって、次のデータをその中に挿入する
比較回数O(n^2)
・シェルソート
挿入整列法を改良したもの
データをいくつかの部分列に分割し、分割したデータに対し挿入整列法を行う
・ヒープソート
ヒープ木を作成し、根の値を最大値としれ取り出す、残りを再構築し、これを繰り返す
計算量は、O(n log n)
・クイックソート
基準となる値を決め、それより大きいか小さいかで分割し、この分割を最後まで繰り返す分割統治法
計算量はO(n log n)
最も高速なソートだが、データが整列済みだとオワッテル
・マージソート
データを最後まで分割し、併合しながらソートしていく分割統治法
大量のメモリが必要
計算量は(n log n)
・安定な整列法
同じ値が含まれている場合、ソート前とソート後でその順序が保たれているものを安定という
安定：バブルソート、納入整列法、シェルソート、マージソート
不安定：ヒープソート、クイックソート
○文字列探索
・力任せ法
前から順に比較し、違ったら比較する位置を１つずらす
・ＫＭＰ法
前から順に比較し、違ったら、そこから比較しなおす
・ＢＭ法
見つけたい文字列の右から比較する。違ったら見つけたい文字列分ずらして比較
実行可能状態にあるプロセスの内、どのプロセスを実行するか
・到着順方式
先に起動したプロセスを先に実行する方法
先に到着したプロセスがCPUを長く利用するプロセスの場合、システムの応答性が低くなる
・処理時間方式
プロセスが必要とする処理時間の短い順に実行する
・ラウンドロビン方式
処理を一定時間行い、時間切れになったら実行可能状態に戻して列の最後に
・優先度順方式
プロセスに優先度をつけ、優先度の高いプロセスから順に実行する
優先度が低いプロセスがなかなか実行されない
・多重待ち行列方式
ラウンドロビン方式に優先度順方式を取り入れたもの
最初は高い優先順位と短いCPU時間を割り当て、その後は優先度を低くしてCPU時間を長くしていく
○排他制御
・デッドロック
複数のプロセスがお互いにロック解除を待ち、先に進まない状態
・セフォマ
排他制御を実行するための変数
0ならロック状態、1ならロック取得可能
・P操作
セフォマが0より大きければ1減らしてロック取得。0なら待機
・V操作
セフォマを1増やし、ロック解除
○データ構造
・リスト
・LIFO（スタック）
逆ポーランド記法で使う
・FIFO
○木
・２分木
親の持つ子要素が２つ以下で左右の子を区別する木
・２分探索木
各接点が持つデータについて、『左部分木の値＜親＜右部分木の値』が成り立つ』木
親が削除された場合、左部分木の最大値か右部分木の最小値を親にする
・ヒープ
各接点について、『親≦子』または『親≧子』の関係が成り立っている２分木
左右の子の大小は問わない
・AVL木
各接点について左部分木と右部分木の高さの差が±１までに収まる２分探索木
挿入や削除の後に最適化を行う必要あり
・Ｂ木
子の最大数がm、最少数がm/2となるタ分木
データは葉に格納
○探索
・線形探索法
前から順にデータをデータを調べていく。データ右端に番兵と呼ばれる目的のデータを入れて終了判定
O(n)
・２分探索法
ソート済みのデータに対し、真ん中の値を調べ、調べる範囲を半分にしていく
O(log n)
・ハッシュ表
データをハッシュ関数（データを配列の長さで割った余り）で求めた場所に格納する
値によって衝突が起こる。衝突時の処理として、オープンアドレス法とチェイン法がある
・オープンアドレス法
衝突が発生した時、別の関数でサイド計算し、そのアドレスに格納する
・チェイン法
衝突が発生した時、その場所にリストを作り、リストに格納する
・ハッシュ法
O(1)で追加、削除、嘆息を行えるが、衝突が多いとこの限りではない
○ソート
・選択整列法
先頭から順に最小値を探し、先頭を交換
比較回数O(n^2)
・交換法（バブルソート）
隣り合わせになっているデータの大小を正していく
比較回数O(n^2)
・挿入整列法
整列部分にデータを挿入する方法。前から順位整列していって、次のデータをその中に挿入する
比較回数O(n^2)
・シェルソート
挿入整列法を改良したもの
データをいくつかの部分列に分割し、分割したデータに対し挿入整列法を行う
・ヒープソート
ヒープ木を作成し、根の値を最大値としれ取り出す、残りを再構築し、これを繰り返す
計算量は、O(n log n)
・クイックソート
基準となる値を決め、それより大きいか小さいかで分割し、この分割を最後まで繰り返す分割統治法
計算量はO(n log n)
最も高速なソートだが、データが整列済みだとオワッテル
・マージソート
データを最後まで分割し、併合しながらソートしていく分割統治法
大量のメモリが必要
計算量は(n log n)
・安定な整列法
同じ値が含まれている場合、ソート前とソート後でその順序が保たれているものを安定という
安定：バブルソート、納入整列法、シェルソート、マージソート
不安定：ヒープソート、クイックソート
○文字列探索
・力任せ法
前から順に比較し、違ったら比較する位置を１つずらす
・ＫＭＰ法
前から順に比較し、違ったら、そこから比較しなおす
・ＢＭ法
見つけたい文字列の右から比較する。違ったら見つけたい文字列分ずらして比較
コメントする