最近やりたいこと(2022/7/26 版)
最近暑すぎませんか？
暑すぎて自転車登校なのに電車を使うようになりました。35℃超えてる日に何十分も外で運動したくないので。
それでも結局帰宅時には疲れているので、あまり自分の時間を有効活用できずにいるのが現状です。そのくせToDoリストは人一倍に溜まっていってしまうので、せっかくやる気が出てもどれからやろうかと考えているうちに就寝時間になってしまうわけです。(これをネットワークの世界で輻輳といいます)
ここでは備忘録も兼ねてやりたいことをつらつらと書いていきます。(それだけなので中身はあまりないです)
ほんぺん
アルゴリズムイントロダクションを一通り読む(現在1章)
研究室で頂いた(正確には借りている？)本です。そもそもこの本が鈍器レベルのデカさを誇るため、読み切るのが困難ですが、演習問題は無視して軽く目を通しておきたいと思っています。
3年くらい競プロをしていたので大体の内容は既知ですが、ライブラリとしてアルゴリズムやデータ構造を使用することはあっても数学的な議論には特に踏み込んでいなかったので、学問的な意義を期待して挑戦中です。
CTFの本を読む(まだ何も)
名前の通りCTFの本です。初心者向けです。ハリネズミとは違いますが。
学部1年生の頃から先輩の影響でCTFに触れていたのですが、実戦によるフィードバックがほとんどだったので、一度腰を据えて勉強してみようと思いました。優先度はあまり高くないですが、そのうち読み切りたいところです。
みかん本を完遂する(途中までやったけど最初から読み直す)
有名なOS自作本です。低レイヤ向けの本にしては新しく、読みやすいので非常に重宝します。ちなみにもう少し昔の、30日でできる方のOS自作本も持っていますが、現代ならとりあえずみかん本でいいかな、と考えています。
コードの写経までしていると、あまりに時間がかかってしまうためにしばらく封印されていました。これやり始めると試験勉強とかできないんですよね。ただ、内容は技術的にも学問的にも重要なため、最後までやりたいです。
Kaggle本を読み切る(まだ何も)
よく見かける、Kaggleで勝つデータ分析の技術です。手をつけていません。前提知識としてscikit-learnが必要だよーと書かれていたので、先にそっちを勉強しようと思い放置してしまいました。
Kaggle自体はほとんど触れていませんが、参加している友人が楽しそうなため、そのうち自分もKaggleの海に飛び込んでいきたいと思っています。(あわよくば賞金を)
CPU自作本を読み切る(まだ何も)
こちらも有名な本です。表紙にメイド姿の女の子が描かれているやつですね。論理設計の授業を受けるついでに購入しましたが、結局Arduinoに甘えてしまったために活用できませんでした。内容は簡単な論理回路の説明から、ステップアップ的にCPUを自作する形式になっているようです。
研究はソフト寄りの論理系ですし、就職もハード系に行く予定はありませんが、教養としてこのくらいは知っておこうかと思っている次第でございます。
実例で学ぶゲーム3D数学を読み切る(まだ何も)
内容もあまり知りません。オライリーのゴリラが表紙の本です。Twitterか何かでおすすめされていたので購入しました。そのうち読みます。
Rustの勉強(少しだけ)
ゆっくり、挙動を確認しながら進めています。have been ingです。普段はC++を使っているのですが、モダンな言語を勉強してみようと思い始めました。enumがまったく別な機能になっていて腰が抜けました。(これ、他の人もそうですよね？)
ちょっとしたことですぐにコンパイルエラーを出す泣き虫言語ですが、ランタイムエラーを防ぐためと考えれば理にかなった設計だと思いますし、実行速度が速いのも気に入ったので、将来的に母語になってもおかしくないです。
あと勉強には次の本を使っています。有名なやつですね。
研究は？
はい……
おわりに
また思い出したら追記していきます。それか別記事を立てるか。
見抜いた人もいるでしょうが、僕は興味だけで行動しない真面目系クズなので、上の一覧を完遂して立派なクズになりたいと思います(まる)
Big Oってなに？
主に競技プログラミングや大学の授業で目にする (Big O)と言う記号ですが、これの定義が曖昧な場合が多いなと思うのでまとめます。すでに多くのwebサイトや書籍で記載されているので新規性はありません。残念。
記法は僕がはてなブログに慣れるための犠牲になりました。
時間計算量と空間計算量
プログラミングにおける計算量には主に2種類、時間計算量と空間計算量があります。ざっくばらんに説明すると、時間計算量はその処理に必要なループ・再帰回数、空間計算量はメモリ使用量にあたります。AtCoderにおいては多くの場合は時間計算量だけを気にしていればいいですが、ゲーム開発や組み込み開発だと結構メモリ不足に悩まされるそうなので、空間計算量も意識する必要があるとかないとか。
記法はこの時間計算量や空間計算量を表現する際にしばしば用いられます。
記法の定義とかとか
計算量はしばしば みたいな感じに表現されますが、
って何を表しているのか知っていますか？僕は1年くらい前まで雰囲気で読み取っていましたが、確か組合せ最適化の本*1を読んだ際に初めてその定義を理解しました。
たまーに雑な定義として、以下のような表現が見受けられます。
の時、
なら
これ、 が共に上に有界でない単調増加関数なら両方とも無限大に飛んでいっちゃうので、比較できませんよね。なので曖昧どころか式自体間違ったものです(ニュアンスはわかるけれど)。そこで、もうちょっとしっかりと定義しておきたいなと思います。
いきなりですが、 の定義を以下のように与えます。
つまり、関数の引数が 以上の時に必ず一方の定数倍がもう一方以上の値をとる場合、
記法で上のように表せるわけです。ここで、[tex : C] は必要なの？って思った人は以下の関数を考えてみてください。
この関数は実際にと表せますが、
による定数倍がなければ永遠に
なため、そう表せなくなります。だから
が、必要だったわけです。
ところで、鋭い人は上の定義をみて、上から押さえることができればなんでもいいの？って思うかもしれません。これはその通りで、別に を
と表現しても問題ありません。実際、ある程度計算量が少ないことさえわかれば十分なこともあるので、雑に評価してそれなりの結果ならOKみたいなことも競プロ中にはやりがちです。
より厳密な表現を使いたい人は、 記法を使いましょう。
は、以下のように定義されます。
非常にシンプルですね。 は一般に成立しませんが、
は常に成立します。
定義よりわかることですが、 と分解される時、もっとも影響の強い項のみを使って
と表すことができます。例えば、
の場合は
と表せます。
いくつかまとめると、項の影響の強さは以下のような順番に並べることができます。
指数関数以降はそれ以前とは比べ物にならない速度で爆発的に増加するので、基本的にプログラムを書く際には避けるべきです。
おわりに
以上、 記法のメモでした。ところで、下から押さえる関数の表現については
記法なんかを使うそうですが、存在と定義は知っているものの利用例を見たことがないのでここでは紹介しませんでした。興味があれば是非調べてみてください。
