アルゴリズム数理Ｂ (N42P)

日本大学理工学部

2015年理工学部シラバス - 数学科

設置情報

科目名	アルゴリズム数理Ｂ
設置学科	数学科	学年	3年
担当者	竹澤　照	履修期	後期
単位	2	曜日時限	木曜2
校舎	駿河台	時間割CD	N42P
クラス

概要

学修到達目標	アルゴリズム表現法と計算量解析法の高度な応用例による学習を通して，問題解決のための手順とコンピュータによってデータ処理を行うときの処理効率の良いデータの蓄え方についての理解を深める。併せてコンピュータの可能性を追求する楽しさを伝えたい。
授業形態及び授業方法	板書およびプロジェクターを中心とした講義形式で行う。なお，演習および実習を随時行う。
履修条件	アルゴリズム数理Aを履修していること。

授業計画

第1回	表の探索（１）：定式化，線形探索アルゴリズム，最大及び平均時間計算量について学び，素朴なアルゴリズムの大切さ，平均値のデータ分布依存性を理解する。
第2回	再帰：再帰的定義（階乗），再帰アルゴリズム（最大公約数），再帰副プログラム及びその実行法について学び，再帰の特徴を理解する。
第3回	表の探索（２）：二分法の原理，二分探索再帰アルゴリズム，再帰方程式，漸近時間計算量，計算量のオーダーについて学び，現実的計算可能性を理解する。
第4回	木：用語，再帰的定義，分節数及び木の分節数，二分木及び多進木，順序木，水準及び木の高さについて学び，木の表現法及び性質を理解する。
第5回	二分木：算術式の記法，逆ポーランド記法の復元アルゴリズム，二分木の走査について学び，コンピュータでの算術式の内部表現及び処理法を理解をする。
第6回	二分探索（１）：定義，木構造，二分探索木の生成アルゴリズムについて学び，動的探索法，再帰データ構造と再帰アルゴリズムとの親和性を理解する。
第7回	二分探索（２）：基本操作(挿入と削除)について学び，二分探索木の扱い及び有用性を理解をする。
第8回	二分探索（３）：二分木の種類，節点数と経路長との関係，平均比較回数，調和数の解析的性質，木の費用と最適な木について学び，二分探索法の高速性を理解する。
第9回	ハッシュ法：原理，ハッシュ関数，衝突，完全最小なハッシュ関数，チェイン法，応用例（名前の相互参照表）について学び，ハッシュ法の最速性，欠点及びその解決法を理解する。
第10回	多倍長整数計算（１）：データ構造，加減算アルゴリズム，桁上げ及び借り処理について学び，コンピュータでの固定小数点算術アルゴリズムを理解する。
第11回	多倍長整数計算（２）：高速乗算アルゴリズムについて学び，高速化手法（分割統治法の再帰的応用）を理解する。
第12回	多倍長実数計算：データ構造，浮動小数点算術アルゴリズムについて学び，高精度計算（円周率）の所要時間を実測し，桁数及びコンピュータ環境依存性を理解する。
第13回	複数個の行列の積（１）：乗算順序の場合の数（カタラン数），素朴な方法による最適な順序，組合せ論的インフレーションについて学び，高速化手法の必要性を理解する。
第14回	複数個の行列の積（２）：最適な順序を求める動的計画法について学び，高速化手法, Ｐ問題及びＮＰ問題を理解する。エピローグ：未解決問題及びアルゴリズムの限界への挑戦。
第15回	平常試験及びその解説。

その他

教科書	特に指定しない。
参考書	D. E. Knuth著／有澤誠，和田英一監訳『Sorting and searching 日本語版（The Art of Computer Programming Vol.3）』アスキー 2006年第1版 R. Sedgewick著／野下浩平他訳『アルゴリズムＣ・新版』近代科学社 2004年第1版竹澤照『データ構造とアルゴリズム』共立出版 1999年第1版 D. E. Knuth他著／有澤誠他訳『コンピュータの数学(Concrete Mathematics)』共立出版 1993年第1版 K. Mehlhorn, P. Sanders著/浅野哲夫訳『アルゴリズムとデータ構造』丸善出版 2012年第1版
成績評価の方法及び基準	演習・実習レポート（40％）及び平常試験（60％）により総合的に評価する。
質問への対応	質問には授業中随時受け付ける。なお授業終了後に教室及び１号館１階講師室（１５：００～１５：３０）でも受け付ける。
研究室又は連絡先	授業中に指示する。
オフィスアワー
学生へのメッセージ	知的好奇心をもって意欲的に講義に臨んで欲しい。

Copyright 2015 Nihon University College of Science and Technology. All rights reserved.