シラバス参照

講義概要/Course Information
2020/04/28 現在

科目基礎情報/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
/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
●2年後期までに、必修科目で(アルゴリズムの正確な定義無しに)クイックソートや二分探索のようないくつかの具体的なアルゴリズムの構造(及びその計算量を少し)を学習した。
●3年前期のこの科目では,これらをふまえ、アルゴリズムの最も広汎的で正確な定義を学ぶ。
そして、その土台のもと良いアルゴリズムとしての基準を計算量などの観点で学び、アルゴリズムの設計において,どの手法を選択するか,またそれぞれの手法の利点と限界の理解し,アルゴリズムの記述などが出来るようになることを目標とする. 
前もって履修
しておくべき科目
/Prerequisites
離散数学
(必修ではなくとも事実上ほとんど全員が単位取得している。言語として記法などを使用する。難しい演習問題は解ける必要無いが、例えば、講義で、定義なしに単射、全射などと言ったとき、すぐに定義を思い出すか、教科書で該当ページを調べられるようにしておくこと。もっとも高校を超える必要予備知識は初回講義で1ページ程度のプリントにして配布する予定なので心配は無いと思う。)
前もって履修しておくこ
とが望ましい科目
/Recommended prerequisites and preparation
・本講義で論理的に必要な科目は、上の離散数学だけです。

・プログラミング経験があったほうが分かり易いという意味で、次は望ましいが前提とはしない。
●アルゴリズムとデータ構造およびプログラミング演習(2年後期必修)、
(プログラミングの経験があったほうが理解しやすい。2分探索木など。ソートなどの具体的なアルゴリズムを覚えている必要はない。)

・前もってというわけではないが、平行して
離散数学応用(3年前期)
もあわせて受講すると、更に効果的です。(アルゴリズム論も広い意味で離散数学の応用と考えることが可能であり、離散数学応用でもアルゴリズムを扱う。)
教科書等
/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完全性の概念を通して学ぶ。そして典型的な例題アルゴリズムを基本として,アルゴリズムの基本的設計技法を解説する.
授業計画
第1回:導入、背景。計算機で出来ることと出来ないこと。
第2回:オートマトンの理論(1)定義と基礎
第3回:オートマトンの理論(2)全体の概観
第4回:チューリング機械(1)定義(決定性と非決定性)
第5回:チューリング機械(2)計算可能性
第6回:帰納的関数
第7回:計算量理論(1);P問題
第8回:計算量理論(2);NP問題
第9回:計算量理論(3);領域計算量
第10回;計算量理論(4);発展
第11回;再帰的アルゴリズム
第12回;グラフアルゴリズム
第13回:近似アルゴリズム
第14回:確率アルゴリズム
第15回:期末試験とその解説・復習
実務経験を活かした
授業内容
(実務経験内容も含む)
/Course content utilizing practical experience
授業時間外の学習
(予習・復習等)
/Preparation and review outside class
講義での疑問点は上にあげた参考書を読むと理解が深まります。離散数学の講義で説明されていないことは全て説明しますので、説明されていない疑問点があった場合には、離散数学の復習プリント(初回講義に配布)にあたって定義から立ち戻ってください。担当教員への質問も歓迎します。
成績評価方法
および評価基準
(最低達成基準を含む)
/Evaluation and grading
主に期末試験によって成績評価をする。
オフィスアワー:
授業相談
/Office hours
水曜5限。
学生へのメッセージ
/Message for students
●他人の出来と比較するよりも、学問を楽しんでください。離散数学(2年前期)で学んだことが役に立つはずです。講義だけで理解できる内容は、もともと知っていたか、よほど薄っぺらいものかのどちらかです。本を読んでください。
過去において、この科目で期末試験受験後不可の学生は(例外なく)全員が、離散数学(2年前期)の理解が不足していました。
その他
/Others
●良いアルゴリズムを設計すること(首尾よく問題を解決すること)も重要であるが、アルゴリズムの限界(問題が難しいこと)を理解することも重要である。暗号や擬似乱数などでは、敵の解読アルゴリズムの計算量が膨大になってしまうこと(敵の抱えている問題が難しいこと)を利用する。
キーワード
/Keyword(s)
アルゴリズム、計算量