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


授業の目的　【日本語】
Goals of the Course(JPN)
数理的にモデル化された様々な問題を計算機で解くために必要な計算資源（計算時間やメモリ）の量を基準にして，問題の持つ複雑さ（計算複雑さ）を測るための理論（計算量理論）を学習する。問題の数学的定式化や計算機の数理モデル（計算モデル）を学んだ後，計算機における計算複雑さの測り方を具体例とともに理解する。そして，計算複雑さの尺度で考えたときに効率的に解ける問題がどういったものかを学び，そのような問題が持つ特徴や基本的性質を修得する。
授業の目的　【英語】
Goals of the Course
In this course, students will learn computational complexity -- theory for measuring the complexity of a problem based on the amount of computational resources (time and memory) required to solve various mathematically modeled problems with a computer. After studying the mathematical formulation of the problem and the mathematical model of a computer (computation model), they will understand how to measure the computational complexity of a computer with concrete examples. Then, they will learn what kind of problems can be solved efficiently when they are considered in terms of computational complexity, and learn the characteristics and basic properties of such problems.
到達目標　【日本語】
Objectives of the Course(JPN)
この授業では，受講者が授業終了時に，以下の知識・能力を身に着けていることを目標とする。
1. 計算モデルの概念について説明でき，技術的内容を理解する。
2. 計算量の概念について説明でき，技術的内容を理解する。
到達目標　【英語】
Objectives of the Course
授業の内容や構成
Course Content / Plan
計算問題をコンピュータで解くための複雑さ（計算複雑さ）を測るための理論（計算量理論）を理解するための基礎事項を詳細に解説する。計算問題，計算モデル，計算量など計算とは何か，計算複雑さとは何かについての数学的定式化を行い，具体例を紹介する。さらに様々な（計算）問題の計算量を評価する方法や多項式時間計算可能性など計算量理論を展開するうえで必要不可欠な事項について説明を行う。

1. ガイダンス
2. 計算問題
3. 計算モデル
4. チャーチの提唱
5. 計算モデルの万能性
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)