計算量理論 計算量入門（演習問題） オススメの本 河村彰星
Computational Complexity
計算量理論 計算量入門（演習問題） オススメの本 河村彰星
More Algorithms and Data Structures, using Haskell
General-purpose algorithms and data structures, illustrated in Haskell. Part II Reflection without Remorse: A conceptual sequence as a tangible and efficient data structure Pure functional, mutation-free, efficient double-linked lists Total stream processors and their applications to all infinite streams Sparse Grids: multi-dimensional interpolation, approximation and integration Fast computation
BLUE*アルゴリズム
2. 論文紹介 • Marc Sebban, et. al. “BLUE*: a Blue-Fringe Procedure for Learning DFA with Noisy Data” • http://labh-curien.univ-st-etienne.fr/~janodet/ pub/tjs04.pdf • ノイズを含む信号列から状態遷移図を推定 →それが何の役に立つの？ 13年4月14日日曜日 3. 論文紹介 • Thomas Arts and Simon Thompson, “From Test Cases to FSMs: Augmented Test-driven Development and Property Inference” • http://www.cs.kent.ac.uk/pubs/2010/3041/content.pdf • ユニットテストの結果
中学生にもわかるウェーブレット行列 - アスペ日記
id:echizen_tm さんの記事「ウェーブレット木の効率的で簡単な実装 "The Wavelet Matrix"」から始まったウェーブレット行列ブームから半年以上が過ぎ、すでに枯れた技術として確立されつつある感があります。 …嘘です。 日本以外ではあんまり来ていません。 理由としては、やはりアルファベット圏では単語境界が明確であるため、こちらの記事で書かれているような「キーワード分割の難易度」といったことがあまり問題にならないということがあるかもしれません。 まあ、そういうわけで局所的に来ているウェーブレット行列ですが、日本語をはじめとする単語境界のない言語圏にとっては重要なネタであると思うため、解説記事を書き直して*1みようと思います。 ウェーブレット行列でできること 主となる操作は、文字列に対する 定数時間の rank() と select()*2 です。 rank() は、「文
20分でわかるPurely Functional Data Structures (PDF)
20分でわかる Purely Functional Data Structures k.inaba (http://www.kmonos.net/) Apr. 4, 2010 あらすじ イ ミ ュ ー タ ブ ル デ ー タ 構 造 は 遅 い Immutable Object だけで作るデータ構造 この本の 内 容を 全速力で 布教する お題：キュー (Queue) • FIFO (First-In First-Out) • pushBack(e) でデータeを入れる • popFront() で取り出せる • 入れた順に出てくる • 以上 破壊的キュー Immutable Object でない 打倒すべき目標 代 入 手続き型でよくある interface Queue<E> { void pushBack(E e); E popFront(); } よくある実装 1 2 3 ・ 4 ・
情報系修士にもわかるLOUDS - アスペ日記
一回でわかりやすく書くのは難しいので、簡潔データ構造 LOUDS の解説（全12回、練習問題付き）というシリーズにまとめました。 (2014/01/26) 古い内容を削除しました。
大規模グラフアルゴリズムの最先端 - iwiwiの日記
昨日，PFI セミナーにて「大規模グラフアルゴリズムの最先端」というタイトルで発表をさせてもらいました．スライドは以下になります． 大規模グラフアルゴリズムの最先端 View more presentations from iwiwi 当日は Ustream もされており，録画された発表もご覧になれます． http://www.ustream.tv/recorded/19713623 内容の流れとしては，以下のようになっています． 導入 アルゴリズム界隈での話題 最新の研究動向 道路ネットワークでの最短路クエリ処理 基礎的な手法：双方向 Dijkstra，A*, ALT 最新の手法：Highway Dimension + Hub-Labeling Algorithm DB 界隈での話題 最新の研究動向 複雑ネットワークでの最短路クエリ処理 基礎的な手法：ランドマークを用いた最短距離推定 最
有名どころな機械学習手法の年表 - 木曜不足
ちょっと機械学習の比較的有名なモデルやアルゴリズムの初出について年表を作ってみた。 って今週末用の資料なんだけどねｗ 1805 Method of Least Squares 1901 PCA (Principal Component Analysis) 1905 Random Walk -1925 Logistic Regression 1936 Fisher's Linear Discriminant Analysis 1946 Monte Carlo Method 1948 n-gram model 1950 RKHS (Reproducing Kernel Hilbert Space) 1950s Markov Decision Process -1957 Perceptron 1958 Kalman Filter 1960s Hidden Markov Model -1961 N
wat-array : wavelet木を利用した高速配列処理ライブラリ - Preferred Networks Research & Development
こんにちは岡野原です。もう年末になりましたが、私の今年はこれからです。 wat-arrayというC++ライブラリを公開しました。 google code:wat-array wat-arrayはフリーソフトウェアであり、修正BSDライセンスに基づいて利用できます． wat-arrayはwavelet木と呼ばれるデータ構造を利用することにより、配列上の様々な処理を効率的に行うことができるC++ライブラリです。 例えば、 – 任意の連続した範囲内にある最大値 /最小値 / k番目に大きい値, またそれらの出現位置、頻度 – 任意の連続した範囲内にある指定した文字cの出現回数、c未満/より大きい文字の出現回数 – 任意の文字のi番目の出現位置 といったものを求めることが全て範囲長、入力長に対して定数時間で行うことができます。 例えば長さ10億、値の範囲が0から1000万であるような配列A中のA[
Lanczos関数による画像の拡大縮小
Lanczos関数を使って画像を拡大縮小すると、高品質な画像が得られるのだそうだ。 その仕組みを知りたいと思っていつも通りGoogleのお世話になったが、仕組みを解説した情報が見つからない。 見つかるのはLanczosという名前の紹介や、画像処理ソフトの紹介ばかり。 もっとも、探し方が悪いのかもしれないけど。 なぜ高品質な画像が得られるのか？ 他の方法とは何が違うのか？ 断片的な情報から調べていって、その理由が理解できた。 はっきり言ってこれを解説するのは難しい！ Lanczos関数 まずはLanczos関数について。 そもそもLanczosを何と読むのかが疑問だったが、ランツォシュと読むらしい。 数学者の名前。 Lanczos sinc関数とかLanczos窓関数とかLanczosフィルタとか、人によって色々な呼び方をしていて、正しい呼称がどれなのかはっきりしないが、Lanczos wi
データ構造とアルゴリズムの記事一覧 - いろいろ解析日記
データ構造 Javaを使うなら必ず覚えておきたいデータ構造 - 配列・リスト・マップ PHPなら覚えるべきデータ構造はひとつだけ？ - 配列 Perlで覚えたいデータ構造 - 配列・ハッシュ VBAで覚えておくデータ構造 - 静的配列・動的配列・ディクショナリ JavaScriptで覚えておくとよいデータ構造 - 配列・オブジェクト Bashで覚えておくとよいデータ構造 - 配列 - 何かしらの言語による記述を解析する日記 アルゴリズム Javaを使うなら理解しておきたいアルゴリズム - 抽出・ソート・結合・集計 (リスト＆マップ編) Javaを使うなら理解しておきたいアルゴリズム - 抽出・ソート・結合・集計 (リスト＆ビーン編) PHPを使うなら理解しておきたいアルゴリズム - 抽出・ソート・結合・集計 VBAを使うなら理解しておきたいアルゴリズム - 抽出・結合・集計 Javascr
「ガベージコレクションのアルゴリズムと実装」という本を書きました。
gcbook, gcai, GCGCLoverのみなさん、お待たせしました。「ガベージコレクションのアルゴリズムと実装」の情報公開です。 書名：ガベージコレクションのアルゴリズムと実装 著者：中村 成洋／相川 光 監修：竹内 郁雄 ページ数：472ページ 本体価格：3,200円 発売開始日：2010年3月17日（水） ※地域・書店によって遅れることがあります ISBN：978-4-7980-2562-9 C3055 読み所 本書は次の2つのテーマを扱います。 1.GCのアルゴリズム（アルゴリズム編） 2.GCの実装（実装編） アルゴリズム編では、これまでに考案されてきた数多くのGCアルゴリズムの中 から、重要なものを厳選して紹介します。伝統的かつ基本的なものから、やや 高度なアルゴリズムを選定しています。GC独特の考え方や各アルゴリズムの特 性などを理解していただくのがアルゴリズム編の最大
経路探索アルゴリズムの「ダイクストラ法」と「A*」をビジュアライズしてみた - てっく煮ブログ
as詳解 ActionScript 3.0アニメーション ―衝突判定・AI・3DからピクセルシェーダまでFlash上級テクニック を読んでいて、経路探索のアルゴリズムで A* が取り上げられていました。A* については、いろいろ検索して調べたりもしたのですが、やっぱり本に書いてあると理解しやすいですね。せっかくなので自分流に実装してビジュアライズしてみました。ダイクストラ法まずは A* の特別なケースでもあるダイクストラ法から見ていきます。クリックすると探索のシミュレーションが開始します。スタート地点(S)からゴール(G)への探索が始まります。色がついたところが「最短経路が決定した場所」です。スタート地点から少しずつ探索が完了していきます。半分ぐらい完了しました。まだまだ進みます。最後まで終わりました。最短経路を黒色矢印で表示しています。ダイクストラ法は、スタート地点から近いノード(=マス
「最強最速アルゴリズマー養成講座」関連の最新 ニュース・レビュー・解説 記事 まとめ - ITmedia Keywords
最強最速アルゴリズマー養成講座： そのアルゴリズム、貪欲につき――貪欲法のススメ アルゴリズムの世界において、欲張りであることはときに有利に働くことがあります。今回は、貪欲法と呼ばれるアルゴリズムを紹介しながら、ハードな問題に挑戦してみましょう。このアルゴリズムが使えるかどうかの見極めができるようになれば、あなたの論理的思考力はかなりのレベルなのです。（2010/9/4） 最強最速アルゴリズマー養成講座： 病みつきになる「動的計画法」、その深淵に迫る 数回にわたって動的計画法・メモ化再帰について解説してきましたが、今回は実践編として、ナップサック問題への挑戦を足がかりに、その長所と短所の紹介、理解度チェックシートなどを用意しました。特に、動的計画法について深く掘り下げ、皆さんを動的計画法マスターの道にご案内します。（2010/5/15） 最強最速アルゴリズマー養成講座： アルゴリズマーの登
Search using Haskell
9. 探索 この文章では、探索問題を通じて、なぜ List に Monad があるのかを説明します。 1. 探索のおさらい ここで、探索 (search) とは 有向グラフのある点（始点）からある点（終点）までの経路を（もしあれば）求めること を指します。 探索のアルゴリズムには大きく分けて、深さ優先探索 (depth first search) と 幅優先探索 (breadth first search) の２つがあります。 深さ優先探索とは、終点にたどり着くか、行き止まりになるまで１つの経路を探索してから、 次の経路を探索する方法です。プログラムが簡単なのと、メモリー量、計算時間が比較的短くて済むという 特徴があります。ただし、最初に見つかった経路が最短経路だという保障はありません。 行き止まりになったら元の地点に戻って他の可能性を探すことをバックトラックといいます。 それに対し、幅優
PythonでA*(A-Star)アルゴリズム - Pashango’s Blog
今回はA*アルゴリズムをPythonでやってみます。 ゲームプログラマの間では、もはや常識となりつつある最短経路問題解決アルゴリズムです。 A*は、古典的手法である「ダイクストラ法」を改良したものです。 スタート地点からノードnを通ってゴールに辿り付くとき、最短距離をf(n)とすると、 f(n) = g(n) + h(n) とすることができます、g(n)は「スタートからノードnまでの最短距離」、h(n)は「ノードnからゴールまでの最短距離」です。 でも、最初から適切なg(n)とh(n)が判ってるなら苦労しませんよね。 だから、テキトーな予測値を使って、最短経路をある程度予測して効率的に経路探索をしてみようという事です。 テキトーな予測値を使った最短経路距離をf*(n)とすると f*(n) = g*(n) + h*(n) となります、f*(n)を求めるためにテキトーなg*(n)とh*(n)を
検索エンジンはいかにして動くのか？ 記事一覧 | gihyo.jp
運営元のロゴ Copyright © 2007-2024 All Rights Reserved by Gijutsu-Hyoron Co., Ltd. ページ内容の全部あるいは一部を無断で利用することを禁止します。個別にライセンスが設定されている記事等はそのライセンスに従います。
Diff algorithm - 枕を欹てて聴く
id:smoking186 さんの指摘を受け, First Authorの名前などを付加しました. どうもです. 記事内のcodeは最適化などを施しておらず, 冗長に, 定義どおりに書いています. ifがまとめられたりとかしますが, そのあたりはご容赦を... Rubyでlevenshtein距離を見て以来, 個人的にdiffブームが来ていた. 計算量O(ND) / O(NP)のalgorithmなどがあるのは知っていたが, 論文(英語)および, 解説のみ, またはソースコードのみなど分かれているものが多く, algorithmに疎い自分には理解するのに大変時間がかかってしまった. しかしやっとわかったので, 解説+JS実装してみる. 解説とソースコードがセットだと, 多少はわかりやすくなるかと... 自分は正直これくらい細かく言われないとすぐにはわかんない人なので(the O(ND)だけ
ジャンル別ゲームの作り方とアルゴリズムまとめ - ネットサービス研究室
ゲームの作り方とアルゴリズムをジャンル別にまとめてみました。ゲーム制作や、プログラミングの勉強用にご活用ください。言語別ゲームプログラミング制作講座一覧もあわせてお読みください。 リンク切れがおきていたものは、URLを表示しておくので、Internet Archiveなどでキャッシュを表示させてみてください。 RPG ゲームの乱数解析 乱数を利用した敵出現アルゴリズムの解説 各種ゲームプログラム解析 FF、ドラクエ、ロマサガのプログラムの解析。乱数の計算など ダメージ計算あれこれ（http://ysfactory.nobody.jp/ys/prg/calculation_public.html） ダメージの計算式 エンカウントについて考えてみる エンカウント（マップでの敵との遭遇）の処理方法いろいろ RPGの作り方 - ゲームヘル2000 RPGのアルゴリズム ドルアーガの塔 乱数の工夫の
Boehm GCを使おう
はじめに CやC++である程度大きなプログラムを書く場合，最大の問題点は メモリ管理である．複雑なプログラムの場合，必要なメモリの量を あらかじめ見積っておくのが難しいから，メモリが必要になった 時点でメモリを確保し，不要になったらそれを解放するという プログラミングスタイルが一般的だ．Cで言えばこんな感じだ． char *x; ... x = (char*)malloc(n*sizeof(char)); ... x を使って仕事をする ... free(x); このプログラミングスタイルの問題点は，おおまかに言って こんなところだろう． free(x) を忘れると，プロセスがどんどん大きくなってしまう． free() してはいけないものを間違ってfree()する(たとえば，同じ メモリを2回 free() してしまうとか)と，その free() の中でなく， 全然違う場所でエラーが発生す
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
