3月31日(火)

予定:

英語リーディング(1時間)→

単語→完了

アルゴリズム:&3、&4 →&3まで完成

pythonサイト:<面向对象高级编程> →未

論理回路:P68ページまで →40ページ(予定)

学校とコンタクトを取る → 進行中。向こうに質問送ったところ

 

今日一日の感想

仕事に邪魔されず、外出等もなく、時間的に集中できた一日でした。

単語、リーディング、アルゴリズム やりましたが、

全体的に、頭に一杯詰め込まれた感があり、復習、振り返りが必要。

以下、簡単に振り返り(アルゴリズムは文章の最後にする):

1、英語: 間違った問題を振り返りする必要がる。

      適宜英語の記事を読んでみてよいかも。

2、朝の時間を有効活用。英語は夜にしても良い。

3、アルゴリズムの計算量の出し方が分からない。(統計の知識がいるっぽい)

 

明日の予定:

アルゴリズム &4

pythonサイト:<面向对象高级编程> 

英語:リスニング、単語

論理回路:P80

学校とコンタクトを取る

 

 

アルゴリズム: 

  2文探索木: 左の子>親、親<右の子

  挿入時の動作: 根から辿っていき、適切な場所に見つけたらそこへノードを追加する。

  削除時の動作: 根から対象ノードを見つけて、削除する。削除された後、空いた穴には、元々子がなければNULLとする/子が1個のみならその子のNODEを持ってくる/左右両方に子がいれば、右側の最小の子を持ってくる。

  プログラム実装時の注意点: 削除関数はNodeとobjectを受取、objectを削除した後の(形整理し直した後の)nodeを返す。また、内部で再帰的に呼び出しはこの性質を利用しする。node.left = delete(node.left,object)のように書く。

  

  平衡木: 要素はすべて葉に格納され、途中ノードは必ず2,3個の子を持つ。

       途中ノードには、2個目と3個目の子の子孫の内の最小値を格納する。

       追加時: 根から辿って行って、挿入する。挿入後、4つ要素になったら、隣の子と二人で独立して、親の兄弟を新しくできる。

       削除時:根から辿って削除する。一人子になったら、隣に3人子いればそこから一人借りて終わる。両隣に二人子しかいなかったら、そこへ移す。ネノードが一人子になったら、根ノードを削除し、その一人子を新しい根にする。

 

 ハッシュ: 衝突が起こりうる。

    →チェイン法: 同じハッシュ値を持つ要素をリストにつなげる。バケットに、リストへのポイントを格納する

    →開番地法:バケットに要素をそのまま格納する。衝突したら、再ハッシュする。削除したら、Deletedマークを残す。探索でDeletedにあったら、再ハッシュする。追加でDeletedにあったら、そのまま入れる。

 

 集合群: あまり理解できなかった

 

 クイックソート:最初2個の値の内、大きい方の値を境界にして、それ以上とそれより小さい の2グループに分ける。←再帰的呼び出しをする。←くっつける。

        配列に適用する方法もある:

          ・partitionを導入する。partition([],i,j,p)で、対象リスト内で、p値より小さい、大きいに分けて、swapする。

 マージソート: 対象列を前半、後半に機械的に分割し、それぞれを再帰呼び出しに渡してソートする。ファイルに対するマージソートはよくわからなかった。