シラバス参照
|
シラバス参照
|
| 講義概要/Course Information |
| 科目基礎情報/General Information |
| 授業科目名 /Course title (Japanese) |
理論計算機科学特論 | ||
|---|---|---|---|
| 英文授業科目名 /Course title (English) |
Advanced Study for Theoretical Computer Science | ||
| 科目番号 /Code |
|||
| 開講年度 /Academic year |
2020年度 | 開講年次 /Year offered |
全学年 |
| 開講学期 /Semester(s) offered |
前学期 | 開講コース・課程 /Faculty offering the course |
博士前期課程、博士後期課程 |
| 授業の方法 /Teaching method |
講義 | 単位数 /Credits |
2 |
| 科目区分 /Category |
大学院専門教育科目 - 専門科目Ⅱ | ||
| 開講学科・専攻 /Cluster/Department |
情報・ネットワーク工学専攻 | ||
| 担当教員名 /Lecturer(s) |
垂井 淳 | ||
| 居室 /Office |
東3-824, East-3 Bldg Room 824 | ||
| 公開E-Mail |
juntarui0@gmail.com | ||
| 授業関連Webページ /Course website |
www.jtlab.cei.uec.ac.jp | ||
| 更新日 /Last updated |
2020/03/01 19:48:15 | 更新状況 /Update status |
公開中 /now open to public |
| 講義情報/Course Description |
| 主題および 達成目標 /Topic and goals |
アルゴリズム設計の多様な問題設定・パラダイムを紹介し解説する。特に、学習アルゴリズム、乱択アルゴリズム（ランダマイズドアルゴリズム）、近似アルゴリズムを重点的にとりあげる。いずれも考え方そのものは単純であるが応用範囲は広い。後半では、計算量クラスについて議論する。クラスＰ、クラスＮＰ、クラスBPPなどの計算量クラスと多項式時間還元性についても説明する。本講義の目標はアルゴリズム理論と計算量理論に関する理解をより確実なものにしつつ、いくつかの新しいパラダイムを知り理解の幅を広げることである。 I will introduce and explain various scenarios and paradigms in algorithm design, e.g., learning algorithms, randomized algorithms, approximation algorithms, etc. I will also explain about complexity theory, e.g., complexity classes P and NP and polynomial-time reducibility among computational problems. |
|---|---|
| 前もって履修 しておくべき科目 /Prerequisites |
なし。 required prerequisite: none |
| 前もって履修しておくこ とが望ましい科目 /Recommended prerequisites and preparation |
なし。 recommended prerequisite: none |
| 教科書等 /Course textbooks and materials |
参考書： 渡辺治「計算可能性・計算の複雑さ入門」近代科学社 M. Sipser「計算理論の基礎」共立出版 reference: Computational Complexity by Arora and Barak |
| 授業内容と その進め方 /Course outline and weekly schedule |
英語タイプIIにより講義を実施 前半は、学習アルゴリズム、乱択アルゴリズム、近似アルゴリズムについて、単純な問題に対する単純なアルゴリズムの具体例を重視しながら説明する。後半では、いくつかの重要な計算量クラスについて、そのクラスに属する具体的問題とともに議論し、また、重要な計算資源、すなわち、時間・記憶領域・ランダムネス・通信量に対する理解を深める。 授業計画： 第１回：学習アルゴリズム（１）軸平行長方形の学習 第２回：学習アルゴリズム（２）Probably Approximate Correct (PAC) 学習パラダイム 第３回：学習アルゴリズム（３）monomial の学習 第４回：論理式に関する復習と解説：DNF, CNF, k-DNF, k-CNF, decision list多項式時間 第５回：学習アルゴリズム（４）k-DNFの学習、k-decision listの学習 第６回：学習アルゴリズム（５）学習が本質的に困難な場合、学習と公開鍵暗号の対比 第７回：学習アルゴリズム（６）学習における仮説表現の重要性、オッカムアルゴリズム 第８回：乱択アルゴリズム（１）単純で効率的な乱択アルゴリズムの例 第９回：乱択アルゴリズム（２）計算資源としてのランダムネス、計算論的擬似ランダムネス 第１０回：近似アルゴリズム（１）Set Coverの近似アルゴリズム、近似率 第１１回：近似アルゴリズム（２）近似率の限界：MAX3SAT 第１２回：計算量（１）クラスP、クラスNP、クラスBPP 第１３回：計算量（２）多項式時間還元性 第１４回：計算量理論のより高度なトピック（１） 第１５回： 計算量理論のより高度なトピック（２） In the first half, I will explain learning algorithms, randomized algorithms, and approximation algorithms through simple, concrete problems and simple algorithms for them. In the second half, I will explain important complexity theoretic notions and classes mainly through concrete computational problems, and I will also explain complexity theory about important computational resources, i.e., time, space (memory), randomness, and amount of communication (bandwidth). |
| 実務経験を活かした 授業内容 (実務経験内容も含む) /Course content utilizing practical experience |
|
| 授業時間外の学習 （予習・復習等） /Preparation and review outside class |
２週間毎の宿題には真剣に取り組んでください． biweekly homework assignments |
| 成績評価方法 および評価基準 （最低達成基準を含む） /Evaluation and grading |
成績評価方法： ２週間毎の宿題・課題に関するレポートによって評価を行なう。 評価基準： 以下のレベルの達成を合格の最低水準とする。学習アルゴリズム、乱択アルゴリズム、近似アルゴリズムのそれぞれに関して、問題とアルゴリズムの具体例をあげつつ説明ができる。さらに、基本的な計算量クラスに関して、そのクラスに属する問題（言語）を具体的にあげつつ説明ができる。 Evaluation will be mainly based on biweekly homework assignments. |
| オフィスアワー： 授業相談 /Office hours |
木曜５限、東３号館８２４にて。時間が不都合な場合は授業後やメールにて相談してください。 Office hours: Thursday 5th period at my office: East-3 Bldg 824 |
| 学生へのメッセージ /Message for students |
効率的に計算できるものとできないものがあるという世界観、および、効率的計算の限界の解明という未解決問題は、現在の数理科学の中で大きな意義をもっています。 |
| その他 /Others |
情報数理コース以外の学生も歓迎します。 |
| キーワード /Keyword(s) |
アルゴリズム，計算量，学習アルゴリズム、乱択アルゴリズム、近似アルゴリズム key words: algorithm, computational complexity, learning algorithm, randomized algorithm, approximation algorithm |