日々精進

新しく学んだことを書き留めていきます

The Art of Computer Programming第一章

1.1アルゴリズム
アルゴリズムの5つの特徴:有限性・明確性・入力・出力・実効性
計算方法は集合論によって厳密に定義できる。(イメージ的にはある初期値を出発点として計算を繰り返す度に解空間に近付いていき、解空間に到達した時点で計算が終了する、という感じ?)


1.2数学的な基礎
1.2.1数学的帰納法
アルゴリズムの正しさを証明するにはアルゴリズムの各操作の前後で成り立つ「表明」を見つければいい。(表明=Bertrand Meyerのいう「契約」)
アルゴリズムを理解するには適当なインプットを与えて机上実行してみること。