2026年06月09日 第1回
計算の本質や問題を「扱いやすい」「扱いにくい」「計算不能」の3種に分類する理論的枠組みを学びました。
内容を理解してくれたと思います．
計算機では、 扱いやすい問題、 扱いにくい問題、 計算不能問題があることがわかりました。 まず、 扱いやすい問題は効率的に解け、 理論的にも実際にも解けることが理解できました。 次に、 扱いにくい問題では理論的には解けるが現実的には解ききれないことや、 計算不能問題ではどんなコンピュータやプログラムでも解けないことが理解できました。 理論的に解ける問題があるとき、 コンピュータやプログラミング言語のアーキテクチャによって問題の扱いやすさが変わるのかどうかが気になりました。 例えば、 C言語とPythonでは同じ計算をするプログラムでも実行時間に大きな差があることなどから、 そのときに用いるコンピュータや言語に左右されてしまうのか、 それともオーダーなどの計算量で扱いやすいかを判断してよいのかが気になりました。 また、 同じ問題について、 不要な処理を含まない複数の手順で解くことを想定したとき、 ある手順では現実的な時間で解けるがそれとは別のある手順では現実的に解けないとすると、 その問題は「扱いやすい問題」と見なしてよいのかが気になりました。
良いコメントですね．次回触れましょう．
計算とは手順に従い状態を変化させる処理であること、 そして計算問題は効率的に解ける「扱いやすい問題」、 膨大な時間を要する「扱いにくい問題」、 絶対に解けない「計算不能問題」の3つに分類できることを学んだ。
よろしいと思います．
講義のバグ検出は原理的に解けないはずなのに、 現実にはバグ検出ツールなどが存在すると思います。 完全には無理でも、 部分的にはできるということでしょうか？
その通りですね．全てのバグを見つけることはできないということです．
コンピュータにできないことはあるのか？という授業中の疑問が興味深かった。
現代のコンピュータはハードもソフトウェアも非常に発達して計算能力も非常に高い。
ただコンピュータにも扱いやすい問題、
扱いにくい問題がある。
AIにも通ずるものがあると感じた。
その通りですね．
最も驚いたのは、 「現在のコンピュータはどんなに計算能力が高くても、 そもそも絶対に解けない計算不能な問題が存在する」ということです。 今まで、 コンピュータの性能が上がり続ければどんな問題もいつかは解けるようになると思っていました。 今後「2の扱いにくい問題」とされているものでも、 天才的なアルゴリズムの発見によって、 将来「1の扱いやすい問題」に変わってしまう可能性はあるのか疑問に思いました。
これも良いコメントですね．次回触れましょう．
今回の講義では、 計算問題を扱いやすい問題、 扱いにくい問題、 計算不能問題の3種類に分け、 理論的に計算可能か、 また現実的な時間内で計算可能かなどの尺度から評価することを学んだ。 また、 扱いやすい問題なら最短経路問題、 扱いにくい問題なら暗号解読、 計算不能問題ならバグの検出のように具体例もいくつか紹介されており、 より理解を深められた。
理解できたようで良かったと思います．
今回の講義を受け、 計算に対する理解が深まった。 例えば、 計算不可能な問題に対して始めは抽象的にでしか考えられていなかったが、 計算を加算減算などから段々と解説があったおかげでアルゴリズムが原理上存在するかどうかで決まり、 理論的に解けないもであると自分の言葉で考えられるものとなった。
コメント文には学籍番号，氏名などは書かないようにしてください．
コンピュータで扱いやすい問題とは、
ある程度の大きさの値で済み、
実際に解け時間もかからず、
扱いにくい問題は暗号解読のような値の大きさをとても大きくすることで、
時間をかけ現実的に解けないような問題である。
様々な暗号
計算式があるため理論上は解けるという点で扱いにくいとされる。
ここから映画のサマーウォーズの主人公が必死に解いてるパスワードは解けてしまっているため暗号化として成立していなかったのかなとも考えました。
また残りの計算不能問題はどちらにも当てはまらない、
現実的にも理論的にも難しい問題が当たると理解しました。
ただ1番例がピンと来ず、
難しかったのでしっかりと調べるなどして理解する必要があるかと思いました。
サマーウォーズですか．みなさん，暗号の話で知っているのですかね．
コンピュータにとって扱いやすい問題、 扱いにくい問題、 計算不能問題とは具体的にどういった問題であるのか、 違いを深く理解することができた。
よろしいと思います．
量子計算の分野に興味があります。 度々耳にすることはありますが、 従来の古典コンピューターのビットと、 量子計算の量子ビットとでは、 なにがどう違うかよくわかっていないので授業で触れるところまで行くのを願っています。
そうですか．それは素晴らしい．講義でも触れることができたらと思っています．
理解できたこと 計算とは単なる算数ではなく、
「決められた手順（アルゴリズム）」通りに動くことだと分かりました。
また、
世の中の問題には、
すぐに解ける「扱いやすい問題」、
時間はかかるが解法はある「扱いにくい問題」、
そして理論上絶対に解けない「計算不能問題」の3つのグループがあることが印象に残りました。
難しかったこと 「扱いにくい問題」において、
データが少し増えただけで計算時間が爆発的に増えてしまう（指数時間）という感覚が、
まだ少しイメージしづらいと感じました
扱いにくい問題については改めて触れます． そのときに考えてみてください．
今回の講義では、
計算問題が「扱いやすい問題」「扱いにくい問題」「計算不能問題」の3種類に分類できることを学んだ。
これまではコンピュータがあればどのような問題でも解くことができると思っていたが、
計算に膨大な時間がかかる問題や、
そもそも解くことができない問題が存在することを知り、
計算機科学の奥深さを感じた。
特に、
計算不能問題として紹介された停止性問題は興味深かった。
コンピュータにも解決できない問題があるという事実は意外であり、
計算の限界について考えるきっかけになった。
一方で、
講義動画は画面の文字が小さく見づらい部分があり、
内容を理解するために何度か見返す必要があった。
しかしその分、
自分で確認しながら学習を進めることで理解を深めることができた。
コメント文中には，学籍番号，氏名は書かないように．
今日の授業を通して、 計算理論は単に数字を計算するだけではなく、 コンピュータに「何が計算できるのか」「どの程度効率よく計算できるのか」を考える分野であることを学びました。 また、 同じ問題を解く場合でも複数のアルゴリズムがあり、 手順によって計算時間や効率が大きく変わることが分かりました。 さらに、 問題には「扱いやすい問題」「扱いにくい問題」「計算不能な問題」があり、 アルゴリズムが存在しても、 入力が大きくなると現実的な時間では解けない場合があることが印象に残りました。
よろしいと思います．理解していますね．
理解できたところ
今回は第1回目の導入ということで、
計算論の全体像がよく分かりました。
特に「計算」という概念が四則演算にとどまらず、
エアコンの制御や掃除の手順など、
あらかじめ決められた手順（アルゴリズム）に従って状態を変化させる行為全般を指すという視点が理解できました。
また、
問題が「扱いやすい」「扱いにくい」「計算不能」の3つに分類され、
理論上解けることと現実的な時間で解けることは別であるという整理が非常にクリアでした。
理解できなかったところ・疑問点
講義の中で「プログラムの全てのバグを検出することは理論上不可能（計算不能）」という例が挙げられていましたが、
なぜそれが絶対に不可能と言い切れるのか、
その理論的な背景（チューリングマシンの話など）についてまだ実感が湧きませんでした。
次回以降、
簡単なPythonのコードを使いながら議論していくとのことなので、
その限界の証明プロセスをしっかり学びたいと思います。
また、
終盤に紹介された量子コンピューティングが、
この「扱いにくい問題」をどう解決するのかにも非常に強い関心を持ちました。
講義では証明として説明していないのですが，数学的に示されているということですね．
計算機（ハードウェアとソフトウェア）を使って処理を行う際の数学的性質や理論を議論する学問であること。 特に何が計算でき、 できないかとどのくらいの時間で計算できるかの2つが重要であることが理解できました。 また、 四則演算だけでなく、 部屋の掃除なども条件分岐と状態変化を伴う手順であり、 計算として捉えられることが分かりました。
理解していると思います．
最短経路問題やページランク、
誤り訂正が解きやすい問題であることは理解がしやすかった。
一方で整数係数の代数方程式の整数解が計算不能問題とされていることはイメージが浮かばず、
興味を持った。
講義では触れることがないのですが，自分で調べてみたらどうでしょうか．
コンピューターの中でどのような計算が行われているのかについて詳しく学んだことがないので、 この講義を通して十分に理解したいと思う。
色々と議論しましょう．
理論上計算ができる問題とできない問題が存在すること、 また計算ができる問題であっても、 現実的な時間で解けるものと、 膨大な時間がかかってしまうものがあるという分類の重要性が分かりました。 量子計算の導入には行列とベクトルの計算が深く関わっているとのことでした。 大学1年次で習った線形代数の知識が、 具体的に量子状態の表現やゲート演算にどのように結びついていくのか、 今後の展開を詳しく知りたいです。
量子計算の入門については時間を作って説明したいと思っています．
今回の講義を受けることで、 計算論が対象とする問題や課題を認識することができた。 特に、 扱いにくい問題というのはコンピュータの性能やプログラムに依存する点が多く、 今後の進歩によってよりよいアルゴリズムや、 コンピュータの性能によって改善される可能性があるのではないかと感じた。 この講義ではPythonを使用すると聞いたが、 Pythonを使うことでの利点や、 多言語との違いがあれば教えてほしいです。
Pythonだと説明がし安いからで，本質的ではありません．
今回の講義では、 計算論という科目についてどのようなことを学んでいくのかと科目の基礎的な部分および基板になる部分を理解することができた。 扱いやすい問題、 扱いにくい問題、 計算不能問題など具体例を用いて理解できた
よろしいと思います．
今まで自分達が行なってきた計算をいざ手順を明確にし、 プログラムに書いたり、 フローチャートに起こそうとすると、 かなりの条件付けや、 分岐が発生することが分かった。 さらに、 身近の機械が行なっている動作に対しても、 計算という概念が当てはまることも理解出来た。
理解できましたね．
計算とは手順があるもの。
コンピューターは、
外的情報を取り入れて決められた手順通りに動く。
計算問題には、
扱いやすい問題、
扱いにくい問題、
計算不能問題がある。
どれに値するかは、
理論的に解けるのか、
計算量がどうかによって変わる。
計算量が多くても量子計算によって解くことができる問題もある。
理解できましたか？