英語の勉強にMITの授業でも Lec 3 | MIT 6.046J / 18.410J Introduction to Algorithms
ダラダラ英語の勉強を続けましょう。本末転倒って奴です←自覚アリ
Divide and Conquer
- 分割征服？ by forceだから統治は政治的意訳？
- 語源は英国らしい。→分割統治 - Wikipedia
- 知ってはならない事だったかも・・・
- とにかく本題へｗ
- →Divide and conquer algorithm - Wikipedia 予習のため音読した。
- 本当は3 steps, Divide Conquer Combine
- Marge sort
- 前回の講義を含めて復習。
- Binary search
- Powering a number
- 分割統治しながら、メモ化すると早そう。
- 偶数を考慮しないとな。
- メモ化の話は無いよ。そらそうか。
- Fibonacci numbers
- 趣味嗜好が完全一致ｗ
- ナイーブな実装はΩ(φ^n)
- メモ化するとΘ(n)だと思った。一般項からΘ(1)と行きたい所だが正確ではない。√5は展開する必要があるのでΘ(n)より早くはならない。
- 数学ガールを読むぞぉ 6 - フィボナッチ数列の一般項 - ボクノス
- 数学ガールを読むぞぉ 7 - フィボナッチ数列の一般項(2) - ボクノス
- Bottom up algorithm
- おぉっと早とちり。上の説明。
- そしてマトリックス・・・苦手だ。激しく苦手。
- 手計算で求まる事は確認。Powering numberと同じ方式。偶数、奇数を考慮すること。
- で、Θ(log n)。不思議だ。証明してないからよーわからんけどスゲー。←いつかやります。
- なんとなくわかったかな・・・。
- Matrix multiplication
- 手計算でオーダーは出した。Θ(n^3)
- Strassen algorithm
- この辺のお話→Strassen algorithm - Wikipedia, the free encyclopedia
- 2x2だと8→7と微妙な改善だが、人類にとってはとんでもなく有用な改善。
- magic！なのだが、手計算なら採用しないわｗ
- ここらへんはCPUかGPUにお任せでｗ
- VLSI layout
- See U later!
単語
今日はムズイ単語もなくすらすら進みそう。
- conquer v
- to take control of a country or city and its people by force 征服
- polynomial n
- an statement in algebra that contains several different numbers and signs which are equal to a specific amount 多項式
- induction n
- a method of discovering general rules and principles from particular facts and examples 帰納法
- pseudo- 接頭
- false or pretended 偽の〜
まとめ＆雑感
- 1時間の講義内容が濃すぎる。
- フィボナッチは更に深かった。新たな発見をまた一つしたので、英語以外にも役立った。
- やっぱりMITの授業は面白い！！
