  シラバス参照
|
| 科目一覧へ戻る | 2019/08/20 現在 |
| 科目名（和文） ／Course |
離散数学 |
|---|---|
| 科目名（英文） ／Course |
Discrete Mathematics |
| 時間割コード ／Registration Code |
23180701 |
| 学部（研究科） ／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/31 |
|---|---|
| 使用言語 ／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 | [まとめ] 講義全体の概略をまとめる. |
| No. |
到達目標 ／Learning Goal |
知識?理解 ／Knowledge & Undestanding |
技能?表現 ／Skills & Expressions |
思考?判断 ／Thoughts & Decisions |
伝達?コミュニケーション ／Communication |
協働 ／Cooperative Attitude |
||
|---|---|---|---|---|---|---|---|---|
| 1 | 集合について理解する. | ○ | ○ | ○ | ||||
| 2 | 命題論理と述語論理を理解する. | ○ | ○ | ○ | ○ | |||
| 3 | グラフ理論の概要について知る. | ○ | ○ | |||||
| 4 | 計算モデルとしてのオートマトンと, 形式言語理論について理解する. | ○ | ○ | ○ | ○ |
| No. |
到達目標 ／Learning Goal |
定期試験 ／Exam. |
中間レポート1 | 中間レポート2 | |||
|---|---|---|---|---|---|---|---|
| 1 | 集合について理解する. | ○ | ○ | ||||
| 2 | 命題論理と述語論理を理解する. | ○ | ○ | ||||
| 3 | グラフ理論の概要について知る. | ○ | ○ | ||||
| 4 | 計算モデルとしてのオートマトンと, 形式言語理論について理解する. | ○ | |||||
|
評価割合（％） ／Allocation of Marks |
70 | 15 | 15 | ||||