情報科学研究科Graduate School of Computer and Information Sciences
PRI500K1（情報学基礎 / Principles of informatics 500）計算機科学のための数学Concrete Mathematics
首藤 裕一
授業コードなどClass code etc
| 学部・研究科Faculty/Graduate school | 情報科学研究科Graduate School of Computer and Information Sciences |
| 添付ファイル名Attached documents | |
| 年度Year | 2022 |
| 授業コードClass code | TZ054 |
| 旧授業コードPrevious Class code | |
| 旧科目名Previous Class title | |
| 開講時期Term | 秋学期授業/Fall |
| 曜日・時限Day/Period | 木5/Thu.5 |
| 科目種別Class Type | |
| キャンパスCampus | 小金井 |
| 教室名称Classroom name | 各学部・研究科等の時間割等で確認 |
| 配当年次Grade | |
| 単位数Credit(s) | 2 |
| 備考（履修条件等）Notes | |
| 実務経験のある教員による授業科目Class taught by instructors with practical experience | |
| カテゴリーCategory |
すべて開くShow all
すべて閉じるHide All
Outline (in English)
This course deals with discrete mathematics and probability theory. Students will be expected to study the topic given in the class around four hours in each week. Your overall grade in the class will be decided based on the following:
final report: 60%, in class contribution: 40%
授業で使用する言語Default language used in class
日本語 / Japanese
授業の概要と目的（何を学ぶか）Outline and objectives
計算機科学分野の研究・学習にとって基本的な高等数学を身に着けておくことは極めて重要である。本授業は、数学の中でも特に計算機科学との関連が高い、離散数学および確率論について高度な内容を理解し、さらに自身で活用できるようになることを目指す。
到達目標Goal
・形式的な定義や厳密に表記された命題を理解できるようになる
・離散数学のいくつかの分野に深く親しみ、理解する。
・確率論のいくつかの分野に深く親しみ、理解する。
・数学的な思考力を身に着け、ある程度高度な証明を自分で書けるようになる。
この授業を履修することで学部等のディプロマポリシーに示されたどの能力を習得することができるか（該当授業科目と学位授与方針に明示された学習成果との関連）Which item of the diploma policy will be obtained by taking this class?
ディプロマポリシーのうち、「DP1」と「DP2」に関連
授業で使用する言語Default language used in class
日本語 / Japanese
授業の進め方と方法Method(s)（学期の途中で変更になる場合には、別途提示します。 /If the Method(s) is changed, we will announce the details of any changes. ）
扱う範囲を離散数学および確率論に絞り、「広く浅く」ではなく、「狭く深い」授業を行う。さらには、体系的かつ普遍的な内容を扱うのではなく、数学的魅力の高いトピックをいくつか厳選し、狭い範囲を、楽しみながら時間をかけて理解してもらう。内容そのものよりも、数学的な思考方法を身につけることに主眼をおく。教員から受講者への一方向的な講義ではなく、適宜グループワークなども交えた全員参加型の授業形態とする。
具体的には、講義40%、グループワーク60%の割合で授業を進める。個々のトピックに関する基本的な考え方や解法を講義で習得し、その理解度をグループワーク演習で確認することを繰り返す。
アクティブラーニング（グループディスカッション、ディベート等）の実施Active learning in class (Group discussion, Debate.etc.)
あり / Yes
フィールドワーク（学外での実習等）の実施Fieldwork in class
なし / No
授業計画Schedule
授業形態/methods of teaching：対面/face to face
※各回の授業形態は予定です。教員の指示に従ってください。
1[対面/face to face]：オリエンテーション
オリエンテーションおよび集合と命題に関する復習
2[対面/face to face]：漸化式（前半）
漸化式の解法を学ぶ。
3[対面/face to face]：漸化式（後半）
漸化式の解法を学ぶ。
4[対面/face to face]：整数論（前半）
整数論を学ぶ。
5[対面/face to face]：整数論（後半）
整数論を学ぶ。
6[対面/face to face]：特別な数（前半）
特別な数について学ぶ。
7[対面/face to face]：特別な数（後半）
特別な数について学ぶ。
8[対面/face to face]：離散数学の振り返り
これまでに習得した離散数学の内容を振り返る。
9[対面/face to face]：事象と確率
事象と確率に関する概念および定義を学ぶ。
10[対面/face to face]：確率変数と期待値。
確率変数と期待値について学ぶ。
11[対面/face to face]：積率と偏差
積率と偏差について学ぶ。
12[対面/face to face]：Chernoff上界
Chernoff上界について学ぶ。
13[対面/face to face]：マルコフ連鎖
マルコフ連鎖について学ぶ。
14[対面/face to face]：確率論の振り返り
これまでに習得した確率論の内容を振り返る。
授業時間外の学習（準備学習・復習・宿題等）Work to be done outside of class (preparation, etc.)
大学院の授業なので、頻繁に課題を出すことはしない。各自、毎回の授業後に理解が不十分な箇所をしっかりと理解すること。学期末に一度だけ、総合的な理解度を確認するための最終レポートを課す。
テキスト（教科書）Textbooks
授業内で配布。
参考書References
Ronald L.Graham（著），Donald E.Knuth（著），Oren Patashnik（著），有澤 誠（訳），安村 通晃（訳），萩野 達也（訳），石畑 清（訳）：コンピュータの数学 第2版，共立出版（2020）
Michael Mitzenmacher（著），Eli Upfal（著），小柴 健史（訳），河内 亮周（訳）：確率と計算，共立出版（2009）
成績評価の方法と基準Grading criteria
最終レポート60%、授業への貢献度などを鑑みた平常点40%。
学生の意見等からの気づきChanges following student comments
令和4年度から新規に立ち上げる授業であり、学生からのアンケートがまだない。
学生が準備すべき機器他Equipment student needs to prepare
講義資料を参照するために貸与パソコンを利用。
その他の重要事項Others
緊急事態宣言発出など真にやむを得ない事情が発生しない限り完全対面で授業を実施する。