科目名	計算論
単位数	2.0
担当者	知能工学専攻　教授　内田　智之（代表教員） 知能工学専攻　准教授　宮原　哲浩
履修時期	前期（第２ターム）
履修対象	３年次以上
講義形態	講義
講義の目的	計算の原理、コンピュータによる計算の本質を理解した後、アルゴリズム設計技法を学ぶことで、問題に対し既知の技法を活用した効率のよいアルゴリズムを設計するための基礎学力を習得する。さらに、計算可能性理論や計算量理論の基本を理解し、実時間では解くことが難しい問題に対する近似アルゴリズムやヒューリスティックを概観することで、アルゴリズム設計技能を身に付ける。
到達目標	計算可能性理論やアルゴリズム設計について理解し、問題解決のために必要となる基礎知識を修得する。【知識2、技能1】 問題解決のためのアルゴリズム設計およびソフトウェアを創造していくことができる。【思考力・判断力、表現力】 自分の考えや主張を他者に論理的に伝えることができる。【主体性、協働性】
受講要件	特になし。
履修取消の可否	可
履修取消不可の理由
事前・事後学修	適宜配布する講義資料を元に、参考書やインターネットを活用して講義内容に関する情報を積極的に収集する事前学修を行い、講義ノートおよび講義資料の整理を通して課題提出による事後学修を適宜行う(週９０分程度)。
講義内容	１　　計算論入門【前半担当者：宮原哲浩】 ２　　原理的な計算可能性 ３　　計算可能性理論入門 ４　　計算機械 ５　　Turing機械 ６　　万能Turing機械 ７　　停止問題の決定不能性 ８　　アルゴリズムとは【後半担当者：内田智之】 ９　　アルゴリズム設計と解析の基礎 １０　探索アルゴリズム[探索問題] １１　整列アルゴリズム[整列問題] １２　グラフアルゴリズム[最短路問題] １３　アルゴリズムの設計手法[分割統治法と動的計画法] １４　アルゴリズムの設計手法[貪欲アルゴリズムと線形計画法] １５　アルゴリズムの設計手法[近似アルゴリズムとヒューリスティック] ※授業の順序は変更することがある。 ※上記とは別に期末試験を実施する．
期末試験実施の有無	実施する
評価方法・基準	前半と後半での評価をもとに総合的に評価する。 前半は前半まとめとレポート等による評価(40%)と授業参加による平常点(10%)で評価する。 前半まとめ及びレポートでは主に講義内容の理解度と完成度、平常点では授業への積極的参加度に関して評価する。 後半は期末試験による評価(30%)と授業参加及び課題提出による平常点(20%)で評価する。 期末試験では主に講義内容の理解度とアルゴリズム設計技能の高さ、平常点では授業への積極的参加度、提出課題の完成度及び表現力に関して評価する。
教科書等	参考書： 有川節夫、宮野悟著「オートマトンと計算可能性」（培風館） 浅野哲夫・和田幸一・増澤利光 共著 「アルゴリズム論」（オーム社) R.　セジウィック著 野下浩平・星守・佐藤創・田口東　共訳 「アルゴリズム」（近代科学社） T. Cormen, C. E. Leiserson and R. L. Rivest "Introduction to Algorithms" (The MIT Press) (浅野哲夫・岩野和生・梅尾博司・山下雅史・和田幸一共訳　「アルゴリズム イントロダクション」(近代科学社)) 広瀬貞樹著 「あるごりずむ」（近代科学社) 杉原厚吉・茨木俊秀・浅野孝夫・山下雅史 「アルゴリズム工学　-計算困難問題への挑戦-」（共立出版)
担当者プロフィール	内田　智之：グラフアルゴリズムと機械学習に基づくデータマイニング手法に関する研究に従事。研究室：情報科学部棟別館5階 502研究室 宮原　哲浩：機械学習とデータマイニングに関する研究に従事。研究室：情報科学部棟別館5階 501研究室
講義に関連する実務経験
課題や試験に対するフィードバック	授業中に行う演習課題やレポート課題は、授業で模範解答を用いた解説を行う。 前期まとめ及び期末試験については、試験後にオフィスアワー等を通じて解答を用いた解説を行う。
アクティブ・ラーニング	TBL、振り返り
キーワード	計算可能性、Turing機械、探索・整列・グラフ・文字列検索アルゴリズム、アルゴリズム設計手法
備考	【教職】高一種(数学): コンピュータで計算すること・解析学及び幾何学の応用等についての教育の方法及び技術の習得を目指します。