|
授業科目名
|
担当教官
|
|||||
|
アルゴリズムとデータ構造III
|
宮本 泉
|
|||||
|
時間割番号
|
単位数
|
コース
|
履修年次
|
期別
|
曜日
|
時限
|
| 263216 | 2 | F | 2 | 後期 | 木 | II |
| ［概要］ | ||||||
| プログラムを実行したときに、どれくらいの時間を必要とするかというのが時間的計算量で、どれくらいメモリーを必要とするかが空間的計算量です。このように計算量の理論はアルゴリズムの効率を調べる基本的な理論です。本講義では時間的計算量について紹介します。誰もが情報ネットワークを使って様々な社会活動を行っている現代では、手軽な方法で安全に情報を送ることが必要です。それに答えたのが公開鍵暗号です。公開鍵暗号系は、計算量の理論に基いて安全性が保証されています。また、代数学を応用したアルゴリズムでもあり、関連する理論の基礎も紹介します。実例の紹介を中心に進めて、計算をすることができるようにすることを目標にします。また、そこで使われている数学の体系の基礎的部分を理解することで、基礎学力を豊かにします。 | ||||||
| ［具体的な達成目標］ | ||||||
| (1) 関数のオーダーを求める． (2) 漸化式から関数のオーダーを求める． (3) 多項式時間と非多項式時間計算量の例の学習． (4) 合同式の計算． (5) 公開鍵暗号に必要となる整数計算の知識とアルゴリズム． (6) 公開鍵暗号の計算法． |
||||||
| ［必要知識・準備］ | ||||||
| 情報数学基礎、アルゴリズムとデータ構造？、？、線形代数学。必要な知識は復習でも補う。 | ||||||
| ［評価基準］ | ||||||
| 期末試験１０0点 | ||||||
| ［教科書］ | ||||||
| (未登録) | ||||||
| ［参考書］ | ||||||
| ［講義項目］ | ||||||
| １．計算量の理論入門 ２．関数の漸近的性質 ３．分割統治法 ４．多項式時間と非多項式時間計算量 ５．暗号の紹介 ６．整数の性質,合同式 ７．公開鍵暗号、RSA暗号 ８．エルガマル暗号,楕円曲線暗号 ９．ディジタル署名 １０．素因数分解と離散対数問題 １１．代数系、群、環、体 １２．有限体と多項式 １３．関連するアルゴリズムの補足（1） １４．関連するアルゴリズムの補足（２）とまとめ １．計算量の理論入門 ２．関数の漸近的性質 ３．ソーティングの計算量 ４．分割統治法 ５．多項式時間と非多項式時間計算量 ６．暗号の紹介，ディジタル署名 ７．整数の性質(1) ８．整数の性質(2), 代数系 ９．合同式 １０．公開鍵暗号、RSA暗号 １１．エルガマル暗号 １２．楕円曲線暗号 １３．素因数分解と離散対数問題 １４．まとめ |
||||||
| ［教育方法］ | ||||||
| 黒板に書きながら説明して講義を進める。受講者が手を動かしてノートをとることにより集中力を養えるようにしている。授業中に簡単な質問に答えさせる，黒板に計算を書かせるなどで，学生とのコミュニケーションと授業中の気分転換を図りつつ、予備知識の確認をしている． | ||||||
| ［JABEEプログラムの学習・教育目標との対応］ | ||||||
| 教育目標(Ａ)暗号，電子署名などが情報通信においてどのように必要になるかを通して，情報処理技術者が社会に与える影響について学習する． 教育目標(Ｂ)ソーティングアルゴリズムを解析するための木構造，代数的暗号系を理解するための数学的構造などについて学習し理解して，基本的な計算処理を習得する． 教育目標(Ｃ)計算量の最良限界を求めるため、公開鍵暗号を実現するためなどの場合に，問題を抽象化，モデル化して解決する例を学ぶ． 教育目標(Ｄ)計算量の理論に基いて，より効率の良いソフトウェア作成方法について学習する．公開鍵暗号に関連する数学的アルゴリズムを習得する． |
||||||
| ［その他］ | ||||||
| (未登録) | ||||||