2025年05月21日 第6回
ハノイの党とナップザック問題について学びました．
ハノイの党を見るにコンピュータの処理速度には到底人間は追いつけないとひしひしと感じました（私はいつか勝ちます）ナップザック問題の身近な使用例について知りたいと思いました．
ハノイの塔ですね．
ハノイの塔の手数を漸化式を使って求める方法をご教授頂いた時，
受験で確率漸化式や場合の数漸化式で苦しめられた過去を思い出しました．
また，
求められたAnが，
最小の手数なのか疑問に思いました．
最小の手数だと思います．
n-1枚での手数とn枚での手数の関係から求めたので．
今回は計算量について学びました．
64枚と128枚では，
視覚的には大きく変わらないようでも，
所要時間は文字通り桁違いになって驚きました．
ハノイの塔の盤を動かす手順はおそらく一つしかないように思いましたが，
ナップザック問題を解くためのアルゴリズムは複数あるような気がしています．
(すでに制限を超過した組み合わせより明らかに重い組み合わせをどうにかして除外するなど)
複数あるのはその通りです．
今日も面白い授業ありがとうございました．
ナップザック問題は池辺先生の授業でやっていたのでよく理解できました．
ハノイの塔の一般化があっていてよかったです．
理解できたようで良かったと思います．
アルゴリズムと聞くと難解な印象があるが，
ハノイの塔のように高校数学でも表現できるものがあり案外身近で面白いと思いました．
ナップザック問題は定義が数式で示されていましたが，
芸術や道徳といった話を除いて，
問題の意味を自然言語で表せても数式では表せない様なものはあるのでしょうか．
良いコメントですね．次回触れたいと思います．
課題ではn個の品物の，
盗む，
盗まないの2択である組み合わせの合計が2^nであることについてしか考えなかったが，
実際は制約条件があり，
どのように最適解を導くか難しくなった．
最適解を導くのは難しいですよ．
以前の講義でコンピューターで理論的には計算できるがかかる時間が長く現実的にできないというのを聞いたが，
今回のハノイの塔やナップザック問題など操作の回数が多いものを処理するという例で納得した．
納得してくれたようで良かったと思います．
今回は指数関数の膨大さが具体値を伴ってわかりました．
そう考えると，
ムーアの法則がもし本当に成り立ったのならPCの性能はとんでもないことになっていたんだろうなと思います．
また，
ジェラトーニの問題について質問なのですが，
ジェラトーニの各サイズのぬいぐるみはそれぞれ1個までしか盗めないのですか？もしいくつでも良いなら最適解は極小2個と小1個を盗んだ時の51万円なのではないかと思いました．
ところで師はジェラトーニを盗んだことがあるのでしょうか？まるでみんなが盗んだことがあるような発言をしてらっしゃったのが聞き捨てならないですね...！
確かにとんでもないことになるのでしょうが，講義でも触れたように限界はありますね．
ジェラトーニ問題は，それぞれが1個までです．
盗んだことはないですし，盗んだことがあるような発言はしていないです．
今回のものは，次回のTSPもですが，あくまで計算量を考えるために用意した架空の話です．
ナップザック問題を実際に黒板で手計算で求めていく過程を見て，
計算量が膨大に増えていく感覚が身をもって感じられた．
先日の池辺先生担当の情報工学概論では関数の最適化を学んだが，
今回のような離散的な量を扱う最適化問題では異なるアプローチを取っていたことが興味深かった．
講義でも話したように最適化については連続なものと離散なものがあります．
ナップザック問題は池辺教授の最適化の課題でやったばっかりだったので，
池口教授の講義で理解がさらに深まりました．
今履修している授業が色々なところで繋がるので日々の授業がとても面白いです．
理解してくれて良かったと思います．
ハノイの塔のnの増加に対するAnの増加量を見て，
指数関数の恐ろしさが分かった．
暗号の話で，
「暗号は絶対に解けないからではなく，
解けるまでの時間が現実的でないほど膨大だから安全なのだ」という話を聞いたことがあったが，
表の増え方を見てその意味を実感できた．
調べてみると，
AES128の解読には2の126乗の計算が必要だそうなので，
現代の暗号は間違いなく安全なのだと納得できた．
この指数関数の爆発的にパターンが増えるという特性は，
良いアルゴリズムを考える上では邪魔でしかないが，
暗号などではそれを逆用しているという二面性が面白いと感じた．
その通りですね．面白いところです．
ハノイの塔においてn=64,n=128というのは現実的な数字なのにかなり効率的なコンピューターでも現実的ではない時間がかかることに驚いた．
列挙法については候補が多くなったり目的関数が複雑だと時間がかかりすぎてしまうため現実的な方法ではないと思った．
その通りです．現実的な方法ではありません．
本日も楽しい講義ありがとうございました．
本日はハノイの塔の一般化やナップザック問題の列挙法について学ばせていただきました．
スーパーコンピュータでも途方のない時間がかかる事象についてぐたいてきにしることができて良かったです．
そうですね．とても莫大な計算量になってしまいますね．
今日の授業もとても楽しかった．
ギガは補助単位であり，
ギガがないという言葉はないという師匠の発言に「ギガっ」とした．
日常生活でも，
人間をAIが超えるかもしれない，
だったり，
根拠のない陰謀論だったり，
誤った発言や言動が多く散見される．
情報工学科に入ったからには，
このような発言を速やかに指摘できるような，
正確で高度な知識をこれからも学んでいきたい．
また，
組み合わせ最適化には興味を持っていたので，
離散最適化との違いについて教えて下さったので，
今後についてきれいな見通しを持つことができました．
ありがとうございました．
講義でもせつめいしましたが，組合せ最適化というのは離散最適化のことです．
今日はハノイの塔とナップザック問題について触れた．
講義内で行われていた列挙法はやはり数が多くなってくると大変であり，
ハノイの塔の時と同様，
すごい時間がかかりそうだ．
そこでどのようなナップザック問題の解き方があるのか気になったので次の講義までに予想したり，
調べて見たりしてみたいと思う．
時間がかかりますよ．
1kg当たりの価格が高い順に優先的に盗むようにすれば(この問題なら極小を盗まないパターンは最初から除外する)手順が少なく済みそうだと思った．
追記 ダッフィー&フレンズ(ジェラトーニはこれに含まれる)はTDSにしか居ないので，
「そもそも盗めない」が正解ですね
これは貪欲法という方法でダメです．最適性がないので．
また，後半のコメントは数年前にもありましたね．
出題の意図を理解してもらいたいと思います．
ハノイの塔やナップザック問題について，
手計算でここまでの量のデータを取り扱うのはミスすることも多くなり，
大変だなと感じました．
また，
キャリアデザインで他の学生さんと話したときにC言語やPythonについて，
本を買って勉強している人が多く焦りを感じました．
置いていかれないように頑張りたいです．
できたほうが良いとは思いますが，できなくても焦る必要が全くないですね．
今回の講義では，
ハノイの塔とナップザック問題に着目して，
コンピューターに向いている計算かどうかについて考えた．
コンピューターをうまく利用する上でコンピューターについての知識を得るだけでなく，
その問題についてもよく知り，
コンピューターが解くにはどういった手順をとるのか考えて，
それが向いているかどうか判断することが大切だと思った．
それと同時に，
どれだけコンピューターが発展しても自分で考えないといけないので，
楽は出来ないと思い少し残念だった．
その通りですね．楽はできないですね．
今日の授業も楽しかった．
ハノイの塔を通して，
指数関数の脅威を感じた．
また，
ナップザック問題についても，
品物の種類が増えれば増えるほど，
列挙法でやろうとすると考える量が指数関数的に増えていって，
大変になるのかなと思った．
その通りです．列挙法を使うとそうなります．
盤を増やしていくとその問題を解決するためには，
人間には想像できない時間が必要であるという事が分かり，
こういった問題が生きている間に解決するかは不明だが，
いつ解決するのかが楽しみである．
今回も言うまでもなく，
とても面白い講義だった．
面白いのであれば良かったと思います．
ハノイの塔において，
かなり高速のコンピュータで計算したとしても盤の枚数が128枚だと途方もない時間がかかることがわかり，
指数関数的に増加することの恐ろしさを改めて実感しました．
その通り，恐ろしいです．
今回も面白い講義ありがとうございました．
先週の課題と授業で扱ったハノイの塔は高校の教室の後ろにおいてあり，
時々遊んでいたので馴染み深かったです．
ハノイの塔の漸化式をといて一般式を求めたとき，
（いつしかのコメントでどなたかがおっしゃっていたかもしれませんが）ドラえもんに出てくる「バイバイン」」という道具を思い出しました．
高校生になり指数関数の授業を受けた際に数学の先生もこのドラえもんの道具について触れ，
いかに"指数関数（的）"という言葉が恐ろしいかを知りました．
またこういった数学的な計算量の問題はなぞなぞのように一見理解しやすいものに感じますが，
非常に奥が深く興味深いと思いました．
やはり数というのは恐ろしい，，．
バイバインは出てきましたね．2の冪乗はあっという間に増えます．
ハノイの塔とナップザック問題について学んだが，
個数を少し増やすだけで，
試行する回数がとてつもなく大きくなり，
高速に処理できても何千年という時間がかかり，
こういう方法では，
パソコンを使っても解けないだろうから，
次の授業で学ぶ方法が楽しみだ．
確かに試行する回数は増えますが，最適解を求める方法もあるのですよ．
次回，簡単ですが触れましょう．
今回の講義ではコンピュータの計算と最適化について学んだ．
ハノイの塔の試行をコンピュータにやらせた時，
Nが大きくなりすぎると計算しきることができないのではないかと考えた．
一方，
ナップザック問題の最適解を計算する時，
列挙法を用いるのは現実的なのではないかと思った．
コンピュータは0と1を使って計算をしているため，
ぬいぐるみを入れる，
入れないを0と1だけで表すことができるナップザック問題は私たちが思うより簡単にできてしまうのではないかと考えた．
列挙法を用いるのは現実的ではないですね．
情報処理演習でemacsを今週使いハノイのコードをemacsで打つことができた．
情報処理演習で習ったことをコンピュータサイエンスの授業で使えたので良かった．
そうですか．やってみましたか．
今日の講義では，
ハノイの塔と，
それの時間的観測に用いる浮動小数点，
ナップザック問題について学んだ．
特にナップザック問題の定義や処理の仕方といった概要的な事柄を知ることができてよかった．
情報工学概論の際の説明にあった「最大化」と「その条件」に関するアルゴリズム的な理解が深まった様に思える．
理解できたのであれば良かったと思います．
ナップザック問題は目的関数を最大にする解を求めるというシンプルに見える問題だが，
ぬいぐるみの種類が増えると人間が列挙法で求めるのが困難なる奥が深いものだと思った．
ハノイの塔と同様に指数関数的に組み合わせが増えるのかと思った．
その通りですね．指数関数的になりますね．
今回の講義では問題の計算量について学んだ．
ハノイの塔，
ナップザック問題はどちらも列挙法で解こうとすると計算量が指数関数的に増加するため現実的でない．
詳しくは知らないのだが，
ナップザック問題は動的計画法を用いると効率的に解くことができるらしい．
是非，
動的計画法についてご教授願います．
この講義は最適化の講義ではないので触れることはありません．
今日の講義はコンピュータサイエンスに関する知識を得るという点だけではなく，
少し言語化しづらいが，
コンピュータ的な考え方というか，
コンピュータを扱う上で慣れておくべきものの見方を知るという点で，
非常に重要な講義だと個人的に感じた．
世の中の文章化された問題を数式に落とし込んで処理する能力は，
これからIT関係の仕事に就く際に必要になってくると思うので，
本日の講義を導入としていろいろな問題について調べて考えてみたりしたい．
そうですね．まずは色々と考えてみることが大切だと思います．
指数関数の爆発力をあらためて実感しました．
私は，
ゲーム内ショップなどを通じて装備を強化していくローグライクのゲームが好きで，
ステータスがインフレしていき，
「1.0e50」といった桁外れの値で壊れていく感覚が楽しくてたまりません．
一方で，
アルゴリズムの分野では，
いかに処理効率を高めるかが重要であり，
処理量が指数関数的に増加しないよう工夫する必要があると考えています．
こうした効率化を考えること自体が私にとって楽しく魅力的であるため，
池辺研究室でそのようなテーマに取り組みたいです．
取り組むと良いと思います．
今日は指数の凄さと離散的問題の解き方について学んだ．
離散的な問題をどうやってコンピュータで解くのかわからなくて面白かったです．
ところで質問があります．
私は今チャットボットを作っていて，
送られた文の要素に対して決められた処理をするプログラムを書いています．
自分はこれだけでも簡易的なAIと呼べると思うのですが先生はどこからAIと呼べると考えますか．
AIの定義ですか．結構深い話ですね．
今回の講義では，
ハノイの塔を例として計算量について考えた．
盤の数n=64のとき2018年のアメリカのコンピュータでは膨大な時間がかかるのに対して，
富岳では一瞬で解けてしまう例から，
コンピュータの進化の早さを実感した．
また，
ナップザック問題は全列挙するとハノイの塔のように指数関数的に計算量が膨大になってしまうので，
理論上問題を解くことができるアルゴリズムではなく効率的に問題を解くアルゴリズムを考える方が重要だと感じた．
今回はn=64だと解けるが，n=128だと実質的に無限と考えてもよいくらい長い時間がかかる，
つまり解けないと考えて良いというところがポイントです．
今日は，
ハノイの塔の問題とナップザック問題の解き方，
考え方を学んだ．
ハノイの塔の盤の数が大きくなると指数関数的に手数が大きくなり，
n=64とn=124では全く違うことに大変驚いた．
ナップザック問題の列挙法が高校の時の樹形図に似ているなと思った．
そうですね．木ではあるので似ているかもしれません．
ハノイの塔に関するパソコンの処理の話で，
枚数が1枚違うだけで処理するものと時間がほぼ2倍になることは数字の上では納得できますが，
実際に数字を見るとここまで爆発的に増えるのかと驚きました．
確かに驚きですね．
今回はハノイの塔とナップサック問題の計算方法について学んだ．
ハノイの塔は数を2倍にすると爆発的に計算時間が長くなることがあると知れて面白かった．
ナップサック問題は列挙法を用いて解くことができることを知ったが，
数が増えたら時間がかかりそうなので他に方法があるのか気になる．
良い質問ですね．方法は色々とありますね．
今日の授業もとても楽しかったです．
ナップザック問題で「決定変数が0と1をとる」と聞いたとき，
量子コンピュータの重ね合わせの性質を使えば一瞬で解けるのでは？と思いました．
しかし，
よく考えると，
重ね合わせ状態から最適解だけを取り出すのは難しいことに気づきました．
うまく最適解を取り出す方法はないのでしょうか？今後もっと学びたいです．
おー，良いコメントですね．すばらしい．
今回の講義ではナップザック問題のシンプルな考え方とそれとは反するような計算量の多さに驚かされました．
ナップザック問題でｎの数が少し増えるだけでも選び方がとても多くなり，
その分時間もかかるということを学びましたが，
では実際にナップザック問題をリアルタイムで解く必要がある場面ではどのようにして時間を短縮しつつ，
最適な解を出しているのか，
もしくは別の方法があるのか気になりました．
こちらも良いコメントですね．次回少しだけ触れましょう．
とんでもない時間がかかる処理というもののスケールが自分の想像よりもとても大きなもので驚きました．
複雑な計算におけるコンピュータの処理の非現実さについてよく理解できました．
そうですね．実際には難しいということになりますね．
高校生の時と比べて数字の規模が跳ね上がってきていて，
大学生らしくなってきたと思うのと同時に，
これから先こうした規模の数字を扱うことになるかもしれないと思うと，
少し胸が高鳴ってきました．
質問になるのですが，
富岳などのスーパーコンピュータで列挙法を使えば，
ある程度実用的なパスワードなどの暗号解読ができるのではないのでしょうか？複雑なパスワードでは指数的に組み合わせが増えていくので，
授業で扱ったような天文学的な数字になると思いますが，
簡単なパスワード程度なら分かるのでしょうか？また，
量子コンピュータが実用化されれば，
暗号解読がより早くできるようになりますか？
「簡単な」というのが定量的ではないのでなんとも言えませんが，
暗号の場合鍵の長さできまるところがあるので，短い場合はだめでしょう．
浮動小数点の話が出てきたが，
自分で電卓を作ってみようとした際，
2進数と10進数を変換しているため0.1+0.2=0.3にならない問題に直面したことを思い出した．
Mathematicaなどの計算機でこんな単純な問題は起こらないと思うが，
そういう意味で完璧な関数電卓はコンピュータ上のプログラムで作れるのか？と思った．
また，
nを大きくするだけでナップザック問題は現実的な時間では解けなくなる(出てきた解が最適解であることの証明が難しい)ので，
未解決問題は意外と簡単に作れるんだなと感じた．
未解決問題ということではないですね．解き方はわかっていて，理論的にはもとまるものなので．
今までコンピュータの歴史や構成要素などに関する授業でしたが，
前回から計算に入り，
一気に数学っぽくなったように感じます．
2021年に作られた富岳の計算速度は442.01PFLOPSと，
授業内で紹介されたSummitの約2倍であり，
3年でそこまで進化するのかと驚きました．
進化の速度は早いですね．
本日の講義では，
ハノイの塔とナップザック問題について学びました．
ハノイの塔で円盤の数を増やすと計算にかかる時間が指数関数的に増加していき，
京や澗といった天文的な数字にまでなることに驚きました．
また，
n=64のときに，
通常のパソコンと比べてスパコンの速さが思っていたよりも早かったのが印象的でした．
あっという間に大きくなりますね．
今回の講義で，
ハノイの塔の一般式やナップザック問題を解くにあたって必要な道具となる列挙法について学ぶことができた．
情報工学科として，
コンピュータのあらゆる問題を知るだけでなく，
実際に自分で実践して解いてみたいなと思った．
そうですね．自分で解いてみることがたいせつですね．
自分のPCのemacsでhanoi-unix(円盤32枚)を実行してみたところ，
盤が移動しているのに中々終わらないのでいつ終わるのだろうと気になりました．
そこで7-zipのベンチマークを実行したところ20000MIPS前後という結果が出たので，
hanoi-unixが終了するまでにかかるのは59.7時間だと概算できました．
それに比べると，
富岳が円盤64枚のハノイの塔を0.46秒で解き終えてしまうというのはやはり驚異的で，
一般的なPCではスーパーコンピュータには足元にも及ばないということを実感できました．
今回はそれが主題じゃないのですけどね．．．
本日の講義で行ったようなとても複雑で，
解決するのにも数え切れない時間を要するものを私たちはこれから処理していかなきゃいけないのでしょうか．
生活が困るのですかね．
また，
MIPSを限界まではやくすると最大何回/秒にすることができますか．
それを使ってもし解決するなら何回程のものを一人の人が生きているうちに処理できるのでしょうか．
難しいと思います．
今日は主にナップザック問題について学ぶことができました．
ナップザック問題という名前は知っていたものの，
具体的な内容は知らなかったため，
興味深いものでした．
今回，
ロッカーへ行って戻ってくるまでの短い時間で前のほうの座席はすべて埋まってしまっていたので次からは最初に教室に寄るようにしようと思います．
最前列は空いていると思いますよ．
今回はナップザック問題について扱いました．
以前に競プロを通してかじったことがあったので，
dp法があり，
選び方を保存しておいて探索するのが良いということは知っていたものの，
細部については忘れてしまっていました．
自分なりに色々考えてはみていましたが，
具体的にどのように探索するのかを遂に思い出せませず，
改めて先人の凄さを体感しました．
確かに先人の知恵はすごいですね．
今回の授業で，
ハノイの塔について扱ったが，
富岳がn=64なら0.46秒で処理できるというのは自分でレポート作成した際にもそのように確認出来て，
ついに元の物語における伝説が破られたのかと驚いた．
人間の生み出した技術でそのような巨大な数を扱えるようになったというのは感動するが，
それと同時に，
更に2倍してn=128にするだけでまた途方もなく不可能になるというのはやはり組み合わせ爆発は恐ろしいと感じた．
ナップザック問題においても同様のことが起こるが，
しかし動的計画法などを用いることによって計算量が大幅に削減されることもあることから，
アルゴリズムの工夫に大きな可能性を感じた．
アルゴリズムの工夫についてはその通りです．
今回の講義では，
コンピュータの計算の限界について具体的な数値をもとに学ぶことができました．
また教授のお気に入りのディズニーキャラクターがジェラトニーであることに驚きました．
お気に入りということではないのですが．．．
計算が爆発しそうに見えても工夫次第で解決できる問題を見たりするので，
計算量は改めて重要だと思ったし色々と知りたいと思った．
その通りです．重要ですね．
今日は，
ハノイの塔とナップザック問題について扱いました．
特に今回の内容は，
最適化と重なる部分が多い内容で，
本格的に実社会において使われているような情報技術の片鱗を味わえているような気がして面白かったです．
最適化といえば，
インターネットショッピングなどの荷物の配送の順序や，
ウーバーイーツの配達の順序のような，
配達経路にも使われている技術だと思うのですが，
巡回セールスマン問題は未解決なのに，
このような技術が存在するのは，
何らかの部分で端折ったり，
工夫をしているからなのでしょうか．
巡回セールスマン問題が未解決というのがどういう意味で言っているのか不明ですが，
解く方法はありますね．端折ったりというのは理解してくれているような気がします．
とても面白い授業でした．
特にハノイの塔でのとても大きな桁の数を見てとても驚きました．
確かにあれだけ膨大になるとコンピュータとはいえ処理に時間がかかってしまうというのも納得できます．
膨大となりますね．
今回は計算を主に行いましたが，
2^64と2^128という一見そんなに差がなさそうな数字同士でも処理するための時間が圧倒的に違うということに驚いた．
最近富士通が開発した２５６量子ビットの超電導量子コンピュータだと，
どれくらい時間がかかるのか知りたい．
調べてみてください．
昔絵本で見たことで，
2の指数が少し増えただけで計算結果の数に大きな差ができる事は知っていた．
しかし，
ハノイの塔の2の64乗は富岳でほぼ一瞬でできるのに対し，
2の128乗は宇宙齢が出てくるほどの計算時間がかかることを知り，
指数関数的に増加するということは計算の複雑さも爆発的に上がるということを感じた．
これにより，
先生が言っていたように，
人では到底なし得ないような速さで計算できるコンピュータにもやはり物理的に解けないものがあるのだと体感した．
その通りです．実際は難しいということが多数ありますね．
ハノイの塔の話で普段耳にしないような単位が出てきて宇宙齢でも桁が数えられないぐらいだったのが驚いたし，
列挙法ではコンピュータでも限界があるんだと納得した．
限界がありますね．
ハノイの塔に関する疑問なのですが，
円盤がいくら増えようと棒の数は3本のままルールを反することなく移動が可能な理由がイメージできません．
小さい円盤が大きい円盤の上にないとダメという制約のためには，
3本ないと難しいと思います．
今回はハノイの塔に関して漸化式を用いて解く方法と，
列挙法について学びました．
授業の後，
emacs hanoiでハノイの塔を自動的に動かすだけの動きを見ましたが，
可愛らしかったです．
疲れが溜まってきたらまた数を増やして再度眺めてみようと思います．
コンピュータで解く際に，
とても処理が早いにも関わらず，
列挙法だと5800年もかかってしまってしまうと知り驚きました．
来週，
再来週あたりは数学の中間考査がいくつかあるため，
課題の提出期限が伸びてくれて一安心です．
本当にありがとうございます．
中間考査ですか．．．まだ高校生？
ナップザック問題と聞いて，
東進の共通テスト模試の情報のプログラミング問題で動的計画法が出題されたことを思い出しました．
流石に難易度が本試験とかけ離れていて（本試験では全探索すらあまり出ない），
平均点がかなり低かったと記憶しています．
受験生にも師の講義を薦めたいところです．
PS：私たちが使っているコンピュータは10^8MIPSより遅いという話がありましたが，
最近の家庭用コンピュータは10^8～10^9MIPSくらいだと聞きました（もちろんCPU次第ですが）．
そうですね．遅いと言った記憶はありませんが，いずれにしてもCPU次第だと思います．
今回の講義ではハノイの塔について学びました．
ハノイの塔の一般項は指数関数で表せますが，
指数関数の増加する量の恐ろしさを改めて感じました．
nが64から128になるだけでコンピュータが計算できる時間があんなに変わるのだと知って驚きました．
余談ですが，
指数関数といえばドラえもんの秘密道具のバイバインをいつも思い出します．
バイバインは以前もコメントで出てきましたね．
計算するのにかかる時間が，
あまり見る機会がない桁を使うほどかかることになると思っていなかったから驚いたし，
計算をするということには変わりないのになぜ計算式に指数関数が入るだけで時間がそんなに変わるのかが気になった．
(指数関数のどんなところに時間がかかるのか，
他にも時間がかかってしまう計算式はあるのかなども)ハノイの塔の問題もナップザック問題のように1と0に分けて考えることは出来ないのか気になった．
(そうしたら指数関数が出ずに問題をとくことができそうだから)
ハノイの塔はパズルなので，問題を解くというのとはちょっと違うと思います．
宇宙が生まれてから137億年も経っていることに驚き，
その後にハノイの塔を64枚，
100mipsでやっても宇宙齢をとうにこえているということを聞き，
師数関数の恐ろしさを少し実感することが出来ました．
実感してください．
今回の授業ではハノイの塔を例に指数関数の処理量の変化具合を実感出来て面白かった．
特に富岳では64枚なら瞬時に出せるものの枚数を倍にする事で天文学的な数字になる事に驚いた．
疑問点としてMIPSという単位を学び1秒あたり何百万回の命令を処理出来るかを表したのものと知ったが，
この命令の処理という物は何が1命令として数えられるのか気になり調べてみようと思った．
そうですね．調べてみてください．
例え100MIPSでおこなったとしても，
盤の数が2倍になっただけで見慣れている数から一気に今後聞きもしないような膨大な数になっており，
改めて指数関数の恐ろしさを実感した．
また教授がトリリオンゲームを知っていることがかなり驚きだった．
知ってますよ．今度映画化されますね．
映画化されると言えば，ラストマンも映画化されるらしいですね．
今回の授業では問題の計算の複雑さや指数関数による計算のさらなる複雑さについて学ぶことができた．
頭の中だけでは考えることが難しい最適化もコンピューターの圧倒的な計算速度や試行回数によって示すことができたが指数関数的に増えるものでは途方もない試行回数となり現実的ではないので他の方法がないのか考えていきたい．
そうですね．考えてみてください．
今回の講義ではハノイの塔に関して，
べき乗によって計算時間が大幅に変わるというところが印象に残りました．
スーパーコンピュータですら途方もない時間がかかるようになるというのは，
コンピュータに対する見方が変わりました．
また，
ハノイの塔に一見似ている，
ナップザック問題の列挙法は要素が増えるごとに列挙する個数が2乗になっていき，
さらにほかの価値や重さといった条件も考える必要があるのが，
非常に厄介だなと思う．
実際，
nの値が大きくなった時，
どのようにして最適な値に近い値を得るべきなのか，
ほかにアルゴリズムは存在しているのか非常に気になりました．
良いコメントですね．アルゴリズムはいくつかありますね．
ハノイの塔やナップザック問題という有名だがあまりよくわかっていなかった問題について丁寧に解説していただき理解が深まった．
理解できて良かったと思います．
今回は指数関数の増加する速度の恐ろしさについて学んだ．
列挙法ではn種類の品物があるときに2^nの場合を考えなくてはならず，
nが増えると現実的な数はなくなってしまうので，
制約条件を満たさないものをさっさと消してしまいたいが，
それをしるために列挙しなくてはいけないのが面倒だなと感じた．
そうなのです．そこがポイントなのですよ．
これまでの講義内容に比べ実践的で専門的な内容になってきたように感じた．
まだそれほど専門的出ないと思います．
ハノイの塔においてn=64から二倍のn=128で物凄い増加の仕方をしていて驚いた．
数字が大きくなったとき，
列挙法では難しいだろうから，
ハノイの塔やナップザック問題のような課題に対して，
どのように対処していくのかとても気になった．
列挙法では，確かに難しいですね．
ハノイの塔が64枚と128枚で2倍しか(も？)変わっていないのに移動回数や処理時間がありえないほど変わっていて驚いた．
ナップザック問題はどこかでやった覚えがあるが，
どこでやったかの記憶がなく忘れていたので次回しっかりと学びたい．
i そうですか．しっかり学んでください．