情報基礎数理
情報工学科 選択 2単位 1年秋学期
【授業の目的】
コンピュータにおける処理の基本となる繰返し処理の形式的表現と計算手順について学習する.帰納は数学的帰納法で行われているように,再帰的に定義されたものを実際に計算するときに有効なものである.本講義ではこれらの基本概念について包括的な説明を行う.
【テキスト】 林晋,八杉満利子:「情報系の数学入門」,オーム社
【評価の方法】 期末テストを基本とするが,レポート提出状況にも配慮する
【授業計画】
再帰的構造とBNF 1.処理の手続き的表現
2.文の意味
処理の関数的表現 3.具体例による処理の表現
4.変数の有向範囲
5.文法
6.計算の木
計算可能性 7.再帰的関数
8.計算できない関数
帰納法
9.構造帰納法
10.ネーター帰納法
11.ネーター帰納法と構造帰納法
12.重みによる帰納法
13.計算帰納法
14.計算の停止性
15.期末試験
【備考】
選択科目ではあるが,情報処理の理論的基礎となる科目なので、できるだけ履修することを薦める.