情報科学部Faculty of Computer and Information Sciences
PRI210KA-CS-207(情報学基礎 / Principles of informatics 200)情報基礎学AFoundations of Computer Science A
尾花 賢Satoshi OBANA
授業コードなどClass code etc
学部・研究科Faculty/Graduate school | 情報科学部Faculty of Computer and Information Sciences |
添付ファイル名Attached documents | |
年度Year | 2022 |
授業コードClass code | J0521 |
旧授業コードPrevious Class code | |
旧科目名Previous Class title | |
開講時期Term | 秋学期授業/Fall |
曜日・時限Day/Period | 火3/Tue.3 |
科目種別Class Type | |
キャンパスCampus | 小金井 / Koganei |
教室名称Classroom name | 各学部・研究科等の時間割等で確認 |
配当年次Grade | |
単位数Credit(s) | 2 |
備考(履修条件等)Notes | |
他学部公開科目Open Program | |
他学部公開(履修条件等)Open Program (Notes) | |
グローバル・オープン科目Global Open Program | |
成績優秀者の他学部科目履修制度対象Interdepartmental class taking system for Academic Achievers | ○ |
成績優秀者の他学部科目履修(履修条件等)Interdepartmental class taking system for Academic Achievers (Notes) |
(1) 受講希望者 (受講検討中の者も含む) は、情報科学部学部Googleフォーム(https://forms.gle/ECvwxVe2NcxmrbTK9)で初回講義前までに希望申請をしてください。(※以下URLのご案内があるGoogleフォームとは異なるのでご注意ください。) (2) 以下のURLと教育開発支援機構事務局の案内に従って、履修希望の申請を行ってください。 https://www.hoseikyoiku.jp/risyu/index.html (3) 履修取消については、ご自身の所属学部の履修取消期間内に必ず同時に履修削除を行ってください。 |
実務経験のある教員による授業科目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)
Course outline: This course introduces basic concept of complexity theory for understanding theoretical computer science.
Learning objectives: Students will learn time complexity, space complexity, complexity classes (such as P, NP, PSPACE, EXPTIME, etc.), polynomial-time reduction, etc.
Learning activities outside of classroom: Students are expected to study more than four hours for a class.
Grading criteria: Short report & Contribution to the class: 20%, Final exam: 80%
授業で使用する言語Default language used in class
日本語 / Japanese
授業の概要と目的(何を学ぶか)Outline and objectives
この講義では,情報科学の基礎的な理論を理解するために必須となる計算の複雑さの理論を学ぶ.
到達目標Goal
計算の複雑さの理論における基本的な概念である時間計算量,領域計算量,多項式時間帰着などを学ぶとともに,P, NP, PSPACE, EXPなどの重要な計算量のクラスを理解する.また,SATのNP完全性の証明などを通じてP vs NP問題に対する解決のアプローチの歴史を理解する.
この授業を履修することで学部等のディプロマポリシーに示されたどの能力を習得することができるか(該当授業科目と学位授与方針に明示された学習成果との関連)Which item of the diploma policy will be obtained by taking this class?
ディプロマポリシーのうち「DP2」と「DP4-1」に関連
授業で使用する言語Default language used in class
日本語 / Japanese
授業の進め方と方法Method(s)(学期の途中で変更になる場合には、別途提示します。 /If the Method(s) is changed, we will announce the details of any changes. )
基本的には講義を通して,計算の複雑さの理論の基本を理解してもらう.重要なポイントでは演習を行い,講義で学習した内容を実感することで理解を深める.授業で課した課題(小テストやレポート)等を取り上げ、授業内で全体に対してフィードバックを行う。
アクティブラーニング(グループディスカッション、ディベート等)の実施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]:時間計算量のクラス,領域計算量のクラス
P, NP, EXP, NEXPなど時間計算量を理解する上で重要となるクラスについて学ぶ.
9[対面/face to face]:P対NP問題
P対NP問題と,関連の深い概念であるNP完全性,NP困難性について学ぶ.
10[対面/face to face]:多項式時間帰着
二つの問題を解く困難さを比較する指標となる多項式時間帰着について学ぶ.
11[対面/face to face]:多項式時間帰着に関する演習
具体的な問題の多項式時間帰着可能性を考えることにより,多項式時間帰着に対する理解を深める.
12[対面/face to face]:計算の複雑さに関する命題の証明手法
演習問題を例に計算の複雑さに関する命題を証明する手法を学ぶ.
13[対面/face to face]:Cook-Levinの定理とSATのNP完全性
論理式の充足可能性問題(SAT)がNP完全問題であることを理解する.
14[対面/face to face]:計算の複雑さと暗号理論
計算の複雑さの理論と公開鍵暗号の関係について学ぶ.
授業時間外の学習(準備学習・復習・宿題等)Work to be done outside of class (preparation, etc.)
前回までの学習内容を完全に把握しておくことは必須.また,講義期間中に複数回出す課題を提出すること.本授業の準備・復習等の授業時間外学習は,各週につき4時間を標準とする.
テキスト(教科書)Textbooks
学習支援システムから配布する.
参考書References
Michael Sipper著,太田 和夫,田中 圭介,阿部 正幸 訳,
計算理論の基礎 [原著第2版] 2.複雑さの理論,共立出版
ISBN 978-4-320-12209-3
成績評価の方法と基準Grading criteria
講義への貢献度,レポート20%,定期試験80%により評価する.
学生の意見等からの気づきChanges following student comments
学生の理解を深めるため、計算の複雑さの理論における命題の証明法に関する回を追加した.
学生が準備すべき機器他Equipment student needs to prepare
学習支援システムを利用する.また,チューリングマシンの演習等においては貸与PCを利用する.