シラバス参照
|
シラバス参照
|
| 講義概要/Course Information |
| 科目基礎情報/General Information |
| 授業科目名 /Course title (Japanese) |
アルゴリズム特論 | ||
|---|---|---|---|
| 英文授業科目名 /Course title (English) |
Topics on Algorithms | ||
| 科目番号 /Code |
|||
| 開講年度 /Academic year |
2016年度 | 開講年次 /Year offered |
全学年 |
| 開講学期 /Semester(s) offered |
後学期 | 開講コース・課程 /Faculty offering the course |
博士前期課程、博士後期課程 |
| 授業の方法 /Teaching method |
講義 | 単位数 /Credits |
2 |
| 科目区分 /Category |
大学院専門教育科目 - 専門科目Ⅱ | ||
| 開講類・専攻 /Cluster/Department |
情報・ネットワーク工学専攻 | ||
| 担当教員名 /Lecturer(s) |
村尾 裕一 | ||
| 居室 /Office |
西9-801 | ||
| 公開E-mail |
murao at cs.uec.ac.jp | ||
| 授業関連Webページ /Course website |
www.edu.cc.uec.ac.jp/cs/lecture/AlgsSN/ | ||
| 更新日 /Last update |
2016/03/08 15:37:16 | 更新状況 /Update status |
公開中 /now open to public |
| 講義情報/Course Description |
| 主題および 達成目標（2,000文字以内） /Themes and goals（up to 2,000 letters） |
各種の代数的応用アルゴリズムでは、算術演算をはじめとした基本演算において、代数的に裏付けられた正確な計算法と効率よく実現する技法が必要となる。本科目では、準数値アルゴリズムと呼ばれる数値処理に準ずる代数的アルゴリズムを主体として、これらに関する代表的な話題と実装上必要となるソフトウェア技法を講義し、併せて、メモリ管理・並列処理など、具体的なソフトウェアへの実装法についてもする。数式の計算や準数値的な処理で用いられる基本的なアルゴリズムを学び、また、それらにおける基本的な考え方を理解することが目標である。 |
|---|---|
| 前もって履修 しておくべき科目（1,000文字以内） /Prerequisites（up to 1,000 letters） |
（特になし） |
| 前もって履修しておくこ とが望ましい科目（1,000文字以内） /Recommended prerequisites and preparation（up to 1,000 letters） |
（特になし） |
| 教科書等（1,000文字以内） /Course textbooks and materials（up to 1,000 letters） |
資料を配布する。 教科書は指定しない。 参考書： ・D.E.Knuth: Seminumerical Algorithms, Third Edition. The Art of Computer Programming, Vol.2. Addison-Wesley, 1997. ・有澤 誠，和田英一 ほか 訳：The Art of Computer Programming (2) 日本語版 Seminumerical algorithms．ASCII Addison Wesley programming series. アスキー，2004． ・J.von zur Gathen and J.Gerhard: Modern Computer Algebra, 3rd Ed.. Cambridge University Press, 2013. ・K.O.Geddes, S.R.Czapor and G.Labahn: Algorithms for Computer Algebra. Kluwer Academic Publishers, 1992. ・J.H.Davenport, Y.Siret and E.Tournier: Computer Algebra, Systems and algorithms for algebraic computation, Academic Press, 1988. |
| 授業内容と その進め方（2,000文字以内） /Course outline and weekly schedule（up to 2,000 letters） |
多倍長整数の表現と演算、最大公約数、中国剰余定理、基数変換、多項式の表現と簡約化、多項式の算術演算と最大公約因子の計算、多項式計算における高速アルゴリズム、多項式の補間、多項式の因数分解、行列の演算、代数方程式系の解法などの基本を学び、応用問題や最新の話題（グレブナ基底、量限定子除去法など）のいくつかを学ぶ。これらを通して、数式の計算や準数値的な処理で用いられる基本的なアルゴリズムを学び、また、それらにおける基本的な考え方とアルゴリズムの設計法を理解する。 第 1回 科目ガイダンス：扱う題材の紹介、関連ソフトウェアの紹介、歴史 第 2回 数式の表現と計算：計算例、多倍長整数と算術演算、 第 3回 多倍長整数：算術演算、最大公約数と色々なアルゴリズム 第 4回 多項式の表現と算術演算 第 5回 モジュラー算法(1)：多項式剰余列と式の膨張、法演算とRSA暗号への応用 第 6回 モジュラー算法(2)：多項式の最大公約因子、中国剰余定理ｑ 第 7回 モジュラー算法(3)：多項式補間、多変数多項式のためのモジュラー算法、 第 8回 多項式計算のための漸近的高速アルゴリズム：高速乗算法、高速フーリエ変換とKaratsuba算法、多項式除算、多項式の多点評価 第 9回 多項式の決定：多変数多項式補間、p進近似、Newton反復とHensel構成 第10回 多項式因数分解(1)：無平方分解、Berlekampアルゴリズム 第11回 多項式因数分解(2)：次数別因数分解、同次数因数分解 第12回 行列の計算：消去法と式の膨張、Bareissのアルゴリズム、高速乗算法 第13回 行列の計算：行列式の計算、線形方程式の解法 第14回 最近の話題の紹介：連立代数方程式の解法とグレブナ基底、量限定子除去など 第15回 まとめ |
| 実務経験を活かした 授業内容 (実務経験内容も含む) /Course content utilizing practical experience |
|
| 授業時間外の学習 （予習・復習等）（1,000文字以内） /Preparation and review outside class（up to 1,000 letters） |
（特になし） 自身の研究内容との関連を検討するとよいでしょう。 |
| 成績評価方法 および評価基準 （最低達成基準を含む） （1,000文字以内） /Evaluation and grading （up to 1,000 letters） |
月に１回程度課す練習問題のレポートにより評価する。 |
| オフィスアワー： 授業相談（1,000文字以内） /Office hours（up to 1,000 letters） |
水3～4限＠西9-801。この時間に都合が付かない場合には、メールや 電話などにより別途アポイントメントを取ること。。 |
| 学生へのメッセージ（1,000文字以内） /Message for students（up to 1,000 letters） |
講義の内容は暗号理論の基礎も含み、数学っぽい内容になりますが、それを題材としてどのように実装するのか考えてみましょう。 また、講義内容は理論的に順序立てて話を進めて行きますが、並列処理やインターネットでの数式の利用法など実際的な話題についてもふれていきます。 数学や理論だけでは現実の問題を処理することはできません。しかし、闇雲に処理をするだけでは解けないこともあります。情報処理をスマートにやるには理論と実践の両輪が必要です。 |
| その他 /Others |
（特になし） |
| キーワード /Keywords |
準数値算法、数式処理、多倍長整数、多項式、多項式因数分解、多項式演算、漸近的高速アルゴリズム |