生物情報学基礎論I

ガイダンス　（バイオインフォマティクスとは何か）[有田]
1. フィボナッチ数列
2. O記法
アルゴリズムと計算量　（計算量の記法、アルゴリズムの定義）[有田]
1. チューリング機械
2. PとNP
3. クックの定理　（← 試験範囲外）
~~分子生物学の基礎　（配列情報と生物学の関係）~~[有田]
全解探索　（制限酵素マッピング、モチーフ探索）[有田]
教科書にある全解探索の見積もり方法を理解しておきましょう。
1. 制限酵素マッピング
2. モチーフ発見
貪欲アルゴリズム　（ゲノムリアレンジメント、リバーサル）[笠原]
動的計画法　（編集距離とアライメント、スコア行列）[笠原]
動的計画法その２　（各種アライメント、最適化への応用）[笠原]
分割統治法　（ブロックアライメント）[木立]
グラフアルゴリズム　（ハミルトン経路、タンパク質アラインメント）[笠原]
組み合わせパターンマッチング　（ハッシュ、接尾辞木、接尾辞行列）[笠原]
クラスタリングと系統樹　（系統樹の構築と最適化の基準）[木立]
隠れマルコフモデル　（ＨＭＭ，ＨＭＭアライメント）[木立]
乱択アルゴリズム　（ギブスサンプラー）[木立]

教科書

出席及び筆記試験。試験問題は授業を担当する各先生が作成します。

２０１０年度の試験日は、２月２８日です。（１４：４０スタート） (last updated 1/28)

有田部分は、テキストに載っている簡単な事項に加え、授業内で解説した本ウェブサイト上の内容から出題します。ただし、Cookの定理の詳細と、授業で説明していないのにウェブ上で説明されている事項（例えばチューリング機械の等価性）に関する出題はありません。

４年生の人で卒業単位の判定が２月上旬になる場合、以下の問題を解いたレポートを有田まで送ってください。単位の判定に間に合うように成績を評価します。

Problem 5.17

Problem 6.28

Problem 8.13

Problem 9.9

Problem 10.14