うさぎとかめ ループ判定法
プログラミングのアルゴリズムの話です。この方法は自分で思いついたわけでなく、どこぞの本で学んだ形。どこぞの本が何かは忘れてしまった。「うさぎとかめ」ネーミングは元々でなく、いわいが名前をつけなおしたと記憶。「鮮やかなアルゴリズムだ」との印象。 a1=func(a0); a2=func(a1); a3=func(a2); a4=func(a3); a5=func(a4); ・・・・・ と状態が分岐のない一連になってるものに使います。 あるfuncは引数が同じなら返り値は同じ値をとります。 １連といっても例えば (1) anとa0が同じだと環状になります。 (2)途中のanとamと同じならば、全体のグラフの形は「６」みたいな形になります。 (1)(2)はループになってますのでそれを判定するアルゴリズムがあってそれが「うさぎとかめ」です。 かめは道の上を１区間づつ進みます。 うさぎは道の上を２区
レーベンシュタイン距離 - Wikipedia
レーベンシュタイン距離（レーベンシュタインきょり、英: Levenshtein distance）は、二つの文字列がどの程度異なっているかを示す距離の一種である。編集距離（へんしゅうきょり、英: edit distance）とも呼ばれる。具体的には、1文字の挿入・削除・置換によって、一方の文字列をもう一方の文字列に変形するのに必要な手順の最小回数として定義される[1]。名称は、1965年にこれを考案したロシアの学者ウラジーミル・レーベンシュタイン (露: Влади́мир Левенште́йн) にちなむ。 レーベンシュタイン距離は、同じ文字数の単語に対する置換編集に使われているハミング距離の一般化であると見なすことが可能である。レーベンシュタイン距離の更なる一般化として、例えば一回の操作で二文字を変換する等の方法が考えられる。 実際的な距離の求め方を例示すれば、「kitten」を「s
トポロジカルソート - Wikipedia
トポロジカルソート（英: topological sort）は、グラフ理論において、有向非巡回グラフ（英: directed acyclic graph, DAG）の各ノードを順序付けして、どのノードもその出力辺の先のノードより前にくるように並べることである。有向非巡回グラフは必ずトポロジカルソートすることができる。 有向非巡回グラフのノードの集合に到達可能性関係 R (ノード x から y への(各辺の向きに逆行しない)経路が存在するとき、またそのときに限り xRy とする)を定めると、R は半順序関係となる。トポロジカルソートとは、この R を全順序になるように拡張したものとみなせる。 トポロジカルソートの典型的な利用例はジョブのスケジューリングである。トポロジカルソートのアルゴリズムはPERTというプロジェクト管理手法[1]のスケジューリングのために1960年代初頭に研究が開始された
徹底解剖「G1GC」 アルゴリズム編
書誌情報 著者: 中村成洋 発行日: 2011-06-27 最終更新日: 2012-02-03 バージョン: 1.0.0 ページ数: 62ページ(A4PDF版換算) 対応フォーマット: EPUB, PDF 出版社: 達人出版会 対象読者 高度なGCのアルゴリズムに興味のある方。すでに『ガベージコレクションのアルゴリズムと実装』を読まれていて、続きを読みたい方 著者について 中村成洋 中村成洋（nari）はネットワーク応用通信研究所に勤めているRubyistです。仕事ではRailsを使ってWebアプリケーションを開発しています。高校を卒業してからはアイス工場に2年半いて、それからプログラマに転職しました。 GCに魅了されてしまった人間で、GC歴は4年になります。CRubyのコミッタとして1年に1度のペースでGCの改善に取り組んでいます。去年はCRubyに新しく取り込まれたLazySweepG
第3回 ベイジアンフィルタを実装してみよう | gihyo.jp
さらに詳細な利用方法が知りたい方は、Yahoo!デベロッパーズネットワークのマニュアルを参照してください。 ベイジアンフィルタの実装 ここから本格的にベイジアンフィルタの実装に入っていきます。 その前に、まずは先程のリスト1のコードを利用して入力された文章をわかち書きし、単語の集合を返す関数を作成しnaivebayes.pyとして保存しましょう。こちらも先程のmorphological.pyと同様にutf-8で保存してください。 リスト2 文章の分割をする関数（naivebayes.py） # -*- coding: utf-8 -*- import math import sys #yahoo!形態素解析 import morphological def getwords(doc): words = [s.lower() for s in morphological.split(doc)
Sleep sortの各言語での実装まとめ – Yuyak
盛り上がってるSleep sort。 僕もどの言語かで実装しようと思ったけどもう色々やられていて悔しいのでまとめてみる。 随時更新。 そもそもの発端 4chan BBS – Genius sorting algorithm: Sleep sort （本家） 常識を覆すソートアルゴリズム！その名も”sleep sort”！ – Islands in the byte stream bash 4chan BBS – Genius sorting algorithm: Sleep sort （本家） 4chan BBS – Genius sorting algorithm: Sleep sort C# 4chan BBS – Genius sorting algorithm: Sleep sort JavaScript 話題のソートアルゴリズム「sleep sort」をJavascriptで実
ビタビアルゴリズム
ビタビ・アルゴリズム Ｖｉｔｅｒｂｉ ａｌｇｏｒｉｔｈｍ ホーム 情報通信のハイパーテキストは下記へ移動しました。 http://www.mnc.toho-u.ac.jp/v-lab/ お探しの内容は、下記の目次にあります。 http://www.mnc.toho-u.ac.jp/v-lab/yobology/index.htm
ビタビアルゴリズム - Wikipedia
ビタビアルゴリズム（英: Viterbi algorithm）は、観測された事象系列を結果として生じる隠された状態の最も尤もらしい並び（ビタビ経路と呼ぶ）を探す動的計画法アルゴリズムの一種であり、特に隠れマルコフモデルに基づいている。観測された事象系列の確率計算のアルゴリズムである 前向きアルゴリズム（英: forward algorithm）も密接に関連している。これらのアルゴリズムは情報理論の一部である。 このアルゴリズムには、いくつかの前提条件がある。まず、観測された事象と隠されている事象は1つの系列上に並んでいる。この系列は多くの場合時系列である。次に、これら2つの並びには一対一の対応があり、1つの観測された事象は正確に1つの隠されている事象に対応している。第三に、時点 での最も尤もらしい隠されている事象の計算は、 での観測された事象と での最も尤もらしい隠された事象の系列のみに依
統計的機械学習入門
統計的機械学習入門(under construction) 機械学習の歴史ppt pdf 歴史以前 人工知能の時代 実用化の時代 導入ppt pdf 情報の変換過程のモデル化 ベイズ統計の意義 識別モデルと生成モデル 次元の呪い 損失関数, bias, variance, noise データの性質 数学のおさらいppt pdf 線形代数学で役立つ公式 確率分布 情報理論の諸概念 (KL-divergenceなど) 線形回帰と識別ppt pdf 線形回帰 正規方程式 正規化項の導入 線形識別 パーセプトロン カーネル法ppt pdf 線形識別の一般化 カーネルの構築法 最大マージン分類器 ソフトマージンの分類器 SVMによる回帰モデル SVM実装上の工夫 クラスタリングppt pdf 距離の定義 階層型クラスタリング K-means モデル推定ppt pdf 潜在変数のあるモデル EMアル
６． 自動翻訳によるコミュニケーションの実用性
６．２．２ コミュニケーション実現性の評価結果 （１） 日本語－英語間の自動翻訳 表６．１～表６．５は，時津小学校（長崎県）とStaten Island Academy（米国ニューヨーク市）の小学校６年生の掲示板上でのメッセージのログを集計・分析した結果である。小グループごとの交流であるが，主にお互いの自己紹介，地域の紹介，衣食住などに関する文化の紹介などを行っている。 表６．１では，それぞれの掲示板上でのメッセージ文数と問題のある各要因数を示している。問題要因のうち，「構文・語法の解釈誤り」，「語彙の解釈誤り」，「翻訳文の表現・語法の誤り」の自動翻訳に関わるいずれかの要因が該当しているメッセージ文の数を「翻訳上の誤り文数」として示している。一つのメッセージ文には，複数の問題要因が含まれていることもあるので，各要因の合計数と「翻訳上の誤り文数」は，必ずしも一致しない。 表６．２は，理解が困
JavascriptでSuffixArray - やればできる子の日記
全文検索エンジンを試作してみたよ - やればできる子の日記とJavascriptを組み合わせてもうちょっとなにかできないかなあと思って、JavascriptでSuffixArrayを作ってみました。 上手い具合に組み合わせるアイデアが思いつけなかった(どうせ全文検索用のインデックスを保持しちゃうので、別途SuffixArrayを保持する意味がなさそう)ので、素のまま公開しちゃいます。 ちなみに、Javascriptも自信ないです。僕はJSでのべ2000行程度しか書いたことないはず。 /* Suffix Array構築のアルゴリズムは色々研究されています。 以下のコードはかなり最悪なアルゴリズムなので、実用の際は調査してください。*/ function genSA(text){ var sa = new Array(text.length) for(var i = 0; i < text.l
((Pythonで) 書く (Lisp) インタプリタ)
Peter Norvig / 青木靖 訳 このページには2つの目的がある。コンピュータ言語の実装について一般的な記述をすることと、Lispの方言であるSchemeのサブセットをPythonで実装する具体的な方法を示すことである。私はこのインタプリタをLispy (lis.py)と呼ぶ。何年か前に私はJavaとCommon LispでSchemeインタプリタを書く方法を示した。今回の目標は、アラン・ケイが「ソフトウェアのマクスウェル方程式」と呼んだところの簡潔さと取っつきやすさを可能な限り実現するということだ。 SchemeのサブセットLispy の構文と意味論 コンピュータ言語の多くは様々な構文的な決まり(キーワード、中置演算子、カッコ、演算子優先順、ドット記法、セミコロンなど)を持っているが、Lisp族言語の1つとして、Schemeの構文はすべてカッコ付きの前置記法であるリストを基本とし
LFM - Wikipedia
LFM(Leniar Filtering Method)とは、データの成分分解法を採用したデータ構造である FAST構造を処理するアルゴリズム群（特許取得済み）の総称。 従来のレコード単位処理に対し、全く新たな概念「ファイル単位一括オンメモリー処理」を実現し、 64ビット、メモリー大容量化、マルチコア、超並列時代に適合したデータ超高速並列処理技術である。 PC（マルチコア）からサーバ（SMP、マルチコア）CELL・パラレルコンピュータに適用可能 数百行小規模データから大規模約21億行（32ビット行カウンタ）まで、普遍的、統一的に処理 世界で初めて、プログラミングインデペンデントでデータ処理の並列化を実現 大規模テーブル（表）データを、ビジュアル、インタラクティブに高速に処理 ソート、ジョイン、検索、抽出、集計、計算、等々各種データ加工処理を関数化して一括処理 中間ファイル用Disc不要；高
Pythonでアルゴリズム - Konnichiwa, A doumo
これはなんですか？ 奥村晴彦氏の著書「C言語による最新アルゴリズム事典」をPythonでやろうと決意。Rubyに翻訳されていたので、Pythonでもやってみようと。でも実は書籍はもっていなくてCとRubyのソースを見つつ翻訳しています。１日１個ペースで進んでいます。 やっているうちにこの本が欲しくなってきました。 個人のPython力を高めるために始めましたので、間違いが含まれているかもしれません。ご指摘等ございましたら連絡[syobosyobo at gmail dot com]ください。 ちょっと方針をかえて、ctopyで訳すことにした。またまた方針をかえて、、、ctopyはあまりつかえない。ちょっといじってやらないと、出力がよくない。コメントとか入ってると、うまく変換してくれないし。 で、そのあとPythonらしい書き方で書いていこう、かと。どうなるかわかりませんが。
遺伝的アルゴリズムを使って数独を解く | TRIVIAL TECHNOLOGIES 4 @ats のイクメン日記
みんなのIoT/みんなのPythonの著者。二子玉近く160平米の庭付き一戸建てに嫁/息子/娘/わんこと暮らしてます。月間1000万PV/150万UUのWebサービス運営中。 免責事項 プライバシーポリシー Solving Sudoku with genetic algorithms(遺伝的アルゴリズムを使って数独を解く) というブログエントリを読んで，遺伝的アルゴリズムの入門記事として面白かったので紹介。 遺伝的アルゴリズムとは，生命の遺伝の仕組みを模した方法を使って解を探索する手法のこと。データを遺伝子で表現した個体を複数用意し，適応度によって個体を選択し，遺伝子に突然変異を起こしたりして解を探索してゆく。実装例としては，PostgreSQLが問い合わせを最適化するのに遺伝的アルゴリズムを使っている。上記エントリでは，この遺伝的アルゴリズムを使って数独の問題を解く手法を紹介している。
最小完全ハッシュ関数の作り方 を JavaScript で - てっく煮ブログ
JavaScriptActionScript/Flex ネタが続いているので、たまには JavaScript ネタを。はてブ経由で知った 最小完全ハッシュ関数の作り方 が面白そうだったのだけど、「最小完全ハッシュ関数」が何か分からないまま読み進めたら、やっぱり話が分からなくなってしまった。分からないまま JavaScript に移植。 /* 順列型の最小完全ハッシュ関数 */ function ChangeNumber(arr) { var work = arr.concat(); var hash = 0; // 階乗値テーブル作成 var FACTOR = [1]; for(var i=0; i { FACTOR.unshift(FACTOR[0] * (i+1)); } for(var i=0; i { hash += work[i] * FACTOR[i]; for (j=i+1;
24.2 キュー
キューは入出力機構の実装に良く用いられるメカニズムで、スーパー のレジに並ぶ買物客を想像すれば良い。この場合、最初に並んだ人から順に 処理され、新しい人は列の最後に並ばなければならない。最後に並んだ人が 最後に処理され出て行くので、Last In Last Out (LILO)とも呼ばれる(一方、 最初に並んだ客が最初に処理されると考えても良く、この場合には FIFO(First In First Out)とも言われる)。 ここでは買物客を例にしたが、買物客の代わりにキーボードから入力された キーデータを考えれば、キーボードバッファの仕組みなるし、通信の際に 出て行くデータの列だと考えれば、通信用の出力バッファの仕組みにもなる。 (こうしたメカニズムが必要なのは多くの場合、キューに入る動作と キューから出ていく動作が同期していないような場合である。そのような とき、キューはデータを管理する
Flyweight パターン - Wikipedia
Flyweight パターン（フライウェイト・パターン）とは、GoFによって定義されたデザインパターンの1つである。等価なインスタンスを別々の箇所で使用する際に、一つのインスタンスを再利用することによって計算資源の浪費を減らすことを目的とする。なお、flyweightとは、英語で「フライ級」を意味し、ボクシングにおける体重別階級の1つである。 Flyweight パターンのクラス図を以下に挙げる。 FlyweightFactory クラスは Flyweight インスタンスのコンテナをフィールドとして持ち、Flyweight オブジェクトを返すメソッド getFlyweight() を実装する。 Flyweight パターンで設計された API では、利用者は Flyweight クラスにあたるインスタンスを取得する場合に、直接そのクラスのコンストラクタを呼び出す代わりに Flyweigh
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
J-Tokkyo.com
Dragons Ahead