シラバス(講義概要)データベース

シラバス

授業科目名	年度	学期	開講曜日・時限	学部・研究科など	担当教員	教員カナ氏名	配当年次	単位数
乱択アルゴリズム	2025	後期	水3	理工学研究科博士課程前期課程	白髪　丈晴	シラガ　タケハル	1年次配当	2

科目ナンバー

SG-IG5-8C52

履修条件・関連科目等

授業で使用する言語

日本語

授業で使用する言語（その他の言語）

授業の概要

乱択は複数のアルゴリズム設計において重要な役割を果たす操作であり, 巧妙に乱択操作を組み合わせた効率的なアルゴリズムが数多く設計されている. 本講義では代表的な乱択アルゴリズムとその解析を通し, アルゴリズム設計における乱択の威力に迫る.

科目目的

アルゴリズム設計においてどのように乱択が用いられているかを複数の具体例を通し学ぶ. また, 乱択操作の帰結としてどの程度の時間でどのような出力が生じるかを確率の言葉で議論出来るようになることを目指す.

到達目標

代表的な乱択アルゴリズムを理解し, 設計が出来る. また, その性能を理論的に評価が出来る. それらを通し, 代表的な解析技法を理解する.

授業計画と内容

第1回乱択アルゴリズムの基礎
第2回クイックソート
第3回逐次構成法
第4回標本乱択の基礎
第5回標本乱択の応用
第6回最小全域木
第7回数直線上のランダムウォーク
第8回ランダムウォークとSAT
第9回マルコフ連鎖と定常分布
第10回既約性と定常分布の存在性・一意性
第11回非周期性と定常分布への収束性
第12回混交時間と乱択近似のフレームワーク
第13回乱択近似数え上げ
第14回投票者モデル

授業時間外の学修の内容

授業終了後の課題提出

授業時間外の学修の内容（その他の内容等）

授業時間外の学修に必要な時間数／週

・毎週１回の授業が半期（前期または後期）または通年で完結するもの。１週間あたり４時間の学修を基本とします。
・毎週２回の授業が半期（前期または後期）で完結するもの。１週間あたり８時間の学修を基本とします。

成績評価の方法・基準

種別	割合（％）	評価基準
レポート	50	主に講義内で扱った代表的な乱択アルゴリズムの理論解析が出来るかどうかで評価する.
平常点	50	講義内で講義内容に関する小課題を与え, その解答状況によって評価する.

成績評価の方法・基準（備考）

課題や試験のフィードバック方法

授業時間内で講評・解説の時間を設ける／授業時間に限らず、manabaでフィードバックを行う

課題や試験のフィードバック方法（その他の内容等）

アクティブ・ラーニングの実施内容

実施しない

アクティブ・ラーニングの実施内容（その他の内容等）

授業におけるICTの活用方法