2025年度/1BGA006001

【金2】アルゴリズム設計論 <前期>

本授業は遠隔授業として実施します。各回の授業形態をよく確認して受講してください。 本講義では、モデルとしての汎用性が高くさまざまな分野で必要とされるおもに離散最適化問題（組合せ最適化問題）を対象とし、まず前半では効率的なアルゴリズム設定のための基本技法を復習した上で、固定パラメータ・アルゴリズム、近似アルゴリズム、乱択アルゴリズムなどの高度なアルゴリズムの設計や解析の技法を講義する。つづいて後半では、そのような問題に有効なメタヒューリスティックスを使ったアルゴリズムの理解と、それを応用する方法について講義する。

担当教員氏名

宇野 裕之、本多 克宏

科目ナンバリング

BGAPRI53002-J1 (公大) / TIPRI5713-E1 (府大)

授業管轄部署

情報学研究科

授業形態

講義

開講キャンパス

遠隔用

開講区分

週間授業

科目分類

専攻基礎科目

配当年次

1年 (公大) / 1年 (府大)

注意: 配当年次は学部・学科によって異なる場合があるので、UNIPAで確認してください。

単位数

2単位 (公大) / 2単位 (府大)

注意: 実際の単位数は学部・学科によって異なる場合があるので、必ずUNIPAで確認してください。

到達目標

おもに組合せ最適化問題を対象とし、実践的・応用的な解法（アルゴリズム）を設計・解析できる知識や力を身につける。講義の前半では，はじめにアルゴリズムの設計と解析に関する基本的な事項を復習する．具体的には，貪欲法，動的計画法，分割統治法などの典型的な効率的なアルゴリズムの設計技法を理解し，具体的な例題を用いてそれらの動作を理解し，自分でも簡単な問題に対してそれらの方法を適用してアルゴリズムを設計し，時間計算量などが解析できるようになる．それらにつづき，より高度で現代的な設計技法である固定パラメータ・アルゴリズム、乱択アルゴリズム、近似アルゴリズムなどの理論的を学び，同様にそれらを用いて効率的なアルゴリズムの設計や解析ができるようになる．講義の後半では、おもにヒューリスティックを使った最適化アルゴリズムを理解し、現実的な問題に応用できる力をつける。

各授業回の説明

授業	授業内容	事前・事後の学習内容
第1回	導入：基本的なアルゴリズム設計・解析技法の復習（担当：宇野裕之）	事後学習：講義中に説明されるアルゴリズムの復習や実装など
第2回	固定パラメータ・アルゴリズム（基礎概念）（担当：宇野裕之）	事後学習：講義中に説明されるアルゴリズムの復習や実装など
第3回	固定パラメータ・アルゴリズム（設計技法）（担当：宇野裕之）	事後学習：講義中に説明されるアルゴリズムの復習や実装など
第4回	乱択アルゴリズム（基礎概念）（担当：宇野裕之）	事後学習：講義中に説明されるアルゴリズムの復習や実装など
第5回	乱択アルゴリズム（設計技法）（担当：宇野裕之）	事後学習：講義中に説明されるアルゴリズムの復習や実装など
第6回	近似アルゴリズム（基礎概念）（担当：宇野裕之）	事後学習：講義中に説明されるアルゴリズムの復習や実装など
第7回	近似アルゴリズム（設計技法）（担当：宇野裕之）	事後学習：講義中に説明されるアルゴリズムの復習や実装など
第8回	メタヒューリスティックス（山登り法）（担当：本多 克宏 ）	事後学習：例題プログラムの実行、改良
第9回	メタヒューリスティックス（ホップフィールド・ネットワーク）（担当：本多 克宏 ）	事後学習：例題プログラムの実行、改良
第10回	メタヒューリスティックス（焼きなまし法）（担当：本多 克宏 ）	事後学習：例題プログラムの実行、改良
第11回	メタヒューリスティックス（遺伝的アルゴリズム）（担当：本多 克宏 ）	事後学習：例題プログラムの実行、改良
第12回	メタヒューリスティックス（遺伝的プログラミング）（担当：本多 克宏 ）	事後学習：例題プログラムの実行、改良
第13回	メタヒューリスティックス（アントコロニー最適化）（担当：本多 克宏 ）	事後学習：例題プログラムの実行、改良
第14回	メタヒューリスティックス（フラクタル・カオス）（担当：本多 克宏 ）	事後学習：例題プログラムの実行、改良
第15回	試験
第16回	理解度確認　講評（担当：本多 克宏 ）

事前・事後学習の内容

予習よりも復習に十分な時間を費やすようにしてください．また，講義時間中に出題する問いかけやクイズを，その週のうちに考えてください．

成績評価方法

毎回の講義で，その回の講義内容に関連した簡単なクイズ形式の質問や演習問題を解説する．期末にはそれらをまとめてレポート課題として出題し，そのうち60パーセント以上理解している場合に合格となる．課題内容にはアルゴリズムの設計分野における貪欲法，動的計画法，分割統治法などの典型的な効率的なアルゴリズムの設計技法から，より高度で現代的な設計技法である固定パラメータ・アルゴリズム、乱択アルゴリズム、近似アルゴリズムなどの理論的を含む．講義の到達目標として，貪欲法，動的計画法，分割統治法などの典型的な効率的なアルゴリズムの設計技法を理解し，具体的な例題を用いてそれらの動作を理解し，自分でも簡単な問題に対してそれらの方法を適用してアルゴリズムを設計し，時間計算量などが解析できるようになることを掲げており，少なくともそれらを理解し，具体的な例題を用いてそれらの動作を理解し，自分でも簡単な問題に対してそれらの方法を適用してアルゴリズムを設計し，時間計算量などが解析できるようになることが必要である．

履修上の注意

とくにありません．

教科書

教科書は指定しません．各回の講義開始前までに，その回の講義に必要なレジメ資料をオンラインにて配布する．講義までにそれをダウンロードしておいてください．

Loading...

参考文献

コルメン，ライザーソン，リベスト，シュタイン．「アルゴリズム・イントロダクション」近代科学社　が参考になる．

オフィスアワー

- 外部公開シラバスのためデータがありません / Please use UNIPA syllabus -

教員への連絡方法（メールアドレス等）

- 外部公開シラバスのためデータがありません / Please use UNIPA syllabus -

その他

実施方法 中百舌鳥キャンパス：同期型オンライン