指数関数を使ったお手軽イーズ・アウト
（この記事にはProcessing.jsによるスケッチがいくつか組み込まれています。環境によっては正しく再生されないかもしれません。Chrome, Safari, Firefox等の使用をおすすめします。） 「丸が１秒おきに左右に滑らか動く」というプログラムを書いてみよう。いちばん簡単なのは、線形移動を使う方法だ。 まあ、これでも十分っちゃ十分なんだけれど、動きとしてはちょっと味気ない。 いわゆるイーズアウト(ease out)を使えば、これを滑らかにすることができる。 上のスケッチでは、漸化式を使ったイーズアウトを実装している。こんな感じの式だ。 pos += (target - pos) * 0.1; pos は現在座標、 target は目標の座標。この式を1回の描画毎に評価する。目標座標までの差分を1割づつ詰めていくような感じ。差分は毎回少なくなっていくから、最初は早く、徐々に遅く
Super Technique 講座〜再帰関数の技
Ｃ言語初心者が戸惑うものとして、「再帰」に関する技法がある。まあ、今時の言語で「再帰関数」を書けないのは、COBOL と FORTRAN, 古典的BASIC くらいのものだが、一般的な言語解説書での説明は大変おざなりなものである。だから、これは意識して憶えないことには、やはり身に着かない。 そこで「Super Technique 講座」では、再帰の技法を、再帰という発想の親玉である Lisp(Scheme) を利用して理解する、という無謀な企てをしてみることにする。「ある言語を理解するのに、何で別な言語を勉強するの？」という当然の疑問が湧くことだろう。しかし、しかし、「それがハッカーというものである」。筆者は MS-DOS の時代に、UNIXのテキストツールの使い方を理解するために、それらを自分で実装した。一見「無駄」に見える技術投資は、ことプログラマにとっては決して「無駄」ではない。Li
ALGORITHM NOTE こだわり
入力例 3 9 500 300 800 200 100 600 900 700 400 4 3 1000 1000 1000 0 0 出力例 1800 1000 解説 Partition Problem といいます。 [この問題では、本の厚さの制限が緩いので、力任せ(本棚の幅を少しづづ厚くしていき貪欲に解く)で解けたのかもしれませんが、点数から察して、悲しいことに設定ミスか、または意図的に難易度を下げたか、または実行時間の制限を厳しくしているのでしょうか。力任せで解けないのであれば難易度はさらに高くなります。] 出題者が求めた解法は、動的計画法または二分法だと思います。 ここでは、動的計画法でこの Partition Problem を解きます。 Partition Problem とは、n 個の数からなる数列 S = {s1, ..... sn} を k 個の部分に分割するときに、各部分
A*アルゴリズムについて整理 - yasuhisa's blog
辞書を参考にしながら。NAISTのI期辺りでやったはずなんだが、かなりすっ飛んでいる。 デジタル人工知能学事典 [CD-ROM付] 作者: 人工知能学会出版社/メーカー: 共立出版発売日: 2008/05/16メディア: 単行本購入: 1人 クリック: 6回この商品を含むブログ (6件) を見る A*アルゴリズムとは?グラフ探索アルゴリズムの一つ。「開始ノードから現在位置に至るまでのコスト」と「現在位置からゴールまでの推定コスト」の2つのコストを用いてadmissibleな条件(後述)の元でコストが最小であるような経路を効率的に見つけることができるアルゴリズムである。1960年代に開発されたアルゴリズムであるが、50年経った今でもばしばし使われている。 現在いるノードをp、開始ノードからpまでの最小コストをg(p)、pからゴールまでの最小コストをh(p)と書くとすればpを経由して開始ノード
diffの動作原理を知る～どのようにして差分を導き出すのか | gihyo.jp
UNIXの基本的なコマンドの1つであるdiff。 これに実装されているアルゴリズムは実に興味深い世界が広がっています。 本稿では、筆者が開発した独自ライブラリ「dtl」をもとに「diffのしくみ」を解説します。 はじめに diffは2つのファイルやディレクトリの差分を取るのに使用するプログラムです。 ソフトウェア開発を行っている方であれば、SubversionやGitなどのバージョン管理システムを通して利用していることが多いかと思います。本稿ではそのdiffの動作原理について解説します。 差分の計算の際に重要な3つの要素 差分を計算するというのは次の3つを計算することに帰結します。 編集距離 2つの要素列の違いを数値化したもの LCS（Longest Common Subsequence） 2つの要素列の最長共通部分列 SES（Shortest Edit Script） ある要素列を別の要
ソートアルゴリズムを映像化してみた - jsdo.it - Share JavaScript, HTML5 and CSS
よくあるやつです。ぼんやり眺めてると、とても癒されます。 2014/2/25 追記: 全面的に書き直しました。 // https://github.com/norahiko/sort-visualize var helper = { range: function(min, max) { var res = []; for(var i = min; i < max; i++) { res.push(i); } return res; }, shuffle: function(ary) { for(var i = ary.length - 1; 0 <= i; i--) { var rnd = Math.random() * (i + 1) | 0; helper.swap(ary, i, rnd); } }, swap: function(ary, a, b) { if(a < 0 ||
探索 - Wikipedia
探索（たんさく、英: search）とは、特定の制約条件を満たす物を見つけ出す行動のこと。 何か問題を解くに当たって、有効な解析的な解法を用いることのできない場合は、試行錯誤によって解を得る場合もある。 一部のアルゴリズムは、元々、機械学習と並んで人工知能の分野のアルゴリズムであるが、現在はその他の分野にも応用されている。類義語として検索（英: search）も参照。 探索アルゴリズムとは、大まかに言えば、問題を入力として、考えられるいくつもの解を評価した後、解を返すアルゴリズムである。 まず解くべき問題を状態（英: state）と状態変化（行動、英: action）に分ける。 最初に与えられる状態を初期状態（英: initial state）といい、目的とする状態は最終状態（ゴール、英: final state, goal）と呼ばれる。 初期状態から最終状態に至る、状態及び状態変化の並び
Rediscover the Monte Carlo - 西尾泰和のはてなダイアリー
僕個人はゲームの思考ルーチンを作ることなどには興味があるので、みんな知っていることだと思っていたのですが、意外と「現在世界最強の囲碁の思考ルーチンはモンテカルロ」ってのは知られてないみたいですね。うっかりすると「そんなわけないだろー」とか言われてしまう。その根底には「モンテカルロはとても収束が遅くて使いものにならない」という過去の記憶があるのかなー。ちょうどJavaScriptが使いものにならないおもちゃ言語だと思われていたように。 囲碁の思考ルーチンを著しく進化させた新しいモンテカルロが昔の単純なモンテカルロとどう違うかというと、UCB1という評価関数で「もっと探索するとヨサゲな局面」を判断して、ヨサゲな局面から優先的に探索するという点なんだけど、そういう定性的な話をしてもピンと来ないよね。同じ発想をモンテカルロで円周率を求めるプログラムに適用したら収束の速さが定量的にはっきり見えて面白
機械学習超入門II 〜Gmailの優先トレイでも使っているPA法を30分で習得しよう！〜 - EchizenBlog-Zwei
最近の論文で The Learning Behind Gmail Priority Inbox D.Aberdeen, O.Pacovsky & A.Slater というのがある。これはGmailの優先トレイで使っている機械学習のアルゴリズムについて解説したもの。というと難しそうな印象があるが、この論文で紹介されているPassive-Aggressiveという手法は実装がとても簡単。なので今回はこれについて解説するよ。 参考資料: Gmail - 優先トレイ Online Passive-Aggressive Algorithms K.Crammer et al. The Learning Behind Gmail Priority Inbox読んだメモ - 糞ネット弁慶 わかりやすい日本語解説 機械学習超入門 〜そろそろナイーブベイズについてひとこと言っておくか〜 - EchizenBl
ALGORITHM NOTE 最長増加部分列 Longest Increasing Subsequence
東西に並んだ高さの異なるｎ本の木があります。あるキコリがこれらの木を、西から東の方向へ木の高さが小さい順に並ぶように、いくつかの木を切り倒すことにしました。木の数を最大にするにはどの木を切れ（残せ）ばようでしょうか？ このような単純な（くだらない）問題でも、考えられる組み合わせを全て調べようとすると、それは各木を選ぶか選ばないかの組み合わせになるので、計算量はO(2n)となってしまいます。 この問題は、与えられた数列の最長増加部分列 Longest Increasing Subsequence (LIS) を求めることに帰着します。 最長増加部分列とは、与えられた数列 S S = a1, a2 , , , an の増加部分列 （ すべてのi, j (i < j)について ai < aj を満たす部分列 ） の中で長さが最大のものをいいます。 例えば、 S = 4 1 6 2 8 5 7 3
Common Subsequence 解説
問題名：Common Subsequence (PKU) 出典：Southeastern Europe 2003 難易度：☆☆☆ 問題の種類：DP 解法：LCS (Longest Common Subsequence) 解答ソースコード： 1458-deq.cpp アルゴリズムの概略 DPの四天王（？），LCS (Longest Common Subsequence) そのままの問題です。 アジア地区予選など，通常はこれをひねった問題が出てきます。 LCSとは，二つの値の列（この問題では文字列）が与えられて，最長の共通部分列を見つける問題です。 部分列は連続している必要はありませんが，順序は変更してはいけません。 例えば X = "abcfbc", Y = "abfcab" であればLCSは "abfc" や "abcb" になります。 LCSは一般的に複数ありえますが，この問題ではその長
最長共通部分列問題 (Longest Common Subsequence) - naoyaのはてなダイアリー
部分列 (Subsequence) は系列のいくつかの要素を取り出してできた系列のことです。二つの系列の共通の部分列を共通部分列 (Common Subsecuence)と言います。共通部分列のうち、もっとも長いものを最長共通部分列 (Longest Common Subsequence, LCS) と言います。 X = <A, B, C, B, D, A, B> Y = <B, D, C, A, B, A> という二つの系列から得られる LCS は <B, C, B, A> で、その長さは 4 です。長さ 2 の<B, D> の長さ 3 の <A, B, A> なども共通部分列ですが、最長ではないのでこれらは LCS ではありません。また、LCS は最長であれば位置はどこでも良いので、この場合 <B, D, A, B> も LCS です。 LCS は動的計画法 (Dynamic Prog
2009年12月27日:釣り師的アルゴリズム
Wikipediaによると 長いのでめんどくさい方は読まないでください。 歴史 [編集] 記録に残る最古のアルゴリズムは、エウクレイデスの原論に載っているユークリッドの互除法であるといわれている。これは、二つの整数の最大公約数を求めるアルゴリズムである。 「アルゴリズム」という名称は、現在のイラクのバグダードにおける9世紀の数学者アル・フワーリズミー (al-Khwarizmi、الخوارزمي) の名前から来ているといわれている。825年に書かれた彼の著作『インドの数の計算法』が、12世紀にチェスターのロバート（あるいはバスのアデレード）によってラテン語に翻訳され、『Algoritmi de numero Indorumアルゴリトミ・デ・ヌーメロ・インドルム』（直訳すると「インドの数におけるアルゴリトミ」）という題で、以後500年間にわたってヨーロッパ各国の大学で数学の主要な教科書とし
「Radeon HD 6800」徹底分析。HD 5800から何が変わったのか？
2010年10月22日，AMDはDirectX 11対応GPUの第2世代モデルとして，Radeon HD 6000シリーズを発表した。 第1弾として市場投入されたのは，「Radeon HD 6870」（以下，HD 6870）と「Radeon HD 6850」（以下，HD 6850）の2モデル。製品概要やベンチマークテスト結果はすでに掲載済みだが，今回は，現地時間19日に台湾で開催されたAMD主催のイベント「Technical Forum & Exhibition 2010」（TFE 2010）における事前技術説明会「Northern Islands Architecture Deep Dive」の内容を中心に，これら新GPUシリーズのアーキテクチャについて，もう少し詳しく見ていくことにする。
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
プログラミングコンテストでのデータ構造
JOI合宿 問題と解説
乱択アルゴリズム紹介(Bloom Filter) - Preferred Networks Research & Development
How to Implement World Fastest Grep.
Efficient data transfer through zero copy
algorithms