JavaScript (ECMAScript) の整数の精度と乱数の精度について / LiosK-free Blog
2010-05-30 カテゴリ: Client Side タグ: JavaScript Tips 久しぶりにJavaScript (というよりECMAScript) のネタ。今日はECMAScriptで扱える整数と乱数について。 ECMAScriptの数値 (Number) はIEEE 754の倍精度浮動小数点数であると仕様書に明記されている。 ECMAScript Language Specification 5th edition 4.3.19 Number value primitive value corresponding to a double-precision 64-bit binary format IEEE 754 value. (強調は引用者) ECMAScript Language Specification 3rd edition 4.3.20 Number Ty
2048 の AI を読んでみた - はやくプログラムになりたい
以前第一回2048AIコンテスト 結果報告という記事を見かけて，興味がわいたので 2048 の AI について調べてみました． 2048 は 4x4 のパズルゲームで，ルールは実際にやってもらったほうが分かりやすいぐらい簡単なものですが，テンポが良くて結構ハマりました． 今回は公開されている 2048 の AI の中で一番メジャーっぽいものを TokyoVim #19 で読んでみました． ov3y/2048-AI - Github 小並感 平穏な感じ AI でした． js/grid.js に各評価関数の定義があり，js/ai.js に探索を行うメインの部分の処理があります． 評価関数 良い手を選ぶには，ある盤面が与えられたときにその盤面がどれだけ有利な状態かを知る必要があります．それを知るために必要なのが評価関数で，今回だと 2048 の 4x4 の盤面を引数に取り，その盤面のスコアを返す
世界中の空港の位置を「ボロノイ図」で表現した「World Airports Voronoi」
普段見慣れた世界地図でも、いつもより見る視点や区切り方を変えてみると全く違った形が見えてくることもあります。世界中の空港を他のどの空港に近いかによってエリア分割し、通常の地図に重ねて示したみたのが「World Airports Voronoi」です。 World Airports Voronoi https://www.jasondavies.com/maps/voronoi/airports/ (*リンク先のページは描画に時間がかかる場合があります。PC環境推奨) 「ボロノイ図」というのは「ランダムに並んだ複数の点が存在している時、それぞれの点から距離の等しい位置を通る線(垂直二等分線)を引き、点ごとの領域を示した図」です。文字で書くとわかりづらいですが、小学校の学区割りで、近隣の学校との距離を計算して極端に通学距離が長くならないようにエリア分けしたりするときに使われます。 「World
平方数かどうかを高速に判定する方法 - hnwの日記
平方数とは、ある整数の平方（＝二乗）であるような整数のことを言います。つまり、0,1,4,9,16,...が平方数ということになります。 ところで、与えられた整数が平方数かどうかを判定するにはどうすれば良いでしょうか。与えられた整数の平方根の小数点以下を切り捨て、それを二乗して元の数になるかどうか、というのがすぐ思いつく実装です。 <?php function is_square($n) { $sqrt = floor(sqrt($n)); return ($sqrt*$sqrt == $n); } しかし、平方根の計算は比較的重い処理です。もっと高速化する方法は無いのでしょうか。 多倍長整数演算ライブラリGNU MPには平方数かどうかを判定するmpz_perfect_square_p関数が存在します（PHPでもgmp_perfect_square関数として利用できます）。本稿ではこの実装
External Memory - FC2 BLOG パスワード認証
ブログ パスワード認証 閲覧するには管理人が設定した パスワードの入力が必要です。 管理人からのメッセージ 閲覧パスワード Copyright © since 1999 FC2 inc. All Rights Reserved.
gdgd
紙媒体のほうの拙著『解析魔法少女美咲ちゃん マジカル・オープン！』は一度絶版になったんだ。自分で言うのも何だが、リバースアセンブルの名著であり、教科書的な存在であるから、アマゾンのマーケットプレイスでは長らく定価の数倍というプレミア価格となっていた。 プレミア価格になってからも「再販しないんですか？」とブログの読者の方などから問い合わせを数多くいただき、これは再販すべきだよなぁと思って出版社のほうに増刷するか、無料でPDFか何かを公開させてもらえないかと何度か出版社の編集担当に交渉したのだが、これがどうもうまくいかなかった。 まず、本文の著作権自体は著者(私)にある。だから絶版になったあと本文だけを公開することは出来る。しかし図は、下書きは私が書いたものではあるが、出版社の編集側で手直ししたものが本には使われているし、組版をしたのは出版社である。これらに関する権利が出版社にある。また、表紙
コンピュータ将棋の基礎知識
この用語集の内容は無保証です。この用語集を信じて開発した将棋ソフトが 選手権で大敗しても、私は責任はもちませんし関知しません。あしからず コードや数式は極力書かず、読み物に徹しています。 ドーピング 自動学習でうまく行かない所や、データがないところを手動で補ってやる行為。語源は棚瀬さん？ FutilityCut 探索中に残り１手の場合に、評価関数の値よりある程度alphaを下回っていれば、あと1手さらに指してもalphaを下回るだろうという予測の元にalphaカットとみなす。逆にある程度betaを上回っていると、あと1手指してもbetaを超えるだろうと予測してbetaカットする、といった後ろ向き枝狩り手法。評価関数の値の代わりに静止探索の値を用い、上回る定数幅をやや広げることで、残り2手の場合にも適用される。 KillerMove 探索中にベータを超えた良い手などを深さに応じて保持しておき
アルゴリズムパズル
大学で計算機科学を教える著者が、「パズルを解くことで、アルゴリズム的思考を鍛える」というコンセプトに基づいて、古今東西150の「アルゴリズム的」な数学パズルを収録。優れたアルゴリズム設計戦略と分析テクニックを通して、アルゴリズム的思考と柔軟な発想を育てます。また、近年では、入社試験にパズル的な難問を出す企業も増えており、その対策としても役立つ一冊です。 質問形式の序文 謝辞 パズル一覧 チュートリアルのパズル 本編のパズル 墓碑銘パズル 第1章 チュートリアル 一般的なアルゴリズム設計戦略 魔方陣（Magic Square） nクイーン問題（The n-Queens Problem） 有名人の問題（Celebrity Problem） 数当てゲーム（Number Guessing）（別名20の扉（Twenty Questions）） トロミノ・パズル（Tromino Puzzle） アナグ
バンディットアルゴリズム概論
1. The document summarizes two papers about bandit algorithms. The first paper proposes a multi-level bandit algorithm that utilizes the taxonomy of ads and web pages to reduce the number of arms to explore. The second paper studies the "mortal multi-armed bandit" problem where arms have finite lifetimes. It models the death rates of arms and proposes the "Stochastic with Early Stopping" algorithm
実践・最強最速のアルゴリズム勉強会 第五回講義資料(ワークスアプリケーションズ & AtCoder)
最小カットを使って「燃やす埋める問題」を解く方法について、問題とソースコードつきで、まとめました。ニコニコ生放送「TopCoderでプログラムしてみた」2000回記念放送の資料です。
実践・最強最速のアルゴリズム勉強会 第三回講義資料(ワークスアプリケーションズ & AtCoder)
最小カットを使って「燃やす埋める問題」を解く方法について、問題とソースコードつきで、まとめました。ニコニコ生放送「TopCoderでプログラムしてみた」2000回記念放送の資料です。
実践・最強最速のアルゴリズム勉強会 第二回講義資料(ワークスアプリケーションズ & AtCoder)
最小カットを使って「燃やす埋める問題」を解く方法について、問題とソースコードつきで、まとめました。ニコニコ生放送「TopCoderでプログラムしてみた」2000回記念放送の資料です。
コンピュータを進化させてきた偉大なるアルゴリズムまとめ
By Kai Schreiber IT技術の進化のスピードには目を見張るものがありますが、それを支えているのはアルゴリズムと呼ばれる処理方法(技術的アイデア)です。さまざまなアルゴリズムの中でも、コンピュータの進化に革命的な影響をもたらしたとされる偉大なアルゴリズムは以下の通りです。 Great Algorithms that Revolutionized Computing http://en.docsity.com/news/interesting-facts/great-algorithms-revolutionized-computing/ ◆ハフマン符号(圧縮アルゴリズム) Huffman coding(ハフマン符号)は、1951年にデービッド・ハフマン氏によって開発されたアルゴリズム。頻出頻度の大小によって対戦するトーナメントツリーを考えて、ブロックごとに0と1の符号をもたせる
実践・最強最速のアルゴリズム勉強会 第一回 講義資料(ワークスアプリケーションズ & AtCoder)
Competitive Programming Advent Calendar 2012の12/01担当分の記事です。
ピックの定理 - Wikipedia
頂点が全て格子点上にある多角形 ピックの定理（-ていり、Pick's theorem）は等間隔に点が存在する平面上にある多角形の面積を求める公式である。この場合の多角形の頂点は全て右図のように、最も近い点同士の間隔を1とする正方格子点（等間隔に配置されている点）上にあり、内部に穴は開いていないものとする。多角形の内部にある格子点の個数を i、辺上にある格子点の個数を b とするとこの種の多角形の面積 S は以下の式で求められる。 例えば図の六角形なら内部にある点が i = 39 個、辺上にある点が b = 14 個なので S = 39 + 14/2 − 1 = 45 と簡単に計算できる。 この定理は 1899 年に ゲオルグ・アレクサンダー・ピックによって初めて示され、エルハート多項式により三次元以上に拡張して一般化することができる。 同公式はまた、多面体上の図形に対して一般化することもで
Random Forestで計算できる特徴量の重要度 - なにメモ
(pixabay.comより) １．背景とか Random Forest[1]とは、ランダムさがもつ利点を活用し、大量に作った決定木を効率よく学習させるという機械学習手法の一種です。SVMなどの既存の手法に比べて、特徴量の重要度が学習とともに計算できること、学習が早いこと、過学習が起きにくいこと（追記注釈１）などの利点が挙げられます。Kinectの姿勢推定に使われているらしいです。 最近、Random Forestをカジュアルに使う例が多く（特にうちの研究室）、一部パラメータやら出力やらがわからない人も多いと思います。使い方はTJOさんの資料[2]を読んでもらえれば理解できると思うし、詳細は波部先生の資料[3]をよんでもらえればわかると思います。 それで、いろいろな日本語の資料をいくら読んでも、Random Forestがもつ特徴の１つである、特徴量の重要度の詳細に関してはほとんどノータッ
高校生がスーパーコンピュータを使って5×5魔方陣の全解を求めることに成功 | 筑波大学 計算科学研究センター
概要 筑波大学計算科学研究センターは、全国共同利用施設として、一般公募による「学際共同利用プログラム」※1を実施しています。平成25年度に、茨城県立並木中等教育学校4年次（高校1年）の杉﨑行優（すぎざき・ゆきまさ）君の申請が採択されました。杉﨑君は筑波大学計算科学研究センターの朴泰祐教授と共同研究を進めた結果、スーパーコンピュータ「T2K-Tsukuba」※2を使った並列計算により、5×5の魔方陣の全ての解を求めることに成功しました。 魔方陣とは、正方形のマス目に、縦・横・斜めの合計が同じになるよう数字を置いたものです。5×5の魔方陣の全解は2億7530万5224通りあることがすでにわかっています。杉﨑君は「枝刈り法」を改良した求解アルゴリズムを考案し、スパコンに並列計算させるためのプログラムを開発しました。朴教授は、並列データの収集や並列化に関する詳細なアドバイスを行いました。並列計算
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
http://arc360.info/algo/privatekey.html
貪欲
実践・最強最速のアルゴリズム勉強会