情報科学部Faculty of Computer and Information Sciences
PRI110KA-CS-104e（情報学基礎 / Principles of informatics 100）離散構造2演習Discrete Structures 2 Lab
李 亜民
授業コードなどClass code etc
| 学部・研究科Faculty/Graduate school | 情報科学部Faculty of Computer and Information Sciences |
| 添付ファイル名Attached documents | |
| 年度Year | 2022 |
| 授業コードClass code | J0417 |
| 旧授業コードPrevious Class code | |
| 旧科目名Previous Class title | |
| 開講時期Term | 秋学期授業/Fall |
| 曜日・時限Day/Period | 水3/Wed.3 |
| 科目種別Class Type | |
| キャンパスCampus | 小金井 / Koganei |
| 教室名称Classroom name | 各学部・研究科等の時間割等で確認 |
| 配当年次Grade | |
| 単位数Credit(s) | 1 |
| 備考（履修条件等）Notes | |
| 他学部公開科目Open Program | |
| 他学部公開（履修条件等）Open Program (Notes) | |
| グローバル・オープン科目Global Open Program | |
| 成績優秀者の他学部科目履修制度対象Interdepartmental class taking system for Academic Achievers | |
| 成績優秀者の他学部科目履修（履修条件等）Interdepartmental class taking system for Academic Achievers (Notes) | |
| 実務経験のある教員による授業科目Class taught by instructors with practical experience | |
| SDGsCPSDGs CP | |
| アーバンデザインCPUrban Design CP | |
| ダイバーシティCPDiversity CP | |
| 未来教室CPLearning for the Future CP | |
| カーボンニュートラルCPCarbon Neutral CP | |
| 千代田コンソ単位互換提供（他大学向け）Chiyoda Campus Consortium | |
| 選択・必修Optional/Compulsory | |
| カテゴリー（2022年度以降入学者）Category (2022~) | |
| カテゴリー（2021年度以前入学者）Category (~2021) | |
| カテゴリーCategory |
専門教育科目 専門科目 |
すべて開くShow all
すべて閉じるHide All
Outline (in English)
In this course, you will learn basic concepts of graph theory and logic which are fundamental items to study computer science. Students will be expected to study the topic given in the class around one hour in each week. Your overall grade in the class will be decided based on the following: short reports: 80%, in class contribution: 20%
授業で使用する言語Default language used in class
日本語 / Japanese
授業の概要と目的（何を学ぶか）Outline and objectives
離散構造2で学ぶ構造のうち，特に重要な「グラフ」「論理学」の基本概念の理解を深める．
到達目標Goal
グラフ、論理学の基本を理解する．特に記号，式，図表の扱いに慣れる．現実問題の抽象化・一般化という考え方を身につけるとともに，プログラミングとの関わりを理解する．
この授業を履修することで学部等のディプロマポリシーに示されたどの能力を習得することができるか（該当授業科目と学位授与方針に明示された学習成果との関連）Which item of the diploma policy will be obtained by taking this class?
ディプロマポリシーのうち「DP2」と「DP3-1」に関連
授業で使用する言語Default language used in class
日本語 / Japanese
授業の進め方と方法Method(s)（学期の途中で変更になる場合には、別途提示します。 /If the Method(s) is changed, we will announce the details of any changes. ）
本講義は演習問題の学習を通して離散構造2で学ぶグラフの基礎概念，命題論理，述語論理，証明法など情報科学の数学的ツールの導入部について学ぶ．講義は主に「離散構造2」の授業に対応した演習問題およびその解説で構成される．授業で課した課題(小テストやレポート)等を取り上げ、授業内で全体に対してフィードバックを行う。
アクティブラーニング（グループディスカッション、ディベート等）の実施Active learning in class (Group discussion, Debate.etc.)
あり / Yes
フィールドワーク（学外での実習等）の実施Fieldwork in class
なし / No
授業計画Schedule
授業形態/methods of teaching：対面/face to face
※各回の授業形態は予定です。教員の指示に従ってください。
第1回[対面/face to face]：グラフ(1)
グラフの基礎概念(1)
第2回[対面/face to face]：グラフ(2)
グラフの基礎概念(2)
第3回[対面/face to face]：グラフ(3)
オイラー路、ハミルトン路、閉路
第4回[対面/face to face]：グラフ(4)
木、木の探索(1)
第5回[対面/face to face]：グラフ(5)
木、木の探索(2)
第6回[対面/face to face]：グラフ(6)
オートマトン
第7回[対面/face to face]：命題論理(1)
命題、命題論理、論理式、真理値、真理値表
第8回[対面/face to face]：命題論理(2)
恒真命題、恒真式、矛盾命題、矛盾式
第9回[対面/face to face]：命題論理(3)
含意、必要条件、十分条件
第10回[対面/face to face]：述語論理(1)
述語論理の構文論
第11回[対面/face to face]：述語論理(2)
述語論理の意味論、恒真、充足可能、充足不可能
第12回[対面/face to face]：証明法(1)
証明法、構成的証明、直接証明、反例、対偶法
第13回[対面/face to face]：証明法(2)
場合分け、背理法、数学的帰納法、鳩の巣原理
第14回[対面/face to face]：総括
グラフ、論理学のまとめ
授業時間外の学習（準備学習・復習・宿題等）Work to be done outside of class (preparation, etc.)
授業で出題する演習課題に取り組むこと．
本授業の準備・復習時間は、計1時間を標準とする．
テキスト（教科書）Textbooks
S. Lipschutz著，成嶋弘監訳：マグロウヒル大学演習「離散数学－コンピュータサイエンスの基礎数学－」，オーム社，1995年．(注：離散構造1の教科書）
参考書References
C. L. Liu著，成嶋弘／秋山仁共訳：「コンピュータサイエンスのための離散数学入門」，オーム社
成績評価の方法と基準Grading criteria
本授業の成績評価はP/F評価である．
演習問題の解答を説明するなどの授業への積極的な取り組み20%および、演習課題の達成度80%で評価する．
学生の意見等からの気づきChanges following student comments
質問および演習問題解説の時間を増やす
学生が準備すべき機器他Equipment student needs to prepare
貸与パソコン