Algorithm

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

引き続き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型のエイリアシングについて多くの説明がこの章では割かれています。確かにプログラミングでよくミスる部分ではありますね。

静的スコープと動的スコープの違い

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

この章ではプログラムを書く上で避けては通れない関数、スコープ、抽象化についてです。

プログラミングにおいては処理をひたすら書いていくだけではなく、共通の処理は関数として切り出したり、変数のスコープを意識して変数が見える範囲を理解する必要があります。 スコープを理解していないと処理の対象がなんなのか、どこまで参照可能なのかを分からずにプログラミングすることになり、効率が悪くなります。

ニュートンラフソン法ってなんだ?

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

この章は算術プログラムの章で、近似について学べます。 前回は浮動小数点について書きました。今回はニュートンラフソン法についてです。

浮動小数点の誤差はなぜ発生する?

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

3章は算術プログラムの章です。近似について学べます。 全順序について述べられていたりする点、さすがアカデミックだなぁと思いつつ読み進めました。

近似に関しては2文法とニュートンラフソン法が示されています。 2分法は名前から想像しやすいですが、2分探索のようにあり得る値の中間値の計算結果の大小から推定値を移動させていく手法です。 ニュートンラフソン法は初耳でした。

また浮動小数点の説明が非常にわかりやすかったです。実際の計算結果からずれることがある、くらいの理解だったのですが、2進数の都合上なぜ、どのようにずれるかが説明してあって納得でした。

スカラ、リテラル

Pythonプログラミングイントロダクション2章まで読みました。 2章はPythonの概要を説明し、変数や分岐、繰り返しについて学べる章です。

この辺りは普段からプログラミングをしていると目新しいことはないですが、 曖昧に理解している用語の再確認には有用です。

コンピュータ、プログラムとは

独学でコンピュータサイエンスの勉強をしたくてPythonプログラミングイントロダクション第二版を購入しました。全24章、学んだことをBlogにまとめていきながら読み進めていきます。

この本はMIT(マサチューセッツ工科大学)の講義に基づいているもので、プログラミング、アルゴリズムの基礎、さらに流行りのデータサイエンスにも触れられるようです。

まずは1章からみていきます。