【授業の目的】
組み合わせ問題を解くアルゴリズムとして様々なものが提案されている．本授業では，それらのアルゴリズムを理解したうえで，実際に計算機上で実装できることを目的とする．
【授業の到達目標】
・アルゴリズムの重要性を理解できる。
・各種組合せ最適化アルゴリズムを理解できる．
・コンピュータ演習を通して各種組合せ最適化アルゴリズムを適切に適用できる．
【授業概要（キーワード）】
組合せ最適化，分枝限定法，焼きなまし法，遺伝的アルゴリズム，学生主体型授業
【学生主体型授業（アクティブラーニング）について】
D-1．演習、実習、実験等を行う機会がある。：51～75％
【科目の位置付け】
この授業はデータサイエンスに関する高度な専門知識の習得を目的とするものである（理工学研究科（理学系）ディプロマポリシー(2)およびカリキュラムポリシー(4)）．
【SDGs（持続可能な開発目標）】
09.産業と技術革新の基盤をつくろう
【授業計画】
・授業の方法
その日のテーマについて解説した後，計算機演習を中心に授業を行う．
・日程
授業計画
第１回：組合せ最適化とは何か？ 組合せ最適化の概念の説明．
第２回：具体例を解く．全探索とその問題点．
第３回：グリーディアルゴリズム．
第４回：分枝限定法．
第５回：分枝限定法のコンピュータ演習（部分和問題）
第６回：分枝限定法のコンピュータ演習（ナップサック問題）
第７回：焼きなまし法
第８回：焼きなまし法のコンピュータ演習（ナップサック問題）
第９回：焼きなまし法のコンピュータ演習（巡回セールスマン問題）
第１０回：遺伝的アルゴリズムの概略
第１１回：遺伝的アルゴリズムの詳細（コード化，適応度評価）
第１２回：遺伝的アルゴリズムの詳細（選択，交叉，突然変異）
第１３回：遺伝的アルゴリズムのコンピュータ演習（ナップサック問題）
第１４回：遺伝的アルゴリズムのコンピュータ演習（巡回セールスマン問題：コード化の検討）
第１５回：遺伝的アルゴリズムのコンピュータ演習（巡回セールスマン問題：計算機実験）
【学習の方法・準備学修に必要な学修時間の目安】
・受講のあり方
アルゴリズムを単に実装するだけでなく，「なぜうまく動くのか？」といったアルゴリズムの仕組みをしっかりと理解するように努めてください．
・授業時間外学習（予習・復習）のアドバイス
プログラミングは「習うより慣れよ」とよく言われます．時間外にできるだけ多くのプログラムを書くようにしてください．授業中に取り組んだ課題を改良する等の自主学習を行うようにしてください。
【成績の評価】
・基準
・アルゴリズムの重要性を理解しているか．
・各種組合せ最適化アルゴリズムを理解できているか．
・コンピュータ演習を通して各種組合せ最適化アルゴリズムを適切に適用できるか．
・方法
理解度および応用力を確認するためのコンピュータ演習課題のレポート(100%)により評価する．
【テキスト・参考書】
必要に応じて授業中に資料を配布します．
また，サンプルコードをwebクラスにて配布します．
【その他】
・学生へのメッセージ
計算機実習が中心の授業です．できるだけ多くのプログラムを書いて，慣れるようにしてください．
・オフィス・アワー
授業時間外に学生の質問に答える「オフィス・アワー」は中西研究室（地教2号館4階）において，原則毎日昼休み（12:10～12:50）としますが，これに限らず在室しているときは随時対応します．
会議や出張等で不在にすることもあるため，確実に面談したい場合は事前に予約をお願いします．連絡先は，初回の授業でお知らせします．
|