Posts

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

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

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

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

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

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

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

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