シラバス参照 |
講義概要/Course Information |
科目基礎情報/General Information |
授業科目名 /Course title (Japanese) |
アルゴリズム基礎論(H27年度以前入学生) | ||
---|---|---|---|
英文授業科目名 /Course title (English) |
Fundamentals of Algorithm Theory | ||
開講年度 /Academic year |
2019年度 | 開講年次 /Year offered |
全学年 |
開講学期 /Semester(s) offered |
前学期 | 開講コース・課程 /Faculty offering the course |
博士前期課程 |
授業の方法 /Teaching method |
講義 | 単位数 /Credits |
2 |
科目区分 /Category |
大学院専門教育科目 - 連携専門科目 | ||
開講類・専攻 /Cluster/Department |
情報・通信工学専攻 | ||
担当教員名 /Lecturer(s) |
武永 康彦 | ||
居室 /Office |
西9-535 | ||
公開E-mail |
takenaga@cs.uec.ac.jp | ||
授業関連Webページ /Course website |
なし | ||
更新日 /Last update |
2019/02/27 16:08:50 | 更新状況 /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回:アルゴリズムの評価、分割統治法 第2回:動的計画法、並列計算モデル 第3回:並列アルゴリズム(1) 共有メモリ型モデル上のアルゴリズム設計手法 第4回:並列アルゴリズム(2) 共有メモリ型モデル上のアルゴリズム 第5回:並列アルゴリズム(3) ネットワークモデル上のアルゴリズム 第6回:並列アルゴリズム(4) 組合せ回路モデル上のアルゴリズム 第7回:分散アルゴリズム 第8回:近似アルゴリズム(1) 近似アルゴリズムとその評価、アルゴリズムの例 第9回:近似アルゴリズム(2) アルゴリズムの例 第10回:確率アルゴリズム 第11回:メタヒューリスティック(1) 局所探索、シミュレーテッドアニーリング 第12回:メタヒューリスティック(2) タブー探索、遺伝アルゴリズム 第13回:二分決定グラフと列挙アルゴリズム 第14回:パラメータ化アルゴリズム 第15回:オンラインアルゴリズム (b) 授業の進め方 授業内容に示した基本的な手法について、数多くの具体的なアルゴリズムを例にとって示しながら、解説を進める。その他のトピックについても適宜紹介する場合がある。 |
実務経験を活かした 授業内容 (実務経験内容も含む) /Course content utilizing practical experience |
|
成績評価方法 および評価基準 (最低達成基準を含む) (1,000文字以内) /Evaluation and grading (up to 1,000 letters) |
評価方法:数回のレポートによる。 評価基準:種々のアルゴリズム設計手法の基本的考え方を理解し、それに基づいたアルゴリズムの設計がある程度できるようになることが合格の基準である。 |
オフィスアワー: 授業相談(1,000文字以内) /Office hours(up to 1,000 letters) |
適宜相談に応じる。なるべく授業終了後に教室で相談すること。 |
学生へのメッセージ(1,000文字以内) /Message for students(up to 1,000 letters) |
種々のアルゴリズム設計の考え方について、本講義では主に理論的立場から解説をおこなうが、実用的なプログラムを作成する際に、これらのアルゴリズム設計手法を知っていることは適切な解法を選ぶ上で非常に重要である。 |
その他 /Others |
なし |
キーワード /Keywords |
アルゴリズム、並列計算、近似、計算量 |