kenta 砂場

貪欲法！動的計画法を使うまでもないわ...

15.1 活動選択問題（区間スケジューリング問題） 1つの会議室がある。会議室では同時に違うミーティングを行うことはできない。この会議室の利用を申請する $n$ 個のミーティングがある。ミーティング時間が被らないという前提のもとで、なるべく多くのミーティングを実施したい。 ...

最長共通部分列LCSと最適二分探索木を動的計画法で解く！

14.4 最長共通部分列なぜ最長共通部分列(LCS)問題を学ぶのかこの節では「最長共通部分列（Longest Common Subsequence: LCS）問題」に取り組む。詳しい定式化は後でやるが、この問題は「似ているけれど同じではない」二つの列（文字列や配列）の共通性を調べるための問題といえる。 ...

動的計画法！メモ化再帰？ボトムアップ？これで丸わかり！

この資料は、アルゴリズム設計・分析の重要なテクニックの一つである動的計画法 (Dynamic Programming, DP) について学ぶことを目的としています。具体的な問題を例に取りながら、その動作原理と適用可能な問題の性質を理解していきます。 ...

分割統治法！マスター法とAkra-Bazzi法

漸化式を解くためのマスター法アルゴリズムの実行時間解析、特に分割統治法に基づくアルゴリズムでは、その計算量を表す漸化式を解くことが求められる。マスター法は、特定の形式の漸化式に対して、その解を体系的に導出するための手法である。 ...

多腕バンディットを知りたい人のための世界標準の入門記事

“Bandit Algorithms” Tor Lattimore & Csaba Szepesvari の輪読会の資料です。世界標準のバンディットの教科書なので、世界標準レベルの入門記事と言えます。（過言）第1章：イントロダクションバンディット問題の源流は、William R. Thompson（1933）の論文です。Thompson は臨床試験に関心があり、その応用を想定してバンディット問題を考えました。 ...

3つの漸近記法 (ΘOΩ) の違いまとめ

『アルゴリズムイントロダクション第4版』の第3章で大事なとこだけまとめました。(ΘOΩ)　←顔みたいでかわいいね。アルゴリズムの実行時間と漸近記法アルゴリズムの効率性を評価し、入力サイズが増加した際のスケーラビリティを把握するために、実行時間の増加のオーダー（漸近的効率）を分析する。これには、係数や低次の項を無視し、入力サイズ $n$ が十分に大きい場合における実行時間の振る舞いに焦点を当てる漸近記法が用いられる。 ...

良いアルゴリズムってなんだ？

『アルゴリズムイントロダクション』§2.2-§2.3です。第２章：さあ、始めよう Part2 アルゴリズムの解析解析するとはなにか？同じ問題を解く複数のアルゴリズムがあるとき、どれを採用するのかを考えよう。このとき重要なのは、アルゴリズムを解析して優劣を決めて選択することだ。解析するとはなにか？ ...

アルゴリズムをなぜ学ぶのか？

以下は私が作成した『アルゴリズムイントロダクション第4版』の輪読資料です。一部、練習問題や章末問題を解いた結果も載せています。対応する教科書セクションは、第1部序論、§1.1～2.1です。 ...