こんなところにグラフ理論が!

岩波講座 ソフトウェア科学〈〔環境〕5〉プログラミング言語処理系」、第8章「コード生成」を読み終わった。

レジスタ割当てにグラフ理論の k-彩色問題が使われていたのは面白かった。というか感動した。グラフ理論による問題の解決ってなんでこう「おお!」と思わせるものが多いのかなあ。体系的にちゃんと勉強したことはないけど、一度腰を落ち着けて勉強したいな、グラフ理論

グラフ理論といえばついこの間、深夜の NHK教育テレビ秋山仁がまさにこの k-彩色問題をやっていた。深夜にたまたまチャンネルを合わせただけなんだけど、ついつい最後まで見てしまった。そしてやっぱり「おお!」と感動した。

限られたリソースを競合なく割当て、ときたら k-彩色問題。
このパターン、重要だぞ。