2026年06月30日 第4回
判定問題について、
第2回から扱ってきた内容と記憶しています。
longerThan1Kなど、
一般的な計算問題に比べて正直回りくどさを感じていましたが、
このような判定問題が計算理論の証明に有効であると理解しました。
また、
このような証明を行う際、
判定問題を用いるとエレガントに証明ができると講義で説明されていましたが、
ここで言われるエレガントとはどういう意味なのか、
またエレガントでない証明について質問したいと思いました。
簡潔に綺麗に証明を示せるということですね．
文字列についての学習をしたのは二年前なので、
今回の授業を通して復習ができた。
また、
新しく学ぶこともあり、
理解が深まった。
経路問題などに関しては、
いままでに一通り学習したが、
その時とは違う授業展開であったため、
自分が知っているものとは違うアプローチ?が出来て、
より一層詳しくなれた。
理解できたようで良かったと思います．
グラフや木、 アルファベット、 文字列、 言語がそれぞれ何であるかと、 それらに対する操作や表し方が理解できました。 また、 計算問題の定義として、 探索問題、 最適化問題、 しきい値問題、 関数問題、 判定問題について理解できました。 さらに、 一般的な計算問題と判定問題の利点・欠点について理解できました。
よろしいと思います．
今回の講義では、 プログラムが解くべき「計算問題」の形式的な定義から、 形式言語、 そして問題のクラス分けに至るまで、 計算理論の基礎となる考え方を学びました。 特に印象に残ったのは、 計算問題の分類です。 単に「どんな入力に対しても正しく動くプログラム」を作ることを目指すだけでなく、 直面している問題が理論的にどの分類に属し、 本質的に解くことが可能な問題なのかを見極める力を養っていきたいなと思いました。
色々と考えてくれていますね．
今回の講義では、 言語には「人間が話す言語」、 「プログラミング言語」、 「計算論における形式言語」の3種類あることが特に印象に残った。
混乱しやすいところですね．
計算問題が入力と出力のペアとして厳密に形式化されている点や、 具体的なPythonのコードを通して判定問題との違いが解説されている部分は、 理論と実装の繋がりが明確でよく理解できました。 一方で、 『IsMember_L問題』における言語Lの具体的な定義など、 前提となる知識についてこの資料のみでは理解しきれない部分もありました。 また疑問点として『CrashOnString問題』の解の条件が直前の問題と同じになっており誤植ではないかと感じた点や、 リスト27のコードのコメント内に意図しない記号（\str）が混ざっている点が気になりました。
まだ，IsMember_L問題もCrashOnString問題も話していませんでしたが，
CrashOnString問題については資料が間違っています．
次回訂正して配布します．
リスト27のコメント文については< とか，<=という文字列という意味ですね．
判定問題は第一回の課題で説明した判定プログラムと同じような定義だと分かった。
理解できましたか．
今日の授業で最も興味深いと思った話は言語です。 普段私たちが扱っている言語(自然言語)とプログラミング言語の他に計算論における形式言語というものが存在することを初めて知りました。 またそこで疑問点が生じました。 (崩れていない)自然言語やプログラミング言語は文型(文法)というものが存在していて、 それらの言語はある意味で状態遷移図で記述できる(パターンが存在する)のですが、 計算論における形式言語にも文型(文法)のようなものは存在しているのかという疑問です。
とても良いコメントですね．次回触れましょう．
これらの問題の間にある計算量的な本質的な違いについて疑問に思いました。 特に、 FINDPATHとHASPATHのように一見すると情報量が異なる問題でも、 理論的には多項式時間で相互変換できるのか、 または本質的に計算複雑性が異なるのかが気になりました。
これらは同じですね．
本日の講義では、
計算問題を形式的に考えるために、
グラフ、
アルファベット、
文字列、
言語について学んだ。
特に、
言語を「文字列の集合」として考えるところが印象に残った。
空文字列と空言語は似ているように見えるが、
意味が違うことも理解できた。
後半の探索問題、
最適化問題、
しきい値問題、
関数問題、
判定問題の違いは、
例を見ると少し分かりやすかった。
特に判定問題は答えが yes/no だけなので、
理論的な証明には使いやすいが、
実際のアプリケーションでは計算問題の方が使われやすいという点が分かった。
まだ、
普通の計算問題をどのように判定問題に変換して考えるのかは少し難しいと感じた。
難しかったですか．不明なところは質問してください．
最も理解できたのは、
計算問題が結局のところ文字列を文字列の集合へ写す関数として捉えられる、
という点です。
ソートワーズの例で、
同じ問題に対して正しい実装が複数あり得る一方、
brokenSortのように一部の入力でのみ破綻するものは問題を解いたとは言えない、
という説明には納得しました。
どのような入力に対しても常に正しく動作しなければ解いたことにならない、
というのは当然のようでいて重要な点だと感じました。
また、
言語に日常言語・プログラミング言語・形式言語の3つの意味があり、
形式言語はアルファベットから構成される文字列の集合であって、
英語として意味をなすかどうかは無関係である、
という整理は理解の助けになりました。
空言語と、
空文字列のみを要素とする{ε}が別物であるという点は、
少し混乱しましたが理解できました。
確かに混乱しますね．でも理解できたようで良かったと思います．
通常の計算問題と、 判定問題バージョンの入力・出力の違いと、 それぞれの利点・欠点を理解できた。 どんな場合にどちらを使うのが最適であるか、 自分で例を考ることでより理解を深めたい。
理解できたのであれば，良かったと思います．