シラバス参照
|
シラバス参照
|
| 講義概要/Course Information |
| 科目基礎情報/General Information |
| 授業科目名 /Course title (Japanese) |
アルゴリズム論 | ||
|---|---|---|---|
| 英文授業科目名 /Course title (English) |
Computer Algorithms | ||
| 科目番号 /Code |
COM502e | ||
| 開講年度 /Academic year |
2020年度 | 開講年次 /Year offered |
3 |
| 開講学期 /Semester(s) offered |
前学期 | 開講コース・課程 /Faculty offering the course |
情報理工学域 |
| 授業の方法 /Teaching method |
講義 | 単位数 /Credits |
2 |
| 科目区分 /Category |
専門科目 | ||
| 開講学科・専攻 /Cluster/Department |
Ⅱ類 | ||
| 担当教員名 /Lecturer(s) |
石上 嘉康 | ||
| 居室 /Office |
西3-205 | ||
| 公開E-Mail |
ishigami AT-MARK uec.ac DOT jp | ||
| 授業関連Webページ /Course website |
http://suzushiro.webcrow.jp/index.html（右側の講義関連情報） | ||
| 更新日 /Last updated |
2020/03/03 09:21:50 | 更新状況 /Update status |
公開中 /now open to public |
| 講義情報/Course Description |
| 主題および 達成目標 /Topic and goals |
●２年後期までに、必修科目で（アルゴリズムの正確な定義無しに）クイックソートや二分探索のようないくつかの具体的なアルゴリズムの構造（及びその計算量を少し）を学習した。 ●３年前期のこの科目では，これらをふまえ、アルゴリズムの最も広汎的で正確な定義を学ぶ。 そして、その土台のもと良いアルゴリズムとしての基準を計算量などの観点で学び、アルゴリズムの設計において，どの手法を選択するか，またそれぞれの手法の利点と限界の理解し，アルゴリズムの記述などが出来るようになることを目標とする． |
|---|---|
| 前もって履修 しておくべき科目 /Prerequisites |
離散数学 （必修ではなくとも事実上ほとんど全員が単位取得している。言語として記法などを使用する。難しい演習問題は解ける必要無いが、例えば、講義で、定義なしに単射、全射などと言ったとき、すぐに定義を思い出すか、教科書で該当ページを調べられるようにしておくこと。もっとも高校を超える必要予備知識は初回講義で1ページ程度のプリントにして配布する予定なので心配は無いと思う。） |
| 前もって履修しておくこ とが望ましい科目 /Recommended prerequisites and preparation |
・本講義で論理的に必要な科目は、上の離散数学だけです。 ・プログラミング経験があったほうが分かり易いという意味で、次は望ましいが前提とはしない。 ●アルゴリズムとデータ構造およびプログラミング演習（２年後期必修）、 （プログラミングの経験があったほうが理解しやすい。２分探索木など。ソートなどの具体的なアルゴリズムを覚えている必要はない。） ・前もってというわけではないが、平行して 離散数学応用（３年前期） もあわせて受講すると、更に効果的です。（アルゴリズム論も広い意味で離散数学の応用と考えることが可能であり、離散数学応用でもアルゴリズムを扱う。） |
| 教科書等 /Course textbooks and materials |
参考書・参考資料等 ★有川・宮野著：オートマトンと計算可能性、培風館ISBN4-563-00789-7（主要参考書） ●Michael Sipser著Introduction to the Theory of Computation (邦訳版あり。計算理論の基礎) ○岩間著 アルゴリズム理論入門 昭晃堂 (2001/05) ○Wilf著（西関・高橋訳）アルゴリズムと計算量入門・総研出版 |
| 授業内容と その進め方 /Course outline and weekly schedule |
まずは定義が簡単で能力がよく分かっている低機能計算機モデル（オートマトン）からはじめ、万能計算機であるチューリング機械へと進む。 計算機モデルとアルゴリズムの定義を正確にする。具体なアルゴリズムを例にして計算量の定義と評価法を説明する。そして効率的なアルゴリズムの定義とともにその限界性をNP完全性の概念を通して学ぶ。そして典型的な例題アルゴリズムを基本として，アルゴリズムの基本的設計技法を解説する． 授業計画 第１回：導入、背景。計算機で出来ることと出来ないこと。 第２回：オートマトンの理論（１）定義と基礎 第３回：オートマトンの理論（２）全体の概観 第４回：チューリング機械（１）定義（決定性と非決定性） 第５回：チューリング機械（２）計算可能性 第６回：帰納的関数 第７回：計算量理論（１）；P問題 第８回：計算量理論（２）；NP問題 第９回：計算量理論（３）；領域計算量 第１０回；計算量理論（４）；発展 第１１回；再帰的アルゴリズム 第１２回；グラフアルゴリズム 第1３回：近似アルゴリズム 第１４回：確率アルゴリズム 第１５回：期末試験とその解説・復習 |
| 実務経験を活かした 授業内容 (実務経験内容も含む) /Course content utilizing practical experience |
|
| 授業時間外の学習 （予習・復習等） /Preparation and review outside class |
講義での疑問点は上にあげた参考書を読むと理解が深まります。離散数学の講義で説明されていないことは全て説明しますので、説明されていない疑問点があった場合には、離散数学の復習プリント（初回講義に配布）にあたって定義から立ち戻ってください。担当教員への質問も歓迎します。 |
| 成績評価方法 および評価基準 （最低達成基準を含む） /Evaluation and grading |
主に期末試験によって成績評価をする。 |
| オフィスアワー： 授業相談 /Office hours |
水曜５限。 |
| 学生へのメッセージ /Message for students |
●他人の出来と比較するよりも、学問を楽しんでください。離散数学（２年前期）で学んだことが役に立つはずです。講義だけで理解できる内容は、もともと知っていたか、よほど薄っぺらいものかのどちらかです。本を読んでください。 過去において、この科目で期末試験受験後不可の学生は（例外なく）全員が、離散数学（２年前期）の理解が不足していました。 |
| その他 /Others |
●良いアルゴリズムを設計すること（首尾よく問題を解決すること）も重要であるが、アルゴリズムの限界（問題が難しいこと）を理解することも重要である。暗号や擬似乱数などでは、敵の解読アルゴリズムの計算量が膨大になってしまうこと（敵の抱えている問題が難しいこと）を利用する。 |
| キーワード /Keyword(s) |
アルゴリズム、計算量 |