基本情報/Basic Information

開講科目名 ／Course	アルゴリズム論b／THEORY OF ALGORITHM(B)
開講所属 ／Course Offered by	経済学部経営学科／ECONOMICS MANAGEMENT
ターム・学期 ／Term・Semester	2020年度／2020 Academic Year　　秋学期／FALL SEMESTER
曜限 ／Day, Period	金1／Fri 1
開講区分 ／semester offered	秋学期／Fall
単位数 ／Credits	2.0
学年 ／Year	2,3,4
主担当教員 ／Main Instructor	木村　昌史

担当教員情報/Instructor Information

教員名 ／Instructor	教員所属名 ／Affiliation
木村　昌史	経営学科／MANAGEMENT

授業の目的・内容 ／Course Objectives	アルゴリズム論aでは狭い意味での決定的アルゴリズムを扱っているが、アルゴリズム論bではやや広い意味でのコンピュータによる問題解決のアプローチとして、非決定的アルゴリズムを中心に採り上げる。一般に解決が困難な問題に対しては、何らかの処理の適用以前に問題設定に対する正しい理解と分析が必要になる。例としてゲームの必勝法や現象の予測などが挙げられるが、それぞれのルールや条件の正しい設定が必要になることを理解する。そして困難となる要因と適用するアルゴリズムの関係から、問題解決には分析的手法に加えコンピュータ特有の発見的方法やシミュレーションが有効になることを理解する。困難な問題においてはこれらは近似的な方法ではあるものの、十分に実用的な価値を持つことを理解する。また経済・経営分野に関連するアルゴリズムのいくつかの応用例を採り上げる。なおテーマごとのアルゴリズムの理解を深めるために、受講者には課外でのPCによる自習・演習により各種アルゴリズムの実践を体験できるものとする。
授業の形式・方法と履修上の注意 ／Teaching method and Attention the course	オンライン形式の授業(ZoomまたはWebexによる)を行う。 講義形式ではあるが、コンピュータ関連の科目であることから内容の理解を深めるために並行して課外でのPCによる自習・演習を推奨する。各回のテーマに関連したサンプルやデモファイルを配布するので学内や自宅で実行できる環境を準備しておくこと。具体的にはExcelとWebの基本操作程度は行えるものと想定している。また獨協大学のOffice 365の環境も利用できる。
事前・事後学修の内容 ／Before After Study	受講者は事前に授業用Webサイト(manaba)に置かれる講義のレジメとともに、WebのソースやExcelファイルによるサンプルやデモを実行してみて各回の授業のテーマや内容を予習する（1時間）。 授業後にはmanabaに置かれるPDF文書の講義資料を入手することにより復習を行い、内容の理解を深めることができる（2時間）。 また定期的にmanabaに課題が提示されるので指定された期限までに提出のこと。
テキスト1 ／Textbooks1	書籍名 ／Title 内容が多岐に渡るので特に指定しない。 著者 ／Author name 出版社 ／Publisher ISBN ／ISBN その他（任意） ／other
テキスト2 ／Textbooks2	書籍名 ／Title 著者 ／Author name 出版社 ／Publisher ISBN ／ISBN その他（任意） ／other
テキスト3 ／Textbooks3	書籍名 ／Title 著者 ／Author name 出版社 ／Publisher ISBN ／ISBN その他（任意） ／other
参考文献等1 ／References1	書籍名/ｻｲﾄ名 ／Title 著者 ／Author name 出版社/URL ／Publisher ISBN ／ISBN その他（任意） ／other
参考文献等2 ／References2	書籍名/ｻｲﾄ名 ／Title 著者 ／Author name 出版社/URL ／Publisher ISBN ／ISBN その他（任意） ／other
参考文献等3 ／References3	書籍名/ｻｲﾄ名 ／Title 著者 ／Author name 出版社/URL ／Publisher ISBN ／ISBN その他（任意） ／other
評価方法 ／Evaluation	manabaに出題する各回演習への提出分を80％、オンライン授業アンケートによる授業内容の理解度を20%として評価する。
関連科目 ／Related Subjects
備考 ／Notes
到達目標 ／Learning Goal	コンピュータ科学の基礎をなすアルゴリズムに関する専門知識を習得し、これを駆使して様々な問題を処理できるようにする。

回 ／Time	授業計画（主題の設定） ／Class schedule	授業の内容 ／Contents of class	事前・事後学修の内容 ／Before After Study
1	決定的アルゴリズムと非決定的アルゴリズム	決定的アルゴリズムとはアルゴリズムの適用により確定的な結果が求まるものであるが、非決定的アルゴリズムとは問題によっては必ずしも的確な結果が得られないものを指すことを理解する。	事前：公開ビデオ視聴(一部) 事後：公開ビデオ視聴(一部)
2	ゲームにおけるアルゴリズム	ゲームは古くからコンピュータによる処理の典型例として扱われるが、その理由とゲームにおける手順と問題解決とは何かについて理解する。	事前：公開ビデオ視聴(一部) 事後：公開ビデオ視聴(一部)
3	最適配置問題と枝刈り探索	ゲームの手順は多くは木構造のグラフとして表現できる場合が多いが、そのグラフの経路を決めることがゲームの解決になることを理解する。	事前：公開ビデオ視聴(一部) 事後：公開ビデオ視聴(一部)
4	囚人のジレンマとゲームの理論	ノイマンによるゲーム理論の代表的問題である囚人のジレンマの戦略をアルゴリズムとして実行できることを理解する。	事前：公開ビデオ視聴(一部) 事後：公開ビデオ視聴(一部)
5	乱数とモンテカルロ法	乱数の利用が確率を含むゲームや現実問題のモデルに適用できることと応用としてモンテカルロ法について理解する。	事前：公開ビデオ視聴(一部) 事後：公開ビデオ視聴(一部)
6	株価変動の問題とシミュレーション	身近な株価変動の問題をどうとらえるかによって、乱数を用いたシミュレーションによってその様子を再現できることとその意味について理解する。	事前：公開ビデオ視聴(一部) 事後：公開ビデオ視聴(一部)
7	在庫管理の問題とシミュレーション	在庫管理の問題における在庫量の変動が確率的であることから、シミュレーションによる予測と評価の有効性について理解する。	事前：公開ビデオ視聴(一部) 事後：公開ビデオ視聴(一部)
8	待ち行列の問題とシミュレーション	待ち行列は応用範囲も広い問題であることと、客の到着時間と窓口のサービス時間が確率的であることから行列が生じることからシミュレーションによる予測と評価の有効性について理解する。	事前：公開ビデオ視聴(一部) 事後：公開ビデオ視聴(一部)
9	巡回セールスマン問題	困難な問題の典型例として巡回セールスマン問題とは何かを理解し、そのアプローチのために多くのアルゴリズムが存在することを理解する。	事前：公開ビデオ視聴(一部) 事後：公開ビデオ視聴(一部)
10	ナップザック問題	困難な問題の別の例としてナップザック問題を理解し、動的計画法をはじめそのアプローチのためのアルゴリズムを理解する。	事前：公開ビデオ視聴(一部) 事後：公開ビデオ視聴(一部)
11	困難な問題とNP完全問題	困難な問題の分類と巡回セールスマン問題のようなNP完全問題とは何かについてとその計算可能性について理解する。	事前：公開ビデオ視聴(一部) 事後：公開ビデオ視聴(一部)
12	遺伝的アルゴリズム	NP完全問題やナップザック問題のようなNP完全問題にアプローチするアルゴリズムの１つとして遺伝的アルゴリズムについて理解する。	事前：公開ビデオ視聴(一部) 事後：公開ビデオ視聴(一部)
13	現代暗号のアルゴリズム	困難な問題をいわば逆用するしくみとして、現代のネットワークのインフラである公開鍵暗号方式のアルゴリズムについて理解する。	事前：公開ビデオ視聴(一部) 事後：公開ビデオ視聴(一部)
14	AIのしくみとアルゴリズム	現在研究や応用が盛んになっているAIのアルゴリズム的観点と、機械学習のしくみについて理解する。	事前：公開ビデオ視聴(一部) 事後：公開ビデオ視聴(一部)