データ構造,アルゴリズム,デザインパターン総合スレ 3©2ch.net
レス数が950を超えています。1000を超えると書き込みができなくなります。
このスレッドは天才チンパンジー「アイちゃん」が
言語訓練のために立てたものです。
アイと研究員とのやり取りに利用するスレッドなので、
関係者以外は書きこまないで下さい。
京都大学霊長類研究所
データ構造,アルゴリズム,デザインパターン総合スレ 2
http://echo.2ch.net/test/read.cgi/tech/1362301811/
【関連スレ】
3Dアルゴリズム全般
http://toro.2ch.net/test/read.cgi/tech/1164171086/
<集大成>アルゴリズム大辞典
http://toro.2ch.net/test/read.cgi/tech/1086272325/
アルゴリズム総合スレ in ム板
http://toro.2ch.net/test/read.cgi/tech/1217773415/
アルゴリズムとデータ構造 - Kaneko Lab.
ttp://www.kkaneko.com/adp/algo/index.html
アルゴリズムとデータ構造 - ソースコード探険隊
ttp://www.codereading.com/algo_and_ds/
各種アルゴリズムの C++ による実装 - Spaghetti Source
ttp://www.prefield.com/algorithm/
アルゴリズムとデータ構造 - プログラミングスレまとめ in VIP
ttp://vipprog.net/wiki/algo_and_data_const.html 最も重要ななのはアルゴリズムとデータ構造
次にI/O
つぎに無名関数やハンドラ、イベント駆動
つぎに並列、非同期処理
その次は画像処理とか3Dとか
ディジタル信号処理またいな各ドメインの専門
技術。
オブジェクトやクラスなんてこれらを達成する
上での手段でしかない。
それ以上のオブジェクト指向の設計思想は
もはや宗教。
唯一絶対に正しいわけでもないし
概念を余計に複雑にするだけ。
SQLやHTML XMLやJavaScript シェルスクリプト
URLなんかが絡んでくるとグダグダに崩壊
するものばかり。
そして現代のアプリケーションはこれら無しで
作るのは無理だからオブジェクト指向の高度な
技法はほどんど不要。 NoSQL db って、Redis以外はわりと滅びた感じ。
RDBでもスキーマレスなデータ扱えるようになったし、
トランザクションあった方が便利なことやっぱり多いし、
SQLってなんだかんだ言って表現力高いし。 pythonスレにも書いたのですが、pandasのMultiIndexにしたデータのままで、データを追加したり、値を更新したり、csvに入出力する方法をご存知の方はいませんか? AOJ の「DPL_1_I: Knapsack Problem with Limitations II」が分からん。
個数制限付きナップサック問題の
・ある品物の重さと個数制限
・ナップサック容量
が極めて大きいバージョン。
例えば解法
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2856557#1
を見ると、品物の価値の総和が i であるときの最大容量を記録した動的計画法テーブルを作った後に貪欲法で答えを出してるんだが
・なぜこの方法で上手くいくのか
・前半の動的計画法で、品物の個数を min(m[i], MAX_V) としている (できる) 理由が分からない。
誰か知恵を貸してください。
僕としてはこの解法が理解できれば満足です。 >>897
どういう意味?
「このアルゴリズムを理解するのに必要な数学の分野」というものがあるならそれを参照するが、そんなものはない (挙げられないでしょ?)
俺個人の専門は物理で、「数学の勉強」というものも一応してきたが、このごく具体的な問の一解法を理解することと「数学の勉強」は関係がない
単純に論理的思考力を上げよ、と言っているなら会話になっていないのでこれ以上は結構 論理的思考力を上げるために将棋をしなさい。数学など不要です。 >>898
数学科の数学と物理科の数学とコンピュータの数学は違う(笑) >>901
最適性の証明のことを言ってるの?
いずれにせよこの問題に限った話じゃないよね?
別に動的計画法が上手くいく理由が分からないと言っているのではなく、>>896の解法が分からないのだが。
>>902
違わない
算術、代数、幾何、解析だ全て 例えば、バブルソートには
数学の、えっと、幾何?の知識が必要だろ?
え? >>906
分からんと思っているだけでは進まない。
なにを目的にして、どのようなフローチャートを描いて、
その結果なにが理解できていて、なにがまだ理解できていないのか、
可能な限り事細かに洗い出して、自分の理解の最前線を特定してみるといい。
と言うことを、私は数学で学んだ。 >>909
だからそれは>>896の時点で書いてるんだが
関係ないことしか言えないならレス不要です
>>907
何を? 俺の周りで物理やってる人はとんでもなく数学ができる人ばかりなのに まあゲームじゃない限り物理なんて使わないよね
本格的な物理系シミュレーションとかだと
専門家が担当するだろうし この程度の問題で数学数学言ってるアホ多過ぎて呆れる
多分>>910みたいな感じで高校の算数基準で話してるんだろうな そんなに言うのなら、具体的に数学のどの分野なのか
それが具体的に何と同じなのか言えって。
どうせ論理的思考力がーみたいな精神論しか言えないんだろ 数列、非線形解析学
はい言いました
論理的思考力が無いのはあなたですね >>916
では、数列、非線形解析学を利用した
アルゴリズムを答えてください >>920
数学の問題をコンピュータで解決するってのはわかる、
だが数学・物理特有の問題以外をコンピュータで解決するのに
数学はいらねーだろって話 >>921
微分積分も理解せずにコンピュータに信号処理をやらせるの?
そういうレベルの質問 信号処理なんて、誰がやっても同じなんだから
一度ライブラリ作って、他の人はそれ使うだけだろ・・・ >>923
それじゃあ初音ミクは生まれないね
こういうやつが技術を停滞させる >>924
だからそういうのは専門家に任せたほうが良くね?
音声合成をやる人は、そういう専門家に任せて
他の人は便利なインターフェースを作るとかさ、
なんでも1人でやるもんじゃないよ? 別にそういう原理を知りたくないんなら勉強しなくて良いんじゃない
表面的なものしか作りたくないなら勉強しないことをおすすめします >>926
だから作る層が違うって言ってんの
水道局で働いてる人全員が
工事技師じゃないんだよ >>927
つまり君はそういう層にはなるのを拒む側ってだけだ >>928
その理屈で言えば、君がそういう層になりたいだけでは?
残念だけど、自分がやりたいことと、他人がやってもらいたいこと
っていうのは同じじゃないんだよね
そして給料っていうのは、他人がやって欲しいことをやった対価として
もらえるものなので、いくら自分がすごいことができるって言ったからって
給料は高くならないんだよね。 >>929
作りたいものがあるから勉強する、それだけ 自分一人で作るような小さいアプリとかなら、
全部を知っておかなければいけない、って思いたくなるのもわかる。
が、通常は数学の専門家でも無い人間を数学で信用する事は無いし、
プログラムの専門家でも無い人間をプログラムで信用する事は無い。
付け焼き刃は事故の元。
大きな仕事になればなるほど役割や責任が細分化される。 ぼやっとして結局何を言いたいのか良くわからんが
何か良い事を言いってみたい必死さは伝わった 言ってることがわからんから、言ってるほうが馬鹿だと思ってるだけじゃないの?
俺に言わせれば、馬鹿だから言ってることがわからないんだと思うが? 俺に言わせれば世界はお前を中心に回ってないってこと >>937
お前を中心に回ってるといいたいのかな? アルゴリズム辞典みたいなものを手元に置いときたいんだが、最も支持されてるのってどれ?
・網羅性が高い
・支持されている(売れている)
・日本語版がある
・コード例はあってもなくても良くて、あるとしたら C/C++ か擬似コードで
という条件で
テーマ別に「どれとどれとどれを持っとけばまず問題ない」という言い方でもありがたい
とにかく網羅性を重視してる 英語は知らんけど、日本語なら
[改訂新版]C言語による標準アルゴリズム事典 (Software Technology)
奥村 晴彦
http://amzn.asia/d/bAqY5Be
が網羅性は随一じゃないかな。
改訂だけど初版が1991年で、収録アルゴリズムは増えてないらしいので、
機械学習とかここ25年の新分野は当然入っていない。 機械学習の何をアルゴリズム辞典に入れるべきだというのか
Amazonレビューかよテメェは >>942
この本はBoyer-Moore法が簡易版しか載っていないし、Aho-Corasick法も載ってないから弱い より網羅的な対案示してからでないと批判にならないよ。
共立のアルゴリズム辞典が現存すればこっちも挙げてたかもしれん。
BM法に関してはコード例は簡略版のみだが。
個別のアルゴリズムについてどこまで踏み込むかは、
辞典の物理的な性質上取捨があるのはしかたないでしょ。 名前がついていて解放も明らかになってるアルゴリズムに興味はない
そんなのいくらやっても新しいものは生み出されない 質問させてください。
マイコンからAD変換で入力したサイン波を配列に格納し、周波数を求めたいと思います。
ゼロクロスの位置を求めれば正確に周波数を求められそうですが、教えてください。
https://i.imgur.com/FC5XP0K.png 質問が不完全だけど、そのためのアルゴリズムを教えてほしいということでよい?
前提として、各周期で確実に2回だけゼロクロスすると保証できるのなら、
前回の値を覚えておいて、今回との積が0以下になったらゼロクロス。
この保証がないのなら十分長く波形をとってFFTしてピークを探す。 有向グラフの有向閉路を求める問題です。
深さ優先探索を実行したときに、 Backward Edge が存在する。
⇔
有向閉路をもつ
⇒は自明ですが、逆はどう証明するのでしょうか? 深さ優先、幅優先探索を理解するのにオススメの本ってありますか?(コードサンプル付きでできればC) >>956
グラフ・ネットワークアルゴリズムの基礎: 数理とCプログラム
浅野 孝夫
固定リンク: http://amzn.asia/d/2MetXvf 学ぶ目的には全くお勧めできないってのはその通りだけど、
手元に置いておいて使う分には便利な本ではあるような。
あ、浅野先生の本も待ってます。
(この分野、浅野先生が2人いて紛らわしい) >>956
プログラミングコンテスト攻略のためのアルゴリズムとデータ構造
渡部 有隆
固定リンク: http://amzn.asia/d/g8qmfS6
↑この本にも、 BFS、DFS共に書いてあります。
解説は非常に雑ですが。 >>959
の本には、再帰を使う DFS プログラムが書いてあります。(スタックを使う DFS プログラムは演習問題にあり、コードをダウンロードできます。) >>963
スタックを使う DFS プログラムは演習問題にあり、コードをダウンロードできますし、本にも解答のところにコードが載っています。) 前置記法(ポーランド記法) + 1 2
後置記法(逆ポーランド記法) 1 2 +
中置記法 1 + 2
確か、構文木をたどる時に、どれかが幅優先で、どれかが深さ優先探索になると、記憶している テンプレのソース探検なんちゃらのサイトいいね
pdf買えはうざいけど
ソートはクイックマージヒープの特性くらい押さえとけば良さそうな感じだな
そこら中に実装あるしまあ
バケットソートは聞いたこと無かったけど、これは局所で凄い威力発揮しそうだ
覚えとく価値ありそう こんにちは、初質問させていただきます、グラフアルゴリズム初心者です
・無向グラフGが入力として与えられる(ファイルからでも、コード内での手打ちでも、どちらも良い)
・Gがサイクルを持てばGの中の最小サイクル(長さが最も短いサイクル)とそのコストを出力する
・各辺、頂点の重みは考えなくても良い(つまり辺のコストは1とする)
といったアルゴリズムを実装したいです。
できればC言語もしくはC系統の言語でコーディングしたいです。
考え方と共に、コーディング例をご教授いただけると幸いです。
浅い知識ではありますが、この実装に必要そうである
・DFS,BFS
・ダイクストラ、ベルマンフォード
に関しては、基礎レベルは把握しています。
お手数おかけしますが、ご助力いただけると幸いです。 適当に言うけど、
すべての辺を1回だけ通りながら、通った頂点を記録していく
それで同じ頂点を、2回以上通ったら、閉路がある? >>971
グラフのサイズが書いてないと答えられないな >>973
条件不足で申し訳ございません
グラフサイズの制約は特に設けないものとしています。
とりあえずは最大でも100頂点程度で考えています。
お手数お掛け致しますが、よろしくお願いします。 >>973
条件不足で申し訳ございません
グラフサイズの制約は特に設けないものとしています。
とりあえずは最大でも100頂点程度で考えています。
お手数お掛け致しますが、よろしくお願いします。 >>975
頂点数をn,辺数をmとする
ある頂点uを含んだ最小閉路は頂点uからbfsをすればO(n+m)で求められる(最初にuに戻ってきたときの経路が最小)
あとはすべての頂点に対してこれをして,その中から一番短いものを選べばいいので,全体でO(n(n+m))で求められる >>976
ありがとうございます。
つまり、例えば
各頂点を始点-終点とするダイクストラアルゴリズム処理を行えば良い
ということでしょうか。 >>977
イメージとしてはそんな感じです
辺を考えたほうがわかりやすいかもしれないです
ある辺(u-v)を含むようなサイクルの中で最小のものを求めたいとします
まずグラフから辺(u-v)を除去します.このグラフ上でuからvの最短距離dを求めます
すると,d + 辺(u-v)が辺(u-v)を含むサイクルの中で最小のものとなります
グラフの中で一番短いサイクルは辺(u-v)を含んでいるかはわからないので,すべての辺に対して上の操作を実行します
その中から一番短いものを選べば,それがグラフの中で一番短いサイクルです
この場合だとO(m(n+m))です >>978
ありがとうございます。
ご教授いただいた考えをもとに、ダイクストラ法を用いて実装してみました。
・ダイクストラ(グラフは頂点とコストで表現)
https://ideone.com/bXF0iQ
また、以前似たものを実装したのですが、これはダイクストラ(もしくはBFS)の考えに則れていますでしょうか・・・?
(グラフは隣接行列で表現)
https://ideone.com/snxvav
どちらにしても、始点と終点が同一でない場合はうまくいくのですが、
始点と終点を同一として閉路で求めようとすると、うまくいきません。
自己ループ辺のコストが0であるから、と思い9999などにしてみましたが、うまくいきませんでした。
すごく単純なミスなのでしょうが、詰まってしまっている状態です。
修正等いただけると幸いです。
一応、(可能であれば)望む仕様と結果としては
・グラフは隣接行列で表現
・辺の重みは非負である(今回、簡易化のために辺の重みは1~9)
・グラフサイズは制限しない(今回、簡易化のために10頂点程度)
・ダイクストラを用いて自分自身を始点かつ終点とする最短経路を求める
・各頂点に対して上のダイクストラを行い、中でも最短の閉路の経路とそのコストを表示する
です。
お手数をおかけしますが、よろしくお願いします。 レス数が950を超えています。1000を超えると書き込みができなくなります。