計算機科学と計算幾何学 草苅 良至 12 月学科会議

計算機‐科学について

「計算」について考える学問 機械的な操作で行えること。 処理。 理想的なコンピュータ（＝計算機モデル） での基本動作の組み合わせ。 計算機科学とは 英語だと、 Computer Sience です。

計算機モデル 「計算」を考えるとき、 実行する機械毎の違いを考えたくない。 理想的な計算機（＝計算機モデル）を考えます。 チューリング機械 RAM （ Random Access Machine) 有限状態 制御部 ヘッド 無限テープ チューリング機械 ・計算機モデル例 実は、これらのモデル間には能力の 差はない。 1930’ 年代 Church-Turing の提唱 λ 計算等

アルゴリズムと問題 「アルゴリズム」とは「問題」を解くために、 モデル上で「基本操作」（命令）を 有限個組み合わせてできる「計算」。 連立方程式を解く 色々な問題 データのソート。 素因数分解。 命令 四則演算 代入演算 比較演算 フーリエ変換。 組み合わせ方 アルゴリズム

問題の大きさ 同じ問題でも、 その大きさ毎に必要な演算数（総ステップ数、計算時間）は異なる。 n 変数の連立方程式 大きさも考えた問題 n 桁の足し算 n 個のデータに対する、ソート n 桁の数の素因数分解 通常入力サイズは、 n,m 等の文字で表します。 n 個のデータに対する、離散フーリエ 変換

アルゴリズムの評価 アルゴリズムは通常「問題」を解くためのものであり、 どんな大きさでも解けないといけない。 総ステップ数を、入力サイズ n の関数 T(n) で評価します。 （使用メモリ量を、入力サイズ n の関数 S(n) で 評価することもあります。）

関数の分類（オーダー記法） 対数（時間） 多項式（時間） 指数 ( 時間）

計算時間と関数 n 1000MIPS(1 秒間に 10 億回の演算可能）の コンピュータで考えてみましょう。 サイズ 関数 1秒1秒 20 秒 30 秒 40 秒 50 秒 1分1分 10 秒 1 分 40 秒 約１日 16 分 40 秒 約 2 時間 47 分 0 ． 01 秒 1秒1秒 1 分 40 秒 約 2 時間 47 分 約 11.5 日 約 3.2 年 秒約 約 3 京世紀 甚大

関数の概形 漸近的評価がいいアルゴリズムは、 多量のデータを扱うときに力を発揮する。

計算機科学の目的 「問題」 解けるか？ 計算不可能 計算可能 実用的に 解けるか？ 指数時間 多項式時間 効率的に 解けるか？ 対数時間 これら、一連の問いに答えるため学問。 さらに、例えば同じ でも、より係数を小さく することも目的になります。

計算‐「幾何学」について

計算幾何学とは、 図形・幾何情報を元に、いかに「計算」できるかを考える学問。 計算機科学の１分野。 計算機科学 計算幾何学 英語だと、 computational geometry.

計算幾何学の応用 CAD GUI VLSI のレイアウト設計 CG バーチャルリアリティ 多次元データ処理 地理情報処理 ロボティクス

計算幾何学の歴史 1978 年 I.Shamos の博士論文「 Computational Geometry 」 年から 幾何学が 3000 年以上の歴史を持っているのに対して、 高々２０年強の歴史しかない。 （もっとも、計算機科学自体でも、 60 年ぐらいなのですが。）

「幾何学」と「計算幾何学」 幾何学では、（数学的）関係に主眼が置かれることが多かった。 これに対して計算幾何学は、『所望の値をどれくらいの「計算」で 求めれるか』まで考える。 a b c 幾何学 計算幾何学 直角を挟む２辺の ２乗和は、 斜辺の２乗に等しい。 斜辺は、 ２回の乗算と、 １回の加算と、 １回の平方根で 求まる。

計算幾何学の代表的問題 凸包問題 幾何的探索問題 最も外側のデータを求める 最も近いデータを求める。

幾何アルゴリズム例 凸包問題 時間 簡単な方法： １．全ての 2 点間に直線を引く。 ２．各直線に対して、 全ての点が同じ側にあるか調べる。 時間 賢い方法：（略） 本 時間／本

扱う問題の複雑化 計算対象（点、線、面等）が、 低次元空間内に初めから固定されて動かない。 計算対象が、動く。 計算対象の個数が 増減する。 高次元の 計算対象を扱う。 折れ線図形の 連続変形問題

折れ線図形（ Linkage ）とは バー ジョイント バー : 節点間の線分 ジョイント : 各節点 折れ線図形：長さの変わらない線分が 各節点で接続している図形

折れ線図形の（平面）連続変形

折れ線図形で禁止されている連続変形 バーは接続しているジョイントから離れない。 バーの長さは変形中に変わらない。

平面変形で禁止されている動 き バーは、平面内だけを移動する。 変形中に、２つのバーは交差しない。

折れ線図形の平面連続変形問題 バーはジョイントから離れない。 バーの長さは変わらない。 図形は平面上だけで変形する。 変形中に、どの２本のバーも交差しない。 これらの条件を満たしながら、 初期配置から、望みの配置に連続変形できるか？ 何回の動作で望みの配置にできるか？ 実際の動作計画を求めるのに必要な計算量は？

応用 バーロボットアーム 動作計画 連続変形問題 建築物の剛性判断 ロボットアームの動作計画、動作解析 間接ジョイント 骨組み折れ線図形 剛性判断 連続変形問題

折れ線図形の連続変形問題 計算機科学 計算幾何学 グラフ理論 折れ線図形問題

平面連続変形の研究１（道状折れ線図 形） 道状の折れ線図形は、 同じバーの系列を持つどんな配置にも平面連続変形できる。 大工の経験則１ 1970 年代から 1990 年代の未解決問題 道状の折れ線図形は、 どんな初期配置からでも直線状に平面連続変形できる。 大工の経験則 １ ’

全ての道状折れ線図形は、 平面連続変形で直線状にできる。 定理１ [Connelly et al. ’00]

平面連続変形の研究２（木状折れ線図 形） 木状の折れ線図形は、 どんな初期配置からでも “ 直線状 ” に平面連続変形できるか？ 問題 ２

平面連続変形では、 直線化できない木状折れ線図形が存在する。 定理２ [Biedl et al. ’98]

新たな問題 全ての木状の折れ線図形は、 平面連続変形で “ 直線状 ” にできるか？ 問題 ２ どのような木状の折れ線図形が、 平面連続変形で “ 直線状 ” にできるのか？ 問題 ３ 単調な木であれば直線化できる。

単調な道と単調な木 （ｘ方向に）単調な道 （ｘ方向に）単調な木 r 根

単調でない道と単調でない木 （ｘ方向に）単調でない道 （ｘ方向に）単調でない木 r 根

結果 [kusakari et. al. '01] r 根 単調な木は、 O(n) 回の変形で直線化できる。 直線化の方法を O(n log n) 時間で、 O(n) の記憶量で求めることができる。 r n : 木のジョイント数 n -1: 木のバー数

これからの計算機科学につい て、 計算原理の多様化 並列・分散アルゴリズム（同時に複数台の計算機を使える） 確率アルゴリズム（計算機がサイコロを振れる） 量子アルゴリズム（計算が振幅で遷移する） 解決困難な問題に挑戦 近似アルゴリズム（最適解をあきらめる） ヒューリスティック（正当性をあきらめる） データの制限をゆるめる オンラインアルゴリズム （アルゴリズム開始時に、全入力データがわからない） ロバストアルゴリズム （データ自身に誤差があるかもしれない）

補足 これ以降のスライドは、 単調な木の直線化手法のより詳しく説明するためのものです。

アイディア １ 引っぱり操作 rr この引っぱり操作だけで直線化できる。 どの順序で、引っぱり操作を行なうかが残る問題。

順序グラフＧ 木Ｔ Ｔ 順序グラフの点集合は、木のバー集合 順序グラフの辺には、 接続辺と可視辺との 2 種類ある。 順序グラフ アイディア ２

接続辺 木Ｔ接続辺集合Ｅ con 木で接続している２辺間に、 （根から辿る順序で） 有向辺を引く。

可視辺集合Ｅ 可視辺 木Ｔ vis 互いに見える２本のバー間に （左から右に）有向辺を引く。

可視対集合Ｅ vis 接続対集合Ｅ con 順序グラフＧ Ｔ

単調な木の順序グラフの性質 順序グラフＧ Ｔ 単調な木の順序グラフには、 有向閉路がない。 全てのバーにとトポロジカルソートで全順序が付けれる。

引っ張り操作の順序 順序グラフＧ Ｔ 木Ｔ

アルゴリズム １．接続辺集合Ｅ を求める； ２．可視辺集合Ｅ を求める； ３．順序グラフＧ を求める； ４．トポロジカルソートでバーの全順序を求 める； ５．得られた全順序の逆順 に引っぱり操作を行なう． con vis T r 引っ張り操作を２回適用後 r 初期配置

計算量 １．Ｏ（ n) 時間 ２．Ｏ（ n log n) 時間（平面走査法） ３．Ｏ（ n) 時間 ４．Ｏ（ n) 時間 ５．Ｏ（ n) 時間 n : 木のジョイント数 n -1: 木のバー数 １．接続辺集合Ｅ を求める； ２．可視辺集合Ｅ を求める； ３．順序グラフＧ を求める； ４．トポロジカルソートでバーの全順序を求 める； ５．得られた全順序の逆順 に引っぱり操作を行なう． con vis T

可視辺集合Ｅ 可視辺の求め方 木Ｔ vis 平面走査法

下界 ソート問題を帰着できるので、 Ω （ n log n) 時間必要。 数その傾きを持つバー 0.1 １ 20 2

結論 r 根 単調な木は、 O(n) 回の変形（引っ張り操作） で直線化できる。 直線化の方法を最適な O(n log n) 時間 O(n) 記憶量 で求めることができる。 r n : 木のジョイント数 n -1: 木のバー数

課題 放射状に単調な木の直線化 順序グラフの単純な拡張だと、 有向閉路ができることがある。