[アルゴリズムとデータ構造　試験対策]の変更点 - 06t's wiki

「アルゴリズムとデータ構造　試験対策」(2008/02/14 (木) 10:38:23) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

一応、途中までなんで恐縮なんですが、今日のアルゴリズムとデータ構造の持込用のカンペができたのであげときます。完成してないんで、明日の朝残りはあげる予定です。前日までに完成してなくて本当にごめんなさい。　如月オーダーについてある式（まずnについての式）をオーダーにする場合、n→∞にしたとき最も早く無限に近づくものだけ残す。例n³+an²+bn　（a,bは自然数）→ O(n³) となる。また、オーダー同士の足し算も同様にn→∞にしたとき最も早く無限に近づくものだけ残す。例 O(n³)+O(n²)　→ O(n³) さらに、掛け算のときは、中身の掛け算をする。例 O(n³)*O(n²) → O(n⁵) ヒープについてヒープとは、わかりやすく言うと次の二つの定義から成り立つ。１　同じ段なら、葉は常に左から詰められていき、それより上の段の要素は親となり最大で子を二つ持つ。２　親は常に子より小さい。ヒープに新しい要素を挿入するときは次のようになる。定義１を満たすために、一番下の段の一番右に新しい要素をいれる。次に、ヒープの定義２を満たすまで親と子の交換を繰り返す。例　③ 　⑥　④ に５を挿入すると、まず　　③ 　⑥　④ ⑤ となり、ここで定義１を満たす。次に定義２を満たすための交換が行われる。　　③ 　⑤　④ ⑥ ここで、挿入が終了する。さらに　２を挿入すると　　　　③　　　　　　　　　　③　　　　　　　　　　② 　　⑤　　　④　　→　　　②　　　④　　→　　　③　　　④ ⑥　②　　　　　　　　⑥　⑤　　　　　　　　⑥　⑤ というふうに、木は変化していく。また、DELETEMIN（最小値の削除）をする場合は次のようになる。まず、一番下の段の一番右の要素を根（一番上の要素）に移す（上書きともいえる）。次に、挿入のときと同じように、定義２を満たすまで親と子の交換を繰り返す。ただし、このとき交換する子はもうひとつの子と比べて小さいほうである。もちろん、子がひとつしかないときは、その子と交換する。例　　　② 　　③　　　④ 　⑥　⑤　⑦ のヒープにDERETEMINNを行うと、まず、　　　　⑦ 　　③　　　④ 　⑥　⑤ となり、次に定義２を満たすための交換を行う。　　　　③ 　　⑦　　　④ 　⑥　⑤ このとき、③と交換したのは④よりも小さいからである。さらに　　　　③ 　　⑤　　　④ 　⑥　⑦ となって、操作は終了する。問題として、配列の状態を答えるような問題が出た場合はまず、木を作る。例　a[0] =10, a[1] =9, a[2] =8, a[3] =7, a[4] =6, a[5] =5, a[6] =4, a[7] =3, a[8] =2, a[9] =1 である場合、木にすると　　　　　　　　 ⑩a[0] 　　　　 ⑨a[1]　　　　　 ⑧a[2] 　　 ⑦a[3] ⑥a[4]　 ⑤a[5]　　④a[6] ③a[7]　 ②a[8]　①a[9] である。あとは、書いてあるプログラムどおりに交換を行えばいい。双方向リストや待ち行列などのプログラムの穴埋めについては、ネットの先生の解答集を参照したほうが早いと思うので説明は割愛。二分探索木について二分探索木とは、わかりやすくいうと次のただひとつの定義から成り立つ。１　ある要素ｘからみてその左の部分は必ずｘより小さく、右の部分は必ず大きい。このとき、部分というのは木にしたときの、子を根とした木のことである。例　　　　⑦ 　　　③　　　⑪ 　　①　⑤　⑨　⑬ のとき、⑦からみた左の部分とは、　　　③ 　　①　⑤ のことであり、右の部分とは　　　⑪ 　　⑨　⑬ のことである。別の言い方をすれば、常に親は左の子と右の子の間の数であり、子どうしでは常に左のほうが小さいともいえる。挿入する場合、ヒープと違い交換は行われない。例6,8,3,7,4,2,1,5を順番に入れる場合以下のようになる　　⑥　　　　⑥　　　　　⑥　　　　　　⑥　　　　　　　　　⑥ 　　　　→　　　⑧　→　③　⑧　→　③　　　⑧　→　　　③　　　⑧　→ 　　　　　　　　　　　　　　　　　　　　　⑦　　　　　　　④　⑦ 　　　⑥　　　　　　　　　　　⑥　　　　　　　　　　　　　　⑥ 　③　　　⑧　→　　　③　　　　　　　⑧　→　　　　③　　　　　　　⑧ ②　④　⑦　　　　②　　　④　　　⑦　　　　　　②　　　④　　　⑦ 　　　　　　　　①　　　　　　　　　　　　　　①　　　　　⑤ また、削除する場合は少し複雑で、 ① 削除する要素ｘが子をもっていなければｘを削除する ② 子を一つ持っていればｘを削除した後子をｘの位置に移動する。 ③ 最後に子を二つ持っていた場合右部分木の最小要素（もしくは左部分木の最大要素）ｙを見つけ、ｙをｘの位置に移動する（上書きともいえる）。その後、③の手順をｙをｘと見て同じことを、ｙが子を持っていないか、ｙが子をひとつしか持ってないという状況になるまで繰り返し、最後に前に述べた①もしくは②の手順を使って、終了となる。例上の二分探索木から３と６をこの順番で削除する場合　　　　　　　　⑥　　　　　　　　　　　　　　⑥　　　　　　　　　　　⑥ 　　　③x　　　　　　　⑧　→　　　　④　　　　　　　　⑧　→　　④　　　　　⑧ 　②　　　④y　　　⑦　　　　　　②　　　y 　　　　　⑦　　　　② ⑤　　⑦ ①　　　　　⑤　　　　　　　　　①　　　　　⑤　　　　　　　　① となり、まず６が削除され、次に３を削除する。　　　　　　　　⑥x 　　　　　　　　　　　　　⑦ 　　　④　　　　　　　　⑧　→ ④　　　　　　　　⑧ 　②　　　⑤　　　　⑦y 　　　　 ② ①　　　　　　　　　　　　　　　① となる。左部分の最小要素を使った方法も根本的にはこれと同じなので割愛。ハッシュ法についてハッシュとはあるデータにたいしてランダムに数値を出す式（ハッシュ関数）をつかってだされた、数値のことである。ハッシュ法とは、あるデータを配列に格納するときに、そのハッシュの値の場所を使う方法である。たとえば、B=8、ハッシュ関数をh(x)=x%B(ｘをBで割った余り)としたとき、１１というデータを格納すると、１１％８＝３でハッシュは３と配列をAとすれば、A[3]に１１というデータは格納されるということである。また、内部と外部の違いはハッシュ値が重なってしまった場合の処理の仕方が違う。内部のほうは、ハッシュ値が重なった場合ハッシュの値の計算を元の値をずらしたりしてやり直し、あいている配列のハッシュ値がでるまでそれを繰り返し、あいてる配列の値がでたらそこに格納する。つまり、配列の箱の中身は常にひとつである。外部のほうは、ハッシュ値が重なった場合、ポインタによって連結して記憶して格納する。つまり、３という配列の箱の中に複数のデータが入ってる場合も存在する。

一応、完成したので、今日のアルゴリズムとデータ構造の持込用のカンペができたのであげときます。遅れてしまって本当にごめんなさい。　如月オーダーについてある式（まずnについての式）をオーダーにする場合、n→∞にしたとき最も早く無限に近づくものだけ残す。例n³+an²+bn　（a,bは自然数）→ O(n³) となる。また、オーダー同士の足し算も同様にn→∞にしたとき最も早く無限に近づくものだけ残す。例 O(n³)+O(n²)　→ O(n³) さらに、掛け算のときは、中身の掛け算をする。例 O(n³)*O(n²) → O(n⁵) ヒープについてヒープとは、わかりやすく言うと次の二つの定義から成り立つ。１　同じ段なら、葉は常に左から詰められていき、それより上の段の要素は親となり最大で子を二つ持つ。２　親は常に子より小さい。ヒープに新しい要素を挿入するときは次のようになる。定義１を満たすために、一番下の段の一番右に新しい要素をいれる。次に、ヒープの定義２を満たすまで親と子の交換を繰り返す。例　③ 　⑥　④ に５を挿入すると、まず　　③ 　⑥　④ ⑤ となり、ここで定義１を満たす。次に定義２を満たすための交換が行われる。　　③ 　⑤　④ ⑥ ここで、挿入が終了する。さらに　２を挿入すると　　　　③　　　　　　　　　　③　　　　　　　　　　② 　　⑤　　　④　　→　　　②　　　④　　→　　　③　　　④ ⑥　②　　　　　　　　⑥　⑤　　　　　　　　⑥　⑤ というふうに、木は変化していく。また、DELETEMIN（最小値の削除）をする場合は次のようになる。まず、一番下の段の一番右の要素を根（一番上の要素）に移す（上書きともいえる）。次に、挿入のときと同じように、定義２を満たすまで親と子の交換を繰り返す。ただし、このとき交換する子はもうひとつの子と比べて小さいほうである。もちろん、子がひとつしかないときは、その子と交換する。例　　　② 　　③　　　④ 　⑥　⑤　⑦ のヒープにDERETEMINNを行うと、まず、　　　　⑦ 　　③　　　④ 　⑥　⑤ となり、次に定義２を満たすための交換を行う。　　　　③ 　　⑦　　　④ 　⑥　⑤ このとき、③と交換したのは④よりも小さいからである。さらに　　　　③ 　　⑤　　　④ 　⑥　⑦ となって、操作は終了する。問題として、配列の状態を答えるような問題が出た場合はまず、木を作る。例　a[0] =10, a[1] =9, a[2] =8, a[3] =7, a[4] =6, a[5] =5, a[6] =4, a[7] =3, a[8] =2, a[9] =1 である場合、木にすると　　　　　　　　 ⑩a[0] 　　　　 ⑨a[1]　　　　　 ⑧a[2] 　　 ⑦a[3] ⑥a[4]　 ⑤a[5]　　④a[6] ③a[7]　 ②a[8]　①a[9] である。あとは、書いてあるプログラムどおりに交換を行えばいい。双方向リストや待ち行列などのプログラムの穴埋めについては、ネットの先生の解答集を参照したほうが早いと思うので説明は割愛。二分探索木について二分探索木とは、わかりやすくいうと次のただひとつの定義から成り立つ。１　ある要素ｘからみてその左の部分は必ずｘより小さく、右の部分は必ず大きい。このとき、部分というのは木にしたときの、子を根とした木のことである。例　　　　⑦ 　　　③　　　⑪ 　　①　⑤　⑨　⑬ のとき、⑦からみた左の部分とは、　　　③ 　　①　⑤ のことであり、右の部分とは　　　⑪ 　　⑨　⑬ のことである。別の言い方をすれば、常に親は左の子と右の子の間の数であり、子どうしでは常に左のほうが小さいともいえる。挿入する場合、ヒープと違い交換は行われない。例6,8,3,7,4,2,1,5を順番に入れる場合以下のようになる　　⑥　　　　⑥　　　　　⑥　　　　　　⑥　　　　　　　　　⑥ 　　　　→　　　⑧　→　③　⑧　→　③　　　⑧　→　　　③　　　⑧　→ 　　　　　　　　　　　　　　　　　　　　　⑦　　　　　　　④　⑦ 　　　⑥　　　　　　　　　　　⑥　　　　　　　　　　　　　　⑥ 　③　　　⑧　→　　　③　　　　　　　⑧　→　　　　③　　　　　　　⑧ ②　④　⑦　　　　②　　　④　　　⑦　　　　　　②　　　④　　　⑦ 　　　　　　　　①　　　　　　　　　　　　　　①　　　　　⑤ また、削除する場合は少し複雑で、 ① 削除する要素ｘが子をもっていなければｘを削除する ② 子を一つ持っていればｘを削除した後子をｘの位置に移動する。 ③ 最後に子を二つ持っていた場合右部分木の最小要素（もしくは左部分木の最大要素）ｙを見つけ、ｙをｘの位置に移動する（上書きともいえる）。その後、③の手順をｙをｘと見て同じことを、ｙが子を持っていないか、ｙが子をひとつしか持ってないという状況になるまで繰り返し、最後に前に述べた①もしくは②の手順を使って、終了となる。例上の二分探索木から３と６をこの順番で削除する場合　　　　　　　　⑥　　　　　　　　　　　　　　⑥　　　　　　　　　　　⑥ 　　　③x　　　　　　　⑧　→　　　　④　　　　　　　　⑧　→　　④　　　　　⑧ 　②　　　④y　　　⑦　　　　　　②　　　y 　　　　　⑦　　　　② ⑤　　⑦ ①　　　　　⑤　　　　　　　　　①　　　　　⑤　　　　　　　　① となり、まず６が削除され、次に３を削除する。　　　　　　　　⑥x 　　　　　　　　　　　　　⑦ 　　　④　　　　　　　　⑧　→ ④　　　　　　　　⑧ 　②　　　⑤　　　　⑦y 　　　　 ② ①　　　　　　　　　　　　　　　① となる。左部分の最小要素を使った方法も根本的にはこれと同じなので割愛。ハッシュ法についてハッシュとはあるデータにたいしてランダムに数値を出す式（ハッシュ関数）をつかってだされた、数値のことである。ハッシュ法とは、あるデータを配列に格納するときに、そのハッシュの値の場所を使う方法である。たとえば、B=8、ハッシュ関数をh(x)=x%B(ｘをBで割った余り)としたとき、１１というデータを格納すると、１１％８＝３でハッシュは３と配列をAとすれば、A[3]に１１というデータは格納されるということである。また、内部と外部の違いはハッシュ値が重なってしまった場合の処理の仕方が違う。内部のほうは、ハッシュ値が重なった場合ハッシュの値の計算を元の値をずらしたりしてやり直し、あいている配列のハッシュ値がでるまでそれを繰り返し、あいてる配列の値がでたらそこに格納する。つまり、配列の箱の中身は常にひとつである。外部のほうは、ハッシュ値が重なった場合、ポインタによって連結して記憶して格納する。つまり、３という配列の箱の中に複数のデータが入ってる場合も存在する。例内部ハッシュ法で、B=8、ハッシュ関数h(x)=x%B、重なった場合ハッシュ値=(ハッシュ値+1)%B、の条件で、11,5,13,9,3,12,6を左から順に入れると、以下のようにハッシュ表は埋まる。まず、それぞれのハッシュ値を求めると、 11のハッシュ値11%B=3, ５のハッシュ値5%B=5, 13のハッシュ値13%B=5 ここで重なったのでもう一度計算する。 (5+1)%B=6, 重ならなかったのでこれが13のハッシュ値となる。 9のハッシュ値9%B=1, 3のハッシュ値3%B=3,(3+1)%B=4, 12のハッシュ値12%B=4,(4+1)%B=5,(5+1)%B=6,(6+1)%B=7, 6のハッシュ値6%B=6,(6+1)%B=7,(7+1)%B=0, となる。よって、ハッシュ表の配列は、以下のようになる。 A[0]=8, A[１]=9, A[2]=なし, A[3]=11, A[4]=3, A[5]=5, A[6]=13, A[7]=12 例外部ハッシュ法で、B=8、ハッシュ関数h(x)=x%Bの条件で、11,5,13,9,3,12,6,21を左から順に入れると、以下のようにハッシュ表は埋まる。まず、それぞれのハッシュ値を求めると、 11のハッシュ値 11%B=3, 5のハッシュ値 5%B=5, 13のハッシュ値 13%B=5, 9のハッシュ値 9%B=1, 3のハッシュ値 3%B=3, 12のハッシュ値 12%B=4, 6のハッシュ値 6%B=6, 21のハッシュ値 21%B=5 となる。よってハッシュ表の配列は以下のように埋まる。 A[1]=9, A[3]=11 3, A[4]=12, A[5]=5 13 21, A[6]=6 クイックソートについてクイックソートとは、ある配列を整列する際に、軸となる要素をひとつ決め、それを軸として配列を二つのグループに分け、その分けたグループをさらに軸となる要素をひとつ決めて分けるといった作業を分割できなくなるまで繰り返し、整列させるものである。分割できないときというのは、そのわけたグループの配列の中身が全て同じか、要素がひとつのときだけである。例6,4,8,3,1,5,7,2の８個の整数をクイックソートを用いて整列させるとクイックソートの呼び出しは以下のように推移する。プログラムはプリントもしくは過去問参照。 quicksort([6,4,8,3,1,5,7,2],0,7) 軸は6→ quicksort([2,4,5,3,1,8,7,6],0,4) 軸は4→ quicksort([2,1,3,5,4,8,7,6],0,2) 軸は2→ quicksort([1,2,3,5,4,8,7,6],0,0) 軸は-1→ quicksort([1,2,3,5,4,8,7,6],1,7) 軸は3→ quicksort([1,2,3,5,4,8,7,6],1,1) 軸は-1→ quicksort([1,2,3,5,4,8,7,6],2,7) 軸は5→ quicksort([1,2,3,4,5,8,7,6],2,3) 軸は3→ quicksort([1,2,3,4,5,8,7,6],2,2) 軸は-1→ quicksort([1,2,3,4,5,8,7,6],3,7) 軸は5→ quicksort([1,2,3,4,5,8,7,6],3,3) 軸は-1→ quicksort([1,2,3,4,5,8,7,6],4,7) 軸は8→ quicksort([1,2,3,4,5,6,7,8],4,6) 軸は6→ quicksort([1,2,3,4,5,6,7,8],4,4) 軸は-1→ quicksort([1,2,3,4,5,6,7,8],5,7) 軸は7→ quicksort([1,2,3,4,5,6,7,8],5,5) 軸は-1→ quicksort([1,2,3,4,5,6,7,8],6,7) 軸は8→ quicksort([1,2,3,4,5,6,7,8],6,6) 軸は-1→ quicksort([1,2,3,4,5,6,7,8],7,7) 軸は-1 となる。軸は次のソートに使うものを書いた。-1と書かれているものは分割できない呼び出しをした場合のものである。

表示オプション

横に並べて表示：

変化行の前後のみ表示：

06t's wiki