三重大学ウェブシラバス


シラバス表示

 シラバスの詳細な内容を表示します。

→ シラバスの一覧にもどる

科目の基本情報

開講年度 2017 年度
開講区分 工学部情報工学科 ・専門教育
受講対象学生 学部(学士課程) : 3年次
選択・必修 選択
選択科目
授業科目名 計算理論
けいさんりろん
Theory of Computation
単位数 2 単位
他学部・他研究科からの受講
市民開放授業 市民開放授業ではない
開講学期

前期

開講時間 金曜日 5, 6, 7, 8時限
開講日は掲示等で指定
開講場所

担当教員 笠井琢美

KASAI, Takumi

学習の目的と方法

授業の概要 本講義では、計算の理論および最近発展が著しい計算量の理論を講義する。計算の理論は、帰納的関数の理論とも呼ばれることもあるが、計算(アルゴリズム)を直接対象とした理論である。ここでは、そもそも計算とは何か、計算できないとは何を意味するのかを解説する。また、可算、帰納的可算などの基本概念や、万能関数の存在などについて解説し、具体的な計算できない問題について述べる。計算について議論するには、計算を実行する媒体である計算機モデルが必要である。本講義では、現在の計算機の忠実なモデルであるランダム・アクセス機械とそのプログラミング言語である whileプログラムを計算機モデルとして用いる。しかし、計算不能な問題は、これらの計算モデルには依存しないことも議論する。
計算の理論では、単にアルゴリズムが存在するかどうかを議論するだけで、そのアルゴリズムの効率については考慮しない。これに対し、計算量の理論では、計算に必要な時間や領域を理論の対象とする。ここでは、非決定性アルゴリズムや、多項式時間計算可能性といった基本的な事項に付いて解説する。また、NP完全問題についても述べる。さらに、現在なぜNP完全問題が実際的な時間では計算できないと見なされているかについて議論する。
学習の目的
学習の到達目標
ディプロマ・ポリシー
○ 学科・コース等の教育目標
○ JABEE 関連項目

○ 全学の教育目標
感じる力
  •  感性
  •  共感
  •  倫理観
  •  モチベーション
  • ○主体的学習力
  •  心身の健康に対する意識
考える力
  •  幅広い教養
  • ○専門知識・技術
  • ○論理的思考力
  •  課題探求力
  • ○問題解決力
  •  批判的思考力
コミュニケーション力
  •  情報受発信力
  •  討論・対話力
  •  指導力・協調性
  •  社会人としての態度
  •  実践外国語力
生きる力
  •  感じる力、考える力、コミュニケーション力を総合した力

授業の方法 講義

授業の特徴

教科書 特になし
参考書 参考書:計算の理論(笠井琢美、戸田誠之助著、共立出版)
成績評価方法と基準 基本的に定期試験で評価する。しかし、2講義に1回程度、演習問題を解いてもらったり、小テストを行っている。定期試験の成績不振者にはこの小テストの点を加味している。
オフィスアワー 電子メールによる受け付け可。
受講要件
予め履修が望ましい科目 オートマトン・形式言語理論。講義では、計算機科学一般で必要とされるごく基本的な概念や、離散数学の基本概念を用いるが、講義の中で基本概念はすべて解説するので、この講義のための前知識は何も仮定していない。
発展科目
授業改善への工夫 従来の計算の理論は、Turing機械と呼ばれる計算モデルを基礎にしており、この機械を習得するのに、授業の大半の時間を必要とした。この講義で用いるwhile プログラムは、現実のプログラミング言語とほとんど同じもので、習得にほとんど時間を要しない。また、講義の間にたびたび学生諸君に演習問題を解く時間を設けている。
その他

授業計画

キーワード
Key Word(s)
学習内容 第1回 while プログラム
第2回 基本プログラミング:基本的な関数、条件文、手続きの処理
第3回 対象の算術化(コード化)、配列の処理
第4回 チャーチの定立
第5回 ランダム・アクセス機械
第6回 万能プログラムと万能関数
第7回 計算可能性の基本定理
第8回 可算と帰納的可算
第9回 計算不能性
第10回 計算不能な具体的な問題:語の問題
第11回 実際的計算可能性: (多項式時間計算可能性)
第12回 非決定性アルゴリズム
第13回 NP完全問題とは
第14回 具体的なNP完全問題
第15回 まとめ
第16回 定期試験
学習課題(予習・復習)
ナンバリングコード(試行) EN-CMPS-3

※最初の2文字は開講主体、続く4文字は分野、最後の数字は開講レベルを表します。 ナンバリングコード一覧表はこちら


Copyright (c) Mie University