はてなブックマーク

数学 大学数学の「わからない」を「わかる」に。線形代数、解析学、離散数学、確率・統計の基本科目から制御数学、複素解析などの応用科目まで。

こんにちは、ももやまです。 動的計画法は、アルゴリズムでもかなり重要な内容です。AtCoderやらプログラミングコンテストとかでもよく出てきます。 ですが、動的計画法は「アルゴリズムを学ぶ上での壁・登竜門」とも呼ばれるとおり、かなり難易度の高いアルゴリズムとなっています。どの参考書を見てもなかなかわかりやすくは書かれていません。 そんな動的計画法を今回はうさぎでもわかるようにわかりやすくかみ砕いて説明したいと思います。 １．動的計画法とは 動的計画法とは、 問題をいくつかの簡単で小さな問題に分割 それぞれの問題の計算結果を表に記録 同じ問題に対しては表から計算結果を参照する の3つの特徴を持ったアルゴリズムです。 といきなり言われてもわけがわからないと思うので、動的計画法のイメージを説明しましょう。 動的計画法のイメージ 例えば、\[ 28 \times 37 \]の計算を解きなさい。 と

１．P、NPって何？まずはP問題、NP問題の違いについて説明していきましょう。 ですが、説明の際に、多項式時間という単語が出てくるので、まずは、多項式時間についての説明をしておきましょう。 多項式時間とは多項式時間*2とは、\( a \) を定数として、\( O(n^a) \) 以下の時間のことを表します。 多項式時間の例としては、 \( O(n^3) \) 、\( O(n \log{n}) \) 、\( O(n^{100}) \) などがあります。 多項式時間ではない例としては、指数関数以上のオーダーのもの、たとえば \( O(2^n) \), \( O(1.2^n) \), \( O(n!) \) などがあります。 今回は、わかりやすく説明するために、多項式時間以内で解けるアルゴリズムのことを効率の良いアルゴリズム、多項式時間以内で解けないアルゴリズムのことを効率の悪いアルゴリズムと呼

２．2分探索木とは 親の左側のノードの値が必ず親よりも小さく、右側のノードの値が必ず親よりも大きくなっている2分木のことを2分探索木と呼びます。 2分探索木では、下の図のようにどの親に対しても値が必ず左の子＜親＜右の子となっています。 さらに左の子だけでなく、左部分木のすべてのノードの値が親よりも小さくなる特性があります。 右部分木のすべてのノードの値も同様に親よりも大きくなる特性があります。 つまり左部分木のそれぞれのノード＜親＜右部分木のそれぞれのノードの関係も成立します。 よって、上の図にある2分探索木のそれぞれのノードに入る値の範囲は下のようになります。 スポンサードリンク ３．2分探索木を用いた探索 2分探索木では、それぞれのノードに対し、「左部分木のそれぞれのノード＜基準ノード＜右部分木のそれぞれのノード」が成り立つので、データの探索を簡単に行うことができます。 実際に上の木構

こんにちは、ももやまです。 今回は基本情報にもよく出てくる探索アルゴリズム（線形探索・2分探索・ハッシュ探索）について説明していきたいと思います。 １．探索とは 配列やリストなどのデータ構造の中から目的のデータを探した出すことを探索といいます。 「データなんて最初から順番に探し出していけばいいじゃん！」 と思うかもしれません。 しかし、もしデータ数が100億あったらどうでしょう。 地道に計算すると日がくれそうです。もっといいアルゴリズムがないかなぁと思いたくなりますよね。 そこで今回はコンピュータ上でよく使う探索アルゴリズム、具体的には 線形探索二分探索ハッシュ探索 の3つを紹介していきたいと思います。 スポンサードリンク ２．線形探索 (1) 線形探索とは 配列の先頭から順番に目的のデータかどうかを調べていく方法を線形探索と呼びます。 しらみつぶしに探していく最も単純な探索アルゴリズムで

数学 大学数学の「わからない」を「わかる」に。線形代数、解析学、離散数学、確率・統計の基本科目から制御数学、複素解析などの応用科目まで。

１．計算量ってなに…？何人かが作ったアルゴリズムの良し悪しを評価したいとします。 評価の方法には様々な方法があるのですが今回は、かかった時間で評価してみるとします。 例えば、Aさんの作ったアルゴリズムは実行に30秒かかりました。 しかしBさんの作ったアルゴリズムはたったの10秒で計算できちゃいました。 あ、Bさんのほうが速度が3倍だからBさんのアルゴリズムのほうが良い！と思うのは実は問題点があります。 極端な例ですが、Aさんのアルゴリズムの実行時間を評価するのにCeleron*1のCPUが入っている計算機(PC)を使い、Bさんのアルゴリズムを評価するときにスーパーコンピューターレベルの計算機を使っていたら計算機の性能の良し悪しが実行時間の差に影響してしまいます。このように、かかった時間で評価する場合は実行する場所（環境）がわからないため明確にアルゴリズムの良し悪しが判別できません。 こんな

１．離散数学って何？　前提科目は？高校時代、数学の様々な科目を履修したはずです。二次関数、図形と方程式、三角関数、指数関数、対数関数、微積、理系の人なら複素数平面などなど……。 でも離散数学という名前だけではどんなことをするのか全然わかりませんよね。 ということで、まずは離散数学とはどんな数学なのかを見てみましょう。 微分積分学の極限に関係しない数学。すなわち〈連続の数学〉に対して離散的な構造を扱う数学。計算可能性の理論，符号理論，オートマトンの理論，計算量の理論，証明論，組合せ論などの幅広い分野が含まれる。 有限でかつ離散的な，非計量の分野を対象とする数学。集合論，整数論，グラフ理論，組合せ論などの分野が含まれる。……… 引用：コトバンク「離散数学」 読んでみると、微積とは全く関係ない内容というのがわかりますね。しかし、離散的な構造を扱うというところが少しわかりにくいかもしれないので、少