読むべきアルゴリズムの本
勉強しなければならないのである。 長くなるので、ここで折り畳んでしまう。 【有料・和訳有】Introduction to Algorithms おそらく一番有名なアルゴリズム本。MITの教科書。 日本語版もあるが、上記は第３版なのに対して、日本語版は第２版までが出ている。 しかも３分冊されていて、３冊目は第１版のものしかないため、私が買い漁った時でも絶版。 アルゴリズムイントロダクション（改定２版） 第１巻 数学的基礎とデータ構造 アルゴリズムイントロダクション（改定２版） 第２巻 アルゴリズムの設計と解析手法 アルゴリズムイントロダクション 第３巻 精選トピックス 【有料・和訳有】Algorithm Design ２番目に有名なアルゴリズム本か。こっちはコーネル大学の教科書。 なんとタイムリーなことに、今年の１０月に第２版が出るらしい。 リンクはその第２版へのもの。 買ってないのだが、1
2009年12月27日:釣り師的アルゴリズム
Wikipediaによると 長いのでめんどくさい方は読まないでください。 歴史 [編集] 記録に残る最古のアルゴリズムは、エウクレイデスの原論に載っているユークリッドの互除法であるといわれている。これは、二つの整数の最大公約数を求めるアルゴリズムである。 「アルゴリズム」という名称は、現在のイラクのバグダードにおける9世紀の数学者アル・フワーリズミー (al-Khwarizmi、الخوارزمي) の名前から来ているといわれている。825年に書かれた彼の著作『インドの数の計算法』が、12世紀にチェスターのロバート（あるいはバスのアデレード）によってラテン語に翻訳され、『Algoritmi de numero Indorumアルゴリトミ・デ・ヌーメロ・インドルム』（直訳すると「インドの数におけるアルゴリトミ」）という題で、以後500年間にわたってヨーロッパ各国の大学で数学の主要な教科書とし
圧縮に関するメモ
データ圧縮について データ圧縮は、対象とするデータに 偏りがあることを利用 して行います。 データに含まれる値の出現頻度に偏りがある (0などの特定の値が多く使われる)とか、 同じ値(パターン)が連続して現れるとか、 近くに似た値が現れやすい、とか、 です。 例えば 00 00 00 00 00 12 12 12 という 8バイトを 5個 の 00 と 3個の 12 と表現すれば 05 00 03 12 と 4バイトにできたりします。 あるいは 00 と 12 の２種しかないようならば８バイトをビット情報として 00000111 のようにまとめ、 00 12 07 と3バイトにできたりします。 また、偏りの少ない/得られにくいデータの場合でも、別の性質や規則性を利用し、いったん 偏りの現れやすいデータに変換する／ 似たような値が続きやすいように並べ替える ことで圧縮しやすくする場合もありま
アルゴリズムとデータ構造 - プログラミングスレまとめ in VIP
計算量 † アルゴリズムがどれだけ効率的かを示す概念が計算量です。通常、単に計算量と述べた場合は、データ数nに対してどれだけ時間がかかるかを示す時間計算量を指しますが、場合によってはどれだけメモリを消費するかを示す空間計算量を問題にするケースもあります。計算量は、通常データ数nが十分大きい場合にnのどういう関数に比例して計算時間／メモリ消費が増えるかという形式で表します。 具体的に、下に述べている線形探索の例で計算量を考えてみましょう。この関数では、ループをサイズn回だけ回していますが、このループ1回辺り時間tだけかかるとしましょう。さらに、関数の呼び出し等により、データ数にかかわらず一定の時間sがかかると考えられます。従ってこの関数に費やす時間はnt+sですね。この時、十分大きいnを考え、かつ定数倍は無視して考えます。例えばntがsの10000倍だと仮定しましょう。この時sの寄与は、体重
「最短経路の本 レナのふしぎな数学の旅」を読みました - 神様なんて信じない僕らのために
きしださんの日記で紹介されていたので、つい買ってみました。 2010-06-18 - きしだのはてな きむら(K)さんに 「今まで読んでなかったんかい」 Twitter / finalfusion: @isoparametric 「今ま�� と突っ込まれるくらい必読本でした。がはっ。 ということで、感想。 要するにグラフ理論の初歩を学ぶための本なのですが、 一般のプログラマ／エンジニアからしたらグラフ理論って、何か意味あるの？ って感じかもしれないです。 でも、 「最短経路を見つける」というアルゴリズムを書くことは結構あるんじゃないでしょうか？ 最短経路を求める方法として、ダイクストラ法なんかが有名ですが、 ゲームなんかだとA*(AStar)アルゴリズムがよく使われます。 でも、これはアルゴリズムだけ知っていれば使えたりするので 実際に最短経路を求めるためにどのようなことをしているか？ と
yebo blog: クヌース教授は間違っていた
2010/06/15 クヌース教授は間違っていた Slashdotによれば、この数十年間、クヌース教授をはじめとするコンピュータ科学者が最適としてきたアルゴリズムを10倍高速にする方法をPoul-Henning Kamp (PHK) というハッカーが見付けたという。その論文タイトルは「You're Doing It Wrong (あなた達のやっている事は間違っている)」で、ACM Queueに掲載されている。別にクヌース教授の考えが間違っているわけではなく、アルゴリズム的には正しいが、実用レベルでは、OSには仮想メモリがあり、VMと干渉しないようにすれば簡単に高性能なシステムが作れる。従来の考え方はモダンな計算機を考慮に入れていないので、現実的には不適合を起こしている。具体的にはヒープにBツリーの要素を取り込んだBヒープというデータ構造を使うことで、バイナリヒープの10倍のパフォーマンスを
トップクラスだけが知る「このアルゴリズムがすごい」――「探索」基礎最速マスター
トップクラスだけが知る「このアルゴリズムがすごい」――「探索」基礎最速マスター：最強最速アルゴリズマー養成講座（1/4 ページ） プログラミングにおける重要な概念である「探索」を最速でマスターするために、今回は少し応用となる探索手法などを紹介しながら、その実践力を育成します。問題をグラフとして表現し、効率よく探索する方法をぜひ日常に生かしてみましょう。 まだまだ活用可能な探索 前回の「知れば天国、知らねば地獄――『探索』虎の巻」で、「探索」という概念の基礎について紹介しました。すでに探索についてよく理解している方には物足りなかったかと思いますが、「問題をグラフとしてうまく表現し、そのグラフを効率よく探索する」というアルゴリズマー的な思考法がまだ身についていなかった方には、得るものもあったのではないでしょうか。 前回は、「幅優先探索」と「深さ優先探索」という、比較的単純なものを紹介しましたが
データ構造とアルゴリズムの記事一覧 - いろいろ解析日記
データ構造 Javaを使うなら必ず覚えておきたいデータ構造 - 配列・リスト・マップ PHPなら覚えるべきデータ構造はひとつだけ？ - 配列 Perlで覚えたいデータ構造 - 配列・ハッシュ VBAで覚えておくデータ構造 - 静的配列・動的配列・ディクショナリ JavaScriptで覚えておくとよいデータ構造 - 配列・オブジェクト Bashで覚えておくとよいデータ構造 - 配列 - 何かしらの言語による記述を解析する日記 アルゴリズム Javaを使うなら理解しておきたいアルゴリズム - 抽出・ソート・結合・集計 (リスト＆マップ編) Javaを使うなら理解しておきたいアルゴリズム - 抽出・ソート・結合・集計 (リスト＆ビーン編) PHPを使うなら理解しておきたいアルゴリズム - 抽出・ソート・結合・集計 VBAを使うなら理解しておきたいアルゴリズム - 抽出・結合・集計 Javascr
マルチコア時代の"データ構造とアルゴリズム"再入門
データ構造とアルゴリズム再入門 はじめに ・並{行|列} & {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
実数探索三種類解説 - 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
3分探索 - ICPC突破専用ザク
凸関数の極値を求める方法を知りたくなってググってみたところid:nodchipさんのエントリがヒットした． 以下，個人的なまとめ． 実数探索三種類解説 - nodchipの日記 http://d.hatena.ne.jp/nodchip/20090303/1236058357 単調関数の零点を求めるのには2分探索が使われるけど，凸関数の極値を求めるのには3分探索が使われるらしい． 三分探索は凸関数の極値を求めるために使うアルゴリズムです。このアルゴリズムは関数が微分不可能な場合にも使えます。やり方は探索領域を三分割し、真ん中二本の境界のうちどちらの値が大きいかを調べ、それとは逆の方の境界を新たな探索領域の端にするというものです。一回のイテレーションで関数の計算を2回行い、探索領域が2/3になります。 3分探索がうまくいく理由は以下のとおり． f : [a,b]→R : 上に凸な関数とし，区
知れば天国、知らねば地獄――「探索」虎の巻
いよいよ今回から、具体的なアルゴリズムの紹介に入っていきます。今回は、プログラミングにおける重要な概念である「探索」について考えます。グラフに変換し、探索する、という流れを知るとともに、そのグラフを効率よく探索する方法について紹介します。 今後紹介していくアルゴリズムについて お待たせしました！ 「最強最速アルゴリズマー養成講座」という連載タイトルのとおり、今回の連載からいよいよ具体的なアルゴリズムの紹介に入っていきたいと思います。 しかし、それを読んでいただく前に、1つ注意してもらいたいことがあります。連載第3回でもお伝えしたように、「問題を、既存の適当なアルゴリズムに当てはめる」という考え方は、非常に危険である、ということです。 筆者の経験上、TopCoderでRedCoder以上を目指すのであれば、回答時間短縮のために、いままでのパターンを利用するのも方法の1つなのですが、本連載では
PythonでA*(A-Star)アルゴリズム - Pashango’s Blog
今回はA*アルゴリズムをPythonでやってみます。 ゲームプログラマの間では、もはや常識となりつつある最短経路問題解決アルゴリズムです。 A*は、古典的手法である「ダイクストラ法」を改良したものです。 スタート地点からノードnを通ってゴールに辿り付くとき、最短距離をf(n)とすると、 f(n) = g(n) + h(n) とすることができます、g(n)は「スタートからノードnまでの最短距離」、h(n)は「ノードnからゴールまでの最短距離」です。 でも、最初から適切なg(n)とh(n)が判ってるなら苦労しませんよね。 だから、テキトーな予測値を使って、最短経路をある程度予測して効率的に経路探索をしてみようという事です。 テキトーな予測値を使った最短経路距離をf*(n)とすると f*(n) = g*(n) + h*(n) となります、f*(n)を求めるためにテキトーなg*(n)とh*(n)を
heap sortを使った上位ランキング取得プログラム - 遥かへのスピードランナー
Managing Gigabytes 4.6章で解説されているソートのプログラムを実装してみた。 検索エンジンなどでN個のデータの中から上位r個を取得したい場合、まずN個のデータからなるmax-heapを構成して、ルート（最大値）から順にr個をヒープから取り除くというアプローチが考えられる。しかしN>>rの場合、r個のデータからなるmin-heapを構成して、残りのN-r個のデータをheapのルート（最小値）と順次比較して、ルートよりも大きい場合はルートと入れ替えて、heapを再構成する、という手順を取った方がより計算量が少なくて済む、という話。 10万件のランダムな数値をスペース区切りで出力するプログラム #include <iostream> #include <stdlib.h> using namespace std; int main (int argc, char *argv[
ソートについて
ソートについて はじめに n個の要素がある配列をソートする方法を挙げていく。 バブルソート バブルソートは最も簡単な方法です。 単純に隣同士を比較して順番が逆なら入れ替えるという操作を 一番目の要素から順番に行っていきます。 この操作をn回行うと、要素の中でもっとも大きな要素が一番n番目に来ます。 そして、また一番目の要素からn-1回操作を行います。 これで二番目に大きな要素がn-1番目に来ます これを繰り返してソートします。 サンプルコード //バブルソート void BubbleSort(int Data[], int n) { int BeginPlace, ComparePlace; //比較を始める位置を最初からn-1まで変えていく for(BeginPlace = 0;BeginPlace Data[ComparePlace])
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
algorithm
サービス終了のお知らせ
プログラミング体験ゲーム：アルゴロジック ｜ JEITA
サービス終了のお知らせ
[Think IT] 【深きプログラミング言語】続・アルゴリズムで頭の体操