シラバス参照
|
シラバス参照
|
| 講義概要/Course Information |
| 科目基礎情報/General Information |
| 授業科目名 /Course title (Japanese) |
理論計算機科学特論 | ||
|---|---|---|---|
| 英文授業科目名 /Course title (English) |
Advanced Study for Theoretical Computer Science | ||
| 科目番号 /Code |
|||
| 開講年度 /Academic year |
2021年度 | 開講年次 /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 update |
2021/03/09 21:11:12 | 更新状況 /Update status |
公開中 /now open to public |
| 講義情報/Course Description |
| 主題および 達成目標（2,000文字以内） /Themes and goals（up to 2,000 letters） |
アルゴリズム設計の多様な問題設定・パラダイムを紹介し解説する。特に、学習アルゴリズム、乱択アルゴリズム（ランダマイズドアルゴリズム）、近似アルゴリズムを重点的にとりあげる。いずれも考え方そのものは単純であるが応用範囲は広い。後半では、計算量クラスについて議論する。クラスＰ、クラスＮＰ、クラス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. |
|---|---|
| 前もって履修 しておくべき科目（1,000文字以内） /Prerequisites（up to 1,000 letters） |
なし。 required prerequisite: none |
| 前もって履修しておくこ とが望ましい科目（1,000文字以内） /Recommended prerequisites and preparation（up to 1,000 letters） |
なし。 recommended prerequisite: none |
| 教科書等（1,000文字以内） /Course textbooks and materials（up to 1,000 letters） |
参考書： 渡辺治「計算可能性・計算の複雑さ入門」近代科学社 M. Sipser「計算理論の基礎」共立出版 reference: Computational Complexity by Arora and Barak |
| 授業内容と その進め方（2,000文字以内） /Course outline and weekly schedule（up to 2,000 letters） |
英語タイプ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 |
|
| 授業時間外の学習 （予習・復習等）（1,000文字以内） /Preparation and review outside class（up to 1,000 letters） |
２週間毎の宿題には真剣に取り組んでください． biweekly homework assignments |
| 成績評価方法 および評価基準 （最低達成基準を含む） （1,000文字以内） /Evaluation and grading （up to 1,000 letters） |
成績評価方法： ２週間毎の宿題・課題に関するレポートによって評価を行なう。 評価基準： 以下のレベルの達成を合格の最低水準とする。学習アルゴリズム、乱択アルゴリズム、近似アルゴリズムのそれぞれに関して、問題とアルゴリズムの具体例をあげつつ説明ができる。さらに、基本的な計算量クラスに関して、そのクラスに属する問題（言語）を具体的にあげつつ説明ができる。 Evaluation will be mainly based on biweekly homework assignments. |
| オフィスアワー： 授業相談（1,000文字以内） /Office hours（up to 1,000 letters） |
授業後やメールで相談してください。 |
| 学生へのメッセージ（1,000文字以内） /Message for students（up to 1,000 letters） |
効率的に計算できるものとできないものがあるという世界観、および、効率的計算の限界の解明という未解決問題は、現在の数理科学の中で大きな意義をもっています。 |
| その他 /Others |
とくになし |
| キーワード /Keywords |
アルゴリズム，計算量，学習アルゴリズム、乱択アルゴリズム、近似アルゴリズム key words: algorithm, computational complexity, learning algorithm, randomized algorithm, approximation algorithm |