指数時間アルゴリズム入門
2. 自己紹介 TopCoder: ◎wata TCO2010Marathon優勝など Twitter: @wata_orz 東京大学情報理工学系研究科コンピュータ科学専攻 理論計算機科学 (アルゴリズムの理論的な解析とか) プログラミングコンテスト チャレンジブック 2 3. 本日の内容 NP困難問題を解くためのアルゴリズムを扱います 𝑂𝑃𝑇 𝐼 ≤ 𝐴 𝐼 ≤ 𝑐𝑂𝑃𝑇(𝐼) 近似アルゴリズム ヒューリスティック 𝑓 𝑘 𝑝 𝑛 FPT アルゴリズム max 𝑐𝑥|𝐴𝑥 ≤ 𝑏, 𝑥: 整数} { 𝑂∗ 𝑐 𝑛 整数計画 厳密指数時間アルゴリズム 3 4. 効率的な指数時間アルゴリズム 何の指数？ 頂点数? 辺の数? それとも… • 2 𝐸 のアルゴリズムはまず役に立たないが，2 𝑉 のアル ゴリズムならコンテストでもよ
What's new in purely functional data structures since Okasaki?
Since Chris Okasaki's 1998 book "Purely functional data structures", I haven't seen too many new exciting purely functional data structures appear; I can name just a few: IntMap (also invented by Okasaki in 1998, but not present in that book) Finger trees (and their generalization over monoids) There are also some interesting ways of implementing already known datastructures, such as using "nested
Topcoder
Topcoder is a crowdsourcing marketplace that connects businesses with hard-to-find expertise. The Topcoder Community includes more than one million of the world’s top designers, developers, data scientists, and algorithmists. Global enterprises and startups alike use Topcoder to accelerate innovation, solve challenging problems, and tap into specialized skills on demand.
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
What are the lesser known but useful data structures?
There are some data structures around that are really useful but are unknown to most programmers. Which ones are they? Everybody knows about linked lists, binary trees, and hashes, but what about Skip lists and Bloom filters for example. I would like to know more data structures that are not so common, but are worth knowing because they rely on great ideas and enrich a programmer's tool box. PS: I
Main Page - Algowiki
AlgoWiki: The Programmer's Compendium Welcome to AlgoWiki, your resource for all algorithms, large and small. Please feel free to contribute as much as you'd like. We're still got a long way to go before we have a decent-sized code base. You can search for topics using the Search box, you can click Random page to go to a random page, or you can go to Special:Allpages to view a list of all the page
マルチキークイックソート - sileのブログ
「Sorting and Searching Strings」で説明されているマルチキークイックソートの実装。 詳細はリンク先を参照。 マルチキークイックソート 文字列の配列のソートが高速に行える URL("http://...")の配列のような接頭部分の重複率が高い文字列配列の場合でも性能が低下しにくい クイックソート + 基数ソート、のような感じ？ ソート方法 基本的には通常のクイックソートと似ていて「ピボット要素*1を選んで、配列を分割する」といったことを繰り返す。 ただし、クイックソートは各段階で配列を二分割(ピボット要素よりも大きいか小さいか*2 )し、そのための比較には要素(文字列)全体を用いるのに対して、マルチキークイックソートでは、配列は三分割(ピボット要素よりも大きいか小さいか、それとも等しいか)され、そのための比較には文字列全体ではなく(各段階で)一文字のみ、が用いられ
Libicpc - nya3.jp
libicpc チーム kkntkr / Unknown による、ACM-ICPC 向けのアルゴリズムの実装をまとめたページです。 基礎 テンプレート マクロ 計算 ビット演算 実数比較 幾何 基礎 データ構造 内積・外積 回転方向関数 射影 面積・体積 円と円の共通部分 多角形の面積 交差 円と円の交点 円と直線の交差判定 円と直線の交点 凸多角形と線分の包含判定 多角形と点の包含判定 直線と直線の交差判定 直線と直線の交点 直線と線分の交差判定 線分と点の交差判定 線分と線分の交差判定 距離 最遠点対 直線と点の距離 直線と直線の距離 直線と線分の距離 線分と点の距離 線分と線分の距離 多角形 凸包 凸多角形のクリッピング その他 アレンジメント ダイス 三次元幾何 直線と直線の距離 グラフ 基礎 データ構造 最短路 Bellman-Ford Dijkstra Warshall-Flo
焼きなまし法ライブラリ2 - nodchipの日記
以前公開していた焼きなましライブラリが古くなったので、新しく公開します。 そして、以前の記事を編集しようとしたところ、誤って削除してしまいました。もとには戻せないようです・・・。 typedef long long ll; #define REP(i,n) for(int i=0;i<(int)n;++i) #define ALL(c) (c).begin(), (c).end() #ifdef _MSC_VER #include <Windows.h> ll getTime() { return GetTickCount(); } #else #include <sys/time.h> ll getTime() { struct timeval tv; gettimeofday(&tv, NULL); ll result = tv.tv_sec * 1000LL + tv.tv_usec
前向きアルゴリズム、Vitebiアルゴリズム - yasuhisa's blog
Viterbi書くの何回目だろ。。。週末にはバウムウェルチ(Baum-Welch)のアルゴリズムこと前向き後ろ向きアルゴリズムを書きたいところ。 www.yasuhisay.info # -*- coding: utf-8 -*- # 確率的言語モデル(東京大学出版)第4章(隠れマルコフモデル) require 'pp' # 品詞iから品詞jへの遷移確率 # 番号と品詞の対応付け: 0(名詞)、1(冠詞)、2(動詞)、3(形容詞)、4(前置詞) a = [[0.3, 0.0, 0.4, 0.1, 0.2], [0.7, 0.0, 0.0, 0.3, 0.0], [0.3, 0.2, 0.1, 0.2, 0.2], [0.5, 0.1, 0.0, 0.4, 0.0], [0.6, 0.3, 0.0, 0.1, 0.0]] # 品詞jから単語iを生成する確率 # 番号と単語の対応付け: 0(T
Topcoder
Topcoder is a crowdsourcing marketplace that connects businesses with hard-to-find expertise. The Topcoder Community includes more than one million of the world’s top designers, developers, data scientists, and algorithmists. Global enterprises and startups alike use Topcoder to accelerate innovation, solve challenging problems, and tap into specialized skills on demand.
マルチコア時代の"データ構造とアルゴリズム"再入門
データ構造とアルゴリズム再入門 はじめに ・並{行|列} & {Lock|Wait}Free ・ABA & ABA' ・volatile ＆ メモリバリア ・プリミティブ ・CAS ・MCAS ・STM ・メモリ管理:free & GC ・Toots List & Skiplist [単方向List] ・リスト ・細粒度リスト ・Lazyリスト ・Lock-Freeリスト ・Lock-Freeリスト2 [SkipList] ・スキップリスト ・Lazyスキップリスト ・Lock-freeスキップリスト [双方向List] Queue & PriorityQueue [UnBounded Queue] ・Queue ・CAS based Lock-Free Queue ・LL/SC based Lock-Free Queue [Unbounded Priority Queue] ・Heap
プログラミングコンテストでのデータ構造
前編 (平衡二分探索木編) はこちら http://www.slideshare.net/iwiwi/2-12188757
プログラミングコンテストでの動的計画法
KMCの例会講座で用いたスライドを一部編集したものです。 ビット演算を組み合わせたトリッキーな方法で様々な操作を高速に行う方法を紹介します。
メモ化を用いたダイクストラ法の実装について 多変数の最適化問題において、問題がより小さな部分問題に分割でき、部分問題の最適解が全体の最適解に 含まれているという関係が再帰的
メモ化を用いたダイクストラ法の実装について 多変数の最適化問題において、問題がより小さな部分問題に分割でき、部分問題の最適解が全体の最適解に 含まれているという関係が再帰的に成り立っているならば、小さな部分問題から逐次的に解いていくことによっ て効率良く全体の最適解を求める動的計画法と呼ばれる手法が利用できる。動的計画法をコンピュータ上で実 装する際に、多くの場合は再帰的関数とメモ化を用いて直感的なプログラムとして容易に実装できる。 ただし、動的計画法の中でも、ダイクストラ法のように、一度求めた変数の値を逐次的に改良していくよう な手法は一般に破壊的代入を用いて記述されており、副作用を取り扱えないメモ化という手段で実装できるか どうか一見すると明らかでない。 しかし、少し考えれば、ある変数の値が改良によって最適値に近づくときに、それらの値の列全体から何ら かの評価関数で選択したものが求め
Spaghetti Source - 各種アルゴリズムの C++ による実装
ACM/ICPC（プログラミングコンテスト）系列の問題を解くことを目標にして，各種アルゴリズムを C++ で実装してみた．極めて意地が悪い類の問題には対応していないし，特定の入力に対して高速に動くということもない．計算量も最良とは限らない． これらを参考にする方への注意とお願い： これらの記述は正確とは限りません．参考文献を参照することを強く推奨します．間違っている場合は是非教えてください． これらのプログラムは間違っているかもしれません．各人で検証することを強く推奨します．バグがあれば是非教えてください． 分類が怪しいので，これはこっちだろう，ということがあればコメントを下さると助かります． 注意！ 現在書き換え中 TODO 分類を正しく行う． 全体的に説明と使い方を詳しく． Verify していないものを Verify． ボロノイ図（いつになることやら……） 基本 テンプレート グラフ
最小費用流 @ C++ - 落書き、時々落学
最小費用流実装した． 最小費用流のアルゴリズムは少なくとも3種類ぐらいある． とりあえず，フローを求めてから，負閉路を頑張って消していく 最小費用0フローからはじめて，augmenting shortest path で増やしていく push, relabelの一般化（よく知らない） 2番目を実装した． 簡単のため，非負費用． 検証は UVa 10594 Data Flow. 適当に組んだら時間オーバーだったので，配列とか使って真面目に書いた． 本体は以下．非負費用というのが大きい．まず，f=0が最小費用0フローになっている． よって，ポテンシャルの決定にベルマンフォードを実行しなくて良い． ただ，単純にダイクストラでガンガン流していけば良い． pair<bool, ll> successive_shortest_path() { typedef pair<ll, int> TV; FOR
実数探索三種類解説 - nodchipの日記
自分がよく使う実数上の探索アルゴリズム「三分探索」「黄金分割探索」「二分探索」のメモです。 三分探索 三分探索は凸関数の極値を求めるために使うアルゴリズムです。このアルゴリズムは関数が微分不可能な場合にも使えます。やり方は探索領域を三分割し、真ん中二本の境界のうちどちらの値が大きいかを調べ、それとは逆の方の境界を新たな探索領域の端にするというものです。一回のイテレーションで関数の計算を2回行い、探索領域が2/3になります。 double search(double left, double right) { for (int loop = 0; loop < maxLoop; ++loop){ if (f((left * 2 + right) / 3) > f((left + right * 2) / 3)){ right = (left + right * 2) / 3; } else
How to Write a Spelling Corrector
One week in 2007, two friends (Dean and Bill) independently told me they were amazed at Google's spelling correction. Type in a search like [speling] and Google instantly comes back with Showing results for: spelling. I thought Dean and Bill, being highly accomplished engineers and mathematicians, would have good intuitions about how this process works. But they didn't, and come to think of it, wh
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
eomole blog » 点を円で囲む方法のあれこれ