シラバス参照
|
シラバス参照
|
| 講義概要/Course Information |
| 科目基礎情報/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 |
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 |