情報科学部Faculty of Computer and Information Sciences
PRI110KA-CS-104（情報学基礎 / Principles of informatics 100）離散構造2（再）Discrete Structures 2
佐々木 晃Akira SASAKI
授業コードなどClass code etc
| 学部・研究科Faculty/Graduate school | 情報科学部Faculty of Computer and Information Sciences |
| 添付ファイル名Attached documents | |
| 年度Year | 2024 |
| 授業コードClass code | J0411-R |
| 旧授業コードPrevious Class code | |
| 旧科目名Previous Class title | |
| 開講時期Term | 秋学期授業/Fall |
| 曜日・時限Day/Period | 月2/Mon.2 |
| 科目種別Class Type | |
| キャンパスCampus | 小金井 / Koganei |
| 教室名称Classroom name | 各学部・研究科等の時間割等で確認 |
| 配当年次Grade | 1～4 |
| 単位数Credit(s) | 2 |
| 備考（履修条件等）Notes | ABクラス（※学び直し科目。受講方法は履修ガイド参照。） |
| 他学部公開科目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, students will learn basic concepts of graph theory and logic.
・At the end of the course, you are expected to understand basic concepts of graph theory and logic, and get accustomed to handle symbols, expressions and diagrams that are essential in those concepts.
・Before each class meeting, students will be expected to solve exercises assigned as homework. Your required study time is
at least four hours for each class meeting.
・Grading will be decided based on mid-term and term-end examinations (100%).
授業で使用する言語Default language used in class
日本語 / Japanese
授業の概要と目的（何を学ぶか）Outline and objectives
情報科学を裏打ちする離散的な構造のうち、特に重要な「グラフ」「論理学」の基本概念の理解を深める。
到達目標Goal
グラフ、論理学の基本を理解する。特に記号、式、図表の扱いに慣れる。現実問題の抽象化・一般化という考え方を身につけるとともに、プログラミングとの関わりを理解する。
授業で使用する言語Default language used in class
日本語 / Japanese
授業の進め方と方法Method(s)（学期の途中で変更になる場合には、別途提示します。 /If the Method(s) is changed, we will announce the details of any changes. ）
離散構造1の続きである。グラフの基礎概念、命題論理、述語論理、証明法など情報科学の数学的ツールの導入部について学ぶ。授業中に出題する例題、演習課題を通して、概念の理解を深める。課題等の提出は「CIS moodle」を通じて行う。授業中に課題に対するフィードバックを行う。
アクティブラーニング（グループディスカッション、ディベート等）の実施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)
命題、命題論理、論理式、真理値、真理値表
第2回[対面/face to face]：命題論理(2)
恒真命題、恒真式、矛盾命題、矛盾式
第3回[対面/face to face]：命題論理(3)
含意、必要条件、十分条件
第4回[対面/face to face]：述語論理(1)
述語論理の構文論
第5回[対面/face to face]：述語論理(2)
述語論理の意味論、恒真、充足可能、充足不可能
第6回[対面/face to face]：証明法(1)
証明法、構成的証明、直接証明、反例、対偶法
第7回[対面/face to face]：証明法(2)
場合分け、背理法、数学的帰納法、鳩の巣原理
第8回[対面/face to face]：グラフ(1)
グラフの基礎概念
第9回[対面/face to face]：グラフ(2)
オイラー路、ハミルトン路、閉路
第10回[対面/face to face]：グラフ(3)
平面的グラフ
第11回[対面/face to face]：グラフ(4)
木グラフ
第12回[対面/face to face]：グラフ(5)
有向グラフ
第13回[対面/face to face]：グラフ(6)
有限状態機械
第14回[対面/face to face]：総括
論理学、グラフのまとめ
授業時間外の学習（準備学習・復習・宿題等）Work to be done outside of class (preparation, etc.)
授業で出題する演習課題に取り組むこと。
本授業の準備・復習等の授業時間外学習は、各週につき4時間を標準とします。
テキスト（教科書）Textbooks
教員が配布するオンライン資料
参考書References
S. Lipschutz, M. Lipson著，渡邊均訳：マグロウヒル大学演習「離散数学－コンピュータサイエンスの基礎数学－(改訂2版)」，オーム社，2022年．
C. L. Liu著，成嶋弘／秋山仁共訳：「コンピュータサイエンスのための離散数学入門」，オーム社
成績評価の方法と基準Grading criteria
中間試験および定期試験による(100%)。ただし，平常授業における参加度を一部加味する．
学生の意見等からの気づきChanges following student comments
練習問題の解説の時間を増やす。
学生が準備すべき機器他Equipment student needs to prepare
貸与パソコン
その他の重要事項Others
ノートをとる．