最大フロー最小カット定理 - Wikipedia
最大フロー最小カット定理（さいだいフローさいしょうカットていり、英: Max-flow min-cut theorem）は、フローネットワークにおける最大フロー問題についての定理である。これは、ネットワークに流れる「もの」の最大流量が、ボトルネックによって決まることを意味している。線形計画法についての定理メンガーの定理から導出することもできる。 左から:1. 与えられたネットワーク。各エッジの容量はすべて等しいとする。2. ひとつのフロー。3. 2の残余ネットワークと、その増加道。 4. 最大フローの残余ネットワーク。s から到達可能な緑の丸印のノードの集合をS, 不可能な青の四角のノードの集合をTとすると、(S, T) が最小カットになっている。 二端子フローネットワーク が与えられたとする。つまり、有限の有向グラフ の各エッジ（辺） に非負実数の容量 が割り当てられており、始点となるノ
フローネットワーク - Wikipedia
フローネットワーク（英: Flow network）は、グラフ理論における重み付き有向グラフの一種であり、各枝に容量（capacity）を設定し、各枝をフロー（flow）が流れる。各枝のフローはその容量を超えることはない。オペレーションズ・リサーチでは、重み付きグラフをネットワークと呼び、頂点をノード、枝をアークと呼ぶ。フローが満足すべき制約条件として、1つのノードに流入するフローとそのノードから流出するフローは常に等しい。ただし、始点（source）と終点（sink）では、その限りではない。このネットワークは、例えば道路網の交通量、パイプを流れる液体、電気回路を流れる電流、その他の何らかのネットワーク上を移動するものをモデル化するのに適している。フローネットワークに関する最適化問題はネットワークフロー問題と呼ばれる。
フォード・ファルカーソンのアルゴリズム - Wikipedia
この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "フォード・ファルカーソンのアルゴリズム" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2015年11月) フォード・ファルカーソンのアルゴリズム（英: Ford-Fulkerson algorithm）とは、フローネットワークにおける最大フローを求めるアルゴリズムである[1]。レスター・フォード Jr.（英語版、ドイツ語版、フランス語版、ロシア語版） と デルバート・ファルカーソン（英語版、ドイツ語版、スペイン語版、フランス語版） にちなんで命名されたもので、1956年に発表された。フォード・ファルカーソンのアルゴリズムの特殊版であ
中国の剰余定理 - Wikipedia
ガウスは『整数論』（1801年）において中国の剰余定理を明確に記述して証明した[1]。 中国の剰余定理（ちゅうごくのじょうよていり、英: Chinese remainder theorem）は、中国の算術書『孫子算経』に由来する整数の剰余に関する定理である。あるいは、それを一般化した可換環論における定理でもある。中国人の剰余定理（ちゅうごくじんのじょうよていり）、孫子の定理（そんしのていり、英: Sunzi's theorem）とも呼ばれる。 『孫子算経』には、「3で割ると2余り、5で割ると3余り、7で割ると2余る数は何か」という問題とその解法が書かれている。中国の剰余定理は、この問題を他の整数についても適用できるように一般化したものである。 3 - 5世紀頃成立したといわれている中国の算術書『孫子算経』には、以下のような問題とその解答が書かれている[2]。 今有物、不知其数。三・三数之、
C - で私も素数を数えてみた : 404 Blog Not Found
2010年07月26日18:30 カテゴリMath C - で私も素数を数えてみた 世間は夏休みだそうだし、連日の猛暑で体調も底だし、というわけで私も素数を数えてみた。 10兆までの素数のリストを作ってみませんか？ - 記者の眼：ITpro もしあなたがプログラマだったら、プログラムを書いて10兆までの素数のリストを作ってみてほしい。情報システムの開発に携わる人であれば、10兆までの素数のリストを出力するシステムの見積もりを考えてみてほしい。費用はどれくらいかかるか、納期はどれくらいか、あなたはどんな答を出すだろうか。仕様書はうまく書けるだろうか。 プライムナンバーズ David Wells / 伊知地宏監訳 / さかいなおみ訳 [原著:Prime Numbers: The Most Mysterious Figures In Math] といっても原田記者と同じように書いても芸がないので
C - で素数を数え直したら、範囲10億で10秒切ったお : 404 Blog Not Found
2010年07月28日01:30 カテゴリMath C - で素数を数え直したら、範囲10億で10秒切ったお というわけで数え直したら… 404 Blog Not Found:C - で私も素数を数えてみた はてなブックマーク - mohnoのブックマーク「Core i7 な iMac で、10億の範囲を検索するのに1プロセス300秒前後」←遅いってこと？ エラトステネスのふるいで、原田氏の記事でも10億なら2分（Core i7 920）、私の手元では20秒（Core 2 Duo E6850）だったんだけど。 10秒を切ってしまったので。 次にアルゴリズムであるが、いろいろいじってみた結果こうした。 まず p < 256 な小さな素数でエラトステネスのふるいにかけ 次にMiller-Rabin素数判定法を適用する これは「個々の64bit整数が素数かどうか」を判定するのには(素数表を引くこ
行列分解ライブラリredsvdを公開しました - DO++
大規模疎行列向けの行列分解ライブラリredsvdを公開しました． redsvd 大規模疎行列向けの特異値分解や主成分分析，固有値分解を行うライブラリredsvdを公開しました． 修正BSDライセンスで公開しており，コマンドラインから使える他，C++ライブラリが用意されています． 例えば，行と列数がそれぞれ10万，非零の要素が1000万からなる疎行列に対する上位20位までの特異値分解を約2秒で処理します． 特異値分解とか，使っている技術の詳細とか応用事例を以下に簡単に紹介しましたので，興味のある方は参考にしてください． 特異値分解とは まず行列を適当に復習します．行列Xの転置をX^tと表すことにします．またIを単位行列とし，Oを全ての成分が0である零行列とします．また，行列XX^t=IであるようなXを直交行列と呼びます．Xが直交行列の時，Xvはベクトルvを長さを変えずに回転させます．ここでは
Sorting algorithms: quite boring until you add sound effects - Geek.com
This site may earn affiliate commissions from the links on this page. Terms of use. Anyone who has ever done a programming course or tried to learn to code out of a book will have come across sorting algorithms. Bubble, heap, merge, there’s a long list of these methods of sorting data. The subject matter is fairly dry. Thankfully someone has found a way to not only make sorting more interesting, b
ridiculous_fish » Blog Archive » The Treacherous Optimization
Old age and treachery will beat youth and skill every time. "I’m going to beat grep by thirty percent!" I confidently crow to anyone who would listen, those foolish enough to enter my office. And my girlfriend too, who’s contractually obligated to pay attention to everything I say. See, I was working on Hex Fiend, and searching was dog slow. But Hex Fiend is supposed to be fast, and I want blazing
why GNU grep is fast
Mike Haertel mike at ducky.net Sat Aug 21 03:00:30 UTC 2010 Previous message: Latest intr problems Next message: why GNU grep is fast Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] Hi Gabor, I am the original author of GNU grep. I am also a FreeBSD user, although I live on -stable (and older) and rarely pay attention to -current. However, while searching the -current mailing list f
Minimax - Wikipedia, the free encyclopedia
This article is about the decision theory concept. For other uses, see Minimax (disambiguation). Minimax (sometimes Minmax, MM[1] or saddle point[2]) is a decision rule used in artificial intelligence, decision theory, combinatorial game theory, statistics, and philosophy for minimizing the possible loss for a worst case (maximum loss) scenario. When dealing with gains, it is referred to as "maxim
アルファ・ベータ法 - Wikipedia
アルファ・ベータ法（アルファ・ベータほう、alpha-beta pruning）は完全情報ゲームにおける探索アルゴリズムの1つである。基本的にミニマックス法と同じであり、同じ計算結果が得られるが、ゲーム木において、計算しなくても同じ計算結果になる部分を枝刈りしている。 アルファ・ベータ法の擬似コードを以下に示す。alphabeta関数がアルゴリズムの実装であり、minimax関数はミニマックス法とインタフェースを揃えるためのラッパーである。 function minimax(node, depth) return alphabeta(node, depth, -∞, +∞) function alphabeta(node, depth, α, β) if node が終端ノード or depth = 0 return node の評価値 if node が自分のノード foreach ch
Algo 23 MSTP
The document discusses algorithms for finding minimum spanning trees in graphs. It describes Prim's and Kruskal's algorithms, which both run in O(ElogV) time where E is the number of edges and V is the number of vertices. It also mentions that Fibonacci heaps can be used to implement Prim's algorithm in O(E+VlogV) time.
Simplex algorithm - Wikipedia
This article is about the linear programming algorithm. For the non-linear optimization heuristic, see Nelder–Mead method. In mathematical optimization, Dantzig's simplex algorithm (or simplex method) is a popular algorithm for linear programming.[1][failed verification] The name of the algorithm is derived from the concept of a simplex and was suggested by T. S. Motzkin.[2] Simplices are not actu
ベルマンフォードのアルゴリズムで実行される結果も逐次表示 - yasuhisa's blog
離散最適化理論の課題が出ていたので、ベルマンフォードのアルゴリズムを実装してみることにした。アルゴリズムが実行されていく様子の例もレポートに貼ろうと思ったんだけど、アルゴリズムはもうあるんだから、その様子をruby-graphvizとかで吐けばいいじゃんということでやってみた。 pngファイルをアニメーションgifに変換するのはこんな感じで。この辺を参考に。 convert -geometry 320x500! -delay 150 -loop 0 bellman_ford_example_a_uniq*.png bellman_ford_example_a.gif 俺はRubyで書いたわけだけど、こんなことをやってるid:mickey24に「それRでできるよ!!」と言われそうである。 単一始点最短路問題に対するその他のアルゴリズムベルマンフォードのアルゴリズムは単一始点最短路問題に対する
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
微分積分
符号とその性質
サービス終了のお知らせ
1 from SIAM News, Volume 33, Number 4 By Barry A. Cipra Algos is the Greek word for pain. Algor is Latin, to be cold. Neither is the root for algorithm, which stems instead from al- Khwarizmi, the name of the ninth-century Arab scholar whose book al-jabr
サービス終了のお知らせ