シラバス参照
|
シラバス参照
|
| 講義概要/Course Information |
| 科目基礎情報/General Information |
| 授業科目名 /Course title (Japanese) |
計算機科学特論 | ||
|---|---|---|---|
| 英文授業科目名 /Course title (English) |
Advanced 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-826 | ||
| 公開E-mail |
nishino@uec.ac.jp | ||
| 授業関連Webページ /Course website |
特になし | ||
| 更新日 /Last update |
2021/09/13 19:12:26 | 更新状況 /Update status |
公開中 /now open to public |
| 講義情報/Course Description |
| 主題および 達成目標（2,000文字以内） /Themes and goals（up to 2,000 letters） |
コンピュータの基礎理論に関する、最近の話題を選んで講義する。まず、理論計算機科学という学問分野を概観した後に、今年は特に、量子計算量理論について解説する。本理論は、量子コンピュータ実現のための基礎理論として、最近注目を集めている。具体的には、下記の項目について講義を行なう。 |
|---|---|
| 前もって履修 しておくべき科目（1,000文字以内） /Prerequisites（up to 1,000 letters） |
特になし |
| 前もって履修しておくこ とが望ましい科目（1,000文字以内） /Recommended prerequisites and preparation（up to 1,000 letters） |
離散数学 |
| 教科書等（1,000文字以内） /Course textbooks and materials（up to 1,000 letters） |
テキスト配布 |
| 授業内容と その進め方（2,000文字以内） /Course outline and weekly schedule（up to 2,000 letters） |
(a) 内容：以下の内容の講義を行う。 1. P = NP ? 問題 2. 計算可能性 3. 決定性 Turing 機械 4. 非決定性 Turing 機械 5. 多テープ Turing 機械 6. 計算量の定義 7. 種々の計算量クラス 8. NP 完全性 9. 確率的計算と量子計算 10. 回路計算量 11. 単調回路計算量 12. Razborov の下界の導出（１） 13. Razborov の下界の導出（２） 14. Razborov の下界の導出（３） 15.今後の展望：知の限界について (b) 進め方：黒板やプロジェクタを用いて授業を行う。 (c) 授業時間外の学習：毎回の授業後に、必ず復習を行うこと。合計で数回、レポート課題を課すので、そのレポート作成も復習時に計画的に行うこと。 The lecture in this course, typeⅡ, is mostly offered in Japanese; materials such as PPT slides and handouts are given in English. 1: P vs. NP Problem 2: Computability 3: Deterministic Turing Machime 4: Non-deterministic Turing Machine 5: Multi-tape Turing Machine 6: Computational Complexity 7: Various Complexity Classes 8: NP-Completeness 9: Probabilistic Computation and Quantum Computation 10. Circuit Complexity 11. Monotone Circuit Complexity 12. Razborov's Lower Bound（１） 13. Razborov's Lower Bound（２） 14. Razborov's Lower Bound（３） 15. Further Studies |
| 実務経験を活かした 授業内容 (実務経験内容も含む) /Course content utilizing practical experience |
|
| 授業時間外の学習 （予習・復習等）（1,000文字以内） /Preparation and review outside class（up to 1,000 letters） |
毎回、予習に相当する課題を宿題として出します。 |
| 成績評価方法 および評価基準 （最低達成基準を含む） （1,000文字以内） /Evaluation and grading （up to 1,000 letters） |
(a) 評価方法：成績は出席とレポートによる。 (b) 評価基準： 以下の到達レベルをもって合格の最低基準とする。 (1) 計算量理論の基本概念を理解している。 (2) 授業で説明した証明の論理展開を理解している。 (3) 授業で説明した証明に必要な計算を自力で行える。 |
| オフィスアワー： 授業相談（1,000文字以内） /Office hours（up to 1,000 letters） |
授業時にお知らせします。 |
| 学生へのメッセージ（1,000文字以内） /Message for students（up to 1,000 letters） |
理論計算機科学はコンピュータの基礎理論であり、数学的にも非常に面白いと同時に、種々の応用が考えられる分野です。特に前提知識は仮定せずに、なるべくわかりやすく解説しますので、この機会にこの分野に接してみたい方は、是非受講して下さい。 |
| その他 /Others |
本講義の受講を希望される方は、nishino@uec.ac.jp 宛てに、９月３０日までにメイルを送って下さい。その際、メイルの件名は、「計算機科学特論受講希望」として下さい。なお、本授業は「オンデマンド型」（直接やりとりする形式）で行います。 |
| キーワード /Keywords |
P = NP ? 問題, Turing 機械, 計算量, 計算量クラス, 量子 Turing 機械, 量子計算量, 量子アルゴリズム |