問題解決の為のアルゴリズム×数学
題名:問題解決の為のアルゴリズム×数学
著者:米田優峻
読む目的
ソフトウェアのコーディングが出来るようになるために、アルゴリズムについて学習する。
paizaで問題が解けるようになるために、アルゴリズムについて学習する。
目標
paizaでB問題が解けるようになる。
15分→アウトプット、30分→アウトプット、1時間→アウトプットでそれぞれ読破する。
アルゴリズムでまとめる部分を抽出
2分探査
素数判定
ユークリッドの互助法
ソート
再帰
漸化式
効率的な余り計算
グラフを使ったアルゴリズム
問題解決の為の数学的
感想
やること、活かしたいこと
15分読書→実際:17分くらいかかった。
アウトプット1
アルゴリズムの理解には、数学的知識が必要
基本的な知識から、公約数、微分積分、行列、フィボナッチ数列など様々な知識が必要になる。
これは、アルゴリズムとは別に勉強、アウトプットが必要そう。
全探索は時間が累乗的に増えてしまう。 そのため、効率的に探索する為のアルゴリズムなどがある。(2分探査など)
数学の基礎知識→アルゴリズムについて→C++での実行方法という手順になっている。
外部サイトで、自分が作ったプログラムが正しいものかを確認できる。
githubにC++以外の言語の答えも記載してある。
基本的には、数学的な考え方が基本で、それをどうやってプログラムに落とし込んでいるかは書いていない。 プログラムの説明はなさそう?
カードの組み合わせ、モンテカルロ法、期待値の出し方、ソートなど24種類のアルゴリズムについて記載している。
最初に数学の基礎知識のページがまとまっている。これは、全ての基礎部分であり、その後にアルゴリズムに関する数学の基礎、アルゴリズムの内容、C++でのコーディング内容が載っている。
まずは、何から勉強するかを選択する必要がある。 全部やる必要は無い。
ただし、後の方に書いてあるアルゴリズムは、前の章で取り扱ったアルゴリズムの知識が基本的に知っていることが前提で書いてあるため、注意が必要。
paizaの問題に関して使えるものなのかの判断はちょっと難しいかもしれない。
30分読書
アウトプット2
1章でこの本の概要
2章で数学的な知識
3章からアルゴリズムの解説の構成になっている。
4章は3章より発展した数学知識が必要になっており、ざっと見たくらいだと全然理解できない。
5章は、4章より数学的な知識については簡単らしい。数学的な見解は必要。
アルゴリズムは、数学的要素の説明が多くて、プログラムよりは問題に対してどのような数学的視点から考えるかが主な内容になっている。
アルゴリズムによって、実行時間が変わり、実行時間がおおよそどのくらいになるかは、O()で表せる。
O()については、2章辺りにまとまっている。
探索、確率関連、微分積分、モンテカルロ法、フィボナッチなどがあり、どの問題にどのアルゴリズムが適用出来そうかなど判断出来るようにする必要がありそう。
問題を、グラフ化や漸化式として表せないかを考えるのは必要そう。
単純に、アルゴリズムを学んでも、すぐに、色々な問題に適用し、かけるようになるのは難しい。
数学的に分からない部分が多いので、それをまずはまとめて理解する必要がある。
プログラムを見て、どうやってプログラムで表しているのかをとりあえず見るのはありかもしれない。
ユークリッドの互除法など、ざっと見ただけでは、一般的にどういった場合に使えるのかよくわからないやつもある。
2章は基本読まなくても分かりそう。
床関数、天井関数、ガウス記号については要確認
標準ライブラリで用意されている配列の扱いについて勉強した方がpaizaには、すぐに使えそう。