シラバス参照

講義概要/Course Information

2024/04/29 現在

科目基礎情報/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 /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) 授業内容 第１回：アルゴリズムの評価、分割統治法 　　　　(Evaluation of algorithms, Divide-and conqure) 第２回：動的計画法、並列計算モデル         (Dynamic programming, Parallel computation models) 第３回：並列アルゴリズム（１）　共有メモリ型モデル上のアルゴリズム設計手法        (Parallel algorithm(1): Methods to design algorithms on shared memory models) 第４回：並列アルゴリズム（２）　共有メモリ型モデル上のアルゴリズム        (Parallel algorithm(2): Algorithms on shared memory models) 第５回：並列アルゴリズム（３）　ネットワークモデル上のアルゴリズム        (Parallel algorithm(3): Algorithms on network models) 第６回：並列アルゴリズム（４）　組合せ回路モデル上のアルゴリズム        (Parallel algorithm(4): Algorithms on combinatorial circuits) 第７回：分散アルゴリズム        (Distributed algorithm) 第８回：近似アルゴリズム（１）　近似アルゴリズムとその評価、アルゴリズムの例        (Approximation algorithm(1): Basics of approximation algorithms) 第９回：近似アルゴリズム（２）　アルゴリズムの例        (Approximation algorithm(2): Approximation algorithms) 第１０回：確率アルゴリズム        (Randomized algorithm) 第１１回：メタヒューリスティック（１）　局所探索、シミュレーテッドアニーリング        (Meta heuristics(1): local search, simulated annealing) 第１２回：メタヒューリスティック（２）　タブー探索、遺伝アルゴリズム        (Meta heuristics(2): tabu search, genetic algorithm) 第１３回：二分決定グラフと列挙アルゴリズム        (Binary decision diagram and enumeration) 第１４回：パラメータ化アルゴリズム        (Parameterized algorithm) 第１５回：オンラインアルゴリズム        (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)