  |
はてなキーワード:動的計画法とは
まず、アルゴリズムの根幹を成す計算複雑性について。O(n)やO(log n)といった表記は表面的な理解に過ぎない。真に重要なのは、問題の本質的な計算困難性だ。P≠NP予想を例に取ろう。この未解決問題は、効率的に解ける問題と解けない問題の境界を定義している。初心者は単にアルゴリズムを暗記するのではなく、この根本的な概念を理解せねばならない。
次に、データ構造。単純な配列やリンクドリストの理解では不十分だ。高度な自己平衡二分探索木、例えばレッドブラック木やAVL木の内部動作を完全に理解し、それらを一から実装できるレベルを目指すべきだ。さらに、アモーティゼーション解析を用いて、これらのデータ構造の操作の平均時間計算量を厳密に証明できる能力も必要不可欠だ。
ハッシュテーブルについても深く掘り下げよう。単純なチェイニングや線形探索法では不十分だ。完全ハッシュ法、クックーハッシュ法、オープンアドレス法における様々な探索手法（二次探索法、ダブルハッシュ法など）の利点と欠点を理解し、具体的な問題に応じて最適な方法を選択できるようになるべきだ。
グラフアルゴリズムにおいては、単にダイクストラ法やクラスカル法を知っているだけでは不十分だ。フロー・ネットワークにおける最大フロー最小カット定理やディニッツのアルゴリズム、さらにはグラフマイナー理論やロバートソン・シーモアの深い結果まで理解する必要がある。
動的計画法は、単純な最長共通部分列問題やナップサック問題を解くだけでは足りない。bitDPやMonge DPなどの高度なテクニック、さらには凸包トリックを用いた最適化まで習得すべきだ。
最後に、乱択アルゴリズム。単純なモンテカルロ法やラスベガス法の理解では不十分だ。シャーマン・モリソンの公式を用いた行列の高速な逆行列計算や、ジョンソン・リンデンシュトラウスの補題を用いた次元削減技術など、確率論と線形代数を駆使した高度な手法まで理解する必要がある。
これらは全て、真のプログラマーが持つべき基礎的な知識の一部に過ぎない。初心者は、これらの概念を深く理解し、実際の問題に適用できるレベルを目指すべきだ。そして常に、より深い数学的洞察と抽象的思考を追求し続けねばならない。
一人で勝手にイタイならいいけど、いい加減我慢も限界でなんとかしたい。
そいつは圏論に裏付けられた静的型付け言語のスバラシサを布教しないと気がすまないらしく、事あるごとに純粋でないオブジェクト指向言語をdisる。
曰く、静的型付け言語だと型を合わせてコンパイラが通るようにするだけで実行時エラーを絶対起こさないコードが書けるらしい。
ああまた始まったと思ってたら、そいつが熱弁する後ろから同僚が近づいて「ヒープ足んねぇ」って書かれたメモを背中に貼っつけてたのは笑った。
お前が書いたn3アルゴリズム(!!!!)も型さえ合えばコンパイラがnlognに書き換えてくれんのかね。
いやそれ、動いてるって言わないから。
型チェックぐらいで取れるバグなんて、せいぜいスタックかキューみたいなもんだろ。
お前の怪しい動的計画法のバグをチェックできるコンパイラなんて存在しないぞ。
圏論なんてやってる時間があるならダイクストラ法でも復習しとけってんだ。
どちらにせよ設計においてはオブジェクト指向が使われるのだから、ほとんど違いなどない。
せいぜい数倍コードが短くなる程度の話に学習コストをかける価値は無い。
彼ら全員が理解しない限り、関数型言語で開発などできるわけがない。
そのコストと、純粋関数型言語によって得られるメリットを差し引きすると、正直何の魅力も感じないのだ。
関数型にかぶれている奴は、プロジェクト全体を見通す力、マクロ的な視野なく、自分の狭い世界だけで騒いでいるだけだ。
ま、厨二病みたいなもんさ。
ランド研究所というのはアメリカ空軍が設立したシンクタンクで、色々面白い研究をしている。
ゲーム理論とか線形計画法、動的計画法、帰納推論に正規表現、論理回路の縮約法、パケット交換ネットワーク、
RAND のレポートが先で、学術論文は後、そんな 1950 年代はアメリカの冷戦パラノイアいっぱい夢いっぱいの時代だった。
彼らがどうも昔のレポートを気まぐれに無料公開しているっぽい。2005年から毎年その数は増えている。半導体のスイッチング速度が10ギガの壁にぶちあたり絶賛停滞中のわれらが人類文明だけど、近過去に目を転じると、けっこーすげーじゃん、って気分になれるかもしれない。
試しに
site:www.rand.org/pubs/papers/2008/
とか
site:www.rand.org/pubs/papers/2005/
とか、年号を変えてぐぐってみよう！
追記：
site:www.rand.org/pubs/research_memoranda/2005/
とかもためしてみてね。ペーパーとメモの違いは正直よくわかりません
