ここギコ！: GPS高度、ジオイド高、標高の関係
GPSでの高度の扱いについて知るために、ちょっとGPSトラッキングを行って実験をしてみました。 より大きな地図で ジオイド調査 を表示 ▲ iPhoneのGPSトラッカーで取得したトラッキングデータ。 ▲ 赤は行きの林試の森付近データ、青は帰りのかむろ坂付近データ。 この区間を歩いた際の、GPSの高度データも当然残っているので、それをグラフ化してみました。 同時に、こちらのサイトから取得できる、トラッキングされた経緯度での標高のデータを取得し、一緒にグラフ化してみました。 ▲ 上が林試の森付近のGPS高度/標高プロファイル、下がかむろ坂付近のそれ。 ▲ 両者間に30mくらいの差がコンスタントに存在。 すると、GPS高度と標高のデータの間に、30mくらいの差があるのが判ります。 これは何なのでしょう？ GPSの取得誤差？標高のデータ取得元に、『算出される標高には最大で50m程度
chichiue.hahaue.com
－ アルゴリズムの探求とJava&Scalaによる実装 － Revised : 2020/07/24 Since : 2006/07/07 圧縮 ｜ 暗号 ｜ 誤り訂正 ｜ 数 ｜ ふぼじぇくと(blog) ｜ 本棚 ふぼじぇくと（旧 夢幻プロジェクト） い～～～っぱいの期待を乗せた夢のプロジェクトとして ぜ～～～ったい完成しないだろう幻のプロジェクトとして 無限の可能性を秘めながら出航する 現在航海中のこのプロジェクトを 父母のコミュニケーションツールとして活用できないかと公 開する “ふぼじぇくと”として新たな旅へ・・・ CONTENTS 圧縮 圧縮の仕組み 情報量の定義、モデル化、符号化、数と符号 連長圧縮、ブロックソート、前方移動 算術符号、レンジコーダ ＬＺ符号、ハフマン符号 暗号 暗号の仕組み 共通鍵方式、共通鍵方式、ハイブリット方式、ハッシュ関数 RSA、ElGamal、楕円
ALGORITHM NOTE 動的計画法
n × n のマス目のそれぞれに 1 または 0 が記してあり、その中から 1 だけから成る最大の長方形の面積を求めて下さい。 これは前に考えた正方形探索の応用で、今回は最大の長方形を探します。この問題も正方形探索で用いたアルゴリズムを応用して動的計画法で解くことができますが、正方形探索ほど単純な式では解決できません。左上角から右下角に向かって個々の要素を計算していく過程で、既に計算された左と上の要素を利用していきますが、長方形探索の場合、W[i][j] の値はそこから左上方向に向かってできる正方形の辺の長さではなく、そこから左上方向に向かってできる全ての長方形の情報を記録する必要があります。このアルゴリズムの詳しい解説が、プログラム・プロムナードに掲載されています。このアルゴリズムは、現在の要素を求めるために重複を避けながら左と上の要素をマージしたりと、プログラムがやや複雑になります。
アルゴリズムイントロダクション輪講 動的計画法の発表資料 - てっく煮ブログ
2009年3月2日に、はてな京都オフィスで開催された アルゴリズムイントロダクション輪講 の第12回で「動的計画法」について発表しました。資料をここにおいておきます。View more presentations from nitoyon.分かりやすくしようと気合を入れてまとめたら165ページの大作になっちゃいました。無駄に長くてすいません。アルゴリズムの設計と解析手法 (アルゴリズムイントロダクション)作者: T.コルメン, R.リベスト, C.シュタイン, C.ライザーソン, Thomas H. Cormen, Clifford Stein, Ronald L. Rivest, Charles E. Leiserson, 浅野哲夫, 岩野和生, 梅尾博司, 山下雅史, 和田幸一出版社/メーカー: 近代科学社発売日: 2007/03メディア: 単行本
ソートについて
ソートについて はじめに n個の要素がある配列をソートする方法を挙げていく。 バブルソート バブルソートは最も簡単な方法です。 単純に隣同士を比較して順番が逆なら入れ替えるという操作を 一番目の要素から順番に行っていきます。 この操作をn回行うと、要素の中でもっとも大きな要素が一番n番目に来ます。 そして、また一番目の要素からn-1回操作を行います。 これで二番目に大きな要素がn-1番目に来ます これを繰り返してソートします。 サンプルコード //バブルソート void BubbleSort(int Data[], int n) { int BeginPlace, ComparePlace; //比較を始める位置を最初からn-1まで変えていく for(BeginPlace = 0;BeginPlace Data[ComparePlace])
kd木 - Wikipedia
3次元のkd木。根セル（白）をまず2つの部分セルに分割（赤）し、それぞれをさらに2つに分割（緑）している。最後に4つのセルそれぞれを2つに分割（青）している。それ以上の分割はされていないので、最終的にできた8つのセルを葉セルと呼ぶ。黄色の球は木の頂点を表している。 kd木（英: kd-tree, k-dimensional tree）は、k次元のユークリッド空間にある点を分類する空間分割データ構造である。kd木は、多次元探索鍵を使った探索（例えば、範囲探索や最近傍探索）などの用途に使われるデータ構造である。kd木はBSP木の特殊ケースである。 kd木は、座標軸の1つに垂直な平面だけを使って分割を行う。BSP木では分割平面の角度は任意である。さらに一般的には、kd木の根ノードから葉ノードまでの各ノードには1つの点が格納される[1]。この点もBSP木とは異なり、BSP木では葉ノードのみが点（ま
Aho Corasick 法 - naoyaのはてなダイアリー
適当な単語群を含む辞書があったとします。「京都の高倉二条に美味しいつけ麺のお店がある」*1という文章が入力として与えられたとき、この文章中に含まれる辞書中のキーワードを抽出したい、ということがあります。例えば辞書に「京都」「高倉二条」「つけ麺」「店」という単語が含まれていた場合には、これらの単語(と出現位置)が入力に対しての出力になります。 この類の処理は、任意の開始位置から部分一致する辞書中のキーワードをすべて取り出す処理、ということで「共通接頭辞検索 (Common Prefix Search)」などと呼ばれるそうです。形態素解析、Wikipedia やはてなキーワードのキーワードリンク処理などが代表的な応用例です。 Aho Corasick 法 任意のテキストから辞書に含まれるキーワードをすべて抽出するという処理の実現方法は色々とあります。Aho Corasick 法はその方法のひと
Tx: Succinct Trie Data Structure
English 概要 TxはコンパクトなTrieを構築するためのライブラリです．従来のTrieの実装（darts等）に比べ1/4〜1/10の作業領域量で辞書を保持することができ、数億〜十億キーワードなど大規模な辞書を扱うことが可能です．Trieは文字列からなるキー集合を処理するデータ構造で、キーが辞書に含まれているかのみではなく、キーのPrefixが含まれているかを高速に求めることができます．内部データ構造にはSuccinct Data StructureであるLevel-Order Unary Degree Sequence (LOUDS)を利用しています． ダウンロード Txはフリーソフトウェアです．BSD ライセンスに従って本ソフトウェアを使用,再配布することができます. tx-0.12.tar.gz: HTTP Archives tx-0.11.tar.gz: HTTP tx
)
トライ (データ構造) - Wikipedia
"A", "to", "tea", "ted", "ten", "i", "in", "inn" というキー群によるトライ木 トライ木（英: trie）やプレフィックス木（英: prefix tree）とは、順序付き木の一種。あるノードの配下の全ノードは、自身に対応する文字列に共通するプレフィックス（接頭部）があり、ルート（根）には空の文字列が対応している。値は一般に全ノードに対応して存在するわけではなく、末端ノードや一部の中間ノードだけがキーに対応した値を格納している。2分探索木と異なり、各ノードに個々のキーが格納されるのではなく、木構造上のノードの位置とキーが対応している。 キーが文字列である連想配列の実装構造としても使われる。右図の例では、ノードを表す丸の中にキーが書かれ、連想される値がその下に書かれている。値が書かれていないノードはキー文字列の途中までにしか対応していない。各英単語
横着プログラミング 第6回: chatty: 小うるさい端末
最終更新日: 2002-09-18 (公開日: 2002-09-18) Unix Magazine 誌に 2002年1月号から 2003年2月号にかけて連載し ていた記事の元の原稿です。 才気に富んだことは個人が行うのが通例であり、信じがたきバカ さ加減は大抵組織に帰されるものである。 -- Jon Bentley *1 役に立たないソフトウェアを作るのが好きだ。面倒な作業を楽にす る横着ソフトウェアもいいが、たまには人を呆れさせるくだらない ソフトウェアを作るのも楽しい。 以前に私が開発した cdbiff*2というソフト ウェアは、メールが届くと PC の CD-ROMドライブが開いてメール の到着を通知するという役に立たないものであったが、そのくだら なさが受けて予想外の好評を得た。今回は、そうした役に立たない ソフトウェアの 1つである、小うるさい端末 chatty*3 を紹介する。
Advanced Data Structures
6.851: Advanced Data Structures (Spring'07) Prof. Erik Demaine TA: Oren Weimann [Home] [Lectures] [Assignments] [Project] [Accessibility] Data structures play a central role in modern computer science. You interact with data structures much more often than with algorithms (think of Google, your mail server, and even your network routers). In addition, data structures are essential building blocks
Blogopolisから学ぶ計算幾何 記事一覧 | gihyo.jp
運営元のロゴ Copyright © 2007-2024 All Rights Reserved by Gijutsu-Hyoron Co., Ltd. ページ内容の全部あるいは一部を無断で利用することを禁止します。個別にライセンスが設定されている記事等はそのライセンスに従います。
12章 素因数分解アルゴリズム
概要 ここでは、素因数分解のための各種アルゴリズムについて解説する。 対象は、以下のとおり。 Brute force method ρ method（Pollard, Brent） p-1 method p+1 method 連分数法（Continued Fraction Method） 複数多項式二次ふるい法（MPQS : Multiple Polynomial Quadratic Sieve Method） 楕円曲線法（ECM : Elliptic Curve Method） 目次 Brute force method (Brute force method ～ Sample Program) ρ method p-1 method p+1 method 連分数法（Continued Fraction Method） 複数多項式二次ふるい法（MPQS : Multiple Polyno
統計的機械学習(Hiroshi Nakagawa)
統計的機械学習 (under construction) 導入ppt pdf 情報の変換過程のモデル化 ベイズ統計の意義 識別モデルと生成モデル 次元の呪い 損失関数, bias, variance, noise 数学のおさらいppt pdf 線形代数学で役立つ公式 情報理論の諸概念 (KL-divergenceなど) 指数型分布族、自然共役 正規分布(条件付き、および事前分布) 評価方法ppt pdf 順位なし結果の評価(再現率、精度、適合率、F値) 順位付き結果の評価 線形回帰と識別ppt pdf 線形回帰 正規方程式 正規化項の導入 線形識別 カーネル法ppt pdf 線形識別の一般化 カーネルの構築法 最大マージン分類器 ソフトマージンの分類器 SVMによる回帰モデル SVM実装上の工夫 モデル推定ppt pdf 潜在変数のあるモデル EMアルゴリズム 変分ベイズ法 Expecta
天気予報から機械学習、金融工学まで - DO++
もう随分経ちますが，先日CompView秋の学校というのに行き，2泊3日みっちり機会学習を勉強してきました．講師陣は豪華でどの話も面白かったのですが特にElad Hazanによる"Prediction in the dark: the multi-armed bandit problem"が非常に面白かったです． その話を説明するために，まず簡単ながら驚くべき性能を達成するアルゴリズムを紹介しましょう． 解きたい問題は，毎日，次の日の天気が晴れか雨かを予想する問題です．t日目が晴れの場合 y(t)=1, 雨の場合 y(t)=0と表すことにしましょう．t日目にy(t+1)を予想するわけです． さて、自分は天気の専門家ではないので，自分で予報せずに，専門家に頼ることにしてみます．M人の天気予報士がいて，それぞれが独自に次の日の天気を予想しています．i人目の天気予報士のt日目の予報をp(i,t)
No Free Lunch Theorem—理想の＊＊の探し方—
すべての評価関数に適用できる効率のよいアルゴリズムは存在しない。 “すべての評価関数”というのは上の例で言えば“すべての”ということである。 この定理を証明する前に、まずよく知られた探索アルゴリズム[5]を挙げて、探索とはそもそもどのようなものなのかを説明しよう。 探索アルゴリズム “探索”というのは問題の解の候補の中からよいものを探し出すことである（同語反復という感じだが）。ここでは次のように、評価関数が定義された問題を解く過程のことを探索と呼ぶことにする。 解の候補の有限集合を、その要素のひとつをとする。 評価関数はから有限集合への写像である（の要素のひとつをで表す）。 の最大値を与えるようなが問題の解で、それを見つけたいのである。 このような探索問題を解くためのアルゴリズムには大きく分けて次の2つがある。 アルゴリズムのように知識を用いて解を構成するもの（適切なヒューリスティックスが
簡単なWebサーチエンジンの作り方 - Imagine with 加藤和彦
筑波大学は3学期制で，12月1日から3学期が始まりました．3学期には私が担当している学類生（普通の大学の学部生）3年生向けの実験があります．約3ヶ月を掛けて，ほどほどの規模のプログラム作成を行います．私が作り，担当しているプログラム実験は「Webサーチエンジン」といいまして，テキストはこちらに公開しています． この実験，結構，自信作なんです．Javaの基本的なプログラミングができることだけを仮定して，漏れのない全文検索を行うWebサーエンジンを作ります．Webデータ収集を自動的に行うクローラー付き．Googleのようなページランキング機能はありませんが，一応，サーチエンジンの基本機能を備えます．自慢は，このテキストが実質A4で印刷して2ページくらいであること．数学の小問を解いていくように，順番に小問を解いていくと，最後にはWebサーチエンジンができます． ミソはサフィックス・アレイ(suf
連想配列の進化 - DO++
キーに対して値を結びつける連想配列は多くのアプリケーションの肝であり、コンパクトかつ高速な処理が可能な連想配列を追い求め日夜研究が進められています。 特に非常に巨大な連想配列を高速に処理するというのが重要な課題となっています。例えば、音声認識・文字認識・機械翻訳などで使われている言語モデルでは、非常に大量のN個の単語列の情報（特に頻度）を格納することが重要になります。 この場合、キーが単語列であり、値が単語列のコーパス中での頻度に対応します。 例えばGoogle N-gram Corpusからは数十億種類ものN-gramのキーとその頻度などが取得できます。これらを主記憶上に格納し、それに関する情報（頻度や特徴情報）を操作することが必要になります。 そのほかにも大規模なデータを扱う問題の多くが巨大な連想配列を必要とします。 ここではこのような連想配列の中でも、キーの情報を格納することすら難し
Oracle の B*Tree インデックスの内部構造についてお勉強中（その１）
お仕事のデータベース一式のリース切れ間近ということで、リース延長で耐えることができるのか、それともシステム更改が必要なのかを見極めるため、最近はデータベース周りのチューニングばかりやってます。 当初設計時に、５年間持つ設計をしたのですが、流石に５年目にもなると予定とはそれなりに乖離が発生するものです。テーブル＆インデックス設計をユーザ向けの処理をとにかく高速に処理できるように設計したので、ユーザ向けの処理は速度的に全然大丈夫なのですが、データの肥大化によるバッチ処理のパフォーマンス劣化が顕著です。単純にストレージと CPU パワーが足りていないのでしょう。 しかしながらチューニングの余地はまだまだ十分にありそうです。バッチ向けの最適化を図ることにしました。うまくいけば来年度どころか、後数年はリース延長で延命できるかもしれません。 今回実施したチューニングの１つのポイントとして、バッチ処理向
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
IBM Developer
