科目名 計算論
単位数 2.0
担当者 知能工学専攻 准教授 内田 智之
知能工学専攻 准教授 宮原 哲浩
履修時期 前期
履修対象 3年次
概要 計算の原理、コンピュータによる計算の本質を理解した後、一般的なアルゴリズム設計技法を学ぶことで、問題に対し既知の技法を活用した効率のよいアルゴリズムを設計するための基礎学力を習得する。さらに、計算可能性理論や計算量理論の基本を理解し、実時間では解くことが難しい問題に対する近似アルゴリズムやヒューリスティックを概観することで、アルゴリズム設計技能を身に付ける。講義の授業形態で行う。
科目の到達目標 計算可能性と計算量に関する基礎理論を学ぶことで、自分の考えや主張を他者に論理的に伝える表現力、アルゴリズム設計能力およびソフトウェアを創造していく力を身に付ける。合わせて、論理的思考力と論理的表現力を身に付ける。
受講要件 特になし。
事前・事後学修の内容 事前・事後学修のための講義資料を適宜配布する。参考書やインターネットを活用して講義内容に関する情報を積極的に収集することで事前学修を行い、講義ノートおよび講義資料の整理を通して事後学修を行う。
講義内容 1  計算論入門(前半担当者:准教授 宮原)
2  原理的な計算可能性
3  計算可能性理論入門
4  計算機械
5  Turing機械
6  万能Turing機械
7  停止問題の決定不能性
8  アルゴリズムとは(後半担当者:准教授 内田)
9  アルゴリズム設計と解析の基礎
10 探索アルゴリズム[探索問題]
11 整列アルゴリズム[整列問題]
12 グラフアルゴリズム[最短路問題]
13 アルゴリズムの設計手法[分割統治法と動的計画法]
14 アルゴリズムの設計手法[貪欲アルゴリズムと線形計画法]
15 アルゴリズムの設計手法[近似アルゴリズムとヒューリスティック]
評価方法 定期試験と平常点を用いて総合的に評価する。定期試験により、講義内容の理解度を評価する。
さらに、課題の完成度および受講態度などの平常点により、表現力やアルゴリズム設計技能の有無を評価する。
教科書等 参考書:
有川節夫、宮野悟著「オートマトンと計算可能性」(培風館)
浅野哲夫・和田幸一・増澤利光 共著 「アルゴリズム論」(オーム社)
R. セジウィック著 野下浩平・星守・佐藤創・田口東 共訳 「アルゴリズム」(近代科学社)
T. Cormen, C. E. Leiserson and R. L. Rivest "Introduction to Algorithms" (The MIT Press)
(浅野哲夫・岩野和生・梅尾博司・山下雅史・和田幸一共訳 「アルゴリズム イントロダクション」(近代科学社))
広瀬貞樹著 「あるごりずむ」(近代科学社)
杉原厚吉・茨木俊秀・浅野孝夫・山下雅史 「アルゴリズム工学 -計算困難問題への挑戦-」(共立出版)
担当者プロフィール 内田 智之:グラフアルゴリズムと機械学習に基づくデータマイニング手法に関する研究に従事。
宮原 哲浩:機械学習とデータマイニングに関する研究に従事。
講義内容・課題等に関する個別学習相談は随時受け付けています。
備考 【教職】高一種(数学)の選択科目です。コンピュータで計算すること・解析学及び幾何学の応用等についての教育の方法及び技術の習得を目指します。