優秀なアルゴリズムの本

>>264
http://www.ececs.uc.edu/~franco/C321/html/RedBlack/redblack.html

>>264
2-3-4木という平衡木について調べよ。この木はN個の節点を持つ場合
最悪でもlog(N+1)回よりも少ない探索及び挿入で済む。赤黒木とは、
この2-3-4木を通常の2分木に1ビットの情報を付加するだけで実現して
いる。

似たような平衡木にAVL木がある。

>>264
2-3-4木と赤黒木
http://www.u-aizu.ac.jp/~qf-zhao/TEACHING/Data-Alg/lec11.pdf

×log(N+1)
○logN + 1

レスくれた方々、ありがとうございます。
さっそく本屋に行っていろいろな本を見たのですが
レッドブラックツリーというのは、二分探索木を知っているだけでは
理解できず、他のツリー構造を勉強する必要があることがわかりました。

今、私の使っているアルゴリズムの本でも
レッドブラックツリーの次の章に 2-3-4 ツリーや B ツリーの解説が
あるようなので、それらを勉強してから再チャレンジしてみようと
思います。

>>270
平衡木がどちらかの枝が重くならないのは、回転操作(１重回転、２重回転)が
あるからだよ。その操作を必要とするのに使用する判断は枝の構造自体にあ
るからよくできている。ただの２分木には回転操作はない。

今現在の話ですが、

Cの絵本（アンク株式会社／翔泳社）
↓
アルゴリズムの絵本（アンク株式会社／翔泳社）
↓
プログラミングの宝箱　アルゴリズムとデータ構造（紀平拓男・春日伸弥／SoftbBank）

・・・といった感じで読み進めています。
解かりやすいとは思いました。

翔泳社の絵本のシリーズは
文字通り挿絵が入っているだけで、
本質的に分かりやすい解説がされて
いるわけではないのが実に残念

絵があるだけで安心してしまうという
初心者の心理をうまくついているけど、
ちょっと商売上手すぎるんじゃないかな？

>>273
む？あっちのが解かりにくかったのか・・・。
おれはむしろわかり易いと感じた。
あと争点はもう一つ。
情報量は少ないが、これも良いか悪いかの話もあるね。

>>274どの、>>272と>>273は同一人物ではございませぬ

>>168
それって、Cアルゴリズム全科のことじゃない？
http://product.esbooks.co.jp/product/keyword/keyword?accd=19558250

age

構文解析というか、スクリプト言語の設計というか、
とにかくそういうことがやりたい。
Ｃライクなスクリプト言語が作ってみたい。
ＣかＣ＋＋で作りたい。
イチから詳しく勉強できる参考書はありませんか？

>>278
言語処理系の本を読め。

グラフアルゴリズムの良書はないでしょうか。私はSedgewick
のAlgorithm in Cと、Ryba&KruseのC++データ構造とプログラム
設計の本を読んでいますが、今一つグラフのアルゴリズムに
詳しくありません。

Sedgewickの本はかなり詳しく書かれてはいるものの、本の
所々に鏤められたプログラム片を集めてコードにするのはかな
り難しく、ページ数節約のためか端折った内容の所もあり、
あまり実用的ではなくて困っています。

プログラミングの本ではなくグラフ理論の本を読みましょう。

>>280
アルゴリズムイントロダクションの２巻がいいよ
擬似コードのってるから、それ参考にしてコーディングしたらいいと思う

>>281
グラフ理論の本は何冊か持っています。しかし大抵の本は
最小全域木で話が終わっていて、maxflow-mincut問題に
触れたものは１冊しかなくて。

>>282
ありがとうございます。早速購入して読んでみます。

>>283
学生ですか？
ぼくと境遇似てるかも、、、

>>284
実はそうです(^^;
アルゴリズムの本は山ほど出ているのに、グラフ理論のアルゴ
リズムを完璧に網羅した奴ってあまり見かけませんね。

boost::graphでも最終的に使おうかと思ってました。

LEDAとかいいらしいけどね、まあ商用だけどね
卒論のプログラム書いてるんでしょ？
似てるものどうし仲良くしようね（　´∀｀）

>>286
ああLEDAですね。かなりboost::graphとかぶる点があるので
どっちか選択したいですね。僕はboost::graph使って、疑似
コードだけWordで書こうと思っていますが甘いですかね。

できればC++の次期標準にgraphクラスを入れるならばLEDA
ですね。boostは思い切りコンパイラを選ぶのでちと苦しい・・・

授業で最小全域木までしかやらなかったのに卒論にmaxflow-
mincutを選んだのが間違いだった＿|￣|○

で、調子はどうよ？>>287

>>maxflow- mincut
計算幾何学と地理情報処理第2版(共立出版)に１０ページ弱記述があります

>>288
ひーこんな時間まで起きてやってます。
どうにか形になってきました。Edmonds-Karpのアルゴリズム
で流量が整数の場合はうまく行きそうです。

問題は流量が実数の場合です。これも何とかなりそう。という
か何とかしなきゃならん。

>>289
やはりGeometryになるのか・・・そちらの関係にmaxflow-mincut
の論文多いですよね。

クヌースの芸術本が新訳ででる(でた？)そうだが、どんな感じになってるのだろうか？

>>291
サイエンス社から出てた本の改訳かぁ。

原著の方はVolume4を執筆中。3分冊で2007年の予定。
Volume5は2010年。その後Volume1〜3を改訂し、
6, 7はさらにその後だそうで。

長生きしないとな。お互いにな。

クヌース本の新訳の話はスラドにも出てましたね。
ttp://slashdot.jp/developers/04/02/08/162240.shtml?topic=102

グラフ理論の本って結構でてるでしょう。
もしかして日本語に限った話をしているの?
Tarjanの本も昔日本語訳されたよね。

これね。

R.E.Tarjan 『データ構造とネットワークアルゴリズム』(岩野和生訳)マグロウヒル(1989)、
Data Structures and Network Algorithms(1983)

22で出ている情報の構造も、グラフ理論系だね。

文法終わって、「図解入門 ｱﾙｺﾞﾘｽﾞﾑの基本としくみ」 と 「ｱﾙｺﾞﾘｽﾞﾑの絵本」 を併用してまつ。

ｱﾙｺﾞﾘｽﾞﾑをやると文法の理解も進むなぁー

「珠玉のプログラミング」は C/C++ の知識が余り無くても読めますか？
当方、Java の基本的なことなら理解しています。

>298 読める
というか言語に依存してない気がする

>>299
サンクス。
http://www.asahi-net.or.jp/~yf8k-kbys/pearls.html
この（翻訳者の）ページに
> 基本的にはＣ／Ｃ＋＋を使っていて、巻末までサンプルコードがぎっしりあるカンジです。
と書いてあったので。

セジウィックの本の新版が出ると、じゅんくどーに張ってあった
気がするんだがどうなったんだ？

Javaの初学者向けの本を一通り終えたので
アルゴリズムに着手したいのですが、お薦めの本はありますか？

>>302
Javaの基礎が身についたのならアルゴリズムはC/C++本でいいじゃん。
両方使えてちょっとお得な気分。

>>302
Javaによるデータ構造とアルゴリズム解析入門
http://www.amazon.co.jp/exec/obidos/ASIN/4894711958
この本はかなりいかしてる。名著だ。

Javaで学ぶアルゴリズムとデータ構造
http://www.amazon.co.jp/exec/obidos/ASIN/4797306947
も評判いいね。

>>295
このスレを見てから探していたのですが、6月25日に発売されるのですね。すご
く楽しみです。

新紀元情報工学シリーズ データ構造とネットワークアルゴリズム
R.ターハン著 岩野和生訳 B5変判 200頁予定 予価3,500円(税別)

http://www.shinkigensha.co.jp/kinkan/

へー、新紀元社ってのはなかなかいい本の版権持っていくねえ。
これは名著だからねえ。

>>305
うゎ、滅茶欲しい。

新紀元社、なんかなつかしい名前だ。
てっきりファンタジー屋さんだとおもってたが...

ファンタジーもやってるよ
6月刊行のクトゥルフ神話ガイドがちょっと興味ある

新紀元社めちゃくちゃ頑張ってるな。

>>304
下の奴買ったけどjdk1.2じゃないと動かないのかな？
1.4だと普通のアプレットになっちゃう
翻訳されてないけど原書の改訂版見てみたい
http://www.amazon.co.jp/exec/obidos/ASIN/0672324539/qid=1085148665/sr=1-3/ref=sr_1_8_3/250-6815944-1881064

>>311
> 1.4だと普通のアプレットになっちゃう

ってなんだろう

>>305
出版遅れるっぽいね。

その下の Human Interface Guidelines の復刻版も欲しいかも。

>>313
ああ、残念です。

8月中旬に渡米してしまうので、それまでに手に入るとよいのですが...

>>301
新宿紀伊国屋書店で見つけたので購入してきました。

近代科学社 アルゴリズムC・新版 基礎・データ構造・整列・検索
R. セジウィック著 野下浩平・星守・佐藤創・田口東訳
B5判 632頁 定価7,140円(本体6,800円)

http://www.kindaikagaku.co.jp/bookdata/ISBN4-7649-0309-1.htm

同じく近代科学社の、大好きな「コンピュータ・ジオメトリ」(仕事がそちら系
ですので...)とほぼ同じ作りのようです。木構造やソートなどを可視化した図
が麗澤に掲載されているので、読み進めるのが楽しそう。

近代科学社のアンカーを追っていたら、この会社のアルゴリズムに関する本が
まとめられているページを発見しました。

計算機科学: アルゴリズム:
http://www2.books.or.jp/asp/cat/list.asp?sc=1392&tc=20C070&cat1=%8cv%8eZ%8b%40%89%c8%8aw&cat2=%83A%83%8b%83S%83%8a%83Y%83%80&home=http%3A%2F%2Fwww%2Ekindaikagaku%2Eco%2Ejp%2F