タグ

アルゴリズムと数学に関するyuisekiのブックマーク (18)

  • メトロポリス・ヘイスティングス法 - Wikipedia

    このアルゴリズムは1953年にボルツマン分布のための特殊形で発表したニコラス・メトロポリスらによって提案され.[1] 、1970年に W.K. ヘイスティングスによって一般化された[2]。ギブスサンプリング法は棄却されることのないM-H アルゴリズムと捉えることが出来て、調整パラメータが少ない点で構成が容易であるが、応用範囲は狭まる。 M-H アルゴリズムを用いると、確率分布 の確率密度関数もしくは確率関数(煩雑なので、以下では「確率密度関数」に統一する)に比例する関数が計算できるならば、 いかなる確率分布 からでも、基的には乱数列を得ることができる。 統計学や統計物理学では、しばしば興味のある確率密度関数の定数倍しかわからないことがある。定数倍部分がわからなくても乱数の生成が可能である点はM-H アルゴリズムの大きな長所である。 M-H アルゴリズムは乱数列を生成する。 乱数列の長さが

    メトロポリス・ヘイスティングス法 - Wikipedia
  • マルコフ連鎖モンテカルロ法 - Wikipedia

    マルコフ連鎖モンテカルロ法(マルコフれんさモンテカルロほう、英: Markov chain Monte Carlo methods、通称MCMC)とは、求める確率分布を均衡分布として持つマルコフ連鎖を作成することによって確率分布のサンプリングを行う種々のアルゴリズムの総称である。具体的には、同時事後分布に従う乱数を継時的に生成する。代表的なMCMCとしてメトロポリス・ヘイスティングス法やギブスサンプリングがある。 MCMCで充分に多くの回数の試行を行った後のマルコフ連鎖の状態は求める目標分布の標として用いられる。試行の回数を増やすとともにサンプルの品質も向上する。 求められる特性を持つマルコフ連鎖を作成することは通常難しくない。問題は許容できる誤差内で定常分布に収束する試行の回数を決めることである。適切な連鎖なら任意の位置から始めても定常分布に速く達し、これを高速混合(rapid mix

  • 数学・アルゴリズム研究室

    当コーナーでは、ゲーム制作や一般アプリケーション開発といったプログラミングの「土台」となる各種アルゴリズムや初級レベル数学の基的概念を確かめるプログラムを作って試してみます。コードの中で何をしたいのか、具体的な「手順」や数学的な背景を考え、それをプログラミング言語の変数やデータ構造、制御構造などで実現していきましょう。 ただ、私自身が数学に関しては素人なので、たいしたことはできません。内容も無保証ですので、ご注意ください。 コーナーでは、Javaアプレットを使用しているページがあります。Javaアプレットが埋め込まれているページでは、プラグインがないとプログラムが実行されません。 数式処理への第一歩>足し算(1999/10/ 6) 連結リスト(1999/10/ 6) 参照(ポインタ)の繋ぎあわせでデータを保持。 16進文字列と数値の変換(2000/ 6/20) 文字列の検索(1999/

  • Amazon.co.jp: 最適化アルゴリズム: 長尾智晴: 本

    Amazon.co.jp: 最適化アルゴリズム: 長尾智晴: 本
  • LAPACKサンプルプログラム目次

    LAPACKサンプルプログラム目次 ホーム >LAPACKサンプルプログラム目次 イントロダクション 実線形方程式 複素線形方程式 実線形最小二乗 複素線形最小二乗 実一般化線形最小二乗 複素一般化線形最小二乗 実対称固有値問題 複素エルミート固有値問題 実非対称固有値問題 複素非対称固有値問題 実一般化対称固有値問題 複素一般化エルミート固有値問題 実一般化非対称固有値問題 複素一般化非対称固有値問題 実特異値分解 複素特異値分解 実一般化特異値分解 複素一般化特異値分解 実 QR 分解 複素 QR 分解 計算ルーチン ご案内 LAPACKサンプルが付属! Fortran Builder NAG Fortran コンパイラ Fortranコンサルティング 関連情報 サンプル実行手順 NAG数値計算ライブラリ Privacy Policy / Trademarks

  • 数値計算 - MacWiki

    数値計算ライブラリ[編集] ATLAS[編集] Automatically Tuned Linear Algebra Software (ATLAS) http://math-atlas.sourceforge.net/ https://sourceforge.net/project/showfiles.php?group_id=23725 Absoft Fortran には、ATLAS の 64bit 版が付属しているそうです。 http://www.hulinks.co.jp/software/pf_mac/section01.html Bayes++[編集] Bayesian Filtering Classes for C++ Kalman filter や各種の非線型フィルタの数値計算ライブラリ http://bayesclasses.sourceforge.net/Bayes++

  • TOKUTEI: algorithm

    Scientific Research of Priority Areas: Algorithm Engineering as a New Paradigm: A Challenge to Hard Computation Problems

  • Algorithm Database

    無向グラフ スケジューリング 量子計算(グローバーのアルゴリズム) 最小カット 投票力指数 (CGI) チャネル割当問題 共有区間列挙問題(CGI) 2次元ボロノイ図構成 グラフエディタの作成(群馬大学 中野研究室) 辺連結度増大アルゴリズム 3次元凸包 グラフ分割問題 最大クリーク問題 巡回セールスマン問題 最短路問題 ハイパーグラフの極小横断 new!!誤差拡散法 (ブラウザの設定で "Javaを有効" にして下さい。)

  • 幾何アルゴリズム

    格子充填曲線の生成プログラム(n×n の2次元格子の、左上隅からはいり右下隅から抜ける、ランダムなハミルトン経路を生成するアルゴリズムで)

  • Sugihara's Integer-Arithmetic Geometric Software

    幾何計算ソフトウエア(製作:杉原厚吉) 以下に掲げるコンピュータプログラムは、「暴走の心配のない幾何アルゴリズム の設計法」とその周辺技術として私たちが長年研究してきた 位相優先法、整数帰着法、記号摂動法、 遅延評価加速法などを組み合わせて作ったものです。これらは、私のコーデイングに ミスさえなければ、決して暴走しない(どんなに意地悪な入力データを与えても 正常に計算を遂行する)ことが理論的に保証されています。さらに, すべてのプログラムにおいて,オーダの意味で計算量最小のアルゴリズムを 採用しています. これらのプログラムを,下の使用条件に同意される方に公開します. 同意される方は, 同意書 をコピーし, それに氏名,連絡先などを記入して,製作者まで電子メールまたはファックス または郵便でお送り下さい.いただいた同意書に対して特にご返事は 差し上げませんが、そのあとはご自由にコピーして

  • 固有値・固有ベクトルって何に使うの?

    ふと、固有値・固有ベクトルって何がそんなに嬉しいのか?何の役に立つのか?と思っていろいろ調べていた。(対角化してべき乗計算が速くできますだけだと、ちょっと勉強する動機づけとしては弱い。。)そういえば、一年前くらいに読んだpage rankの論文に固有値・固有ベクトルが使われていたのを思い出したので、これをちょこっと紹介。(解釈に間違いなどありましたら、ご指摘ください。) まず、page rankアルゴリズムについて。これは、いわずと知れたgoogleの検索処理において中心的な役割を果たす処理です。page rankの基的な考え方は、”たくさんリンクを張られているサイトほど重要なサイトである”ということです。つまり、たくさんリンクを張られているサイトが検索で上位に現れます。加えて、同じリンクを張られているでも、重要なページ/人気のあるページからリンクを張られているのか、重要でない/人気でな

  • クヌース–モリス–プラット法 - Wikipedia

    クヌース–モリス–プラット法(Knuth–Morris–Pratt algorithm、KMP法と略記)とは、文字列検索アルゴリズムの一種。テキスト(文字列)Sから単語Wを探すにあたり、不一致となった位置と単語自身の情報から次に照合を試すべき位置を決定することで検索を効率化するアルゴリズムである。 このアルゴリズムは1977年、ドナルド・クヌースと Vaughan Pratt および(単独で)J. H. Morris が発明し、3人共同で発表した。 項目では文字列を表すにあたって、0 からインデックスを開始する配列を用いる。従って(後述の)単語 W 内の文字 'C' は W[2] と表される。

  • 矢沢久雄の情報工学“再”入門

    ITエンジニアの皆さんなら,一度は「情報工学」を学んだことがあるかもしれない。しかし,その知識をしっかり身に付けている人は少ないのではないだろうか。連載では,プロフェッショナルの必須知識と言える情報工学の様々な理論について解説していく。 第1回 アルゴリズムと計算量---「計算量理論」を理解し,アルゴリズムを評価する 第2回 形式言語とオートマトン---「文」のルールを知り,機械に解釈させる 第3回 符号化理論---あらゆる情報を数値で扱う「符号化」理論を知る 第4回 ブール代数---論理を「1」と「0」で表す「ブール代数」を理解する 第5回 グラフ理論---要素同士のつながり方を「点」と「辺」で分析する 第6回 オペレーションズ・リサーチ(OR)---数学モデルを駆使して,経営戦略を立案する 第7回 集合論---数学の「集合論」にRDBの正体を見る 第8回 RDBの正規化理論---から

    矢沢久雄の情報工学“再”入門
  • データマイニングで使われるトップ10アルゴリズム - データサイエンティスト上がりのDX参謀・起業家

    2006年のデータマイニング学会、IEEE ICDMで選ばれた「データマイニングで使われるトップ10アルゴリズム」に沿って機械学習の手法を紹介します(この論文は@doryokujin君のポストで知りました、ありがとうございます!)。 必ずしも論文の内容には沿っておらず個人的な私見も入っていますので、詳細は原論文をご確認下さい。また、データマイニングの全体観をサーベイしたスライド資料がありますので、こちらも併せてご覧下さい。 データマイニングの基礎 View more presentations from Issei Kurahashi 1. C4.5 C4.5はCLSやID3といったアルゴリズムを改良してできたもので、決定木を使って分類器を作ります。決定木といえばCARTが良く使われますが、CARTとの違いは以下のとおりです。 CARTは2分岐しかできないがC4.5は3分岐以上もできる C

    データマイニングで使われるトップ10アルゴリズム - データサイエンティスト上がりのDX参謀・起業家
  • 粒子フィルタ - Wikipedia

    この項目「粒子フィルタ」は途中まで翻訳されたものです。(原文:en:Particle Filter 15:26, 20 September 2007) 翻訳作業に協力して下さる方を求めています。ノートページや履歴、翻訳のガイドラインも参照してください。要約欄への翻訳情報の記入をお忘れなく。(2007年10月) 粒子フィルタ(りゅうしフィルタ、英: particle filter)や逐次モンテカルロ法 (ちくじモンテカルロほう、英: sequential Monte Carlo; SMC)とは、シミュレーションに基づく複雑なモデルの推定法である。1993年1月に北川源四郎がモンテカルロフィルタの名称で[1]、1993年4月にN.J. Gordonらがブートストラップフィルタの名称で[2]同時期に同じものを発表した。 この手法はふつうベイズモデルを推定するのに用いられ、バッチ処理であるマルコフ

  • 幾何学・CG のアルゴリズム集

    作成中 スマートフォン (AndroidiPhone) など最近のモバイル機器には3軸地磁気センサ (電子コンパス) と3軸加速度センサ (モーションセンサ) を搭載しているものがある.これらを用いると,基準となる3方向 (水平磁北方向,水平東方向,鉛直方向) をそれなりの精度で求めることができ, さらにその結果を用いて端末の姿勢 (向いている方向) や方位角 (azimuth), 傾き角 (roll,pitch) を計算することができる. 余談だが,Android のマニュアルにある azimuth の定義はおかしい (はっきり言って間違っている) のでセンサアプリ開発者は注意. この定義によると水平面に対する画面の傾きが大きくなるほど azimuth の誤差が大きくなり,画面を垂直にすると全く方位とは無関係な値になる. 実際,ストリートビューに定義どおりの azimuth を渡した場

  • 画像処理におけるアルゴリズム

    ここでは各画像処理におけるアルゴリズムを簡単に解説する。 2値化 明るさ調整 色成分の抽出 色反転 コントラスト調整 切り出し ガンマ補正 グレイスケール化 増色 画像枠付加 鏡像反転 ノイズ除去 輪郭抽出 輪郭追跡 拡大縮小 任意角回転 セピア調化 ぼかし 2値化 指定画像を白と黒の2階調の画像に変換する処理であり、研究で作成した2値化処理は単一手動閾値方式、P-タイル法、また、誤差分散法およびその拡張型である Floyd&Steinberg 型誤差分散、Jarvice,Judice&Ninke 型誤差分散の5つである。 次にそれぞれのアルゴリズムについて解説する。 単一手動閾値方式 指定された色深度を基準として、その値より入力画素の色深度値が明るければ白、暗ければ黒色として2値化する。下の式を用いている。 このとき、出力画像は初期状態で黒色となるので、入力画像の画素値が閾値以

  • 病みつきになる「動的計画法」、その深淵に迫る

    数回にわたって動的計画法・メモ化再帰について解説してきましたが、今回は実践編として、ナップサック問題への挑戦を足がかりに、その長所と短所の紹介、理解度チェックシートなどを用意しました。特に、動的計画法について深く掘り下げ、皆さんを動的計画法マスターの道にご案内します。 もしあなたが知ってしまったなら――病みつきになる動的計画法の集中講義 前回の『アルゴリズマーの登竜門、「動的計画法・メモ化再帰」はこんなに簡単だった』で動的計画法とメモ化再帰を説明しましたが、前回の説明ではまだ勘所をつかめていない方がほとんどでしょう。そこで、これらを完全にマスターするため、今回はもう1つ具体例を挙げながら練習したいと思います。 どういった問題を採用するかは悩みましたが、非常に有名な「ナップサック問題」を取り上げて説明します。 ナップサック問題とは以下のような問題です。 幾つかの品物があり、この品物にはそれぞ

    病みつきになる「動的計画法」、その深淵に迫る
  • 1