シラバス参照/View Syllabus |
科目一覧へ戻る/Return to the Course List | 2024/08/29 現在/As of 2024/08/29 |
開講科目名 /Course |
アルゴリズム論b/THEORY OF ALGORITHM(B) |
---|---|
開講所属 /Course Offered by |
経済学部経営学科/ECONOMICS MANAGEMENT |
ターム?学期 /Term?Semester |
2024年度/2024 Academic Year 秋学期/FALL SEMESTER |
曜限 /Day, Period |
月2/Mon 2 |
開講区分 /semester offered |
秋学期/Fall |
単位数 /Credits |
2.0 |
学年 /Year |
2,3,4 |
主担当教員 /Main Instructor |
木村 昌史 |
遠隔授業科目 /Online Course |
- |
教員名 /Instructor |
教員所属名 /Affiliation |
---|---|
木村 昌史 | 経営学科/MANAGEMENT |
授業の目的?内容 /Course Objectives |
アルゴリズム論aでは狭い意味での決定的アルゴリズムを扱っているが、アルゴリズム論bではやや広い意味でのコンピュータによる問題解決のアプローチとして、非決定的アルゴリズムを中心に採り上げる。一般に解決が困難な問題に対しては、何らかの処理の適用以前に問題設定に対する正しい理解と分析が必要になる。例としてゲームの必勝法や現象の予測などが挙げられるが、それぞれのルールや条件の正しい設定が必要になることを理解する。そして困難となる要因と適用するアルゴリズムの関係から、問題解決には分析的手法に加えコンピュータ特有の発見的方法やシミュレーションが有効になることを理解する。困難な問題においてはこれらは近似的な方法ではあるものの、十分に実用的な価値を持つことを理解する。また経済?経営分野に関連するアルゴリズムのいくつかの応用例を採り上げる。なおテーマごとのアルゴリズムの理解を深めるために、受講者には課外でのPCによる自習?演習により各種アルゴリズムの実践を体験できるものとする。 学科専門科目として、情報学におけるハードウェア、ソフトウェア、ネットワークにわたる基幹をなす考え方を理解し、コンピュータを手段とした問題解決を発想できる能力を身につける(DP)。 また教職「情報」取得に必要な教科の指導法を修得するための教職関連科目でもある(AP)。 コンピュータ基礎科目を学んだ後、さらに広く情報学を応用するための基礎となることを目的とする。 |
||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
授業の形式?方法と履修上の注意 /Teaching method and Attention the course |
?講義形式ではあるが、コンピュータ関連の科目であることから受講者には内容の理解を深めるために並行して課外でのPCによる自習?演習を推奨する。 ?各回のテーマに関連したサンプルやデモファイルを配布するので学内や自宅で実行できる環境を準備しておくこと。具体的にはExcelとWebの基本操作程度は行えるものと想定している。 ?各回の課題の回答例などは次回以降の授業時またはWebにて提示する。 |
||||||||||
事前?事後学修の内容 /Before After Study |
受講者は事前に授業用Webサイト(またはPortaⅡ)に置かれる講義のレジメやWebのソースを参考にし、またExcelファイルによるサンプルやデモの指示がある場合もあるので、これを実行してみて各回の授業のテーマや内容を予習する(1時間)。 授業後には同所に置かれるPDF文書の講義資料を入手して復習を行い、内容の理解を深めることができる(2時間)。 また定期的にWeb(manabaなど)に各回の演習課題が提示されるので指定された期限までに提出のこと。 |
||||||||||
テキスト1 /Textbooks1 |
|
||||||||||
テキスト2 /Textbooks2 |
|
||||||||||
テキスト3 /Textbooks3 |
|
||||||||||
参考文献等1 /References1 |
|
||||||||||
参考文献等2 /References2 |
|
||||||||||
参考文献等3 /References3 |
|
||||||||||
評価方法 /Evaluation |
試験または前半?後半レポートを60%、各回の確認演習課題への提出分を40%として評価する。 |
||||||||||
関連科目 /Related Subjects |
コンピュータ入門a コンピュータ入門b コンピュータ?アーキテクチャ 情報通信ネットワークa 情報通信ネットワークb 情報と職業 |
||||||||||
備考 /Notes |
|||||||||||
到達目標 /Learning Goal |
コンピュータ科学の基礎をなすアルゴリズムに関する専門知識を習得し、これを駆使して様々な問題を処理できるようにする。 |
回 /Time |
授業計画(主題の設定) /Class schedule |
授業の内容 /Contents of class |
事前?事後学修の内容 /Before After Study |
---|---|---|---|
1 | 決定的アルゴリズムと非決定的アルゴリズム | 決定的アルゴリズムとはアルゴリズムの適用により確定的な結果が求まるものであるが、非決定的アルゴリズムとは問題によっては必ずしも的確な結果が得られないものを指すことを理解する。 | |
2 | ゲームにおけるアルゴリズム | ゲームは古くからコンピュータによる処理の典型例として扱われるが、その理由とゲームにおける手順と問題解決とは何かについて理解する。 | |
3 | 最適配置問題と枝刈り探索 | ゲームの手順は多くは木構造のグラフとして表現できる場合が多いが、そのグラフの経路を決めることがゲームの解決になることを理解する。 | |
4 | 囚人のジレンマとゲームの理論 | ノイマンによるゲーム理論の代表的問題である囚人のジレンマの戦略をアルゴリズムとして実行できることを理解する。 | |
5 | 乱数とモンテカルロ法 | 乱数の利用が確率を含むゲームや現実問題のモデルに適用できることと応用としてモンテカルロ法について理解する。 | |
6 | 確率的株価変動のシミュレーション | 身近な株価変動の問題をどうとらえるかによって、乱数を用いたシミュレーションによってその様子を再現できることとその意味について理解する。 | |
7 | 在庫管理の問題とシミュレーション | 在庫管理の問題における在庫量の変動が確率的であることから、シミュレーションによる予測と評価の有効性について理解する。 | |
8 | 待ち行列の問題とシミュレーション | 待ち行列は応用範囲も広い問題であることと、客の到着時間と窓口のサービス時間が確率的であることから行列が生じることからシミュレーションによる予測と評価の有効性について理解する。 | |
9 | 巡回セールスマン問題 | 困難な問題の典型例として巡回セールスマン問題とは何かを理解し、そのアプローチのために多くのアルゴリズムが存在することを理解する。 | |
10 | 遺伝的アルゴリズム | 巡回セールスマン問題やナップザック問題のようなNP完全問題にアプローチするアルゴリズムの1つとして遺伝的アルゴリズムについて理解する。 | |
11 | 現代暗号のアルゴリズム | 困難な問題をいわば逆用するしくみとして、現代のネットワークのインフラである公開鍵暗号方式のアルゴリズムについて理解する。 | |
12 | RSA暗号のアルゴリズム | 公開鍵暗号方式で一般的なRSA暗号のアルゴリズムについて簡単な例から理解する。また他の暗号の例も紹介する。 | |
13 | セルオートマトンと複雑系のアルゴリズム | セルオートマトンや複雑系との問題をアルゴリズム的観点から理解する。 | |
14 | AIのしくみと秋学期まとめ | 現在研究や応用が盛んになっているAIのアルゴリズム的観点と、機械学習のしくみについて理解する。秋学期テーマについて総括する。 |