  |
はてなキーワード:ダイクストラとは
実在してるかは謎だよね
時間は永遠に続くって思われてるかもだけど、それは証明されてない
だから永遠って基本的には「ない」ものとして扱ったほうがよくない？
数学が「永遠（＝無限）」を完全に排除したら、現代数学の99％以上が崩壊し、現代文明そのものが成り立たなくなります。
どれだけヤバいことになるか、段階的に見てみましょう。
1. 基礎の基礎が全部消える
•微積分が全滅（極限の概念が使えないので、ニュートンもライプニッツも泣く）
2.現代科学が死ぬ
•物理学：相対性理論、量子力学、電磁気学のほぼ全てが無限（極限操作）を使っている
•工学：フーリエ変換、信号処理、制御理論が使えなくなる →スマホ、テレビ、GPS、MRI、全部終わり
•コンピュータ科学：アルゴリズムの計算量解析（O(n), O(log n) など）が意味を失う
•暗号理論（RSAなど）が崩壊 →ネットバンキングもビットコインも即死
3.日常すら壊れる
• 「1リットルの牛乳を3人で均等に分ける」→ 0.333…リットルが定義できない
•円周率πが「3.14で打ち切り」になる →タイヤもロケットも正確に作れない
•地図アプリの最短経路計算が不可能になる（ダイクストラ法などが死ぬ）
結論：永遠（無限）を捨てたら人類は石器時代に逆戻り
無限を捨てると、現代数学は「巨大だけど有限な数までしか扱えない超巨大なそろばん」に成り下がります。
ロケットは飛ばない、インターネットは死ぬ、医療機器も止まる、経済も崩壊。
つまり、
「永遠（無限）」は人類が発明した「最も危険で、最も美しい爆弾」
捨てたら即死、抱えたままでもいつか爆発するかもしれない——
ノード：金
エッジ：玉
金玉集合 ←金玉未確定金玉 ←金玉距離[金] ← 0距離[玉] ←金玉金玉繰り返す: 最小金玉 ←金玉の中の最小金玉 未確定金玉から金玉を除去 隣接金玉について:候補金玉 ← 最小金玉 + 玉 もし候補金玉 <距離[隣接金玉] なら距離[隣接金玉] ←候補金玉 親金玉[隣接金玉] ←金玉
玉（＝エッジ）を辿るたびに金玉がぶら下がる
最も軽い金玉を優先
最終的に 最短金玉経路（Minimum KintamaPath） が得られる
金–玉–金–玉–金 \ 玉 玉 \ 金–玉–金
1.関数呼び出しが S1(),S2(), S3(),,, と連続で行われた場合に、各関数がちゃんと動くことが証明できれば、全体の流れとしてもちゃんと動く（といいな）
2. IF 条件 ==TRUE THENS1() ELSES2() という条件分岐があった場合に、S1,S2がちゃんと動くことが証明できれば、IF文全体としてもちゃんと動く（といいな）
...(繰り返しについて、一周がうまく動くなら、任意のn週もうまく動く（といいな）)
みたいな、だったらいいなが成立するなら、イケるやろ、というところまでなのが、イマイチ流行らないところ
そこを補うために、上記のだったらいいなを成立させるために何が必要なのか、妥協すればいいのか
ニルズはそこに対するアプローチと言える、、、、言えない、、、知らん
ダイクストラが提唱した抽象（abstraction）指向の構造化は、その思想の前衛性から1970年代を通して理解を得られることはなく、発案者本来の構造化プログラミングは上流工程視点からも普及することはなかった。
ダイクストラは、プログラマは正しいプログラムを作り出すばかりでなく納得のいくやり方で正しさを証明（検証）することも仕事の一つであるという立場を取っていた[33]。プログラムがどんなに巨大化しても良く構造化（well-structured）されていれば、サイズに関係なくその正当性を検証[34]できるというのが彼の信念であった[注釈 5][35]。
オプションが10個あってその先のオプションが10個あってさらにその先に10とやっていってったら証明は難しくなる
テストにしたって無理になる
オプションを増やさないその先で分岐させないってのは日常的にあるよね
それをOOPでやろうが他のなんだろうが同じことで
まず、アルゴリズムの根幹を成す計算複雑性について。O(n)やO(log n)といった表記は表面的な理解に過ぎない。真に重要なのは、問題の本質的な計算困難性だ。P≠NP予想を例に取ろう。この未解決問題は、効率的に解ける問題と解けない問題の境界を定義している。初心者は単にアルゴリズムを暗記するのではなく、この根本的な概念を理解せねばならない。
次に、データ構造。単純な配列やリンクドリストの理解では不十分だ。高度な自己平衡二分探索木、例えばレッドブラック木やAVL木の内部動作を完全に理解し、それらを一から実装できるレベルを目指すべきだ。さらに、アモーティゼーション解析を用いて、これらのデータ構造の操作の平均時間計算量を厳密に証明できる能力も必要不可欠だ。
ハッシュテーブルについても深く掘り下げよう。単純なチェイニングや線形探索法では不十分だ。完全ハッシュ法、クックーハッシュ法、オープンアドレス法における様々な探索手法（二次探索法、ダブルハッシュ法など）の利点と欠点を理解し、具体的な問題に応じて最適な方法を選択できるようになるべきだ。
グラフアルゴリズムにおいては、単にダイクストラ法やクラスカル法を知っているだけでは不十分だ。フロー・ネットワークにおける最大フロー最小カット定理やディニッツのアルゴリズム、さらにはグラフマイナー理論やロバートソン・シーモアの深い結果まで理解する必要がある。
動的計画法は、単純な最長共通部分列問題やナップサック問題を解くだけでは足りない。bitDPやMonge DPなどの高度なテクニック、さらには凸包トリックを用いた最適化まで習得すべきだ。
最後に、乱択アルゴリズム。単純なモンテカルロ法やラスベガス法の理解では不十分だ。シャーマン・モリソンの公式を用いた行列の高速な逆行列計算や、ジョンソン・リンデンシュトラウスの補題を用いた次元削減技術など、確率論と線形代数を駆使した高度な手法まで理解する必要がある。
これらは全て、真のプログラマーが持つべき基礎的な知識の一部に過ぎない。初心者は、これらの概念を深く理解し、実際の問題に適用できるレベルを目指すべきだ。そして常に、より深い数学的洞察と抽象的思考を追求し続けねばならない。
atCoderとかはそうだよ
ただGAFA面接だと競プロ的にはものすごく基本的なやつしか聞かれなくて応用力を求められる
A*なんて聞かれないし知っててもプラスには多分ならない
そもそもの論点として競プロがちょっとできてもエンジニアとしては「ハイスキル」ではないってことなんだよね
もちろん日本のSWEは、昔の自分もふくめて、アルゴリズムとかデータストラクチャなんか知りませんやってこともありませんという人が普通にいるし、ひょっとしたら大部分だけども
競プロは少なくともその二つとか計算量のBigOはわかってないと出来ないという意味で比較で言えばハイスキルではある
ただ、実際のシステムの開発では例えばダイクストラをA*にしましょうなんてことはないわけで、アルゴリズムいるなら自作だし
そういう場面も滅多にないのでOOPとかDDDとかの「実践」、後で機能つけるとか変えるときに数十数百億円流れてるってプレッシャーの中どれだけ簡単に早く確実にやれるかという技術と経験と実績が大事なんだよなあ
世の中の「エンジニア」のほとんどがソフトウェアエンジニアリングというよりはちょっとDayforceのレポートの設定がうまいくらいを求められてるのはその通りなんだけどね
去年4月に新卒入社した会社を今月末に退職して4月からフリーランスになることに決まった。
備忘録として、また他のフリーランスになりたい人役に立てるために現状を残しておく。
Web系のベンチャーでインターン(マーケター)したところ面白くてずっと働いてたら中退することになった。ちなみに会社は潰れたのでそこで働くことはできなかった。
情報系の大学院だがWebサイト構築できるわけでもなくサーバーサイドをガリガリかけるわけでもなかった。アルゴリズムは結構書いてて、2分探索木とかナイーブなダイクストラ法を実装できるレベル
エンジニア派遣の会社に入った。理由としては研修がしっかりしてて採用担当の人が賢そうでネットで悪い評判が見当たらなかったから。
エンジニアになりたかったが就活時期が就職の2ヶ月前から始めたため大手に入ることができず、Dodaとかリクナビで適当に「エンジニア 未経験」で出てきた会社に入った。
本当は自社開発の会社に入りたかったがスキルに自信がなかったため未経験歓迎の会社しか受けなかった。
初任給は300万くらい。正直言って自分の学歴からエンジニア派遣の会社に入ることは屈辱的だったが結果としてこの選択は非常に良かった。
3ヶ月の研修を経て現場に行ったのだが良い人に囲まれてガシガシ開発をできることは最高の経験だった。おまけに研修も少人数で行えたので非常に楽しく、良き友人に恵まれた。
初年度はとにかく勉強を頑張った。
平日は必ず定時に退社して毎日4-5時間勉強。休日は8時間勉強。日曜日は休みでフットサルして散歩してた。
その結果大学院の時はできなかったWebサイトの構築、サーバーの構築、REST APIでのサーバー実装くらいは余裕でできるようになった。
現場で使っている技術がサチってきて、学べることが少なくなってきたので営業に現場の交代を依頼したがのらりくらりとかわされたため退職を決意
ちなみにこれは営業が全て悪いわけではなく取引先に一方的な都合で派遣を解除することは難しかったり、次の現場の候補がなかったりといろいろな事情があるため一概に会社が悪いとは思っていない。
フリーになって初めて知ったがこの単価からエージェントの手数料と消費税が引かれて大体63万になるらしい。そこから社会保険とか諸々引かれて、、、一体いくらになるのだろう。
来年の給与がボーナスなしで月38万と聞いていたので正直会社辞めなくても良かったと若干後悔している。
自分の会社は自信を持っておすすめできるが業界全体としては正直わからない。
合格をもらった会社の中では研修なしで1年間携帯販売の仕事をしながら自社に帰って勉強しながらエンジニアを目指すとかいう意味不明な会社もあったので会社によってピンキリ
また現職の会社は一部上場企業の子会社でコンプラしっかりしててやたら他業界からエンジニアを目指してやってきた高学歴ばっかで基本国立大学以下はいなかった気がする。
そのおかげで開発案件しか派遣先にないらしく良い経験をできたがブラックでまともな研修を受けられない会社もあるらしいのでなんとも言えない。
間違いなく言えるのはエンジニアを目指すのは東京に来た方が良いということ。
自分は運悪く研究室に恵まれず十分な指導を受けられなかったり、軽いパワハラを受けていたので大学院は全く楽しくなかったですが企業は成果を出すことを求められるので社員のスキルを上げる合理的な理由があり研修を行ってくれるし何より同じ目標を持った仲間とチームで開発することはかけがえのない最高の経験になります。
また、大学や研究室は学力のみのフィルタリングで良いひともいれば嫌な人もいますが企業は採用段階で強くフィルタリングがかかるので正しく会社を選べば良い人しかいない職場で気持ちよく働けます。
適当に感想を述べる。ただの主観なので履修に悩んでいる人はシラバスと逆評定を読め。L系列については書かない。
「¬A ∧ (A ∨ B) ⇒ B」みたいな命題の証明を、ある規則に従って行ったりする。理科生的には数学の根源を掘っているみたいで楽しい。
全13回の授業で毎回違う教員がいろいろ話をしてくれる。各回ごとにレポート課題が出るが、最終的に提出するのは1つだった。単位に関係あるのは実質1回だけなので、結構気楽に聞くことができて癒しになる。普通の講義は毎回理解を求められるが、この授業は理解できなければその回のレポート課題を選ばなければよいだけなので。
人間の認知機能と脳機能の関係をやる。説明の都合なのか話題の9割が視覚（特に錯視）についてだった。脱線が激しすぎて全体的に何を言いたいのかいまいちわからない。ノートとスライドと教科書を見比べまくってなんとかしたが面倒すぎた。良い勉強方法が最後までわからない。
学際の香りがする。主に扱うのは二酸化炭素とオゾンホールとプラスチックとダイオキシン。「地球に温室効果がなかったら気温は-15℃」というのはよく聞くと思うが、その根拠をエネルギー収支の計算から示したりする。意外と覚えることは多い（フロン番号の命名規則とか）。
印象がない。新しいことを学んだ気がしない。とにかく簡単だった。
天下り的にいろんな化学が降ってくるが、具体的な理論づけは全くやらないので結局暗記ゲーと化した。基礎化学で扱う内容は、後々その他の化学系の科目で詳しく扱うので正直取る意味がなかったと思う。
熱力学の更なる応用みたいな感じ。ルシャトリエの原理とかの証明をしたり、酵素の阻害剤がどう働くのかをやる。学ぶところが多くて楽しいが結構難易度は高い。
なにもわからん。
Pythonやってれば楽勝。Pythonの実用みたいな感じ。アルゴリズム力よりコーディング力が付く。
アルゴリズム入門よりアルゴリズム寄り。ダイクストラ法とかやる。毎回課題が出るので面倒さは結構ある。アルゴリズム好きな人は楽しいと思う。
