計算量理論 10/1
眠くて寝てしまいました。来週以降出席するか分かりません。出席していればとりあえず単位を取るのは簡単ぽいけれど…。
計算の理論全体、情報科学の基礎のなかで どういう位置づけになっているか 量っていうのは所謂量 水かさが多いとか時間がかかる 概念的には理解しやすいと思う では計算とは何か 計算問題に対する操作 計算問題を理解することによって計算を理解する では計算問題とは何か 入力→□→出力 何を入力としてとって何を出力するのかが 誰にでも分かる形式で記述されたもの これが計算問題 ・かけ算 ・素因数分解問題 ・グラフ三色問題 この3つはそれぞれある種の問題を代表している 計算問題を理解したい 物事を理解するのによく採る手段はものを分類すること これを計算問題でも行う 全体 原理的に計算可能（計算のリソースはいくら使っても良い） 現実的に計算可能 現実的に計算不可能 原理的に計算不可能（それ以上もう手をつけようがない） われわれの力は、現実的に計算可能な問題だけに注げばいい
