![]() ![]() |
講義概要/Course Information |
科目基礎情報/General Information |
授業科目名 /Course title (Japanese) |
応用アルゴリズム論 | ||
---|---|---|---|
英文授業科目名 /Course title (English) |
Applied Algorithms | ||
科目番号 /Code |
|||
開講年度 /Academic year |
2021年度 | 開講年次 /Year offered |
全学年 |
開講学期 /Semester(s) offered |
後学期 | 開講コース・課程 /Faculty offering the course |
博士前期課程 |
授業の方法 /Teaching method |
講義 | 単位数 /Credits |
2 |
科目区分 /Category |
大学院専門教育科目 - 専門科目Ⅰ | ||
開講類・専攻 /Cluster/Department |
情報・ネットワーク工学専攻 | ||
担当教員名 /Lecturer(s) |
小林 聡 | ||
居室 /Office |
西9-735 | ||
公開E-mail |
kobayashi.satoshi@uec.ac.jp | ||
授業関連Webページ /Course website |
http://www.comp.cs.uec.ac.jp/lectures/ | ||
更新日 /Last update |
2021/09/26 00:52:55 | 更新状況 /Update status |
公開中 /now open to public |
講義情報/Course Description |
主題および 達成目標(2,000文字以内) /Themes and goals(up to 2,000 letters) |
本講義では,生物情報学領域へのアルゴリズム論の応用など、アルゴリズム論の応用的な側面を重視して,先進的な内容を講義する。以下を達成目標とする。 1) 講義で取り扱う各応用問題に対するアルゴリズムの動作と正当性およびその計算量の解析結果を理解する. 2) 講義で紹介するアルゴリズムの設計手法の原理を理解し,新しい類似問題への適用ができる能力を身に付ける. This lecture provides an advanced theory of algorithms which are applied to the problems related to biology, biophysics, bioinformatics, etc. |
---|---|
前もって履修 しておくべき科目(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) |
資料を配布する. Printed materials are provided at the lecture. |
授業内容と その進め方(2,000文字以内) /Course outline and weekly schedule(up to 2,000 letters) |
(a) 授業内容 第1回:導入および分子生物学概観 Introduction to molecular biology 第2回:遺伝子配列のペアワイズアラインメント問題とは? Pairwise alignment problem 第3回:ペアワイズアラインメント問題への動的計画法の応用 DP algorithms for pairwise alignment problem 第4回:RNA 二次構造予測問題とは? RNA secondary structure prediction problem 第5回:RNA 二次構造予測問題への動的計画法の応用(1) --- 線形構造の場合 DP algorithm for RNA secondary structure prediction --- linear structure case --- 第6回:RNA 二次構造予測問題への動的計画法の応用(1) --- シュードノット構造を含まない場合 DP algorithm for RNA secondary structure prediction --- pseudoknot-free structure case --- 第7回:形式文法とRNA二次構造予測 Formal grammars and RNA structure prediction 第8回:木文法によるRNA二次構造のモデル化 Modeling RNA secondary structure with tree grammars 第9回:木文法の部分クラス Subclasses of Tree Grammars 第10回:木文法の認識アルゴリズム Recognition Algorithms for Tree Grammars 第11回: RNA一分子の平衡状態計算 Equilibrium computation for an RNA molecule 第12回: 最適化問題としてのRNA 分子の干渉問題--- 二次構造レベルでの解析 --- RNA interaction analysis as an optimization problem 第13回: RNA 分子干渉問題を解く最適化アルゴリズムの紹介(1) --- グラフによる構造の数え上げの発想 --- RNA interaction analysis : Enumerating structures using graphs 第14回: RNA 分子干渉問題を解く最適化アルゴリズムの紹介(2) --- グラフ理論を用いた最適化アルゴリズム --- An optimization algorithm using graph theory for analyzing RNA interaction 第15回: RNA 分子干渉問題を解く最適化アルゴリズムの紹介(3) --- ハイパーグラフ理論を用いた最適化アルゴリズム--- An optimization algorithm using hyper-graph theory for analyzing RNA interaction (b)授業の進め方 講義では、例を与えながらアルゴリズムの動作を説明するとともに、アルゴリズムの正しさを理解するために、その正当性の証明にも重点をおいて進める.正しさをきちんと理解することは、応用力をつけるために必須である.講義資料は基本的に英語の資料を用意する.説明は日本語で行う. |
実務経験を活かした 授業内容 (実務経験内容も含む) /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) |
指定された事項に関するレポートの評価などを総合して判断する. 達成目標で述べた1)と2)の達成度が一定の水準以上であれば合格とする. |
オフィスアワー: 授業相談(1,000文字以内) /Office hours(up to 1,000 letters) |
適宜相談に応じるがメールなどてアポイントを取ること。 |
学生へのメッセージ(1,000文字以内) /Message for students(up to 1,000 letters) |
なし NONE |
その他 /Others |
特になし |
キーワード /Keywords |
アラインメント、RNA二次構造、RNA二次構造予測、RNA干渉問題、最適化アルゴリズム Alignment, RNA secondary structure, RNA secondary structure prediction, RNA interaction analysis, optimization algorithm |