徳島大学 教育・研究者情報データベース(EDB)

Education and Research Database (EDB), Tokushima University

徳島大学ウェブサイトへのリンク

授業概要: 2006/数理情報処理特論

ヘルプを読む

「授業概要」(授業概要のリスト)は,授業の概要を登録するテーブルです. (この情報が属するテーブルの詳細な定義を見る)

  • 項目名の部分にマウスカーソルを置いて少し待つと,項目の簡単な説明がツールチップ表示されます.

この情報をEDB閲覧画面で開く

EID
129650
EOID
581461
Map
0
LastModified
2011年4月11日(月) 17:58:10
Operator
大家 隆弘
Avail
TRUE
Censor
0
Owner
[教務委員会委員長]/[徳島大学.人間·自然環境研究科]
Read
継承
Write
継承
Delete
継承
種別 必須 人間・自然環境研究科 (授業概要)
入学年度 必須 西暦 2006年 (平成 18年)
名称 必須 (日) 数理情報処理特論 / (読) すうりじょうほうしょりとくろん
コース 必須
  1. 2006/[徳島大学.人間·自然環境研究科.自然環境専攻]/選択科目 数理科学/[修士課程]
担当教員 必須
  1. 蓮沼 徹([徳島大学.大学院社会産業理工学研究部.理工学域.数理科学系.数理情報分野]/[徳島大学.理工学部.理工学科.応用理数コース.数理情報講座])
    肩書 任意
単位 必須 2
目的 必須

(日) 多くの組合せ最適化問題がNP困難(即ち最適解を求める効率のよいアルゴリズムを見つけることは期待できないと信じられている)であることが知られている.このような最適化問題に対して,最適解ではなく近似解を効率よく求めるというアプローチがある.本講義では近似アルゴリズムの基礎について解説する.

概要 必須

(日) 近似アルゴリズム

キーワード 推奨
先行科目 推奨
関連科目 推奨
注意 任意
目標 必須
  1. (日) NP困難性といった近似アルゴリズムの背景の理解,及び近似アルゴリズムの設計手法,近似クラスについて理解する.

計画 必須
  1. (日) アルゴリズムの設計と解析(1)

  2. (日) アルゴリズムの設計と解析(2)

  3. (日) アルゴリズムの設計と解析(3)

  4. (日) 計算量クラス

  5. (日) 帰着可能性

  6. (日) 最適化問題の計算量(1)

  7. (日) 最適化問題の計算量(2)

  8. (日) 近似アルゴリズムの設計手法(1):グリーディ法

  9. (日) 近似アルゴリズムの設計手法(2):ローカルサーチ

  10. (日) 近似アルゴリズムの設計手法(3):線形計画法

  11. (日) 近似アルゴリズムの設計手法(4):動的計画法

  12. (日) 近似の精度(1)

  13. (日) 近似の精度(2)

  14. (日) 近似クラス(1):APX

  15. (日) 近似クラス(2):PTAS

  16. (日) 近似クラス(3):FPTAS

評価 必須

(日) 授業への取り組み状況やレポート等により総合的に評価する.

再評価 必須
教科書 必須
  1. (日) 参考書:G.Ausiello et al., Complexity and Approximation, Springer 1999

  2. (日) 参考書:V.V.Vazirani, Approximation Algorithms, Springer 2001

参考資料 推奨
URL 任意
連絡先 推奨
  1. 蓮沼 徹([徳島大学.大学院社会産業理工学研究部.理工学域.数理科学系.数理情報分野]/[徳島大学.理工学部.理工学科.応用理数コース.数理情報講座])
    オフィスアワー 任意

    (日) オフィス·アワー 金曜日 9·10 講時

科目コード 推奨
備考 任意