日本語 English
| 開講年度/ Academic YearAcademic Year |
20242024 |
| 科目設置学部/ CollegeCollege |
理学部/College of ScienceCollege of Science |
| 科目コード等/ Course CodeCourse Code |
CA182/CA182CA182 |
| テーマ・サブタイトル等/ Theme・SubtitleTheme・Subtitle |
代数的アルゴリズム入門 |
| 授業形態/ Class FormatClass Format |
対面（全回対面）/Face to face (all classes are face-to-face)Face to face (all classes are face-to-face) |
| 授業形態（補足事項）/ Class Format (Supplementary Items)Class Format (Supplementary Items) |
対面 |
| 授業形式/ Class StyleCampus |
講義/LectureLecture |
| 校地/ CampusCampus |
池袋/IkebukuroIkebukuro |
| 学期/ SemesterSemester |
春学期他/Spring OthersSpring Others |
| 曜日時限・教室/ DayPeriod・RoomDayPeriod・Room |
ログインして教室を表示する（Log in to view the classrooms.） |
| 単位/ CreditsCredits |
22 |
| 科目ナンバリング/ Course NumberCourse Number |
MAT3430 |
| 使用言語/ LanguageLanguage |
日本語/JapaneseJapanese |
| 履修登録方法/ Class Registration MethodClass Registration Method |
科目コード登録/Course Code RegistrationCourse Code Registration |
| 配当年次/ Assigned YearAssigned Year |
配当年次は開講学部のR Guideに掲載している科目表で確認してください。配当年次は開講学部のR Guideに掲載している科目表で確認してください。 |
| 先修規定/ Prerequisite RegulationsPrerequisite Regulations |
|
| 他学部履修可否/ Acceptance of Other CollegesAcceptance of Other Colleges |
履修登録システムの『他学部・他研究科履修不許可科目一覧』で確認してください。 |
| 履修中止可否/ Course CancellationCourse Cancellation |
×（履修中止不可/ Not eligible for cancellation） |
| オンライン授業60単位制限対象科目/ Online Classes Subject to 60-Credit Upper LimitOnline Classes Subject to 60-Credit Upper Limit |
|
| 学位授与方針との関連/ Relationship with Degree PolicyRelationship with Degree Policy |
各授業科目は、学部・研究科の定める学位授与方針（DP）や教育課程編成の方針（CP）に基づき、カリキュラム上に配置されています。詳細はカリキュラム・マップで確認することができます。 |
| 備考/ NotesNotes |
集中講義：日程はR Guide「集中講義日程」を確認すること LC194/RC194情報科学特論４と合同授業 |
Computations, where mathematical formulas such as polynomials are dealt with as they are, are called "symbolic computations", and those, where algebraic operations such as addition, subtraction, multiplication, and division are mainly dealt with, are called "algebraic computations". In this class, students will understand basic algorithms for polynomials as the basics on algebraic computations. Moreover, they will understand the difference between operations in Mathematics and those on a computer, and learn basic ideas for designing algebraic algorithms.
As an introduction to algebraic computations, basic algorithms for polynomials, such as GCD, factorization, and moreover, resultant, basic operations on polynomial ideals will be explained. The difference between operations in Mathematics and those on a computer lies in the efficiency of computations, and the notion of the complexity is used to measure this efficiency. In this class, the basics of complexity theory will be explained, and then how the basic algorithms for polynomials were designed and improved will be also explained. In the second half of the class, as the most basic notion for polynomial ideal operations, Groebner basis will be explained.
| 1 | 導入：アルゴリズムとその計算量理論の基礎と、計算機上での整数、多項式の四則演算を説明し、計算量の基本を学ぶ。さらに、高速化計算法についても学ぶ。 |
| 2 | 一変数多項式の計算その１：一変数多項式の最大公約因子(GCD)計算を主題として、そのアルゴリズム開発の歴史を説明する。これにより、計算量を良くする工夫として、可換環としての性質がどのようにアルゴリズムに活用されているかも学ぶ。 |
| 3 | 一変数多項式の計算その２：引き続き一変数多項式の最大公約因子計算を説明する。主要なアリゴリズムで使われている高速化の工夫について学ぶ。素数を法とする計算法では、素数判定や素数生成にも言及する。 |
| 4 | 一変数多項式の計算その３：多項式の因数分解について説明する。ここでは、体論（ガロア理論）がどのようにアルゴリズムの設計に活用されているかを学ぶ。 |
| 5 | 一変数多項式の計算その４：引き続き、多項式の因数分解について説明する。ここでは、効率的とされる「多項式時間アルゴリズム」の設計法について説明し、計算量の改善について学ぶ。 |
| 6 | 素数判定と素数生成について：一変数多項式環のGCD や因数分解で使われる素数に関して、その判定・生成アルゴリズムについて説明し、その計算量を学ぶ。 |
| 7 | 前半のまとめと演習：前半で説明したアリゴリズムの設計法についてまとめを行い、併せて実際の計算機を使って計算実 験を行う。小レポート1の課題を提示する。 |
| 8 | 多変数多項式の計算理論のための導入:ここでは、まず２変数の場合を取り上げ、連立代数方程式の解法としての、終結式と擬 剰余を説明する。 |
| 9 | グレブナー基底の基本その１:多変数連立代数方程式を解くことを主題として、多項式イデアルとそのグレブナー基底の 概念を導入する。ここでは、単項式順序と、それに付随する剰余計算を説明する。 |
| 10 | グレブナー基底の基本その２:引き続き、グレブナー基底の説明を行う。ここでは、Buchberger の計算法を理解するための重要な概念である S 多項式と Buchberger の判定法について説明する。また、Buchberger がどのようにして S 多項式という概念にたどりついたのか、その背景を検証する。 |
| 11 | グレブナー基底の基本その３: Buchberger の計算法について説明する。さらに、計算に関する問題点をいくつか列挙し、それへの対応法がどのように考えられたのかを説明する。 |
| 12 | グレブナー基底の応用その１:グレブナー基底を用いた連立代数方程式の解法について説明する。ここでは、イデアルが０次元の場合の線形代数的な手法や、解の表現法などを紹介する。 |
| 13 | グレブナー基底の応用その２:グレブナー基底を用いたイデアル演算計算について説明する。まずは、イデアルの交わり、イデアル商、飽和イデアル商などの基本を紹介した後で、それらを駆使した準素イデアル分解なども説明する。 |
| 14 | 多変数多項式の計算のまとめと演習:グレブナー基底の概念とその計算法、そしてその応用について、アルゴリズムがどのように生まれてきたかを検証する。また、実際の計算機でグレブナー基底の計算実験を行う。小レポート2の課題、および最終レポートの課題を提示する。 |
板書 /Writing on the Board
スライド（パワーポイント等）の使用 /Slides (PowerPoint, etc.)
上記以外の視聴覚教材の使用 /Audiovisual Materials Other than Those Listed Above
個人発表 /Individual Presentations
グループ発表 /Group Presentations
ディスカッション・ディベート /Discussion/Debate
実技・実習・実験 /Practicum/Experiments/Practical Training
学内の教室外施設の利用 /Use of On-Campus Facilities Outside the Classroom
校外実習・フィールドワーク /Field Work
上記いずれも用いない予定 /None of the above
授業時間外の学習に関する指示は，必要に応じて別途指示する。
| 種類 (Kind) | 割合 (%) | 基準 (Criteria) |
|---|---|---|
| 平常点 (In-class Points) | 100 |
小レポート１(30%) 小レポート２(30%) 最終レポート(Final Report)(40%) |
| 備考 (Notes) | ||
なし/None
| No | 著者名 (Author/Editor) | 書籍名 (Title) | 出版社 (Publisher) | 出版年 (Date) | ISBN/ISSN |
|---|---|---|---|---|---|
| 1 | 横山和弘 | 『多項式と計算機代数』 | 朝倉書店 | 2022 | 9784254117677 |
| 2 | 長坂・岩根・北本・讃岐・照井・鍋島 | 『計算機代数の基礎理論』 | 共立出版 | 2019 | 9784320113732 |
| 3 | vonJ. zur Gathen, J. Gerhard | Modern Computer Algebra | Cambridge University Press | 2013 | 9781107039032 |
| その他 (Others) | |||||
| 授業中に随時参考文献を紹介する。 | |||||
学部１・２年次で学ぶ線形代数および学部３年次で学代数学の基礎（可換環論、体論）をある程度理解していること。また、プログラムの基本もある程度理解していること。
個人所有の PC で数式処理ソフトを実行できることが望ましい。
多項式などの数式を式のまま計算する計算を記号計算といい、その中で、加減乗除などに代表される代数的な操作を中心にした計算を代数的計算という。この授業では、代数的計算の基本として多項式の基本アルゴリズムを理解する。さらに、数学における操作と計算機上での操作の違いを理解し、アルゴリズム設計の指針を習得する。
Computations, where mathematical formulas such as polynomials are dealt with as they are, are called "symbolic computations", and those, where algebraic operations such as addition, subtraction, multiplication, and division are mainly dealt with, are called "algebraic computations". In this class, students will understand basic algorithms for polynomials as the basics on algebraic computations. Moreover, they will understand the difference between operations in Mathematics and those on a computer, and learn basic ideas for designing algebraic algorithms.
多項式の基本アルゴリズムである、GCD、因数分解、さらには終結式や多項式イデアルの基本操作などを解説する。数学における操作と計算機上での操作の違いは、その計算の効率にある。この効率を測るツールとして計算量があり、計算量によってアルゴリズムの良し悪しが定まる。そこで、計算量の初歩を解説し、多項式の基本アルゴリズムがどのようにして生まれ、改良されたかの背景を解説する。授業の後半では、多変数多項式におけるイデアル操作に関して、その基本となるグレブナー基底を説明する。
As an introduction to algebraic computations, basic algorithms for polynomials, such as GCD, factorization, and moreover, resultant, basic operations on polynomial ideals will be explained. The difference between operations in Mathematics and those on a computer lies in the efficiency of computations, and the notion of the complexity is used to measure this efficiency. In this class, the basics of complexity theory will be explained, and then how the basic algorithms for polynomials were designed and improved will be also explained. In the second half of the class, as the most basic notion for polynomial ideal operations, Groebner basis will be explained.
| 1 | 導入：アルゴリズムとその計算量理論の基礎と、計算機上での整数、多項式の四則演算を説明し、計算量の基本を学ぶ。さらに、高速化計算法についても学ぶ。 |
| 2 | 一変数多項式の計算その１：一変数多項式の最大公約因子(GCD)計算を主題として、そのアルゴリズム開発の歴史を説明する。これにより、計算量を良くする工夫として、可換環としての性質がどのようにアルゴリズムに活用されているかも学ぶ。 |
| 3 | 一変数多項式の計算その２：引き続き一変数多項式の最大公約因子計算を説明する。主要なアリゴリズムで使われている高速化の工夫について学ぶ。素数を法とする計算法では、素数判定や素数生成にも言及する。 |
| 4 | 一変数多項式の計算その３：多項式の因数分解について説明する。ここでは、体論（ガロア理論）がどのようにアルゴリズムの設計に活用されているかを学ぶ。 |
| 5 | 一変数多項式の計算その４：引き続き、多項式の因数分解について説明する。ここでは、効率的とされる「多項式時間アルゴリズム」の設計法について説明し、計算量の改善について学ぶ。 |
| 6 | 素数判定と素数生成について：一変数多項式環のGCD や因数分解で使われる素数に関して、その判定・生成アルゴリズムについて説明し、その計算量を学ぶ。 |
| 7 | 前半のまとめと演習：前半で説明したアリゴリズムの設計法についてまとめを行い、併せて実際の計算機を使って計算実 験を行う。小レポート1の課題を提示する。 |
| 8 | 多変数多項式の計算理論のための導入:ここでは、まず２変数の場合を取り上げ、連立代数方程式の解法としての、終結式と擬 剰余を説明する。 |
| 9 | グレブナー基底の基本その１:多変数連立代数方程式を解くことを主題として、多項式イデアルとそのグレブナー基底の 概念を導入する。ここでは、単項式順序と、それに付随する剰余計算を説明する。 |
| 10 | グレブナー基底の基本その２:引き続き、グレブナー基底の説明を行う。ここでは、Buchberger の計算法を理解するための重要な概念である S 多項式と Buchberger の判定法について説明する。また、Buchberger がどのようにして S 多項式という概念にたどりついたのか、その背景を検証する。 |
| 11 | グレブナー基底の基本その３: Buchberger の計算法について説明する。さらに、計算に関する問題点をいくつか列挙し、それへの対応法がどのように考えられたのかを説明する。 |
| 12 | グレブナー基底の応用その１:グレブナー基底を用いた連立代数方程式の解法について説明する。ここでは、イデアルが０次元の場合の線形代数的な手法や、解の表現法などを紹介する。 |
| 13 | グレブナー基底の応用その２:グレブナー基底を用いたイデアル演算計算について説明する。まずは、イデアルの交わり、イデアル商、飽和イデアル商などの基本を紹介した後で、それらを駆使した準素イデアル分解なども説明する。 |
| 14 | 多変数多項式の計算のまとめと演習:グレブナー基底の概念とその計算法、そしてその応用について、アルゴリズムがどのように生まれてきたかを検証する。また、実際の計算機でグレブナー基底の計算実験を行う。小レポート2の課題、および最終レポートの課題を提示する。 |
板書 /Writing on the Board
スライド（パワーポイント等）の使用 /Slides (PowerPoint, etc.)
上記以外の視聴覚教材の使用 /Audiovisual Materials Other than Those Listed Above
個人発表 /Individual Presentations
グループ発表 /Group Presentations
ディスカッション・ディベート /Discussion/Debate
実技・実習・実験 /Practicum/Experiments/Practical Training
学内の教室外施設の利用 /Use of On-Campus Facilities Outside the Classroom
校外実習・フィールドワーク /Field Work
上記いずれも用いない予定 /None of the above
授業時間外の学習に関する指示は，必要に応じて別途指示する。
| 種類 (Kind) | 割合 (%) | 基準 (Criteria) |
|---|---|---|
| 平常点 (In-class Points) | 100 |
小レポート１(30%) 小レポート２(30%) 最終レポート(Final Report)(40%) |
| 備考 (Notes) | ||
なし/None
| No | 著者名 (Author/Editor) | 書籍名 (Title) | 出版社 (Publisher) | 出版年 (Date) | ISBN/ISSN |
|---|---|---|---|---|---|
| 1 | 横山和弘 | 『多項式と計算機代数』 | 朝倉書店 | 2022 | 9784254117677 |
| 2 | 長坂・岩根・北本・讃岐・照井・鍋島 | 『計算機代数の基礎理論』 | 共立出版 | 2019 | 9784320113732 |
| 3 | vonJ. zur Gathen, J. Gerhard | Modern Computer Algebra | Cambridge University Press | 2013 | 9781107039032 |
| その他 (Others) | |||||
| 授業中に随時参考文献を紹介する。 | |||||
学部１・２年次で学ぶ線形代数および学部３年次で学代数学の基礎（可換環論、体論）をある程度理解していること。また、プログラムの基本もある程度理解していること。
個人所有の PC で数式処理ソフトを実行できることが望ましい。