シラバス参照

講義概要/Course Information
2020/04/28 現在

科目基礎情報/General Information
授業科目名
/Course title (Japanese)
Advanced Communication Engineering and Informatics Ⅲ(Computational Complexity)(学域)
英文授業科目名
/Course title (English)
Advanced Communication Engineering and Informatics Ⅲ(Computational Complexity)
科目番号
/Code
INT003c INT003d INT003f INT003g
開講年度
/Academic year
2020年度 開講年次
/Year offered
3/4
開講学期
/Semester(s) offered
後学期 開講コース・課程
/Faculty offering the course
情報理工学域
授業の方法
/Teaching method
講義 単位数
/Credits
2
科目区分
/Category
専門科目
開講学科・専攻
/Cluster/Department
Ⅰ類/Ⅱ類
担当教員名
/Lecturer(s)
垂井 淳
居室
/Office
E3-824
公開E-Mail
/e-mail
juntarui0@gmail.com
授業関連Webページ
/Course website
www.jtlab.cei.uec.ac.jp
更新日
/Last updated
2020/03/01 19:48:41 更新状況
/Update status
公開中
/now open to public
講義情報/Course Description
主題および
達成目標
/Topic and goals
In the academic year of 2019, the subject of this course will be Computational Complexity, which studies questions such as "Which computational problems have efficient algorithms?" and "Do quantum computers have more computational power than classical computers?" The course will be an introduction to Computational Complexity, and will cover a wide spectrum of topics.
前もって履修
しておくべき科目
/Prerequisites
none
前もって履修しておくこ
とが望ましい科目
/Recommended prerequisites and preparation
Students should have taken an introductory course on algorithms, and should have written at least one computer program.
教科書等
/Course textbooks and materials
none
授業内容と
その進め方
/Course outline and weekly schedule
In the first half of the course, we will dicuss the following various algorithmic paradigms:
(1) learning algorithms
(2) randomized algorithms
(3) approximation algorithms
In the second half, we will discuss the following:
(1) complexity classes inculuding importand classes P and NP
(2) theory of NP-completeness
(3) theoretical cryptography

More specific plan of 15 lectures is as follows.
I will somewhat fine-tune the lecture plan after finding out backgrounds of actual class attendees.

1. overview, review of algorithm analysis
2. review of sorting algorithms and their analysis
3. explanation of programming project
4. learning algorithm (1): learning axis-parallel rectangles
5. learning algorithm (2): PAC learning paradigm
6. learning algorithm (3): learning conjunctions and DNFs
7. student presentation of programming project
8. randomized algorithm
9. approximation algorithm
10. complexity classes P and NP
11. NP-completeness (1): reduction
12. NP-completeness (2): 3SAT
13. NP-completeness (3): 3coloring
14. cryptography
15. P vs NP conjecture
実務経験を活かした
授業内容
(実務経験内容も含む)
/Course content utilizing practical experience
授業時間外の学習
(予習・復習等)
/Preparation and review outside class
at least 1.5 hour/week expected
成績評価方法
および評価基準
(最低達成基準を含む)
/Evaluation and grading
Grading will be based on biweekly homework reports and one programming project. To pass the course, you have to understand at least two-thirds of the topics in class well enough to the extent that you can give simple examples for explanation, and you have to complete well at least two-thirds of your homework.
オフィスアワー:
授業相談
/Office hours
TBA
学生へのメッセージ
/Message for students
Regular UEC students from all departments are very much welcome.
その他
/Others
If you have questions about this course, please feel free to ask me by email.
キーワード
/Keyword(s)
algorithm, computational complexity, learning algorithm, NP-completeness