Bin Packing 問題 近似アルゴリズム
Bin Packing 問題 近似アルゴリズム ■ Bin Packing 問題は次のように定義される： いろいろな大きさのコップに、その容積一杯に水が入っているとする。各コップ u の容積は正の整数 s(u) とするとき、コップの集合を U とする。 一方、容積がどれも正の整数 B であるビンが K 個あるとする。 各コップの水はどれか一つのビンに注ぐとするとき、各ビンがこぼれないように注ぐ方法はあるか？ このように、方法が存在するか否かを問う問題は、「決定問題」と呼ばれる。 ■ 一方、次の問題を「最適化問題」と呼ぶ。 コップの集合Uに対して、最小何個のビンがあれば、各ビンがこぼれないようにできるか？ 最適化問題を解いて、最小のビンの数が OPT 個と分かったならば、決定問題は OPT ≦ K ならば、方法が存在し、 K ＜ OPT ならば、方法は存在しない というように簡単に解くこと
Data Structure Visualization
Currently, we have visualizations for the following data structures and algorithms: Basics Stack: Array Implementation Stack: Linked List Implementation Queues: Array Implementation Queues: Linked List Implementation Lists: Array Implementation (available in java version) Lists: Linked List Implementation (available in java version) Recursion Factorial Reversing a String N-Queens Problem Indexing
MapReduce Patterns, Algorithms, and Use Cases
In this article I digested a number of MapReduce patterns and algorithms to give a systematic view of the different techniques that can be found on the web or scientific articles. Several practical case studies are also provided. All descriptions and code snippets use the standard Hadoop’s MapReduce model with Mappers, Reduces, Combiners, Partitioners, and sorting. This framework is depicted in th
最小二乗法 [物理のかぎしっぽ]
横軸に時間，縦軸に位置をとり，これをグラフにしてみます （説明のため，グラフ中では横軸を x，縦軸を y と書いています）． 厳密な等速直線運動ならば，このデータは直線で結ばれ，その傾きは速度を表します． しかし実験には誤差がつきもので，ものさしの誤差， 測定者のくせによる誤差，測定環境の変化による誤差など，いろいろな誤差が存在します． ですから，測定データは一直線上には並びません．だからといってデータの各点を のように繋げて折れ線グラフにしてもあまり意味がありません． このグラフの傾きは速さを表すはずですが， 折れ線グラフから傾きを求めることはできないですし， そもそも誤差を含んでいる点をそのまま結んでも仕方がありません．そこで のようにどのデータポイントからもあまり外れないように直線を引くのが妥当だといえます． 直線は1次関数ですから y = ax + b とおけるハズです． 目分量で
Compressed Suffix Arrayの記事まとめ - EchizenBlog-Zwei
一応CSAの記事を書き終えたので、各記事へのリンクリストを。 補足:記事を7つも読むの面倒くさい人は、↓にもう少し簡単な圧縮法の解説を書いておいたので参照されたい。 15分でわかる(とうれしい)Suffix Arrayの簡単な圧縮法 Compressed Suffix Arrayの解説(1) -Suffix Array- Compressed Suffix Arrayの解説(2) -SAの計算量- Compressed Suffix Arrayの解説(3) -圧縮の方針- Compressed Suffix Arrayの解説(4) -unary記法- Compressed Suffix Arrayの解説(5) -Succinct Bit Vector- Compressed Suffix Arrayの解説(6) -B Vectorと Ψ Vector- Compressed Suffix
クラスカル法 - Wikipedia
クラスカル法（英: Kruskal's algorithm）は、グラフ理論において重み付き連結グラフの最小全域木を求める最適化問題のアルゴリズムである。 概要[編集] このアルゴリズムは、1956年にジョゼフ・クラスカル（英語版）が Proceedings of the American Mathematical Society で発表した (pp. 48–50)。 クラスカル法は貪欲法の一種で、最小全域木を求める他のアルゴリズムとしては、プリム法、逆削除法（英語版）、ブルーフカ法などがある。最小全域木とは、グラフの全ての頂点を含む木で、辺の重みの総和が最小のものを言う。連結されていないグラフでは、「最小全域森」（それぞれの連結部分の最小全域木の集合）を求められる。 アルゴリズムの解説[編集] クラスカル法の手順は次の通り。 グラフの各頂点がそれぞれの木に属するように、森（木の集合） F
プリム法 - Wikipedia
プリム法とは、グラフ理論で重み付き連結グラフの最小全域木を求める最適化問題のアルゴリズムである。全域木（対象となるグラフの全頂点を含む辺の部分集合で構成される木）のうち、その辺群の重みの総和が最小となる木を求めるものである。このアルゴリズムは1930年に数学者 Vojtěch Jarník が発見し、1957年に計算機科学者ロバート・C・プリムが独自に発見、さらに1959年にはエドガー・ダイクストラが再発見しダイクストラ法の論文に記載している。そのため、DJP法、Jarník法、Prim-Jarník法などとも呼ばれることがある。アルゴリズムの発想や計算量は同時期に発表されたダイクストラ法に類似している。 アルゴリズムの解説[編集] このアルゴリズムでは1つの辺から始めて、全頂点を覆うようになるまで連続的に木の大きさを拡大していく。 入力: 重み付きグラフ（頂点集合 V、辺集合 E） 出力
perfecthash
最小完全ハッシュ函数 ハッシュ函数のうち、可逆で、かつ、生成するハッシュ値の値域が最小である函数のことを、最小完全ハッシュ函数と言います。 その作り方を解説していきたいと思います。
ループ構造の正しさを証明してやる！ [それはBooks]
Code Readingを読んで、ループ性能(妥当性)に関しての議論を考えるときに、有効な手段があると書いてあった。「バリアント(variant)」と「インバリアント(invariant)」という概念を使う方法だ。「バリアント(variant)」とは、変わりやすいとか変更されるといった意味を持っている。 逆に「インバリアント(invariant)」は、変わらないとか不変なとかという意味を持っているらしい。 この「バリアント(variant)」と「インバリアント(invariant)」を使って、ループ構造が正しいかを証明する方法が、Code Readingの2章に載っていたので、忘れないうちに復習しておきたいと思います。 それにしても、Code Readingは面白いですね。技術者のツボをついた本だと思います。 概要と解説ループ処理の開始と終了の時点で共に成り立つ条件をループインバリアント
きまぐれ日記: 動的配列への追加コストはなぜ O(1)?
動的配列への追加コストは O(1) ってのは覚えていればそれだけの話ですが，どうしてかと言われると意外と難しいものです． というのも, このO(1)ってのは動的配列の実装方法に強く依存しているからです．実装を知っていないと答えられません． 一般論として，1つ要素を追加するとき，配列に空きがなかったら新しく配列を作り直して全要素をコピーする必要があります．コピーのコストは O(n) だから，追加コストも O(n) になるという議論が混乱の元になっています． こういうときは，要素追加を n 回繰り返したときの計算量を n で割った平均をとるという解析方法が使われるそうです．一般に, ある operation C の計算量を C を n 回行ったときの計算量 O(n) を n で割った値 O(n)/n で評価する手法をならし解析 (amortized analysis)と言うそうです． さて，s
Security Akademeia【セキュリティアカデメイア】
当サイトの一部ページには、アフィリエイト・アドセンス・アソシエイト・プロモーション広告を掲載しています。 Amazonのアソシエイトとして、Security Akademeiaは適格販売により収入を得ています。 広告配信等の詳細については、プライバシーポリシーページに掲載しています。 消費者庁が、2023年10月1日から施行する景品表示法の規制対象（通称:ステマ規制）にならないよう、配慮して記事を作成しています。もし問題の表現がありましたら、問い合わせページよりご連絡ください。 参考：令和5年10月1日からステルスマーケティングは景品表示法違反となります。 | 消費者庁 毎月8日はメルカードの日Amazonファーマシー3日はau PAY ありがとうギフト、がんばったボーナスの付与日ソースネクストの創立感謝フェアdポイント増量キャンペーン2024SummerキャンペーンAEON Pay現金チ
Loop unrolling - Wikipedia
Loop unrolling, also known as loop unwinding, is a loop transformation technique that attempts to optimize a program's execution speed at the expense of its binary size, which is an approach known as space–time tradeoff. The transformation can be undertaken manually by the programmer or by an optimizing compiler. On modern processors, loop unrolling is often counterproductive, as the increased cod
アルゴリズムとデータ構造 演習第 10 回
アルゴリズムとデータ構造 演習第 10 回 サーチ１（二分探索） データの中から、あるデータを探すことを探索といいます。 ここでは二分探索 （アルゴリズムＣ 第２巻 p.8） を用いて探索を行います。 問題１ ［印刷用 PostScript］ 次のようなソートされたデータがある。 1 4 6 9 10 13 19 23 25 30 (1) このデータから二分探索を用いて 9 を探索する過程を書きなさい。 (2) このデータから内挿探索を用いて 9 を探索する過程を書きなさい。 二分探索、内挿探索はソートされているデータに対して行う探索方法です。 二分探索（アルゴリズムＣ 第２巻 p.8） 真ん中のデータが見つけたいデータかどうか調べます。 見つけたいデータが真ん中のデータより小さければ左側に対して、 大きければ右側に対して、同じことを繰り返します。 内挿探索（アルゴリズムＣ 第２巻 p.1
Interpolation search - Wikipedia
This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Interpolation search" – news · newspapers · books · scholar · JSTOR (September 2017) (Learn how and when to remove this message) Interpolation search is an algorithm for searching for a key in an array t
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Similarity Join Algorithms: An Introduction
obstruction-free
定兼 邦彦 (Kunihiko Sadakane) - 簡潔データ構造講義資料 - researchmap
データ構造とアルゴリズム: ヒープとヒープソート
データを加工して圧縮率を高めよう
サービス終了のお知らせ