2026年07月14日 第6回
ハノイの塔や巡回セールスマン問題のような扱いづらい問題について、 計算時間が数千年からめったに聞かない桁に跳ね上がったりしたため、 計算量が指数関数的に増大することを、 恐ろしさとともに理解できました。
そうですね．確かに恐ろしいです．
並べ替え問題（バブルソート）や計算時間の話題が、 コンピュータ概論のときに学んだ内容に似ていて、 深く理解できた。 循環セールスマン問題など、 最適解がまだみつかっていないという点はとても興味深かった。
まだ見つかっていないということはないです． 講義をちゃんと聞いていたかな？
ハノイの塔のように、 漸化式によって試行回数が求められる場合や、 列挙木の葉の数から試行回数が求められることが理解できました。 また、 経路に関する問題がグラフによって解けるということに、 今まで納得がいかなかったのですが、 今回の講義でグラフにすることで組合せの問題として考えられるということが理解でき、 腑に落ちました。 また、 オーダー表記によって表される計算量により、 効率の良さが測れるということが数学的に理解でき、 面白いなと思いました。 講義のなかでバブルソートの計算量について考えていましたが、 クイックソートなど、 同じソートでも計算量が異なる方法はどのように発見できるのか疑問に思いました。 これについて、 実際にプログラムを書いてみなければわからないのか、 理論的に導くことができるのか、 が気になりました。
ぜひ自分で調べてみて下さい．
今回の講義を通じて、 「解けるかどうか」という問いの次に、 「効率的に解けるかどうか」という問いがアルゴリズム設計において本質的に重要であることを理解できた。 最後に触れられたP・NPという分類、 特に「多項式時間で解けることが証明されていない」ことと「解けないと証明されている」ことは全く異なるという指摘は、 今後の講義で扱われるP対NP予想の内容を理解する上での重要な前提になると感じた。
P対NP問題についてはまだ話していないですね．次回詳しく話します．
今回の授業は「計算量と計算の複雑さ」の章で、 漸近実行時間とハノイの塔の話が印象に残りました。 特にハノイの塔の逸話(ブラーマ寺院の僧侶が64枚の盤を移し替え終えると世界が終わる、 という話)が計算量の爆発的な増加をイメージしやすく示していて面白かったです。 emacsでM-x hanoiを実際に動かして確認できる点も、 理論と実践がつながっていて良いと思いました。
ぜひ自分で確かめてみましょう．
第一回の課題で扱いやすい問題や扱いにくい問題などについて例を挙げて説明したが、 その時は多項式時間で解けるか否かだと考えていたが、 効率的に解けるかどうかを次回の授業で検証してそれが扱いやすい問題かという話につながるということを聞き、 効率的に解けるかどうかを重視するために「扱いやすい問題」といった定義をしていたのだと考えさせられた。
単に多項式時間かどうか，ということではないですね．
今回の講義で最も興味深いと思った内容は組み合わせ最適化とスターリングの公式です.一定の条件を課した組み合わせを考える問題では最適なアルゴリズムが見つかっていないため列挙法で地道に最適な組み合わせを考えるしかなく,また列挙法では実行時間が階乗で表されるものもあり,更にスターリングの公式から階乗はnのn乗と同等の急増加する値であるから,組み合わせ最適化の難しさを実感しました.
また講義の最後ではP対NP問題の話も少し触れていましたが,コンピュータには計算不能問題があるのと似たように,数学でもゲーテルの不完全性定理から解けない命題があるので,もしP≠NP予想が解けない命題だとしたら恐ろしい問題だなと思います.
色々と知っていますね．よく勉強しているようですね．素晴らしい．
今回の講義では、
計算量と計算の複雑さについて学んだ。
計算できるかどうかだけでなく、
計算にどれくらい時間がかかるのかを考えることが重要だと分かった。
特に、
ハノイの塔やナップザック問題では、
問題の数が少し増えるだけで、
必要な計算量が急に大きくなる点が印象に残った。
また、
ソーティング問題では、
並べ替えの方法によって比較回数が変わり、
アルゴリズムの選び方が大切だと感じた。
巡回セールスマン問題も、
都市数が少ないと簡単そうに見えるが、
都市が増えると組合せが一気に増えるため、
すべて試すのは難しくなる。
今回の講義を通して、
コンピュータの性能だけでなく、
効率のよい解き方を考えることが大事だと思った
そのとおりですね．情報系だとこのようなことを考えますね．
指数関数の爆発の恐ろしさを実感した。 ハノイの塔は円盤64枚で1億回/秒の計算機でも約5800年、 128枚では宇宙年齢の1兆倍超。 nを2倍にしただけで桁違いになる2のn乗の性質に驚いた。 TSPやP対NP問題への繋がりも興味深かった。
問題のサイズが2倍になっただけなのに．．．ですね．
巡回経路問題は、 巡回する場所が増えるほど指数関数上にオーダーが増えることが理解できました。
よろしいと思います．
「ハノイの塔」や「巡回セールスマン問題」を通し、
入力サイズ N の増加に伴って計算量が指数関数的・階乗的に爆発する現象を数値データで視覚的に理解できました。
・配列 [100, 38, 76, 98, 25] を用いたソートのトレースにより、
隣り合う要素の比較とスワップを繰り返して最小値を浮かび上がらせる規則性を実感できました。
・「ナップザック問題」について、
ぬいぐるみの重量制限（7kg）と価格最大化という身近な例から、
制約条件と目的を直感的にイメージしやすかったです。
ハノイの塔の漸化式 A_(n+1) = 2(A_n + 1) から、
一般項 A_n = 2^n - 1 を導出して計算量 O(2^n) を数学的に評価するプロセスをより深く復習したいです。
・巡回セールスマン問題のように計算量が爆発する困難な課題に対し、
実際の物流システム等ではどのような近似アルゴリズムを用いて実時間内に解決しているのか疑問に思いました。
オーダーが指数上になると、 想像以上に計算回数が増え、 時間がかかると思った。 nの数が増加するほど対数関数のような計算量が少ない解法が重宝されると思った。