:apple: Learning Algorithm 第1回 :apple:

# :apple: Learning Algorithm 第1回 :apple: ## ファシリ - 松本 ## 日程 * 2022/~~06/07~~ 06/14 19:00 - ~~20:00~~ 20:30 ## 範囲 * 1章から3章まで(p39まで) ------------------------------------- ## 第1章アルゴリズムとは ### 目安の時間 10分 ### 感想・気づき - 電子書籍で読んでるので、ページ番号じゃなくて節とか項の番号で引用していただけるとうれしいです:bow:(山田) - 目次見た感じ、最適化（何々をするときのコストを最小化してね・何々のスコアを最大化してね）がメインで、数え上げ（条件を満たすなにかしらの個数を求めてね系の問題）はあんまりやらない？前者の方がイメージつきやすいから？ / えびちゃん ### 疑問・わからなかったこと - 1.5 『問題を解決するという行為を、（中略）問題に対する具体的な解を書き下すことができなくても解を得るための「手順」を与えることができればよい、という見方ができるように』なるってどういうこと？（前川） :+1: :+1: :+1: ### [任意]章末問題の回答この章はなし！ :+1: ------------------------------------- ## 第2章計算量とオーダー記法 ### 目安の時間 30分 ### 感想・気づき - p22 つよい > 1 秒間で処理できる計算ステップ回数は $10^9 = 1,000,000,000$ 回程度です - 最適化の効きやすさとかで、「$10^9$ 回ループすれば 1 秒くらいかかる」とは限らなかったりする（もっとかかったり、もっと早かったりする）/ えびちゃん - 計算量のことを complexity（複雑さ）という言い方をするのはどうして？と言われそうな気がしました / えびちゃん :+1: :+1: - 計算複雑性という概念がある（問題に対しての複雑さ） - 「アルゴリズムの複雑さ」との区別のために「計算量」がある？かも - ランダウのO記法には、プログラミング言語や実行環境の影響による微妙な問題を吸収する役割もあるのか。（前川） ### 疑問・わからなかったこと - p22　何を言っているかわからない→「底の交換公式」「定倍数」をググる > ただし、$a > 1$なる実数$a$に対して、底の交換公式によって > $$ \log_2 N = \frac{\log_2 N}{\log_2 a} $$ > が成立することから、底を変更しても定倍数の違いしか生じません - 山田の解釈 2.5節によると、オーダー記法においては定数倍の違いは無視するみたいです。計算量が$3N$でも$5N$でも$10N$でもオーダー記法にするとこれらはすべて$O(N)$になるし、 $2N^2$、$3N^2$、$7N^2$などは$O(N^2)$になります。同様に対数の計算量を定数倍しても、$log N$、$2log N$、$10log N$は$O(logN)$になります。シンプルですね。次に、$log_2 N$、$log_3 N$、$log_5 N$のように対数の底を変えたときにオーダー記法にはどう影響するの？と考えてみます。 (対数の底とは何者かというと、$2^3=8$を対数を用いて表記すると$log_2 8=3$になりますが、このときの$2$のことです。) ところで、対数には底の変換公式というものがあります。 $$ \log_a b = \frac{\log_c b}{\log_c a} $$ この公式をもとに、試しに$log_3 N$、$log_5 N$の底を2に変換してみます。 $$ \log_3 N = \frac{\log_2 N}{\log_2 3} = \frac{\log_2 N}{1.58} = 0.63 log_2 N $$ $$ \log_5 N = \frac{\log_2 N}{\log_2 5} = \frac{\log_2 N}{2.32} = 0.43 log_2 N $$ いずれも$log_2 N$の定数倍になりました。この公式に当てはめれば、$log_a N$の底$a$がどんな数であったとしても、必ず$log_2 N$の定数倍になりそうです。つまり、$log_2 N$も、$log_{10} N$も、$log_{100} N$も、オーダー記法にすると全部$O(log_2 N)$って書けちゃうみたいです。オーダー記法においては底はわりとどうでもいいってことですね。(たぶん作者が言いたかったこと) そんなわけでこの本では、底に2を使うけど、今後省略して$log_2 N$を$log N$と表記していくそうです。 (山田) - えびちゃんの補足 ↑ O の文脈で底の 2 などを省略するのは、$O(2N)$ とかを単に $O(N)$ と書くのと同じような気持ちがある気がします（$2$ を使う、とかをいちいち気にしたくないという感覚がありそう）。あと、底は定数である必要があります（$\log_{\sqrt{N}}(N)$ とかだと $\log_2(N)$ の定数倍ではないので）/ えびちゃん - 底（てい） - そもそも「定倍数」というのは、極限の世界でいうと一定の倍数を掛けることは極めて小さな差しか生み出さないので、基本的に無視して考えてOKという数という認識であっていますか？(松本) - ↑ なにが小さな差なのかは文脈によりそうだけど、ざっくりはそんな気持ちでよさそう。O の文脈で定数倍を無視するのは、O 自体が「定数倍をうまくやれば（$N$ が十分大きいときは）上から抑えられる」を意味する記法だからです（なので、$3N+1$ を $O(2N^2)$ とか言っても嘘ではない）/ えびちゃん - アルゴリズムの文脈で定数倍を無視したくなる動機としては、コンピュータのスペックアップで無視できるようになりがちというのがある気がします（スペックが上がってもアルゴリズムのオーダーは変わらないが、2 倍になったりはするので、アルゴリズム自体の定数倍の評価をしてもうれしくないことが多い）（定数倍をちゃんとやる文脈もあって、$1.5n + o(n)$ みたいな書き方をしたりするかも）/ えびちゃん - オーダー記法を使うときには、「Nが増えると計算時間が爆発的に増えてしまわないだろうか？実用的な時間で計算できるのかな？」みたいなことが関心事なんだと思います。Nが定数倍になっても計算時間は爆発しないので、この文脈では無視してるんだと理解してます。(山田) - ↑ :+300: くらいある / えびちゃん - 「計算量が小さすぎちゃう」みたいな心配をする必要は基本的にはないため、上から抑えたいことが多そう。「お前のアルゴリズム遅すぎ〜」という主張をしたいときは下から抑える必要がある / えびちゃん - 章末問題で、筆者オリジナルの問題の場合、入力形式が書かれていないので、他の人と異なる形式だった場合に同じファイルでテストできなくてちょっと面倒かも（筆者のコードを見に行けばよいが、それも面倒）/ えびちゃん :+1: - 統一はしない方向でやっていく！ ### 用語関連 - 2.5 計算量の使い方「上から抑えて評価する」 - 「上から抑え（て評価す）る」は不等式の言い回しで、「$x$ がどれくらい大きくなるか知りたいよ〜」ってときに「$x \le y$（$y$ より大きくはならない）」のことを「$x$ を $y$ で（上から←文脈から明らかなら省略されたりする）抑える」とか言ったりします。あるいは上記の「知りたいよ〜」の部分を「$x$ を上から抑えたい」と言ったりします。「$x$ に関する何らかの不等式を作る」ことを「$x$ を評価する」と言うこともあるかも / えびちゃん - 「$N$ が十分大きい」というような言い回しをすると、「$N$ が小さかったら成り立たなくない？」とかそういう議論を無視できる（なにかしらの値以上で成り立っていればよい）（なにかしらの値も適当に選んでよくて、境界ぎりぎりの値でなくてもよい）/ えびちゃん - 「陽（よう）に」：「具体的に」「明示的に」「explicit に」みたいな意味合い。対義語は「暗に」「陰に」「implicit に」など。~~オタクはよく使う~~ / えびちゃん - 数学コンテキストでの特殊な使われ方。意味はこちらの[研究](http://repository.tufs.ac.jp/bitstream/10108/69729/3/jlc38004.pdf)参照。 ### 記法関連の補足ここはある程度慣れてから読み直すのでもいいかも :+1: 実際には、$O(f(N))$ というのは（十分大きい $N$ においては）$f(N)$ の**定数倍で上から抑えられる関数の集合**を表します。$O(N^2) = \{N^2, 3N^2+1, 2N-3, 10, \log_2(N), \dots\}$（無限個ある）など。たとえば計算量が $3N^2+1$ だったとき、（$3N^2+1\in O(N^2)$ なので）単に「計算量は $O(N^2)$ です」と言ったりします。$n$ 人（$n$ は偶数）の人間がいたときに、偶数 $\{\dots, -4, -2, 0, 2, 4, \dots\}$ の値を陽には言わずに「偶数人います」と言えるのと似ています（「奇数月」とか「素数個」とかの例の方があるあるかも） / えびちゃん $O(f(N))$ は上から抑えたいときに使いますが、下から抑えたいときは $\Omega(f(N))$ と書き、上下から抑えたいときは $\Theta(f(N))$ と書きます（ちゃんと本にも記載あったね） / えびちゃん $o(f(N))$ や $\omega(f(N))$ という記法もあって、直感的には「$O(N^2)$ よりオーダー下がらないの？（不正確お気持ちフレーズ）」のことを「$o(N^2)$ にできないの？」とか言えます / えびちゃん O とかは計算量以外の文脈でも使えて、「$O(n)$ bits」「$O(n^2)$ 個」「$O(n \log(n))$ 回」とか言えます。逆に、計算量の文脈では O とかで書かなきゃいけないというわけでもない / えびちゃん O の中でも必ずしも底を無視できるわけではなくて、$O(N^{\log_2(3)})$ と $O(N^{\log_3(4)})$ は別物です / えびちゃん 🦐えびちゃんのブログが詳しい→https://rsk0315.hatenablog.com/entry/2021/10/13/235627 ### [任意]章末問題の回答この章もなし！ ------------------------------------- ## 第3章設計技法(1): 全探索 ### 目安の時間 30分 ### 感想・気づき - > 最悪計算量は $O(N)$ で変わりません（3.2 節最後） - ここでは下から抑えたい文脈なので、$\Omega$ や $\Theta$ が本来は適切 / えびちゃん - 線形探索をしたと思ったらいきなりビット全探索の話になっており、初心者的にはこれいけるのか？みたいな気分になった / えびちゃん :+1: - 2 進数とかビット演算とかに慣れるのが必要？ / えびちゃん - ビットシフトとかマスクとか慣れてないと厳しいかも / 山田 - 初心者の松本まったくいけないので助けてください / まつもと :+1: - 人々がどういう環境で C++ を実行したりしてるのか気になるかも（テストとか） / えびちゃん :+1: - VSCodeで書いてるけど環境構築面倒で[AtCoderのコードテスト](https://atcoder.jp/contests/apg4b/custom_test)で実行してる（手元でテスト実行したい） / まつもと - 手元のテストには [`oj` ってツール](https://github.com/online-judge-tools/oj) が便利です。普段ターミナルでコンパイル・実行してるので、VS Code のことはすぐアドバイスできないかも / えびちゃん ```bash # test/問題名/ケース名.in と test/問題名/ケース名.out を用意しておく % oj d -d test/問題名 AtCoder問題URL # あれば。なければ手動 % oj t -c ./実行ファイル test/問題名/* ``` - macだったらデフォルトでgccでコンパイルできると思います！山田 ```shell g++ -o 実行ファイルソースコード ``` - ↑ それは実は GCC ではなくて Clang だったりしそうです（多くの場合はそれでも問題ないはずだけど、たまに変な感じにつまずくので、どうしたものか迷う）/ えびちゃん ### 疑問・わからなかったこと - p36 部分和問題の話全体的に難しい・・・ - 部分和問題の解き方の話は自分の中ではこんなふうに理解しました。山田 :+1: > - 組み合わせの全パターンにIDを割り当てる考え方。 > - IDに整数を使うことで、範囲指定でループを回して全探索のアルゴリズムに使える。 > - IDから各組み合わせの状態を復元できるようにすると、IDだけ管理すればいいので便利。 > - 整数のIDを2進数で解釈するとフラグが並んでいるように見えるので、状態を復元するのに使えて便利。 - ↑ 単にループしたときの順が更新順に反しないのが肝 - 1 は 4 の後に更新する必要があり、4 は 0 の後に更新する必要があり、... などバラバラだとつらい（再帰で書けばバラバラでもなんとかなる）/ えびちゃん - なるほどわからん / まつもと - 3.4の問題、3.4のペアの全探索だと思いこんで全然O(N)にできなかった...前川 - 3.7の問題のこのテクニックかしこい(tmpはlong long, S[i]はchar)...前川 :eyes: ``` tmp += S[i] - '0'; ``` ↑ `S[i] - '0'` は `char` ではないので、勘違いするとたまにバグる（暗黙に型変換されがちというのもある）/ えびちゃん ### [任意]章末問題の回答 - 前川 (tomokikun) - https://github.com/tomokikun/ands/pull/1 - 山田 (YamadaKyohei) - https://hackmd.io/@yamadakyohei/ByxqTNLuq#3%E7%AB%A0 - えびちゃん (rsk0315) - https://github.com/rsk0315/learn_algo (private) に置きます - C++での最大 - https://github.com/rsk0315/learn_algo/blob/main/cxx/exercise_3_3.cpp#L13