ブログ パスワード認証 閲覧するには管理人が設定した パスワードの入力が必要です。 管理人からのメッセージ . 閲覧パスワード Copyright © since 1999 FC2 inc. All Rights Reserved.
. - FC2 BLOG パスワード認証
ブログ パスワード認証 閲覧するには管理人が設定した パスワードの入力が必要です。 管理人からのメッセージ . 閲覧パスワード Copyright © since 1999 FC2 inc. All Rights Reserved.
素数判定 - あどけない話
要約：素数判定に使われるミラーラビン法を解説しながら、Haskell で実装してみる。 フェルマーテスト 大きな数を確実に素数だと判定するには、大変時間がかかるので、実用的には「ほぼ素数だ」と確率的に判定する。確率的な素数判定の代表格がフェルマーテストである。 フェルマーテストには、以下に示すフェルマーの小定理を利用する。 a^p ≡ a (mod p) a は任意の整数。p は素数である。法 p の下で a を p 乗したものは、a と合同であると言う意味だ。a には制限はないが、特に a を p より小さい整数、0 ≦ a ≦ p - 1 とすれば、a を p 乗して、p で割ると a に戻るとも解釈できる。 最初に見たときは、だからどうしたと思われるかもしれない。しかし、有名なフェルマーの大定理が実用上何の役にも立たないのに対し、フェルマーの小定理はいろんな場面で活躍する。 実際に計
Bayesian Setsによる関連文書検索システムStupa - mixi engineer blog
都会よりも田舎が好きなfujisawaです。Bayesian Setsというアルゴリズムを使って、関連する文書を高速・高精度に検索できるシステムを作成しましたので、そのご紹介をさせていただきます。 Bayesian Setsとは Bayesian Setsはいくつかアイテムを入力すると、それを補完するようなアイテムを返してくれるアルゴリズムです。原著論文の先頭に"Inspired by Google Sets"と書かれているように、Google Setsを参考にして作成されています。実際にどのような出力が得られるか、Google Setsに以下の表のクエリを検索して試してみますと、 クエリ 出力 apple, banana chocolate, strawberry, vanilla, cherry, ... apple, macintosh software, windows, mac,
Winny解析 - binzume.net
Winnyの利用者は未だに多いようですが，事実上開発者不在となっており，今後の発展は見込めない状態になっています(そんな状態でも，未だにユーザが多くネットワークも維持しているWinnyの完成度には驚きですが)．Winnyをターゲットとしたワームも蔓延しているらしいことを考えると，そろそろ次のバージョンが欲しくなるところです．しかし，仕様が公開されていないWinnyの場合，誰か他の人が互換性のあるファイル共有ソフトを作ることが難しくなっています． 2003年にWinnyユーザが逮捕され話題になった時期にWinnyを解析してみましたが，解析結果を公開するのはWinnyのネットワークに対して害はあっても利は無いと思い，しばらく自粛していました． しかし，開発者逮捕に続き「Winnyの技術」が発売されたことだし，そろそろ公開しても問題は少なくなったと判断して，これを公開します． 注意 ２年以上前に
動的計画法とナップサック問題を学びたい人におすすめのサイト - ダウンロードたけし（寅年）の日記
組み合わせ最適化の手法として「動的計画法」というモノがあります。 wikipediaから抜粋 動的計画法（どうてきけいかくほう、英: Dynamic Programming, DP） コンピュータ科学の分野において、ある最適化問題を複数の部分問題に分割して解く際に、そこまでに求められている以上の最適解が求められないような部分問題を切り捨てながら解いていく手法 一見難しそうですが、実は理解するのは以外と簡単です。いろいろな場面で応用が利く便利な手法ですので、覚えておいて損はないものです。コンピュータ系、情報系のお勉強をする人であれば、おそらく一度は習ったりするかもしれません。 ナップサック問題と動的計画法 動的計画法の一番親しみやすそうな例として「ナップサック問題」というのがよく取り上げられます。 こんな感じの問題です。 今ここに様々な大きさの品物が置いてあるとします。そしてそれらの品物は各
最強最速アルゴリズマー養成講座：アルゴリズマーの登竜門、「動的計画法・メモ化再帰」はこんなに簡単だった (1/5) - ITmedia エンタープライズ
動的計画法とメモ化再帰 今回は、非常によく用いられるアルゴリズムである、「動的計画法」「メモ化再帰」について説明します。この2つはセットで覚えて、両方使えるようにしておくと便利です。 なお、メモ化再帰に関しては、第5・6回の連載の知識を踏まえた上で読んでいただけると、理解が深まります。まだお読みになっていない方は、この機会にぜひご覧ください。 中学受験などを経験された方であれば、こういった問題を一度は解いたことがあるのではないでしょうか。小学校の知識までで解こうとすれば、少し時間は掛かるかもしれませんが、それでもこれが解けないという方は少ないだろうと思います。 この問題をプログラムで解こうとすると、さまざまな解法が存在します。解き方によって計算時間や有効範囲が大きく変化しますので、それぞれのパターンについて考えます。 以下の説明では、縦h、横wとして表記し、プログラムの実行時間に関しては、
Hadoopで、かんたん分散処理 (Yahoo! JAPAN Tech Blog)
ヤフー株式会社は、2023年10月1日にLINEヤフー株式会社になりました。LINEヤフー株式会社の新しいブログはこちらです。LINEヤフー Tech Blog こんにちは、地域サービス事業部の吉田一星です。 今回は、Hadoopについて、Yahoo! JAPANでの実際の使用例を交えながら書きたいと思います。Hadoopとは、大量のデータを手軽に複数のマシンに分散して処理できるオープンソースのプラットフォームです。 複数のマシンへの分散処理は、プロセス間通信や、障害時への対応などを考えなければならず、プログラマにとって敷居が高いものですが、 Hadoopはそういった面倒くさい分散処理を一手に引き受けてくれます。 1台では処理にかなり時間がかかるような大量のデータも、複数マシンに分散させることで、驚くべきスピードで処理を行うことができます。 例えば、今まで1台でやっていた、あるログ集計処理
[NLP][機械学習] 言語モデル覚え書き - tsubosakaの日記
この文章について 最近言語モデル方面にも少し興味があるので自分の知識を整理する意味で書いてみた。NLPは専門ではないので、おかしなことを書いてある可能性がありますがその場合はご指摘ください。 本文章ではn-gramモデル、単語の出現確率がn-1個前の単語のみに依存するモデルを考える。 問題 who is * という文が与えられたときに*にくる文字の確率を求めることを考える。この場合だと*には例えばheが当てはまるかもしれないが, isが入ることはまずなさそうに思える。このことは文法的にも説明ができると思うが、文法のルールを作るのは大変だし、文法的に正しい単語の中でどれが出やすいかということはできない。 一方で機械学習を使った言語モデルの文脈では文法的知識を余り持たず、与えられたコーパスから自動的に出やすい単語/表現を学習する方針をとる。 最尤推定 一番簡単なモデルとしては最尤推定を使うもの
![[NLP][機械学習] 言語モデル覚え書き - tsubosakaの日記](https://cdn-ak-scissors.b.st-hatena.com/image/square/fd5873fc29a8487ca585cedd187a3197a9282658/height=288;version=1;width=512/https%3A%2F%2Fogimage.blog.st-hatena.com%2F17680117127124028144%2F17680117127124030005%2F1557332435)
ベジエ曲線を整数の加減算だけで描画する方法 - Studio RAIN's diary
だいぶ前にちらっと書いたことがあるのだが、かれこれ 20 年ほど前に、ベジエ曲線を整数の加減算だけで描画する方法を考えたことがある。こういう会社員時代の仕事を紹介するためには、いろいろと制約があったりするのだが、このアルゴリズムは多分守秘義務には含まれていないし、技術自体がいい加減時代遅れの技術で、多分今はもっといい方法が開発されているはずなので、公開してもどこからも文句は来ないと思う。だから、機会があればいつか紹介したいと思っていた。 だだ、このアルゴリズムを説明するには、ややこしい数式を並べる必要があって、それが面倒で避けていたところもあった。しかし、今回 Maxima を使って計算したら、わりと簡単に再現できたので、せっかくだから記録にとどめておくことにする。 ベジエ曲線というのは、空間からいくつかの点を選択したときに、その点との関係で定義される。たとえば、２次のベジエ曲線だったら、
興味ないね
A, B の small, large を提出して 56 点 411 位で通過. 去年は Round1 で敗退したので, 今年は少し進歩したということか ? A は問題文が長いので, 先に B を見る. B の small の方が点数が低い. B は std::next_permutation 使う. 最後の順列だった場合は, ソートして先頭の文字と 0 でない最小の文字を入れ替えて, 一文字目に 0 を挿入する. 知っててよかった STL. A は, 問題文から二分木作る問題. std::istream の文字切り出しを使いたいのだが, ) の前は空白がない場合があるとの説明書き. ) の前には空白を挿入して構文解析しました. C は, 一つずつ式を増やしてクエリの数字と答え合わせするぐらいしか思いつかず. 後で作りましたが, small は通りましたが large は全然だめでした.
コンピュータサイエンス史上最大の課題「並列処理による性能向上」～情報処理学会創立50周年記念全国大会の招待講演
「いま、並列処理の壁というコンピュータサイエンス史上最大の課題に直面しています。しかしこれはチャンスでもあります。新しい時代を切り開いていきましょう」。IBM名誉フェローのFran Allen氏は、昨日3月10日に行われた日本の情報処理学会創立50周年記念全国大会の招待講演の演壇からこんなメッセージを聴衆に投げかけました。 Fran Allen氏は、コンパイラやプログラミング言語が専門で、女性で初めてチューリング賞を受賞した人。今回の招待講演のためにわざわざ来日したと紹介されました。 講演のタイトルは「The Challenge of the Multicores」。ここからは、Allen氏の講演の内容を紹介しましょう。 （この講演は英語で行われたものです。内容にはできるだけ正確を期したつもりですが、理解不足のところや聞き取れなかったところもありました。もし誤解や不正確なところがありました
Ruby でパターンマッチ - まめめも
ref: 未来の国のアリス - d.y.d. で紹介されている implicit future が Ruby に欲しい！ # promise を作る x = Promise.new a = [1, x, 2, x, 3, x] # 今はまだ値になっていない p a #=> [1, _promise_, 2, _promise_, 3, _promise_] # この promise は 42 に決めた！ (代入ではないよ) x === 42 # x の箇所は勝手に 42 になっている p a #=> [1, 42, 2, 42, 3, 42] というのも、これがあれば Ruby でパターンマッチができる気がするんですよね。こんな感じに。 # 何にでもマッチする箇所には _ と書く (実体は Promise.new) def _ Promise.new end # + と定数だけからなる抽象
ベイズ理論 - yasuhisa's blog
同時確率、条件付き確率からベイジアンアップデートまで。パラメトリック、ノンパラメトリック(データサイズが増えるにつれて、パラメータ数が対数オーダーで増える)のところは初めてだとたぶんわけわからないところで、ちょっと前で説明してみたけど、若干でしゃばりすぎた気がする。どうするべきかちょっと迷うところではある。難しい。 ベイジアンな考え方は、自分もちゃんと理解するまで3ヶ月はかかったので(パラメータの事前分布ってなんですか!!とか)、今日初めてという人はたぶんわけわからなかったかもなーと(宗教なので、最初は受け入れ難いものなんですよ、きっと)。コインの例のやつは、自分も最初よく分からなかったので、Rで事後分布がupdateされていく様子とかをRで書いたりしていました。 ベイズの事後分布と事後予測分布を出してみた - Seeking for my unique color. FSNLPの例は分か
さあ、Yコンビネータ(不動点演算子)を使おう！ - よくわかりません
前回、おとうさんにもわかるYコンビネータ！(絵解き解説編) - よくわかりませんというエントリで、Yコンビネータ(不動点演算子)と再帰の絵解き解説をしました。 Yコンビネータ自身は、結局のところ再帰を産み出してくれるだけです。関数(正確にはλという単純な文字列変換ルール)だけで出来て、プログラミングに関するいろんな原理の研究を可能にするのが凄い訳です。その辺のさわりを、きしださんが解説されています。しかし、単なる再帰なら、実際のプログラミングではYコンビネータなんて使わなくても出来ます。 じゃあ、Yコンビネータとか不動点とかは、偉い学者さんとかが研究に使えばいいもので、普通のプログラマには何の意味もないモノなのでしょうか？ というわけで、今回はポジティブに、Yコンビネータや不動点で出てくる考え方を、理論だけじゃなく、実際のプログラミングに応用する例を見てみましょう。 今回、プログラムの例を
おとうさんにもわかるYコンビネータ！(絵解き解説編) - よくわかりません
先日YコンビネータのきしださんのYコンビネータのエントリが話題になっていました。 ずいぶん日にちが経ってしまいましたが、自分も、自分なりにYコンビネータのあたりを絵解きで整理してみたいと思います。きしださんのエントリタイトル*1に引っ掛けて、目標として、自分の父親(非プログラマ。その辺のおっさん)でも解る内容を目指します。 なぜ不動点演算子というのか、不動点だったらなぜ再帰なのか、この辺りも含めて、実感を持って納得できればいいなと思います。 きしださんのエントリのおさらい 本題の前に、きしださんのエントリをおさらいしておきます。 Yコンビネータはただのオモチャじゃないんだよ 関数だけで色んな事が出来る 条件分岐をする関数ってのもある。 再帰(ループ)を作れる関数もある。←これがYコンビネータ。 数値も関数で表現できる。 つまり、関数だけで、条件分岐も、再帰(ループ)も、数値も作れちゃう！！
肉厚と抜き勾配をおさえるべし！（1/3） － ＠IT MONOist
本連載「100円均一でモノの仕組みを考える」では、実際に100円均一ショップで販売されている商品を分解／観察して、その仕組みや構造を理解しながら、製品開発の過程を考察していきます。連載第12回のお題は、文房具の定番商品の1つ「テープディスペンサー」です。
Unix Magazine「インターフェイスの街角」
Unix Magazine「インターフェイスの街角」関連資料 掲示板 2006年4月号 「写真の位置登録」 2006年3月号 「マイ認証」 2006年2月号 「索引ナビゲータ」 2006年1月号 「Greasemonkeyによるブラウザ機能の拡張」 2005年12月号 「本棚演算」 2005年11月号 「Rindaで実世界指向プログラミング」 2005年10月号 「並べる! 技術」 2005年9月号 「TV番組の検索と録画予約システム」 2005年8月号 「位置情報からの検索」 2005年7月号 「逆リンクと兄弟リンク」 2005年6月号 「携帯から位置情報を活用」 2005年5月号 「Ajax」 2005年4月号 「Phidgetsシステム」 2005年3月号 「ファイルシステムによる階層型データの管理」 2005年2月号 「最近の画像認証」 2005年1月号 「位置コミュニケーション」
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Binaryworld - RC4 Implementation in java ... [ JAVA -> security ]
Tech - RC4 Encryption in Java
Wikipediaから作成したN-gramデータを公開しました - nokunoの日記