CS

2項分布をPythonで理解する

Pythonプログラミングイントロダクション(15章)まで読みました。 15章では確率統計を題材に、正規分布や関連する話題として信頼区間について述べられています。

貪欲アルゴリズムを学ぶついでにハフマン符号を学ぶ

引き続きPythonプログラミングイントロダクション(12章)をみていきます。 この章ではナップザック問題を題材に貪欲アルゴリズムについて説明がされていますが、貪欲アルゴリズムはハフマン符号という符号化にも利用されています。 そして、ハフマン符号はJPEGやZIPで利用されている符号化です。

JPEGやZIPのような馴染みのある要素技術として利用されているハフマン符号とは何か、貪欲アルゴリズムの使いどころはどこなのかをみていきます。

重み付き有向グラフの探索を優先順位付きキューで実装してみる

Pythonプログラミングイントロダクション12章まで読みました。 12章は最適化問題についてです。 空き巣が最適な盗みをはたらくためにはどのようなアルゴリズムで物を選んで盗んでいけば良いかを考えるナップザック問題や、 島をつなぐ橋を丁度一度ずつ渡るような散歩が可能か、オイラーによって定式化されたケーニヒスベルクの橋の問題などのグラフ最適化問題が題材になっています。

最短路問題としては深さ優先探索と幅優先探索が取り上げて、実装について丁寧に説明してくれています。 グラフ最適化問題の仕上げとして、章の最後に重み付き有向グラフの探索アルゴリズムについての練習問題があります。 この練習問題を元に重み付き有向グラフの探索問題を考えていきました。

計算複雑性の対数はどこからくるのか?

Pythonプログラミングイントロダクション10章まで読みました。 9,10章は計算複雑性についてです。O(n)となる線形な計算量はイメージしやすいのですが、O(log n) のように対数が出てくるケースがどういうケースか最初イメージしずらかった覚えがあります。

この本では、9章で計算複雑性についての概念を、10章では二分探索やマージソートを例に、計算複雑性に対数が現れる様子を詳しく説明してくれています。

リスコフの置換原則(LSP)をPyhonで考える

Pythonプログラミングイントロダクション8章まで読み終わりました。

6,7章はさらっと読み進められましたので飛ばして、今回は8章をみていきます。この章ではオブジェクト指向についての説明がされています。 継承、カプセル化、オーバーライド等のオブジェクト指向やクラスの定番の話題が説明がされている中で、リスコフの置換原則について軽く触れられていましたので詳しくみていきたいと思います。

エイリアシングによるオブジェクトの参照

Pythonプログラミングイントロダクション5章まで読みました。

5章をみていきます。この章ではPythonの構造型と呼ばれるtuple ,list, str, rangeについてみていきながら、可変性と不変性の違いが説明されています。 また、関数を引数として渡すような高階関数についても説明されています。

特にlist型のエイリアシングについて多くの説明がこの章では割かれています。確かにプログラミングでよくミスる部分ではありますね。