![]() ![]() |
講義概要/Course Information |
科目基礎情報/General Information |
授業科目名 /Course title (Japanese) |
アルゴリズム基礎論 | ||
---|---|---|---|
英文授業科目名 /Course title (English) |
Fundamentals of Algorithm Theory | ||
科目番号 /Code |
|||
開講年度 /Academic year |
2021年度 | 開講年次 /Year offered |
全学年 |
開講学期 /Semester(s) offered |
前学期 | 開講コース・課程 /Faculty offering the course |
博士前期課程 |
授業の方法 /Teaching method |
講義 | 単位数 /Credits |
2 |
科目区分 /Category |
大学院専門教育科目 - 専門科目Ⅰ | ||
開講類・専攻 /Cluster/Department |
情報・ネットワーク工学専攻 | ||
担当教員名 /Lecturer(s) |
武永 康彦 | ||
居室 /Office |
西9-535(W9-535) | ||
公開E-mail |
takenaga@cs.uec.ac.jp | ||
授業関連Webページ /Course website |
なし(none) | ||
更新日 /Last update |
2021/03/08 19:49:31 | 更新状況 /Update status |
公開中 /now open to public |
講義情報/Course Description |
主題および 達成目標(2,000文字以内) /Themes and goals(up to 2,000 letters) |
効率の良いアルゴリズムを設計することは、問題解決とコンピュータの活用において非常に重要であることはいうまでもない。しかし、非常に大規模で複雑な問題に対しては、最適解を求めることが困難な場合が多い。このような問題に対処するため、並列コンピュータの利用、最適解に近い解を求める手法の開発などが重要となってきている。本講義では、これらのアルゴリズム設計手法について理解し、目的や状況に応じて適切な方法を選択してアルゴリズム設計を行なえるようになることを目標とする。 (Though it is very important to design efficient algorithms, it is often difficult to find the best solution for computationally hard problems. Several methods to design algorithms to cope with such problems are introduced in this course.) |
---|---|
前もって履修 しておくべき科目(1,000文字以内) /Prerequisites(up to 1,000 letters) |
なし(none) |
前もって履修しておくこ とが望ましい科目(1,000文字以内) /Recommended prerequisites and preparation(up to 1,000 letters) |
なし(none) |
教科書等(1,000文字以内) /Course textbooks and materials(up to 1,000 letters) |
なし(none) |
授業内容と その進め方(2,000文字以内) /Course outline and weekly schedule(up to 2,000 letters) |
(a) 授業内容 第1回:アルゴリズムの評価、分割統治法 (Evaluation of algorithms, Divide-and conqure) 第2回:動的計画法、並列計算モデル (Dynamic programming, Parallel computation models) 第3回:並列アルゴリズム(1) 共有メモリ型モデル上のアルゴリズム設計手法 (Parallel algorithm(1): Methods to design algorithms on shared memory models) 第4回:並列アルゴリズム(2) 共有メモリ型モデル上のアルゴリズム (Parallel algorithm(2): Algorithms on shared memory models) 第5回:並列アルゴリズム(3) ネットワークモデル上のアルゴリズム (Parallel algorithm(3): Algorithms on network models) 第6回:並列アルゴリズム(4) 組合せ回路モデル上のアルゴリズム (Parallel algorithm(4): Algorithms on combinatorial circuits) 第7回:分散アルゴリズム (Distributed algorithm) 第8回:近似アルゴリズム(1) 近似アルゴリズムとその評価、アルゴリズムの例 (Approximation algorithm(1): Basics of approximation algorithms) 第9回:近似アルゴリズム(2) アルゴリズムの例 (Approximation algorithm(2): Approximation algorithms) 第10回:確率アルゴリズム (Randomized algorithm) 第11回:メタヒューリスティック(1) 局所探索、シミュレーテッドアニーリング (Meta heuristics(1): local search, simulated annealing) 第12回:メタヒューリスティック(2) タブー探索、遺伝アルゴリズム (Meta heuristics(2): tabu search, genetic algorithm) 第13回:二分決定グラフと列挙アルゴリズム (Binary decision diagram and enumeration) 第14回:パラメータ化アルゴリズム (Parameterized algorithm) 第15回:オンラインアルゴリズム (Online algorithm) (b) 授業の進め方 授業内容に示した基本的な手法について、数多くの具体的なアルゴリズムを例にとって示しながら、解説を進める。その他のトピックについても適宜紹介する場合がある。 (Many examples of algorithms are shown to explain the algorithms described above. Other topics may be included.) |
実務経験を活かした 授業内容 (実務経験内容も含む) /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) |
評価方法:数回のレポートによる。 評価基準:種々のアルゴリズム設計手法の基本的考え方を理解し、それに基づいたアルゴリズムの設計がある程度できるようになることが合格の基準である。 (Evaluation: Based on several reports. Students must be able to design algorithms with the understanding of the methods to design algorithms.) |
オフィスアワー: 授業相談(1,000文字以内) /Office hours(up to 1,000 letters) |
なるべく授業終了後に教室で相談すること。それ以外はまずメールで連絡してください。 (After class or contact me by email.) |
学生へのメッセージ(1,000文字以内) /Message for students(up to 1,000 letters) |
種々のアルゴリズム設計の考え方について、本講義では主に理論的立場から解説をおこなうが、実用的なプログラムを作成する際に、これらのアルゴリズム設計手法を知っていることは適切な解法を選ぶ上で非常に重要である。 (Though we deal with the methods for algorithm design mainly from the theoretical point of view in this class, it is also practically important to know the methods so that we can choose appropriate algorithms.) |
その他 /Others |
なし(none) |
キーワード /Keywords |
アルゴリズム、並列計算、近似、計算量 (algorithm, parallel computing, approximation, computational complexity) |