アルゴリズム

Burrows-Wheeler変換

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

クリークを探せ

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

ハムサンドイッチ定理

駆け足で読む計算幾何学入門 第8章 おわりに

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

駆け足で読む計算幾何学入門 第7章 警備問題

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

駆け足で読む計算幾何学入門 第6章 幾何的探索

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

駆け足で読む計算幾何学入門 第5章 アレンジメント

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

駆け足で読む計算幾何学入門 第4章 ボロノイ図

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

駆け足で読む計算幾何学入門 第3章 凸包の計算

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

駆け足で読む計算幾何学入門 第2章 交差

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

駆け足で読む計算幾何学入門 第1章 はじめに

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

駆け足で読む計算幾何学入門〜幾何アルゴリズムとその応用〜

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

線形計画法の用語 3 線形計画法 駆け足で読む B.コルテ/J.フィーゲンの 組合せと最適化-理論とアルゴリズム

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

アルゴリズムグラフの耳分解 2.3 連結性 (グラフ) 駆け足で読む B.コルテ/J.フィーゲンの 組合せと最適化-理論とアルゴリズム

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

2.3 連結性 (グラフ) 駆け足で読む B.コルテ/J.フィーゲンの 組合せと最適化-理論とアルゴリズム

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

2.2 木、閉路、カット (グラフ) 駆け足で読む B.コルテ/J.フィーゲンの 組合せと最適化-理論とアルゴリズム

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

16.4 グリーディ彩色アルゴリズム 駆け足で読む B.コルテ/J.フィーゲンの 組合せと最適化-理論とアルゴリズム

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

1.2 マージソート 駆け足で読む B.コルテ/J.フィーゲンの 組合せと最適化-理論とアルゴリズム

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

1.1 列挙 駆け足で読む B.コルテ/J.フィーゲンの 組合せと最適化-理論とアルゴリズム

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

教科書 駆け足で読む B.コルテ/J.フィーゲンの 組合せと最適化-理論とアルゴリズム

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

分枝限定法、切除平面法、分枝切除法

URLメモ

メタ戦略

URLメモ

時間計算量と領域計算量

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

時間計算量クラス

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

計算可能性

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

計算モデル

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

アルゴリズム

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

グラフの問題は難問が多い

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

確率的アルゴリズムと近似アルゴリズム

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

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