シラバス参照
|
シラバス参照
|
| 講義概要/Course Information |
| 科目基礎情報/General Information |
| 授業科目名 /Course title (Japanese) |
応用アルゴリズム論 | ||
|---|---|---|---|
| 英文授業科目名 /Course title (English) |
Applied Algorithms | ||
| 科目番号 /Code |
|||
| 開講年度 /Academic year |
2025年度 | 開講年次 /Year offered |
全学年 |
| 開講学期 /Semester(s) offered |
後学期 | 開講コース・課程 /Faculty offering the course |
博士前期課程 |
| 授業の方法 /Teaching method |
講義 | 単位数 /Credits |
2 |
| 科目区分 /Category |
大学院専門教育科目 - 専門科目Ⅰ | ||
| 開講類・専攻 /Cluster/Department |
情報・ネットワーク工学専攻 | ||
| 担当教員名 /Lecturer(s) |
小林 聡 | ||
| 居室 /Office |
西9-738 | ||
| 公開E-mail |
kobayashi.satoshi@uec.ac.jp | ||
| 授業関連Webページ /Course website |
Google classroom にて詳細情報を記載する（遠隔授業に関する項目を参照のこと） | ||
| 更新日 /Last update |
2025/03/21 11:45:18 | 更新状況 /Update status |
公開中 /now open to public |
| 講義情報/Course Description |
| 主題および 達成目標（2,000文字以内） /Themes and goals（up to 2,000 letters） |
本講義では，生物情報学領域へのアルゴリズム論の応用など、アルゴリズム論の応用的な側面を重視して，先進的な内容を講義する。以下を達成目標とする。 １) 講義で取り扱う各応用問題に対するアルゴリズムの動作と正当性およびその計算量の解析結果を理解する． ２) 講義で紹介するアルゴリズムの設計手法の原理を理解し，新しい類似問題への適用ができる能力を身に付ける． This lecture provides an advanced theory of algorithms which are applied to the problems related to biology, biophysics, bioinformatics, etc. The goals to be achieved are as follows: 1) to understand the correctness and the analysis of time and space complexity of the algorithms given in the lecture, 2) to understand the principle for designing algorithms given in the lecture, and to develop the ability to apply it to new similar problems. |
|---|---|
| 前もって履修 しておくべき科目（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） |
資料を配布する． Lecture slides are provided at the google classroom. |
| 授業内容と その進め方（2,000文字以内） /Course outline and weekly schedule（up to 2,000 letters） |
英語タイプ：Ca Type Ca: Japanese-based course with English materials (a) 授業内容 Lecture Contents 第１回：導入および分子生物学概観 Introduction to molecular biology 第２回：遺伝子配列のペアワイズアラインメント問題とは？ Pairwise alignment problem 第３回：ペアワイズアラインメント問題への動的計画法の応用 DP algorithms for pairwise alignment problem 第４回：RNA 二次構造予測問題とは？ RNA secondary structure prediction problem 第５回：RNA 二次構造予測問題への動的計画法の応用(1) --- 線形構造の場合 DP algorithm for RNA secondary structure prediction --- linear structure case --- 第６回：RNA 二次構造予測問題への動的計画法の応用(1) --- シュードノット構造を含まない場合 DP algorithm for RNA secondary structure prediction --- pseudoknot-free structure case --- 第７回：形式文法とRNA二次構造予測 Formal grammars and RNA structure prediction 第８回：木文法によるRNA二次構造のモデル化 Modeling RNA secondary structure with tree grammars 第９回：木文法の部分クラス Subclasses of Tree Grammars 第１０回：木文法の認識アルゴリズム Recognition Algorithms for Tree Grammars 第１１回： RNA一分子の平衡状態計算 Equilibrium computation for an RNA molecule 第１２回： 最適化問題としてのRNA 分子の干渉問題--- 二次構造レベルでの解析 --- RNA interaction analysis as an optimization problem 第１３回： RNA 分子干渉問題を解く最適化アルゴリズムの紹介(1) --- グラフによる構造の数え上げの発想 --- RNA interaction analysis : Enumerating structures using graphs 第１４回： RNA 分子干渉問題を解く最適化アルゴリズムの紹介(2) --- グラフ理論を用いた最適化アルゴリズム --- An optimization algorithm using graph theory for analyzing RNA interaction 第１５回： RNA 分子干渉問題を解く最適化アルゴリズムの紹介(3) --- ハイパーグラフ理論を用いた最適化アルゴリズム--- An optimization algorithm using hyper-graph theory for analyzing RNA interaction （ｂ）授業の進め方 The description how the class will proceed 講義では、例を与えながらアルゴリズムの動作を説明するとともに、アルゴリズムの正しさを理解するために、その正当性の証明にも重点をおいて進める．正しさをきちんと理解することは、応用力をつけるために必須である．講義資料は基本的に英語の資料を用意する．説明は日本語で行う． The explanation of the correctness of the algorithms is focused in this lecture, where we give examples to help understand how the algorithms and the mathematical models behind them effectively work. |
| 実務経験を活かした 授業内容 (実務経験内容も含む) /Course content utilizing practical experience |
|
| 授業時間外の学習 （予習・復習等）（1,000文字以内） /Preparation and review outside class（up to 1,000 letters） |
講義されたアルゴリズムの実装などを行って理解を深めることが好ましい。 It is better to implement the algorithms given in the lecture in order to understand deeply about their behaviors. |
| 成績評価方法 および評価基準 （最低達成基準を含む） （1,000文字以内） /Evaluation and grading （up to 1,000 letters） |
講義期間中に実施される試験および、レポート課題によって評価する． 達成目標で述べた１)と２)の達成度が一定の水準以上であれば合格とする． Evaluation is based on the exams and report assignments. Students will pass this class if the achievement levels of the goals (1) and (2) are above the acceptable threshold. |
| オフィスアワー： 授業相談（1,000文字以内） /Office hours（up to 1,000 letters） |
適宜相談に応じるがメールなどてアポイントを取ること。 Any time, but appointments by e-mails are needed. |
| 学生へのメッセージ（1,000文字以内） /Message for students（up to 1,000 letters） |
なし NONE |
| その他 /Others |
特になし NONE |
| キーワード /Keywords |
アラインメント、RNA二次構造、RNA二次構造予測、RNA干渉問題、最適化アルゴリズム Alignment, RNA secondary structure, RNA secondary structure prediction, RNA interaction analysis, optimization algorithm |