lionfan2回答ポイント 200pt

コンピュータサイエンスの授業をします。

初心者に、計算量のオーダーについて教えたいのですが、

[1] ソート以外の、
[2] 面白く
[3] 理解が簡単な問題で、
[4] 複数の解くアルゴリズム(4つ以上)があり、
[5] [4]の計算量のオーダーがそれぞれ違う(以下の内、4つ以上を含むのが望ましい)
　　https://ja.wikipedia.org/wiki/%E3%83%A9%E3%83%B3%E3%83%80%E3%82%A6%E3%81%AE%E8%A8%98%E5%8F%B7#.E4.B8.80.E8.88.AC.E7.9A.84.E3.81.AA.E3.82.AA.E3.83.BC.E3.83.80.E3.83.BC

ような問題をご存じでしたら教えて下さい。
難しい注文かとは思いますが、よろしくお願いいたします。

※ 有料アンケート・ポイント付き質問機能は2023年2月28日に終了しました。

ログインして回答する

ベストアンサー

a-kuma32015/07/22 00:36:15
満足50pt
難しい。うん、難しいですねえ、本当に。

「並べ替え」と同列でよく題材に出されるのは「探索」だと思います。
- http://gihyo.jp/dev/serial/01/java-calculation/0074
- http://gihyo.jp/dev/serial/01/java-calculation/0075
ただ、並べ替えと違ってすっきりのは、事前に並べ替えておいたり、ハッシュ値を求めておくのは計算量の中には入れないのかい、という初学者にとってやや反則めいた部分があるところ。
あまり面白いとは言えず（[2]に違反）、4つ以上のアルゴリズムではない（[4]に違反）ので、題意にもそぐわず。

計算量のオーダーって、考え方としては大切だけどちょっと古いかなあ、と思います。
「古い」というのは、それを気にしなくちゃいけない場面が少なくなってしまったから、という意味です。

昔は、限られた領域の中で、比較演算（引き算）のコストが馬鹿にならなかったから、それを減らすことが限りある CPU リソースを有効に使う、という意味ではとても大切だった。
今は、CPU リソースがふんだんにあるので、比較演算よりも、それの準備にかかるコストの方が馬鹿にならない時代になったなあ、と。

極端なケースで言うと、あるデータを整列するときに、それを比較するための基準値は DB をアクセスすると手に入る状況。
比較用の関数を渡せるようなライブラリを備えているものが多いので、その比較用の関数の中で DB をアクセスに行っちゃう。
先に DB をアクセスしておいて、比較用の値はあらかじめ取得しておこうね、と。
＃ん？　DB のアクセスにコストがかかるから、計算量のオーダが大切という話にもなる？

複数のアルゴリズムがあって、題材が面白い、という意味では、オセロやチェスの最適手を求める、というのが良いかな、とは思うのですが、面白いというところに達するまでの時間がかかり過ぎるのが難点。
MIN-MAX 法の話があって、取りうる手が木構造で表現できて、αβ刈りまでいって、ようやく計算量の話になる。
でも、どこで計算を打ち切るか、って部分が大きいので、ランダウの記法で表される計算量の理解には、すんなりとはいかないかな...

「ソート以外の」という [1]に違反しているんですが、並べ替えの過程を図示するの、って、初めて見たときに面白いと思ったんですけれど、どうでしょう。
http://www.ics.kagoshima-u.ac.jp/~fuchida/edu/algorithm/sort-algorithm/index.html

100個の配列に、1～100までの数字が入っていて、十分にシャッフルされている。
横軸に、配列のインデックス。縦軸に、その値をとってプロットすると、並べ替える前は、プロットの点が一様に散らばっているように見えます。
そのグラフを、並べ替えの過程の途中で表示させると、何ステップで、どのように並べ替えられていくのかが目で見てわかります。
端から順番に並べ替えていくと、きれいに並んでいく様子が分かるけど、完了するまでに時間（ステップ数）がかかる。
よく分からないけど、全体的にざっくりと並べ替えていく方法だと、最初は並び替えられているのかどうか、よく分からないけど、ステップが進むにつれて、ざくざくときれいに整列していく。

計算量のオーダや、各アルゴリズムの計算過程、加えて、自分がひねり出すようなロジックは得てして効率は良くない、というところが直観的に理解できるのではないかな、と、思います。
スター
- 2件のコメントを見る
- lionfan2 2015/07/22 21:34:39
  
  a-kuma3様、計算量のオーダーが昔ほど、重要ではなくなったとの指摘、ありがとうございます。
  自分も普段、プログラミングする際、あまりオーダーについて考えてないなあと思っていました。
  教えていただいたURLも、たいへん参考になりました。
  
  スター
- a-kuma3 2015/07/22 22:17:42
  
  計算量のオーダーという考え方があって、それを減らすアルゴリズムって大事だよね、ってところは知ってて欲しいところだと思います。
  ただ、大半の人は、良く練られたアルゴリズムを使う側になっちゃうんですよね。
  下手に自分で作り込むよりは、きちんと調べて、先駆者の資産を使うことが大切。
  
  それを踏まえたうえで、並べ替えって、題材としては結果が分かりやすいし、一番面白いと思うんですよね。
  
  計算量としては、良く知られたところだとクイックソートかマージソートが効率良いよね、というところなのですが、条件が加わると、また違ってきます。
  
  ほぼ整列されているのだけれど、ほんのいくつかだけ並んでないのが紛れ込んでいる場合には、挿入ソートは割りと効率が良いとか。
  ハードディスクのようにデータのアクセスにコストがかかるものを直接交換しなければいけない（整列のキーはメモリにキャッシュできるけど、並び替えたいデータは大きくてメモリに乗せられない、とか）場合には、比較が演算コストにつながるのではなく、データの入れ替えが演算コストに効くのだとか。
  
  こういったことを「面白ぇなあ」と思える人が、次のステップに進んで、とんがったことにのめり込んでくれるんじゃないかな、と思います。
  
  スター

その他の回答

多食斎友好＝世田介2015/07/21 23:46:42
満足30pt

１ピタゴラス数を重複さずに順番に見つける。
２素数を重複さずに順番に見つける。
３ＸＹ平面上の点を3点ずつ（線が交差する事なく）結ぶ。---できる図は1通りではありませんが、1つだけできたら終わりにする。---計算量は大体点数の４乗になります比例します。

スター
- 1件のコメントを見る
- lionfan2 2015/07/22 21:32:35
  
  tazikisai-mukou様、ありがとうございます。参考にいたします!!
  
  スター

LLマン2015/07/22 05:08:07
満足30pt

ソート以外だと、エイトクイーンが定番ですね。
条件の[4]までは満たしていると思います。

8クイーンのどのあたりが教材として優れているかといえば、
チェスの盤面がイメージしやすいため、
何をしようとしているか想像しやすいところにあります。

逆に高度なアルゴリズムでは、初見の生徒が
何をしているかパッと想像できないと思います。

また、一桁クイーンなら短時間で計算できるとか、
単純な解法ならコードが難解にはならないとか、
ゲームへの応用を想像できる（から面白い）、
などというのもメリットです。

それから、ご質問の意図とは異なってしまいますが、
ソートが実際にどのように使われているのか、
説明する方向でも面白くできるかもしれません。
（プログラミング自体に興味がなくても面白いと思えるかも）

たとえば、ブログのエントリが
日付順に並んでいるのもソート（の結果）ですし、
RPGの道具屋でアイテムが
価格順に並んでいるのもソートでしょう。

生徒側の心理を見たときに、
それが実用的にどのように使われているか分からないと、
自分の役に立つと思えず、興味も湧かないのだと思います。

スター

1件のコメントを見る
lionfan2 2015/07/22 21:36:43

dev2様、ありがとうございます。8クイーン問題、了解です。
ソートについては、学生は教育学部が多く、あまりというかほとんど、プログラミングに興味がないのだろうと思います。なので、実用面を話すのはいいですね。

スター

みやど2015/07/22 14:02:24
満足25pt

普通の数学との関係からすると、変数の多い連立一次方程式の解法はどうでしょうか。

詳しいことは私も分かりませんが、いわゆるクラメルの公式は計算量が多くて使い物になりません。

スター

1件のコメントを見る
lionfan2 2015/07/22 21:37:12

みやど様、いつもありがとうございます。了解です。これはわかりやすくていいですね。

スター

たけじん2015/07/22 15:13:38
満足15pt

巡回セールスマン問題、と思ったが、最適解を求めるのが大変だから、出てきた解を評価できないなぁ。

スター

2件のコメントを見る
たけじん 2015/07/22 15:14:48

あ、コメントのつもりが回答に・・・

スター
lionfan2 2015/07/22 21:37:54

takejin様、巡回セールス問題は、わかりやすいのに難しい問題で、アルゴリズムの重要性の説明には面白いと思います。ありがとうございます。

スター

早く帰りたい2015/07/23 22:40:00
満足50pt

最近だとこんな記事がありましたね。

Atomの重要なプリミティブの最適化 | コンピュータサイエンス | POSTD
http://postd.cc/optimizing-an-important-atom-primitive/

Atomというエディタで、テキスト内部の範囲を表現する「マーカ」という構造体の扱いによって処理速度が大きく変わってくるという内容です。

単にテキスト内部の位置を保持するだけのマーカの処理でも、数が多くなると計算量が問題になってくるわけです。
最近流行りのいわゆるビッグデータやディープラーニングなども大概データ量が多いので、常に計算量を意識しないと、まずまともに動きません。
なので計算量のオーダーの話が古い、なんてことはありませんよ。

さて上記のマーカの問題に戻りますが、「効率的な探索方法」のところで、探索木の中で22番目の位置を含む領域にアクセスするのがO(log(n))とされています。同じように22番めの要素にアクセスする場合でも、配列に格納して22番目に直接アクセスできればO(1)、配列ではなく隣接リストでデータを持っていて最初から一つずつたどる必要があればO(n)になります。
他にも例えば「全てのマーカの対を考え、そのマーカに重複する部分があれば出力しろ」といった問題をナイーブに処理するとO(n^2)になるでしょう。

上記の話は「一つの問題」ではないので、お望みの回答ではないかもしれません。
ただ個人的には、何に使うのかわからない呪術的なアルゴリズムを幾つか読み解くよりも、普段自分が書いている簡単なプログラムの計算量を確認したり、データを1億倍にした場合の悪夢を体験させたりした方が良い学びになるかと思います。

計算量を「特殊なアルゴリズムを利用する際に優劣を決めるためのもの」と考えるとつまらないですが、「プログラムが遅くて困ったときに見直すと、100倍以上の改善の可能性があるもの」と考えると面白いですよ。

スター

1件のコメントを見る
lionfan2 2015/07/23 23:18:26

ite様、興味深い記事のご紹介、ありがとうございます。了解です。

スター

その他の回答を読む

この質問へのコメント

lang_and_engine2015/07/22 10:53:02

▶ アルゴリズムの凄さを伝えるアニメかと思ったらマジキチアニメだった件 - YouTube
https://www.youtube.com/watch?v=_-KfZCZ4F0Q

この動画を，ぜひ生徒たちに見せてあげてください。

（４つ以上という条件を満たしてはいませんが・・・）
lang_and_engine2015/07/22 11:00:53

↑
北大で，組み合わせ探索のアルゴリズムの計算量の爆発的な増大について
知らせるために作成された動画です。
インパクトが大きく良い教材になると思います。
lionfan22015/07/22 19:15:43

lang_and_engine様、ありがとうございます。もちろん、これは知っておりました!!　見せるつもりです。
その他の「つかみ」つしては、今のところ「見合い問題」はどうかなあ、と思っています。
ただ後者は、オーダーについての話ではないので、もう少し、募集したいです。

コンピュータサイエンスの授業をします。

ベストアンサー

a-kuma32015/07/22 00:36:15
満足50pt

lionfan2 2015/07/22 21:34:39

a-kuma3 2015/07/22 22:17:42

その他の回答