2025年05月28日 第7回
今回も面白い授業ありがとうございました．
回数について指数関数になるよりもｎの多項式のなるほうが少ない手数になってよいと学びました．
また今度もお願いします．
了解しました．
指数関数的に数字が増加するということは恐ろしいことだと感じた．
そのため最適解を求めるのは非常に難しいということが理解できた．
近似値であればより短い時間で答えを求めることはできるかもしれないが最適解とのずれがどれぐらいあるのか気になった．
確かに恐ろしいですね．良いコメントですね．近似解がどの程度かが大切な指標です．
今回はソーティング問題や巡回セールスマン問題について取り扱いました．
以前暗号について調べていたことがあり，
その際，
"多項式時間"という言葉についてぼんやりとしか理解していませんでしたが，
今回の講義でよりはっきりと理解することが出来ました．
よろしいと思います．
バブルソートと選択ソートに関しては高校で教わったので懐かしく感じた．
またハノイの塔やナップザック問題，
TSP問題を学んだあとにソーティングに関して学ぶとP問題とNP問題の違いがよく分かった．
そうでしたか．習っていたのですね．
バブルソートは高校時代も情報の問題集で取り扱ったので，
馴染みがあったが，
詳しく知ることができたので面白かったです．
バブルソートもナップサック問題も単純な式ではあるが，
多項式である場合と累乗の場合で大幅に調べる必要のある総数に違いが出るというのが，
グラフで見ると一目瞭然で驚きでした．
ソーティングに関して，
様々なソート方法があると思うので，
それぞれの特色について調べ，
実際に実行してみようと思います．
どのようなソーティングがあるかは今回の主題ではないですが，
調べてみると良いですね．
階乗の存在を忘れていたのですが，
暗号に使う場合は階乗を使った方が組み合わせの数自体は多くなると思います．
それでも楕円曲線暗号や素因数分解が使われているのは，
そちらの方が扱いやすい理由があるからですか？
ちょっと違いますね．暗号入門のところで説明できると思います．
今回の授業では，
計算量に関する問題として，
ソーティング問題と，
TSPを扱いました．
最初の方で解説があったように，
実生活に最適化を利用するということであれば，
必ずしも最適化の問題自体を直接的に解く必要がなく，
"適当"に選んだ中で最適なものを選べばよいということに驚きました．
確かに，
十分な試行回数でランダムに解を選んだ中で最適な解を選べば，
"実生活"の場面においては十分に有用性があると思いました．
適当に選んでもそれがかなり良くないとだめですよ．
基本的に階乗>指数関数で計算量がやばくなるのがよく分かった．
計算量でこれだけひどい値になるのを見ると，
実際に計算するときはメモリの使用率というか必要な計算領域の広さが破滅的なことになってしまいそうで恐ろしいです．
実際に計算してはいけません．
バブルソートは共テの情報で問題をやった時のことを思い出した．
指数関数と多項式のnが大きくなった時の違いは数学の極限の時に感覚的にやっていたので，
調べて視覚的にはじめて見て，
本当に指数関数はnが大きくなると値がとても大きくなることを実感した．
そうですね．大きくなりますね．
Youtubeで海外の方が上げている，
ソートアルゴリズムを可視化している動画を見るのが好きです．
その動画ではいろいろなソートアルゴリズムを順番に試していて計算量の違いが一目でわかるのでソートアルゴリズムに興味を持つ入門としてとても良い動画だと思います．
ありがたいです．
ボゴソートが単純明快で好きです．
今回の主題はソーティングではないですね．
今回は列挙法で問題を解く際に計算量が膨大になってしまう例について学んだ．
実際Pythonで簡易的なシミュレーターを作ってナップザック問題やハノイの塔をパソコンに解かせてみたが，
予想以上に計算量が多く(というより計算速度が遅く)終わる気がしなかった．
問題を解決するために多くの研究が進められているのも納得だった．
その通りです．膨大な時間がかかります．
様々な問題について計算量という，
私からすると新しい観点で考えることはとても興味深いです．
理解できましたか．
今日も面白くて考えさせられる内容でした．
楽そうなやり方は最適性が保証されず，
大変な列挙法は指数関数が出てくると非現実的になるというのが難しいと感じました．
話は変わるのですが以前のOSの授業でマウス操作が再現性がないという話を聞いてから操作をボタンだけで完結できたほうがいいと考え始めたのですが，
それに関して最近PC版CLASSでの出席登録をカーソルで登録アイコンを押すのではなくエンターボタンを押して登録するシステムにしたほうがいいのではないかということを思いつきました．
おー，素晴らしい．その通りですね．でも実現しないでしょうね．．．
本日も面白い授業ありがとうございました．
ソーティング問題は高校の情報の授業でそのプログラムを作る授業があったので非常に懐かしく感じました．
グラフ理論等，
離散数学がよく出てきてワクワクします．
ワクワクしてくれて良かったと思います．
今まで計算の手順の数を意識してプログラムを組んだことが無かったので，
プログラムを組む前に手順を数えて計算に時間がかからないかを注意したいと思った
そうですね．計算量を見積もるというのは大切なことですね．
今回の講義では巡回セールスマン問題について取り扱った．
例で挙げられた48州を巡回する巡回路は小さめに見積もっても10の50乗のオーダーとなり，
到底現実的とは言えない．
これがさらに地点の数が増えていくと天文学的という表現すら足りないほどの計算量になるだろう．
その通りです．天文学的を超えますね．
今日の技術で前回と今回で扱った問題をネット上で処理しようとしたときにデータが莫大すぎてバグを起こしたりショートするのか上手いことやり過ごして解決できてしまうのでしょうか．
今日の技術というのがどれかよく分からないです．
ネット上で処理とは？
現実では，
まだnが2桁程度の問題にしか出会わない（あっても解こうと思わない）が，
これからはそのような問題にも直面すると考えると，
怖くなる反面，
ワクワクもしている．
ワクワクしてください．
本日は列挙法とバブルソートの計算量の比較と，
巡回セールスマン問題の概要を扱いました．
ナップザック問題でも列挙法で解こうとすると計算量は指数関数になっておりかなり計算にかかる時間がかなり大きくなっていたのに，
TSPはそれを更に超えてきそうでめまいさえ感じそうでした．
確かに目眩がしますね．．．
総数をnの式で表したとき，
nの多項式なら現実的でnの指数関数になると現実的ではなくなることが分かった．
ナップザック問題でも巡回セールスマン問題でも列挙法だと候補が非常に多くなるため現実的ではないと思う．
その通りです．
ハノイの塔とTPS問題の解の候補の数は違う指数関数で表されて増幅する早さが違うとわかった．
列挙法ではさっさと解を限定できるかが重要なのだとわかった．
確かにそうなのですが，限定できても，計算量は多いです．
指数関数と多項式では最初あまり差がなくても大きくなるにつれて差がとてもあったことが面白かったです．
急激に差が出ますね．
今日の授業も分かりやすかったです．
特に，
軸をうまく設定することでn^2と2^nの差がはっきりと分かるのが面白かったです．
「TSPを列挙法で解くのは現実的か」という問題ですが，
これは現実的ではないと考えます．
TSPではナップザック問題以上に分枝の数が増えるため，
ナップザック問題でも非現実的だった列挙法を用いるのは困難だと思います．
さらにTSPでは「AからBまでの距離は長いがそれ以降が短かった」といった場合が考えられるので，
最適化の手法を考えるのもより難しくなるのではないかと想像しています．
その通りです．よく考えていますね．
本日も興味深い講義ありがとうございます．
今回の講義ではナップザック問題の列挙法やソーティング問題のバブルノート，
巡回セールスマン問題について学びました．
指数関数と多項式の大小関係が面白かったです．
また，
自分の頭では最適な解を答えることができない問題に出会えてワクワクしました．
今日は，ワクワクが多いですね．
今回の講義では，
まず列挙木による全解列挙が品物数 n に対して解の数が 2ⁿ と指数関数的に増大するため現実的でないことを学びました．
また，
厳密解法と近似解法の違いを確認し，
不要な探索を打ち切る分枝限定法や，
単位重さ当たりの価値に基づく貪欲法の長所・短所について具体的に理解できました．
ソーティング問題では，
バブルソートをPythonコードを自分で組み実際に動かした中で O(n²) の計算量を体感し，
多項式時間アルゴリズムと指数関数的アルゴリズムの実用性の差を実感しました．
最後に巡回セールスマン問題（TSP）の定義とその NP 困難性に触れ，
最適解を求める難しさを改めて認識しました．
今後は，
近似アルゴリズムやヒューリスティック手法を自分でも実装し，
NP 困難問題への理解を深めていきたいと思います．
NP困難性については触れていないですね．
コメントは自分で考えて書くようにしてください．
バブルソートの手順に似たような問題を小学生の場合の数の単元の時に解いたように思う．
．
そうですか．
本日はソーティング問題と巡回セールスマン問題について考えた．
指数関数とnの2次式では大きくなる度合いが圧倒的に違うと改めて感じた．
ソーティング問題はnの数がある程度大きくなっても，
コンピュータで計算することができることも分かった．
ソーティング問題はコンピュータで計算できるから，
excelで降順昇順の機能を使えるのだと感じた．
（今日扱った方法ではないかもしれないが）
エクセルは使わないのでよく分からないですが，何かしらの方法を使っているでしょう．
指数よりも，
多項式の方が，
計算量が少ないということは，
グラフで示すことで，
直感的に分かりました，
また，
個人的には，
貪欲法が，
最適に近似できることと，
計算量の，
二つの課題の中間をとっているような気がして，
一番好みです．
貪欲法が最適に近似できるとは限らないですね．
今回の講義では，
ソーティング問題と巡回セールスマン問題について学びました．
ソーティング問題でのバブルソートを使用した計算量は，
前回のナップザック問題の計算量よりはるかに小さいことをグラフや表を用いて説明されており，
とてもわかやすかったです．
いつもわかりやすい授業をありがとうございます．
今回の授業で取り上げられた2つの問題について，
少し興味がわいたので調べてみたところ，
巡回セールスマン問題はその言葉のままヒットしたのですが，
ソーティング問題は「ソーティング」と問題という単語がないままヒットしました．
なぜでしょうか，
ご返答お待ちしております．
あってもなくても同じですね．
今日も興味深い授業をありがとうございました．
列挙法だと計算量が膨大であるが，
バブルソートを用いることでこんなにも計算量が減るのかと関心しました．
これよりも計算量が少ない方法ってあるのでしょうか．
バブルソートを紹介したのは，あくまで簡単で説明しやすいからで，
他にももっと早いソーティングのアルゴリズムはあります．
高校の情報の授業でバブルソートをExcelで作ったことを思いだしました．
その時は数が少なかったので直ぐに結果が出ましたが，
数が多いとたしかに時間がかかりそうだと式を出してみて実感しました．
今日は，ソーティングを解く方法としてバブルソートを紹介しましたが，
時間がかからない例ということでお話ししました．
巡回セールスマン問題やソーティング問題など高校の情報の授業の時にやったことがある内容でしたが大学に来て自分の学びたい分野として改めて学ぶのはとても楽しいですし，
理科大の情報工学科に入学してよかったなと思っています．
これからの授業も楽しみにしています．
そうですか．高校で習うのですか．驚きです．
本日の講義ではソーティング問題と巡回セールスマン問題について学んだ．
nが大きくなるにつれ総数が大きくなるのでより最適な導き方を学ぶ必要があると思った．
そうですね，列挙法ではだめですね．
「最適なトラックの配送ルートの決定」という身近な問題が，
実は計算量が大きいと知って驚いた．
理由もなく，
身近な問題は簡単に解けるに違いないと考えていたが，
そのような考えはよくないのだと思いなおした．
ところで，
「計算量としてn^2はまあまあだが，
n^3，
n^4となってくると微妙」といった話があったが，
この曖昧な言い回しの意図が気になった．
ただ，
最終的な計算時間を決めるのはその場その場のデータの個数であることを踏まえると，
「結局，
アルゴリズムの良し悪しは実際に使用される環境で決まる」という意味合いなのだと推測した．
理論的にはn^5は多項式ですが，実際に，nが大きくなる
と計算量は大きいということになるのですね．
巡回セールスマン問題を列挙法で考えると，
(n-1)!と階乗の増え方をしていてnを大きくすると，
とんでもない増え方をすることがわかった．
サップザック問題と違い，
条件を簡単に満たしてしまうので，
分岐限定法が使いにくそうで，
どのようにこの問題に向き合うのかが気になった．
分枝限定法ですが，使えますね．
バブルソートの考え方を見た時に，
すごく簡単な作業だけれどたくさんのデータがあった際に凄く大変な作業になりそうだなと考えた．
手計算などだったら素早く終わりそうだからこそ，
より素早く入れ替える方法はないのか気になった．
あと今回は雑談が普段より少なめだったので少し寂しかったです．
今回はアルゴリズムの説明のために5個の例を使いましたが，
実際はコンピュータを使いますね．
今回は，
ソーティング問題やバブルソートに関して学んだ．
前回に引続き，
列挙法を用いる場面が多かったことや，
バブルソートでも２つ同士の比較を続けることで求めるものが導出されることから，
「比較」の連続で行うこの方法は，
手間ではあるが正確性を考えると最良な手法であると強く実感した．
比較する物の数が増えるにつれて列挙法が現実的であるかという問題に関しては，
機械の処理速度の向上に更に期待を寄せたいところである．
バブルソートよりも早く正しくソーティングできるアルゴリズムはあります．
今日は巡回セールスマン問題やソーティング問題について学びました．
階乗が指数関数よりも増加幅が大きいことに驚きました．
また，
今回の授業とはあまり関係ないのですが，
授業中にお子さんがいらっしゃると伺ったのですが，
やはり理系脳は遺伝するのでしょうか？
まだ，階乗の話はしていないですね．
今日の授業もとても面白かったです．
ソーティング問題は高校の情報の授業でも登場していたのでよく理解することができました．
他の内容も同様に理解できるようによく復習しようと思います．
そうしてください．復習は大切です．
今回はソーティング問題と巡回セールスマン問題について学んだ．
最短経路を求めるような問題でも列挙法で考えることができることを知って驚いた．
最短経路を求める話はしていないです．TSPは閉路になる必要があります．
指数関数と多項式の，
nが大きくなった場合の増加の具合の違いを理論的にも感覚的にも理解出来ました．
n^2よりも計算量の少ないものとしてn^1があると思いますが，
一次関数的に最適解をもとめられるほうほうなどそもそも存在するのかな？と思いました．
また，
TSP問題も列挙法以外で解く方法があるんだろうなと思いました．
ナップザック問題と同じく，
現実的な計算量ではなさそうなので．
そうですね．列挙法以外の方法はあります．
今日も面白い授業ありがとうございました．
バブルソートなどを学んで単純な方法が必ずしも効率的では無いということを学ぶことが出来ました．
また，
列挙法以外の方法を知る中で，
計算の速さと正確さの両立は難しいことなのだと改めて気づかされました．
正確さというのは最適性の保証のことを言っていますか？
現在，
基本情報技術者試験の勉強を行っているため，
バブルソートなどの参考書でやった内容が出てきて嬉しかったです．
資格勉強をしていても出てこない，
知らない問題もたくさん出てきて聞いてて飽きないです．
試験頑張りましょう．
巡回セールスマン問題は電車などの乗換検索と似ていると思いましたが，
電車の時刻表や駅内を歩く時間など，
考慮すべき点がかなり多いにも関わらずほぼ一瞬で検索できるのは全ての点を経由するという制約がないからであり本質的には全く違うのだとわかりました．
似ているかもしれませんが，違いますね．
授業ありがとうございました．
計算量が多くなるとコンピュータでの計算に時間が多くかかるので，
なるべく小さく，
特に指数関数が計算量に入ってくるようなことは避けたほうがいいと思いました．
計算量をへらすことは動作の軽量化にもつながるので様々な計算量を減らす工夫をしたいです．
そうですね．そのようにするのが良いでしょう．
何か問題を解く際に，
あるアルゴリズムよりも良いアルゴリズムがあるのか，
それともそのアルゴリズムしかないのかということは悪魔の証明であると思った．
はっきりと答えのある数学のテストのようでなく，
答えのないかもしれない現実の問題を解いていくのにはコンピュータでも困難な事があると感じた．
確かにそうですね．でも困難ではないと思います．
バブルソートでは，
比較回数や交換回数などを通じて計算量の概念を理解できました．
単純なアルゴリズムでも，
計算量の増加がどれほど非効率になるかを数式で実感できたのが印象的でした．
巡回セールスマン問題は組合せ最適化の典型例であり，
経路数が(n−1)!/2通りになるという数式から，
問題の難しさを具体的に感じました．
どうして，(n−1)!/2通りになるか説明できますか．
私は今日の講義を聞いて，
先人たちの計算が複雑すぎる問題に対してこの問題を解きたいという強い気持ちが様々な近似公式を生み出したのだと感じた．
コンピュータサイエンス序論の前の講義のキャリアデザインで知的財産について学んだのですが，
近似式や公式に名前を付けるのってどうやってやるのですか．
さて，どうするのでしょうね．調べて教えてください．
ある問題を解く際には様々なアルゴリズムを考えることができ，
それぞれの計算量や最適性の有無は異なるということや，
計算量に階乗や指数が含まれるアルゴリズムでは十分大きいnについて現実的な時間で解くことはできないということを学んだ．
TSPの列挙法による解放は計算量が(n-1)!/2になる(数珠順列)ので階乗オーダーであり現実的でないと思う．
また，
以下は少し場違いなコメントだが，
アルゴリズムは最適性の保証の有無によって厳密解法と近似解法に分けられるという話を聴き，
量子アルゴリズムには近似解法が多いのだろうかと思った．
量子アルゴリズムは欲しい結果が観測される確率が高くなるように設計されるので，
確率的に良い解が求まる貪欲法や山登り法と考え方が似ていると感じたからだ．
ただ，
量子アルゴリズムでも誤り訂正によって確率的でない答えを出すことができるらしい．
私の理解に至らぬ点があれば指摘してくださると助かります．
アーキテクチャや理論に詳しくないので理解が浅いです．
どうして，(n-1)!/2になりますか？
セールスマン巡回問題などの私生活で発生する問題を数式に落として最適解を求めていくのは凄く面白いと思った，
またあえて指数関数を使い最適解にたどり着くまでの手順をわざと増やすときがあるのか気になった．
おー，面白い考えですね．
今回はバブルソーティングや巡回セールス問題について学んだ．
確実に答えを出すことのできる列挙法では莫大な計算量を必要するものであることが分かった．
改めて指数関数の計算量の多さを実感させられた．
その通りです．大きいですね．
やはり世の中の問題で列挙法以外の解法が見つかるほうが珍しいのでしょうか．
列挙法は確実ではあるが，
計算量が莫大になってしまい使いどころが狭そうなのがのが悩ましいと思いました．
列挙法以外もありますよ．例えば，分枝限定法というのがあると紹介したと思います．
カーナビのように出発点と到着点が定まっているものは解くことができるが，
巡回路の問題はまだ発見されていないというのに驚いた．
TSP問題の列挙法は列挙する数が膨大になりそうだったので巡回路の総数がどうなるのか考察したい．
発見されていないというのは，ちょっと言い過ぎですかね． 次回話ができると思います．
今回の授業では巡回セールスマン問題について学びました．
nがあまりにも大きいと，
解を仮定して近似するという話を聞いて納得しました．
そこで質問なんですが，
実際にそのように解を仮定しなければいけないほどnが大きいような問題は現実ではどのようなものがあるのでしょうか．
質問の意図が不明ですが，TSPなどがそうなりますし，他にも色々ありますが，
次回触れましょうか．
今回の授業ではいくつかの問題について考え，
その計算量がどのような形の式で表されるかによって計算の現実性が大きく変わる事を学んだ．
これによってどの解法が優れているのか比較する時の1つの指標を得た．
また，
TSP問題についてスタート地点に帰る必要があるかないかで計算量の式が大きく変わる事に驚いた．
直感的には帰る必要がない場合の最短経路にスタートまでの距離を足せばTSP問題の解として悪くない値になりそうだと考えたが実際はどうなのか気になった．
TSPは閉路になる必要があります．
バブルソートとその操作の回数についての問題は共通テスト対策でなじみのある問題でした．
問題に対して数学的にモデル化する手法に関して非常に興味があり，
今回も有意義に受講できました．
ところで，
C言語の統合開発環境のエディタなどのツールで教授のおすすめのもの，
または後期のプログラミング演習で指定のものがあれば教えていただけますでしょうか
emacs ですね．
今回の講義では列挙法より計算量の少ないバブルソート法を学ぶことができた．
指数関数とnの多項式の比較について，
高校数学で極限の計算をするときに指数関数の方が発散スピードが速いと習っていたので理解しやすかった．
理解してくれて良かったと思います．
今回も計算についての講義であった．
𓏸𓏸問題といったのが講義で出てくるが，
そもそもこのような問題に気づくことに感心した．
もっと色々とありますよ．
今回の講義では，
ソーティング問題と巡回セールスマン問題について学びました．
処理回数を指数関数ではなく多項式や対数関数の形で表せると，
扱う量を大きくしても現実的な時間内で解けることが分かりました．
また，
巡回セールスマン問題は宅配便の配送ルートの最適化など身近なところでも活用されていると思いました．
そうです．身近ですね．
バブルソートの説明の際，
必ずしもこの解法が最適ではないということを学んだ点が面白いと思った．
バブルソートの説明で，
最終的にn-1,n-2,...1.0の足し算になった点が特に気になった．
今回と前回の授業を聞いている中で，
最終的に用いている解法が，
高校範囲でいうと，
数列や場合の数に帰着されていると感じた．
分野的に幾何学などは，
あまり深く関連するとは考えられないのですが，
複数解法が取れる中で，
幾何学のような想定外なものを使うとどう解けるのか知りたいと思った．
幾何学的な方法もあります．次回，触れましょうか．
今日は巡回セールス問題について学んだ．
多項式では表すことができないことの証明があったら，
あきらめがつくのになと思った．
なるほど．一つの考えですね．
セールスマン問題についてデータ量が多くなると列挙法は現実的ではないとかんじた．
その通りです．