学部・大学院区分
Undergraduate / Graduate		情報学部
時間割コード
Registration Code		1001060
科目区分
Course Category
専門科目(自然情報)関連専門科目(人社，CS)
科目名　【日本語】
Course Title		数理情報学２
科目名　【英語】
Course Title		Mathematical Informatics 2
コースナンバリングコード
Course Numbering Code		SIS-11-3008-J
担当教員　【日本語】
Instructor		西村　治道 ○ 大舘　陽太 BUSCEMI Francesco
担当教員　【英語】
Instructor		NISHIMURA Harumichi ○ OTACHI Yota BUSCEMI Francesco
単位数
Credits		1
開講期・開講時間帯
Term / Day / Period		秋２期 金曜日 ２時限
Fall2 Fri 2
対象学年
Year		３年
3
授業形態
Course style		講義
Lecture
開講系（学部）・開講専攻（大学院）
Subject
自然・数理情報
必修・選択
Required / Selected
選択


授業の目的　【日本語】
Goals of the Course(JPN)
本講義は数理情報学1で学習した計算複雑さの概念をもとに，計算量理論の根幹を成す基本事項を修得する。PとNP，多項式時間帰着，NP完全，NP困難の概念を具体例とともに学習し，様々な問題の持つ計算複雑さを体系的に理解する。また，乱択アルゴリズムなど発展的なアルゴリズムを定式化する計算モデルと，それらのアルゴリズムで効率的に解ける問題の持つ特徴や基本的性質を修得する。さらに計算量理論の現在暗号へのつながりなど応用的な話題も学習する。
授業の目的　【英語】
Goals of the Course
In this lecture, based on the concept of computational complexity learned in Mathematical Informatics 1, students will learn the basic items that form the basis of computational complexity theory. They will learn the concepts of P and NP, polynomial-time reduction, NP-completeness, and NP-hardness with concrete examples to systematically understand the computational complexity of various problems. In addition, they will learn the computational models that formulate advanced algorithms such as randomized algorithms, and the characteristics and basic properties of problems that can be efficiently solved by those algorithms. In addition, students will learn applied topics such as the connection of computational complexity theory to current cryptography.
到達目標　【日本語】
Objectives of the Course(JPN)
この授業では，受講者が授業終了時に，以下の知識・能力を身に着けていることを目標とする。
1. NP, 多項式時間帰着, NP完全の概念が説明でき，技術的内容を理解できる。
2. 乱択アルゴリズムとその計算モデルや計算量クラスが説明でき，技術的内容を理解できる。
到達目標　【英語】
Objectives of the Course
授業の内容や構成
Course Content / Plan
PとNP，多項式時間帰着，NP完全，NP困難の概念を具体例とともに学習し，様々な（計算）問題の持つ計算複雑さを体系的に理解する。また，乱択アルゴリズムなど発展的なアルゴリズムを定式化する計算モデルと，それらのアルゴリズムで効率的に解ける問題の持つ特徴や基本的性質を修得する。さらに計算量理論の現在暗号へのつながりなど応用的な話題も学習する。

1. ガイダンス
2. 非決定性アルゴリズムとNP
3. 検証とNP
4. 多項式時間帰着
5. NP完全，NP困難
6. 乱択アルゴリズムと計算モデル
7. 確率計算量クラス
8. 計算量理論の応用
履修条件・関連する科目
Course Prerequisites and Related Courses
履修条件は特にないが，数理情報学１を履修していた方が望ましい。
成績評価の方法と基準
Course Evaluation Method and Criteria
課題や期末試験を通じて到達目標に達していることが確認できるようなものを最低限の合格基準とする。授業中に与える課題の評価40％，期末試験60％，合計100点満点で60点以上を合格とする。
教科書・参考書
Textbook/Reference book
教科書は指定しないが，講義プリントを配布する。参考文献は必要に応じて授業中に示す。
課外学習等（授業時間外学習の指示）
Study Load(Self-directed Learning Outside Course Hours)
授業後に毎回学んだ内容を復習すること。宿題が出たときは（他の学生と相談してもよいので）解いておくこと。
授業開講形態等
Lecture format, etc.
遠隔授業（オンデマンド型）で行う場合の追加措置
Additional measures for remote class (on-demand class)