参考→こちらのPPTはよい Burrows-Wheeler変換の特徴をそのPPTから抜粋 可逆変換 圧縮しやすい(同じ文字が並びやすいから) 元の文書なしで全文検索が可能 部分文字列・部分一致文字列探索に向いている→次世代シークエンサーのマッピングに応用 接尾辞木の節点…

クリークとは、グラフの一部(部分グラフ)であって、その部分グラフのすべてのノード間にエッジがあるようなもの これの探索には、1970年台に出たBron-Kerboschアルゴリズムというものが、現在も使われている。 Wikipedia 原論文 Bron-Kerboschアルゴリズムの…

ハムサンドイッチ定理

いくつかの発展のためのコメントがあるが、このブログの性格上、もっとも発展が望ましい方向は 「離散幾何学と組合せ幾何学」への発展で、参照文献はこちら組合せ幾何学のアルゴリズム作者: Herbert Edelsbrunner,今井桂子出版社/メーカー: 共立出版発売日: …

美術館問題 多角形内に最小個数の点をとり、多角形内のすべての点が「見える」ようにするための「監視員配置点」を求める問題 美術館定理 単純多角形の三角形への分割 - 警備員巡回路問題 美術館問題では、監視員は不動だったが、１人の監視員が移動してもよ…

幾何的探索 幾何的探索の前に、スカラー的探索とは 多数のデータがあって、該当データを探すとき、データに決まりがなければ、しみつぶしにするしかない データに順序があれば、その順序を利用して探索をかける(ソートしたリストを用いた２分探索) データに…

アレンジメントとは ２次元の場合：直線による平面の分割 ３次元の場合：平面による空間の分割 分割は、点、辺、セル(いくつかの辺に囲まれる凸領域)などを要素として構成されるが、それらの間の接続関係 アレンジメントの組合せ特性と構成アルゴリズム 単純…

Wikipediaの記事 ボロノイ図とは 自然現象に頻発し、既存の自然科学・社会科学ですでに利用されている 数学の対象であり、既存の幾何構造の理論などを利用可能 直接の関連の見出しにくい幾何問題にも応用が利くことが多い ボロノイ図の定義と性質 母点 ボロ…

凸包のアルゴリズムの出力 凸包を構成する点集合の決定 凸包構成点の周回順序の決定 包装法 確定した凸包構成点から次を探す Grahamの走査法 ある点からの偏角による位置の評価とソート 逐次構成法 部分データでの解を求め、データを加えながら、解を変更し…

２線分の交差をどう判定するか ｎ本の線分の交差 ２線分の組合せが多くなる：取り扱いの工夫が必要 ２分探索木を用いた対処 水平・垂直線分の場合 任意方向線分への拡張 応用(２次元表示(グラフィクスが中心)) 隠面除去 線形分離・凸多角形の交差 長方形交差

計算幾何学 幾何学的な問題を扱うアルゴリズムの設計と解析の学問。幾何学的な対象は、従来の情報処理方式と異なったアプローチを要することが多く、独特な特徴を備える 幾何用語 d次元ユークリッド空間 点・直線・平面・線形多様体・多面体 線分 凸領域・凸…

計算幾何学入門―幾何アルゴリズムとその応用作者: 譚学厚,平田富夫出版社/メーカー: 森北出版発売日: 2001/10メディア: 単行本購入: 1人 クリック: 23回この商品を含むブログ (5件) を見る

3.0 線形計画問題(Linear Programming;LP) においての制約のもとでを最大化せよ、という問題である 意味を書き下すと、m個の１次線形不等式を制約条件とし、その制約条件を満たす、n個の値のセット(ベクトル)の中で、によって定められるスカラー量を最大にす…

グラフがある。それは、次のようにできているとみなせるとする。 １つの閉路がある。これをG0とする。その閉路と１点のみを共有する閉路か、その閉路と２点のみをい共有するパスがある。このG0＋閉路またはパスをG1とする。このG1|G0(G1からG0をのぞいた部分…

グラフの実装表現 接続行列表現 行に点、列に辺をとり、点が辺の端点なら１(始点なら１、終点なら−1)、そうでなければ、０ 必要領域：O(点の数ｘ辺の数) 隣接行列表現 行と列に点をとり、点のペア間に辺があれば１、なければ０。向きを考慮するときは辺があ…

グラフにおける閉路とカット 閉路はぐるっと一巡するタイプのグラフ 定義としては、点と辺を交互にたどってもとの点に戻ってくるような点と辺の集合である。ただし、このとき点と辺はそれぞれ１度ずつしか使用しないし、１度は使用するものとする。 カットは…

点彩色問題の位置 集合があり、その部分集合の作る集合の集合(べき集合)があるときに、与えられた条件のもとでの最適な(ある指標を最小化する)べき集合の組み合わせを求める問題の１つ 最小集合カバー問題と呼ばれる べき集合数は、元の集合の要素数に対して…

O(n log n)時間でのソート。この時間は、ソート対象列のデータ型・データ構造の条件を用いない場合には、最短なものの１つ。 本項中のその他の記述。「任意の再帰アルゴリズムを計算時間を増加させることなく、再帰呼び出しなしのアルゴリズムで書ける」 リ…

すべての場合を数え上げ(enumeration)ることが膨大なので、それを省略することが本書の中心であるが、そうはいっても、数え上げたいことはある。n個の要素の順列は、。この方法はであって、限界は早い。 例として、複数の２次元座標空間上の点の並び替えて、…

教科書 組合せ最適化-理論とアルゴリズム 作者: B.コルテ, J.フィーゲン, 浅野孝夫, 平田富夫, 小野孝男, 浅野泰仁 出版社/メーカー: シュプリンガー・フェアラーク東京 発売日: 2005/11/15 メディア: 大型本 駆け足で読めるかどうか、少々不安。全部読むか…

URLメモ

URLメモ

ryamadaのコンピュータ日記の記事へリンク：時間計算量と領域計算量

ryamadaのコンピュータ日記の記事へリンク：時間計算量クラス

ryamadaのコンピュータ日記の記事へリンク：計算可能性

ryamadaのコンピュータ日記の記事へリンク：計算モデル

ryamadaのコンピュータ日記の記事へリンク：アルゴリズム

グラフの問題には、アルゴリズム上の難問が多く知られている。アルゴリズム上の難問は計算量などによって定義・分類されるが、そのための基礎知識のために『アルゴリズムと計算量』(臨時別冊 数理科学 SGCライブラリ43)谷 聖一 サイエンス社おすすめ度★★★☆☆…

ryamadaのコンピュータ日記の記事へリンク：確率的アルゴリズムと近似アルゴリズム

『Algorithms in C アルゴリズム 第３巻 グラフ・数理・トピックス』近代科学社 R.セジウィック 著 野下浩平・星守・佐藤創・田口東 共訳 おすすめ度★★★★☆、ただし、新版が出ている模様。 ３分冊の１冊 アルゴリズムC〈第3巻〉グラフ・数理・トピックス 作者…