数学

2進数で有限小数となる10進有理数

10進法で表記した有理数を2進法の小数で表記したときに,有限の桁数で表すことができる有限小数になるための特徴付けを与える.この応用として10進法で表記した有限小数が計算機上で誤差を含む数値かどうかの判定ができる.

点と超平面の間の距離

次元ユークリッド空間上の点と超平面の間の距離を求める.点 と超平面 との間のハウスドルフ距離は, である.

Prüfer sequence

ラベル付き木から prüfer sequence(プリューファ列)と呼ばれる整数列への一対一対応を説明します.

再構成問題

グラフ理論の有名な未解決問題である再構成予想について紹介します.

頂点被覆問題のNP完全性

頂点被覆問題がNP完全であることを示します.頂点被覆問題のNP完全性から独立集合問題とクリーク問題がNP完全であることが導かれます.

毎日が誕生日パーティー

問題. 毎日が誕生日パーティー(勝手に命名) 1年が365日の世界に, 人の社員がいる.各社員の誕生日は365日の間に等確率で分布する.このとき,どの日にも少なくとも1人の社員が誕生日となる確率を求めたい(誕生日の人がいるとパーティー). (1) が 365 …

DAGの最小道被覆問題

問題. DAGの最小道被覆問題 DAG が与えられる. の最小道被覆を求めよ.

比較可能グラフは理想グラフ

比較可能グラフが理想グラフであることを示します.

グラフ描画用のツール

グラフを描画するためのツールをまとめておきます.他に知っている方は教えてくださると喜びます.