担当別５０音一覧 担当別５０音一覧
計算とアルゴリズム理論

科 目
計算とアルゴリズム理論
区 分
情報通信工学科選択科目群
授業番号
3580
開設セメスター
6S
曜日・時限
金/12
単位数
2単位
担当者名
小林　由紀男
授業の概要
        計算とはなにか，特に機械で行う計算とは，あるいは人間にできる計算とはなにか
        について考える．また，計算の手順を記述するアルゴリズムの基礎的な理論を理解
        し，プログラムとコンピュータで計算できる問題の範囲について検討する．本授業
        は，実際に問題を解くための方法についての勉強ではなく，本質的な問題である「
        理論的に計算可能である」または「実際に計算可能である」問題とはなにかについ
        て，より深く学習することを目指している．
授業計画
テーマ
内 容
第1回目
        計算とはなにか
                  人間のできる計算とできない計算，数えることか
第2回目
        計算とはなにか
                  計算する機械(抽象的計算機械)
第3回目
        計算のモデルとオートマトン
                  計算のモデルとチューリング機械
第4回目
        計算のモデルとオートマトン
                  抽象的計算機械(オートマトン)で計算する
第5回目
        計算のモデルとオートマトン
                  計算手順の記述とアルゴリズム
第6回目
        計算できる関数(問題)と

        計算できない関数(問題)
                  計算可能な関数(計算可能性，帰納的関数,...)
第7回目
        計算できる関数(問題)と

        計算できない関数(問題)
                  解くことのできる問題と解くことのできない問題がある
第8回目
        計算と言語

        (プログラミング言語へ)
                  形式言語とオートマトン
第9回目
        計算と言語

        (プログラミング言語へ)
                  文脈自由型文法とプッシュダウン・オートマトン
第10回目
        計算の量とアルゴリズム

        (問題)の複雑さ
                  計算の複雑さ(問題の難しさ)とは何か
第11回目
        計算の量とアルゴリズム

        (問題)の複雑さ
                  複雑さ(計算時間の評価)による問題の分類
第12回目
        計算の量とアルゴリズム

        (問題)の複雑さ
                  理論的に計算可能と実際的に計算可能
第13回目
        アルゴリズムとは
                  アルゴリズムとプログラム
第14回目
        アルゴリズムとは
                  プログラムとデータの構造
第15回目
        アルゴリズムとは
                  プログラムの正当性検証

使用テキスト
・計算機科学の基礎／米田 政明／森北出版／２，６００円

        ・授業時に随時プリント配布
参考文献
・アルゴリズムと計算理論／足立 暁生／森北出版／２２００円
成績評価方法
・試験／レポート／出席を考慮して評価する．
履修条件等
・ソフトウェアの数理を必要とする理工系の学生を対象に考えています．

        ・集合・整数に関する初歩的な知識を必要とします．

担当別５０音一覧