Paxosアルゴリズム - Wikipedia
Paxosとは信頼性が低いプロセッサのネットワークにおいて合意の問題を解決するためのプロトコルの集合である。 合意とは参加者のグループにおいて単一の結果について合意を得るプロセスである。参加者や通信手法に障害が起きる可能性がある場合、この問題は困難なものとなる[1]。 合意プロトコルは分散コンピューティングにおける状態機械アプローチの基礎であり、これはレスリー・ランポート[2]により提案され、Fred Schneiderによってサーベイがなされている[3]。 Paxosプロトコルは1990年に登場し命名されたが、論文として出版されたのは1998年であった[4]。 これ以前に、ナンシー・リンチ、Cynthia Dwork、Larry Stockmeyerは"部分同期"システムの広い範囲における合意形成方法を例証している。Paxosは分散トランザクションの文脈において、1988年にOkiとBa
動的計画法解説 [TopCoder SRM 468 Div2 250/Div1 500]
動的計画法解説 [SRM 468 Div2 250/Div1 500] 目次 問題１（入門編） 全探索 再帰と漸化式 メモ化再帰 動的計画法 問題２（初級～中級編） 全探索 再帰と漸化式 動的計画法 問題１ 王様は長い間出張していたので、できるだけ早く女王のもとに帰りたいと思っています。王様は都市 0 におり、女王は都市 N (1 <= N <= 50)に居ます。全ての都市 i (0 <= i <= N - 1) に対して陸路と空路があります。配列 roadTime, flightTime が与えられ、それぞれの i 番目の要素は都市 i から都市 i + 1 までの陸路、空路の所要時間 (1 以上 1000 以下) を表わします。しかし王国の科学力は低く、空路による移動は墜落の危険を伴います。そのため、王女は王様に空路は K (0 <= K <= N) 回までに留めるように言いました。王
線形補間 - Wikipedia
区分的線形補間の例 区分線形補間の例 2次元の区分線形補間の例 線形補間（せんけいほかん、英: Linear interpolation, lerp）は、多項式補間の特殊なケースで、線形多項式（一次式）を用いた回帰分析の手法である。1次補間としても知られている。 なお、3つ以上のデータに対し線形補間といった場合、1つの線型近似によるフィッティングではなく、区分線形関数を使った区分線形補間（1次スプライン補間、いわゆる折れ線グラフ）のことである。 線形補間は数学の世界（特に数値解析）やコンピュータグラフィックスを含む多くの分野で非常によく使われている。補間の非常に単純な形式であり、これより単純なのは最近傍補間（0次補間）しかない。 座標(x0, y0)と(x1, y1)があるとする。ここで、 [x0, x1]の間にあるxが与えられたときに、この線上にある点を得たいとする。図をよく見ると次のこ
リバーシプログラムの作り方 サンプル
序章 はじめに リバーシのルール ソースコードの記述について 第１章 盤面の処理 1.1 定数と関数の定義 1.2 盤面の生成、初期化 1.3 石を返す処理 1.4 返せる石数を調べる処理 1.5 盤面をコピー、反転させる処理 1.6 その他の盤面処理 1.7 盤面の操作と表示 第２章 ゲーム木と探索 2.1 コンピュータ思考の関数定義 2.2 各関数の実装 2.3 ゲーム木 2.4 MinMax法とNegaMax法 2.5 αβ法 第３章 盤面の評価 3.1 評価関数の定義 3.2 パターンによる局面評価 3.3 評価クラスの構造 3.4 評価クラスの生成とファイルの読み書き 3.5 評価関数の実装 3.6 評価パラメータの更新 3.7 中盤の探索 3.8 自己対局による学習 第４章 性能改善 4.1 石数取得の高速化 4.2 着手の高速化 4.3 候補手リストの導入 4.4 終盤探索の
ソート済みファイルをトライ木に見立ててレベル順(幅優先)探索を行う - sileのブログ
以下のような内容のファイルがあるとする。 # ファイル名: sample.txt ※ この部分はファイルに含まれない ab abc abef 1 1248 126 13579 これは次のような構造を持つトライ木として考えることができる。※'_ROOT_'は仮想的なスーパールート 今回は、上のようなソート済みのファイルを入力とし、それに対応する木(トライ木)をレベル順(幅優先)に探索する、といったことを行う。 補助クラス まずは、そのために必要な補助的なクラスを定義。 /*** * ファイル名: char_stream.h * 概要: * - 文字ストリーム * - char* の軽いラッパークラス */ #ifndef CHAR_STREAM_H #define CHAR_STREAM_H class CharStream { public: CharStream(const char*
二分探索木 - Wikipedia
この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "二分探索木" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2023年3月) 二分探索木 二分探索木（にぶんたんさくぎ、英: binary search tree）は、コンピュータプログラムにおいて、「左の子孫の値 ≤ 親の値 ≤ 右の子孫の値」という制約を持つ二分木である。探索木のうちで最も基本的な木構造である。 構造は二分木と同じだが、「左の子孫の値 ≤ 親 ≤ 右の子孫の値」という制約を持つ。左の子孫の値と右の子孫の値の両方に等号をつけているが、実際にはどちらかに統一しておく必要がある。 平衡（左右のバランスがとれている状態）し
Phone Directory Implementation Using TRIE
Download demo project - 28.2 KBDownload source files - 28.5 KB Introduction Trie is an ordered tree data structure that uses strings as keys. Unlike Binary Trees, Tries do not store keys associated with the node. The key is actually determined based on the position of the node on the tree. Any descendants of a node shares a common prefix of the key string associated with that node. Hence, trie is
)
トライ (データ構造) - Wikipedia
"A", "to", "tea", "ted", "ten", "i", "in", "inn" というキー群によるトライ木 トライ木（英: trie）やプレフィックス木（英: prefix tree）とは、順序付き木の一種。あるノードの配下の全ノードは、自身に対応する文字列に共通するプレフィックス（接頭部）があり、ルート（根）には空の文字列が対応している。値は一般に全ノードに対応して存在するわけではなく、末端ノードや一部の中間ノードだけがキーに対応した値を格納している。2分探索木と異なり、各ノードに個々のキーが格納されるのではなく、木構造上のノードの位置とキーが対応している。 キーが文字列である連想配列の実装構造としても使われる。右図の例では、ノードを表す丸の中にキーが書かれ、連想される値がその下に書かれている。値が書かれていないノードはキー文字列の途中までにしか対応していない。各英単語
404 Blog Not Found:アルゴリズム百選 - 二分探索(binary search)
2007年12月04日08:30 カテゴリアルゴリズム百選Math アルゴリズム百選 - 二分探索(binary search) 今回は二分探索を取り上げます。 検索:コンピューターの最もよくある利用法 「二分探索って何?」「ググレカス」と言われないためにこの記事は存在するのですが、Webの検索に限らず、「目的のデータを見つけて取り出す」というのは、およそコンピューターの利用法で最もポピュラーなものです。 配列:コンピューターがデータを扱う根本的な方法 そのデータはコンピューターのなかでどう置かれているかというと、非常に単純です。デジタル化されたデータ=数値が一定間隔で並んでいるだけです。こういうデータ構造を、配列(array)といい、この数値一個一個のことを要素(element)と言います。 現代のコンピューターでは、最小要素はバイト(byte)と呼ばれています。このバイトの中には0と1
床関数と天井関数 - Wikipedia
この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "床関数と天井関数" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2016年11月) 床関数 天井関数 床関数（ゆかかんすう、英: floor function）と天井関数（てんじょうかんすう、英: ceiling function）は、実数に対してそれぞれ、自身以下の最大、自身以上の最小の整数を出力する関数である。 英語の floor, ceiling といった名称と、, という記法は、プログラミング言語 APL の元となる A Programming Language という本の中でケネス・アイバーソンによって1962年に導入され
コーダーの聖地「TopCoder Open」で日本人が2部門制覇
日本最強のアルゴリズマーたち、世界をうならせる プログラミングコンテストを企画・運営する米TopCoderは10月15日、コンピュータ・プログラミングと創造的設計のトーナメントである「2010 TopCoder Open」で、日本人が2部門を制したことを発表した。 TopCoderでは、さまざまなジャンルのコンテストが開催されており、例えばAlgorithm部門では、ほぼ毎週のようにSRM（Single Round Match）が開催されている。TopCoder Open（TCO）は、年に一度開催されるトーナメント制の大会で、オンラインで行われる数回の予選を経て、米国ラスベガスで開催される決勝戦に参加できる。TopCoderで日々しのぎを削る世界中のコーダーたちの中でも、特に優れた者だけが参加を許されるコーダーの聖域ともいえる大会。 今回のTopCoder Openに日本人としてラスベガス
二分木 - sotarokのお勉強
BTreeを書いた．集合型ということで． setと最小値を取り出すminpopのみサポート．木のバランスが崩れたときの再構築とかは考えていない． <?php // BTree.php // set class BTree { public $num = null; public $left = null; public $right = null; public function set($x) { if ($this->num === null) { $this->num = $x; } else { if ($this->num > $x) { $call = "left"; } else if ($this->num < $x) { $call = "right"; } else { return ; } if ($this->{$call} === null) { $this->{
ダイクストラ法（最短経路問題）
ダイクストラ法 (Dijkstra's Algorithm) は最短経路問題を効率的に解くグラフ理論におけるアルゴリズムです。 スタートノードからゴールノードまでの最短距離とその経路を求めることができます。 アルゴリズム 以下のグラフを例にダイクストラのアルゴリズムを解説します。 円がノード，線がエッジで，sがスタートノード，gがゴールノードを表しています。 エッジの近くに書かれている数字はそのエッジを通るのに必要なコスト（たいてい距離または時間）です。 ここではエッジに向きが存在しない（＝どちらからでも通れる）無向グラフだとして扱っていますが， ダイクストラ法の場合はそれほど無向グラフと有向グラフを区別して考える必要はありません。 ダイクストラ法はDP（動的計画法）的なアルゴリズムです。 つまり，「手近で明らかなことから順次確定していき，その確定した情報をもとにさらに遠くまで確定していく
category プラグインを利用した タグクラウド 表示プラグイン - SmallStyle(2006-05-23)
_ category プラグインを利用した タグクラウド 表示プラグイン tDiary のプラグインつくりが最近は結構楽しくなってきて，いろいろアイデアが出ては実装できるかなぁとか，ちまちまプログラミングをしているわけですが，今日は category プラグインを機能拡張したタグクラウド表示プラグインを作ってみました．タグクラウドとは， tag cloud。SBMのようなタグを利用するウェブサイトで、多くのタグを集めて表示したもの。またそのような情報の表示方法。クラウドは「雲」や「群れ」の意味。 最初にタグクラウドを利用したウェブサイトはウェブアルバムサービスのFlickrであると言う（Flickrの人気タグページ）。それと同様に人気や利用頻度の高いタグが大きな文字で強調される表示方法がとられる場合が多い。 はてな - タグクラウドとはより引用 というもので，最近は tDiary でも c
Tag Cloud in Ruby [ruby] [tagging] [cloud] [options]
Never been to DZone Snippets before? Snippets is a public source code repository. Easily build up your personal collection of code snippets, categorize them with tags / keywords, and share them with the world The options.delete with the default looks mildly interesting. Just wanted to remember that. def font_size_for_tag_cloud( total, lowest, highest, options={} ) return nil if total.nil? or high
タグクラウドのアルゴリズム (それなりブログ)
それなりブログ 20台後半からWebエンジニアに転生した人が書く、プログラム・無駄口とかのそれなりのブログ 管理人: kjirou 座右の銘: 「三度の飯より、四度の飯」 タグクラウドの大きさを決めているアルゴリズムはどうなってるのかなと、PHPのTagCloud.phpと、Rubyのtagcloud-rubyを読んみました。 両方ともCSSセレクタ生成等が処理の中に入ってしまっており、ライブラリとしてはやや微妙な感じ。（元のPerlの実装に合わせているからだと思いますが） なので、アルゴリズムだけ貰おうかと。 【最も基本的なアルゴリズム】 最終的に、各タグの大きさは25段階の範囲で区分される。 ソース内ではこれを level と読んでおり、0-24の範囲で指定している。 level算出方法は以下の通り 1. 最もタグ付けされている回数が多いタグの回数を取得し、それの平方根を求
YouTube - What different sorting algorithms sound like
This particular audibilization is just one of many ways to generate sound from running sorting algorithms. Here on every comparison of two numbers (elements) I play (mix) sin waves with frequencies modulated by values of these numbers. There are quite a few parameters that may drastically change resulting sound - I just chose parameteres that imo felt best. After making this video I found that so
Hexerpents of Hexwamp
Problem C: 六角沼の六角大蛇 六角沼は不思議な沼で，正六角形の窪みが整然と並ぶ．この沼をゆったり這いまわる六角大蛇(ろっかくおろち)は，環境に適応して正六角形の節が並んだ蛇．窪みひとつに節ひとつ． 六角大蛇が這うときには，いくつかの節を今ある窪みから隣の窪みに移す．体を分断するわけにはいかないので，動く前に隣同士だった節は，動いた後も隣同士でなくてはならない．ある節を動かすとき，すぐ隣の節はその動きを支えるので，一緒には動かせない．隣り合っていない節ならいくつでも同時に動かせる． 少し考えてみれば節を動せる先は，体の両端でせいぜい2箇所の窪み，体の中間の節ではせいぜい1箇所しかないのがわかるだろう． たとえば，障害物がないときには六角大蛇は図C-1に左から右に示すように体をよじらせながら前進できる．8個の節のうち4個ずつを一度に動かし，4ステップかけてちょうど1コマ前進したこと
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
C_memo(5)
Heapsort audibilization
