シラバス参照

授業情報／Course information

科目一覧へ戻る 2019/08/20 現在

授業基本情報
科目名（和文）
／Course		 離散数学
科目名（英文）
／Course		 Discrete Mathematics
時間割コード
／Registration Code		 21140301
学部（研究科）
／Faculty		 情報工学部
学科（専攻）
／Department		 情報通信工学科
担当教員（○：代表教員）
／Principle Instructor （○） and Instructors		 ○小野　孝男
オフィスアワー
／Office Hour		 小野　孝男(火曜日 ５限)
開講年度
／Year of the Course		 2017年度
開講期間
／Term		 後期
対象学生
／Eligible Students		 1年
単位数
／Credits		 2.0
授業概要情報
更新日
／Date of renewal		 2017/03/30
使用言語
／Language of Instruction		 日本語
オムニバス
／Omnibus		 該当なし
授業概略と目的
／Cource Description and Objectives		 コンピューターは「離散的なもの」しか扱うことができない.したがって, 「離散的なもの」を数学的に扱う「離散数学」はコンピューターサイエンスにおける基本的な分野ということができる.
そこで本講義ではまず基本的な数学的概念として集合と数理論理学を紹介する. 次に, 応用上非常に重要なモデルであるグラフについて紹介する. 最後に, コンピュータープログラムの根底にある「計算」の基本的な概念として, オートマトンと形式言語理論について学ぶことを目的とする.
履修に必要な知識・能力・キーワード
／Prerequisites and Keywords		 離散数学は「数学」とついているが高校までの数学からは離れている点も多い. しかし, 基本的な分野であるため「定義をきちんと理解する」ことは非常に大切である. 定義の文章を「そのまま」理解することを忘れないようにしてほしい.

キーワード: 集合, 命題論理, グラフ, 計算理論, 形式言語理論
履修上の注意
／Notes		 離散数学はコンピューターサイエンスにおいて基本的というだけでなく, 数学そのものの根幹を含んだ分野である. したがって, あやふやな理解のままでは先に進めなくなってしまうこともある. 困ったときには「自分が何を理解できていないのか」を振り返り, きちんと理解することが必要である.
教科書
／Textbook(s)		 柴田正憲, 浅田由良, 「情報科学のための離散数学」, コロナ社
参考文献等
／References
自主学習ガイド
／Expected Study Guide outside Coursework/Self-Directed Learning Other Than Coursework		 予習として, 事前に教科書の該当部分を確認しておくことが望ましい. また, これまでの「数学」とは異なる部分もあるので教科書の問題を自分で解くことによって理解を深めてほしい.
資格等に関する事項
／Attention Relating to Professional License
備考
／Notes
授業計画詳細情報
No. 単元（授業回数）
／Unit (Lesson Number)		 単元タイトルと概要
／Unit Title and Unit Description		 時間外学習
／Preparation and Review		 配布資料
／Handouts
1 1 [集合]
講義全体について概要を説明する. また, 集合の記法と基本的な演算について確認する.
2 2 [関係]
集合を用いて「関係」を定義し, その性質を知る. 特殊な関係である順序関係と同値関係について理解する.
3 3 [関数]
関係を用いて形式的に関数を定義し, 単射・全射・全単射といった性質と逆関数について学ぶ.
4 4 [命題論理]
基礎的な論理としての命題論理を理解する.
5 5 [述語論理]
命題論理がきわめて記号的であって日常的な表現すら扱えないことを理解し,命題論理の発展である述語論理について理解する.
6 6 [ブール代数]
集合と命題論理との間には類似点が多い. そこで, 似たところを抽出して「ブール代数」として抽象化できることを知る.
7 7 [論理回路]
命題論理の応用として, コンピューターのハードウェアにあたる論理回路の概要を学ぶ.
8 8 [グラフ理論]
複数の「もの」の関係を表す概念である「グラフ」の基本事項を学ぶ.
9 9 [いろいろなグラフ]
理論的に, また現実的な場面であらわれる特徴的なグラフを紹介する.
10 10 [木]
非常に特殊かつ重要なグラフである木について学ぶ. また, グラフに対する操作の 1つとしてすべての頂点を列挙する方法を紹介する.
11 11 [有向グラフとネットワーク]
応用で現れるグラフの中には辺に向きが存在する有向グラフも多い. さらに, グラフの応用であるネットワークについても簡単に学ぶ.
12 12 [チューリング機械]
「計算」を数学的に扱うモデルの 1つであるチューリング機械を学び, その性質から「アルゴリズムが設計できない問題」が存在することを理解する.
13 13 [有限オートマトンと正規表現]
チューリング機械を簡素化した有限オートマトンと, それに対応する正規言語・正規表現を学ぶ.
14 14 [文脈自由文法とプッシュダウンオートマトン]
プログラミング言語の多くで採用されている文脈自由文法について理解し, プッシュダウンオートマトンを知る.
15 15 [まとめ]
講義全体の概略をまとめる.
授業評価詳細情報
到達目標及び観点／Learning Goal and Specific Behavioral Viewpoints
No. 到達目標
／Learning Goal		 知識・理解
／Knowledge & Undestanding		 技能・表現
／Skills & Expressions		 思考・判断
／Thoughts & Decisions		 伝達・コミュニケーション
／Communication		 協働
／Cooperative Attitude
1 集合について理解する. ○ ○ ○
2 命題論理と述語論理を理解する. ○ ○ ○ ○
3 グラフ理論の概要について知る. ○ ○
4 計算モデルとしてのオートマトンと, 形式言語理論について理解する. ○ ○ ○ ○
成績評価方法と基準／Evaluation of Achievement
※出席は2/3以上で評価対象となります。
No. 到達目標
／Learning Goal		 定期試験
／Exam.		 中間レポート1 中間レポート2
1 集合について理解する. ○ ○
2 命題論理と述語論理を理解する. ○ ○
3 グラフ理論の概要について知る. ○ ○
4 計算モデルとしてのオートマトンと, 形式言語理論について理解する. ○
評価割合（％）
／Allocation of Marks		 70 15 15

科目一覧へ戻る