山口大学教務システム - 3261420760-アルゴリズム特論

開講年度	開講学部等
2025	大学院創成科学研究科（博士前期）
開講学期	曜日時限	授業形態	AL（アクティブ・ラーニング）ポイント
前期後半	火3～4	講義	1.0
時間割番号	科目名[英文名]			使用言語	単位数
3261420760	アルゴリズム特論			日本語	1
担当教員（責任）[ローマ字表記]					メディア授業
荒木　徹也[ARAKI Tetsuya]					ー
担当教員[ローマ字表記]
荒木　徹也　[ARAKI Tetsuya]
特定科目区分		対象学生		対象年次
ディプロマ・ポリシーに関わる項目			カリキュラムマップ(授業科目とDPとの対応関係はこちらから閲覧できます)

授業の目的と概要

現実社会において現れる様々な問題に対するアルゴリズムの基本的な設計技法について理解し，計算量・計算困難性の面から効率的なアルゴリズムを設計する力を身に付ける．

授業の到達目標


・アルゴリズムの代表的な設計手法について理解する．・計算困難な問題に対する発見的手法や近似解法について理解する．

授業計画

【全体】

前半は，アルゴリズムの評価基準としての計算量や代表的な設計手法について講義する．
後半は，具体的な問題に対して計算困難性の側面を交えてどのようにして効率的なアルゴリズムが実現されているかについて講義する．

	項目	内容	授業時間外学習	備考

第1回	計算量と計算複雑性	漸近記法クラスPとクラスNP	授業中に指示した内容の復習 (学修時間の目安:４時間以上)

第2回

動的計画法

部分和問題
ナップサック問題

授業中に指示した内容の復習
(学修時間の目安:４時間以上)

第3回

ヒューリスティック

局所探索法
焼きなまし法
遺伝的アルゴリズム

授業中に指示した内容の復習
(学修時間の目安:４時間以上)

第4回

近似アルゴリズム

定数近似アルゴリズム
多項式近似スキーム

授業中に指示した内容の復習
(学修時間の目安:４時間以上)

第5回

クラスタリング

ウォード法
k-means
DBSCAN

授業中に指示した内容の復習
(学修時間の目安:４時間以上)

第6回

マッチング・ネットワークフロー

ゲール・シャープレー法
フォード・ファルカーソン法
エドモンズ・カープ法

授業中に指示した内容の復習
(学修時間の目安:４時間以上)

第7回

グラフ

ハミルトン閉路
最小全域木

授業中に指示した内容の復習
(学修時間の目安:４時間以上)

第8回

期末試験

演習問題の見直しを中心に４時間以上学習すること

※AL（アクティブ・ラーニング）欄に関する注
・授業全体で、AL（アクティブ・ラーニング）が占める時間の割合を、それぞれの項目ごとに示しています。
・A〜Dのアルファベットは、以下の学修形態を指しています。
【A：グループワーク】、【B：ディスカッション・ディベート】、【C：フィールドワーク（実験・実習、演習を含む）】、【D：プレゼンテーション】

A: --%　B: --%　C: 10%　D: --%

成績評価法

出席は欠格条件とし，２回以上の欠席は欠格とします．
期末試験100％

教科書にかかわる情報

備考

授業に関する資料を随時配布する．

参考書にかかわる情報

参考書	書名	アルゴリズムとデータ構造 : 基礎のツールボックス				ISBN	9784621061879
参考書	著者名	K. メールホルン, P. サンダース著 ; 浅野哲夫訳 ; シュプリンガー・ジャパン編	出版社	丸善出版				出版年	2012

参考書	書名	計算困難問題に対するアルゴリズム理論 : 組合せ最適化・ランダマイゼーション : 近似・ヒューリスティクス				ISBN	9784621065488
参考書	著者名	J.ホロムコヴィッチ著 ; 和田幸一, 増澤利光, 元木光雄訳	出版社	丸善出版				出版年	2012

備考

メッセージ

キーワード

アルゴリズム，計算量，ヒューリスティック，グラフ

持続可能な開発目標（SDGs）

(教育)すべての人に包摂的かつ公正な質の高い教育を確保し、生涯学習の機会を促進する。

(インフラ、産業化、イノベーション)強靱（レジリエント）なインフラ構築、包摂的かつ持続可能な産業化の促進及びイノベーションの推進を図る。

メディア授業