アルゴリズムイントロダクション:１日目

最近ようやく涼しくなってきましたね。最近ブログを投稿できてなかったのは、大体微積のせいです。決してサボってたわけじゃないからね！

やった本

アルゴリズムイントロダクション 第3版 第1巻: 基礎・ソート・データ構造・数学 (世界標準MIT教科書)

やったこと

• Ⅰ基礎

  • 序論 全体の流れとアルゴリズムについて語ってる。語り口調がすき。

  • 1 計算におけるアルゴリズムの役割

    • 1.1 アルゴリズム

      そもそもアルゴリズムとは何なのか、そしてどのようなところでどのような手法が使われるかが明確に書いてある。私のような、根本が知りたい人にはとても興味深い内容でした。

    • 1.2 科学技術としてのアルゴリズム

      適切なアルゴリズムを使うことによって効率化が図れるってお話。適当に全探索してればいいってもんじゃない。

  • 2 さあ、始めよう
    ソーティング問題を解く挿入アルゴリズムの検討と、アルゴリズム設計に対する分割統治手法を用いてマージソートの開発と実行時間の解析をやるらしい。

    • 2.1 挿入ソート 挿入ソートはソーティング問題(sorting problem)を解く ソートしたいと思っている数値......キー 概念的には列をソートしているが、実際の入力は　n個の要素を持つ配列 挿入ソート......トランプで左が小さくなるように差し込んでいくイメージ アルゴリズムの正当性を示すためにループ不変式に対して3つの性質を示す。
      1. 初期条件:ループの実行開始直前ではループ不変式は真である
      2. ループ条件:ループの何回目かの繰り返しの直前でループ不変式が真ならば、次の繰り返しの直前でも真である
      3. 終了条件:ループが停止したとき、アルゴリズムの正当性の証明につながる有力な性質が不変式から得られる

感想

文字がいっぱいあるととても分かりやすいんですけど、読むのは疲れますね。