英語の勉強にMITの授業でも Lec 1 | MIT 6.046J / 18.410J Introduction to Algorithms

English

アルゴリズムの授業をダラダラ聞いてみる。
字幕付いてるので聞き取れなくても安心。


  • 最初の方は授業の進め方。
    • 飛ばしていいと思うが、耳慣らし。
  • パフォーマンスより重要なことは？
    • ひみつ
  • sortingのお話。
    • 定番ネタ。
    • わかりやす！！
  • Insertion sort 挿入ソート。
  • 段々本題のanalysisの方へ。
    • 早速深い底へ降りた。流石MITデス。
  • BIG IDEA!
    • 数学的に落としこむ。
    • 数学は時間を無視出来るのに、計算量って意外と矛盾してる側面がある気がする。for what?
  • この辺のさわり。asymptotic notication→Big O notation - Wikipedia
  • merge sort
    • シンプル！！
    • 半分に分けて、一つのリストにまとめていく。
    • 再帰をanalysis
    • この辺思い出した。ヒープソート - ボクノス
    • Haskellの実装がオモロイな。マージソート - Wikipedia 全部分割された状態から始めれば、リストを半分にする手間がイラナイ。なるほど！！
    • 以下考察
    • 計算量は、T(n) = 分割O(T(n)x2) + 結合にO(n)、葉がO(1)。再帰。
      • 正確に計算量を求めるとn * log_2(n) + n回。
      • リストの結合にかかるコストは、どのレベルでも変わらないので、横列はn回。
      • 葉の部分を除いた高さは、n = 2^h。h = log_2(n)。
      • 葉の部分は含まれてないので+n回。
      • 漸化式の一般項を求めるとかやった気がする。スキル不足を感じました。
    • 次回が楽しみ。

単語

忘れてたけど英語の勉強ね。OALD,LDOCE,genius辺りから。

assumption n.
a belief or feeling that sth is true or that sth will happen, although there is no proof 当然のことと考えること
bogus adj.
pretending to be real or genuine いんちきの
asymptote n.
a straight line approached by a given curve as one of the variables in the equation of the curve approaches infinity. 漸近線 asymptoticは形
moderately adv.
to an average extent; fairly but not very 多くもなく、少なくもなく。
sloppy adj.
that shows a lack of care, thought or effort

雑感

  • 質問ドリブンな授業って感じ。たぶん教授自身も成長する。
  • プログラマの生産性もこんな感じ。
    • 追いつけない相手には一生・・・
  • MITの授業って考え方を教えてるんだなぁ。
  • 今までやってきたことが生きた動画だなぁ。数学、アルゴリズム、英語。感動のコラボレーションだ。無駄なことなんて一つもない。

まとめ

教えてる内容は普通でしたが、アプローチによってこんなに授業が変わるのかと感動しました。I was moved!