シラバス参照
|
シラバス参照
|
| 講義概要/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 |
2023年度 | 開講年次 /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 update |
2023/02/27 07:11:24 | 更新状況 /Update status |
公開中 /now open to public |
| 講義情報/Course Description |
| 主題および 達成目標（2,000文字以内） /Themes and goals（up to 2,000 letters） |
In the academic year of 2023, 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. Each year, many students taking this course have not-enough experience in algorithm design and programming. After finding our the actual group of students, I will include appropriate amount of lectures about algorithm design. |
|---|---|
| 前もって履修 しておくべき科目（1,000文字以内） /Prerequisites（up to 1,000 letters） |
none |
| 前もって履修しておくこ とが望ましい科目（1,000文字以内） /Recommended prerequisites and preparation（up to 1,000 letters） |
Students should have taken an introductory course on algorithms, and should have written at least a few computer program. |
| 教科書等（1,000文字以内） /Course textbooks and materials（up to 1,000 letters） |
none |
| 授業内容と その進め方（2,000文字以内） /Course outline and weekly schedule（up to 2,000 letters） |
The following is a plan when most students have sufficient background, which is often not the case. When augmenting the lecture by adding more explanations about algorithm design is desirable, I willl do so after interacting with students; I may decide to give one or two mini algorithm design and programming assignments, where you are given only a problem description and are asked to design your algorithm and implement it (ie write a program) . In the first half of the course, we will discuss 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 including important 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 |
|
| 授業時間外の学習 （予習・復習等）（1,000文字以内） /Preparation and review outside class（up to 1,000 letters） |
at least 1.5 hour/week expected |
| 成績評価方法 および評価基準 （最低達成基準を含む） （1,000文字以内） /Evaluation and grading （up to 1,000 letters） |
Grading will be based on homework reports and mini algorithm design-programming projects. 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. |
| オフィスアワー： 授業相談（1,000文字以内） /Office hours（up to 1,000 letters） |
Ask me after class (whichi will be lunch-break time); you can email me any time; or we can discuss about when to meet at my office |
| 学生へのメッセージ（1,000文字以内） /Message for students（up to 1,000 letters） |
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. |
| キーワード /Keywords |
algorithm, computational complexity, learning algorithm, NP-completeness |