シラバス参照

講義概要/Course Information

2020/04/28 現在

科目基礎情報/General Information

授業科目名 /Course title (Japanese)	アルゴリズム特論
英文授業科目名 /Course title (English)	Topics on Algorithms
科目番号 /Code
開講年度 /Academic year	2020年度	開講年次 /Year offered	全学年
開講学期 /Semester(s) offered	後学期	開講コース・課程 /Faculty offering the course	博士前期課程、博士後期課程
授業の方法 /Teaching method	講義	単位数 /Credits	2
科目区分 /Category	大学院専門教育科目 - 専門科目Ⅱ
開講学科・専攻 /Cluster/Department	情報・ネットワーク工学専攻
担当教員名 /Lecturer(s)	村尾　裕一
居室 /Office	西9-801
公開E-Mail /e-mail	murao at mura.cs.uec.ac.jp
授業関連Webページ /Course website	（未定）
更新日 /Last updated	2020/02/28 02:23:34	更新状況 /Update status	公開中 /now open to public

講義情報/Course Description

主題および 達成目標 /Topic and goals	各種の代数的応用アルゴリズムでは、算術演算をはじめとした基本演算において、代数的に裏付けられた正確な計算法と効率よく実現する技法が必要となる。本科目では、準数値アルゴリズムと呼ばれる数値処理に準ずる代数的アルゴリズムを主体として、これらに関する代表的な話題と実装上必要となるソフトウェア技法を講義し、併せて、メモリ管理・並列処理など、具体的なソフトウェアへの実装法についても言及する。数式の計算や準数値的な処理で用いられる基本的なアルゴリズムを学び、また、それらにおける基本的な考え方を理解することが目標である。 In order to realize algebraic application algorithms, exact computing methods and efficient implementation techniques for basic operations including arithmetics are indispensable.  This lecture focuses on algebraic and seminumerical algorithms for computer algebra, and discusses various major topics in the area as well as practical software technologies required for implementation, such as memory management, parallel processing and so on.  The overall objective is the study of fundamental algorithms for symbolic computation of mathematical expressions and seminumerical processing, and to understand the underlying concept and the common strategies for algorithmic design.
前もって履修 しておくべき科目 /Prerequisites	（特になし）
前もって履修しておくこ とが望ましい科目 /Recommended prerequisites and preparation	（特になし）
教科書等 /Course textbooks and materials	資料を配布する。 教科書は指定しない。 参考書： ・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.
授業内容と その進め方 /Course outline and weekly schedule	第 1回 科目ガイダンス：扱う題材の紹介、関連ソフトウェアの紹介、歴史   guidance and introduction 第 2回 数式の表現と計算：計算例、多倍長整数と算術演算、   representation of mathematical expressions. integers with arbitrary precisions(BIGINTs) and arithmetics. 第 3回 多倍長整数：算術演算、最大公約数と色々なアルゴリズム   BIGINT: arithmetics, algorithms for GCDs. 第 4回 多項式の表現と算術演算   representation and arithmetics of polynomials. 第 5回 モジュラー算法(1)：多項式剰余列と式の膨張、法演算とRSA暗号への応用   modular algorithms (1): polynomial remainder sequence and expression growth. modular arithmetics and application to RSA. 第 6回 モジュラー算法(2)：多項式の最大公約因子、中国剰余定理   modular algorithms (2): polynomial GCDs. Chinese remainder theorem. 第 7回 モジュラー算法(3)：多項式補間、多変数多項式のためのモジュラー算法、   modular algorithms (3): polynomial interpolation. treatment of multivariate cases. 第 8回 多項式計算のための漸近的高速アルゴリズム：高速乗算法、高速フーリエ変換とKaratsuba算法、多項式除算、多項式の多点評価   asymptotically-fast algorithms for polynomial calculation: polynomial multiplication.  FFT.  Karatsuba algorithm. polynomial division.  multipoint evaluation. 第 9回 多項式の決定：多変数多項式補間、p進近似、Newton反復とHensel構成   polynomial determination: interpolation of multivariate polynomials.  p-adic approximation. Newton itertion and Hensel construction. 第10回 多項式因数分解(1)：無平方分解、Berlekampアルゴリズム   polynomial factorization (1): square-free decomposition.  Berlekamp algorithm 第11回 多項式因数分解(2)：次数別因数分解、同次数因数分解   polynomial factorization (2): distinct-degree factorization.  equal-degree factorization. 第12回 行列の計算(1)：消去法と式の膨張、Bareissのアルゴリズム、高速乗算法   matrix computation (1): elimination and expression growth.  Bareiss algorithm. fast matrix multiplication. 第13回 行列の計算(2)：行列式の計算、線形方程式の解法   matrix computation (2): determinants.  solution of linear systems. 第14回 最近の話題の紹介(1)：連立代数方程式の解法とグレブナ基底、量限定子除去、   advanced topics (1): solving systems of algebraic equations.  Groebner basis. quantifier elimination 第15回 最近の話題の紹介(2)：並列処理、数式のUIやコミュニケーション   advanced topics (2): parallel processing. user-interface and communications of mathematical expressions
実務経験を活かした 授業内容 (実務経験内容も含む) /Course content utilizing practical experience
授業時間外の学習 （予習・復習等） /Preparation and review outside class	特にないが、自身の研究内容との関連を検討するとよいでしょう。 None.  But the investigation of the relations with private research subject is recommended.
成績評価方法 および評価基準 （最低達成基準を含む） /Evaluation and grading	月に１回程度課す練習問題のレポートにより評価する。 four times monthly assignments.
オフィスアワー： 授業相談 /Office hours	メールでアポイントメントを取ること。
学生へのメッセージ /Message for students	講義の内容は暗号理論の基礎も含み、数学っぽい内容になりますが、それを題材としてどのように実装するのか考えてみましょう。 また、講義内容は理論的に順序立てて話を進めて行きますが、並列処理やインターネットでの数式の利用法など実際的な話題についてもふれていきます。 数学や理論だけでは現実の問題を処理することはできません。しかし、闇雲に処理をするだけでは解けないこともあります。情報処理をスマートにやるには理論と実践の両輪が必要です。 The subjects treated in this lecture  may seem to be too mathematical, however, it should be noticed that they can be good materials for programming.  The series of lectures are basically organized on the basis of theoretical relations of treated materials, but also include practical issues.  It should be noticed that the combination of theory and practice is important for solving problems in practice.
その他 /Others	（特になし）
キーワード /Keyword(s)	準数値算法、数式処理、多倍長整数、多項式、多項式因数分解、多項式演算、漸近的高速アルゴリズム