|
授業科目名
|
担当教官
|
|||||
|
アルゴリズムとデータ構造III
|
宮本 泉
|
|||||
|
時間割番号
|
単位数
|
コース
|
履修年次
|
期別
|
曜日
|
時限
|
| 263216 | 2 | F | 2 | 後期 | 木 | II |
| ［概要と目標］ | ||||||
| プログラムを実行したときに、どれくらいの時間を必要とするかというのが時間的計算量で、どれくらいメモリーを必要とするかが空間的計算量です。このように計算量の理論はアルゴリズムの効率を調べる基本的な理論です。本講義では時間的計算量について紹介します。誰もが情報ネットワークを使って様々な社会活動を行っている現代では、手軽な方法で安全に情報を送ることが必要です。それに答えたのが公開鍵暗号です。公開鍵暗号系は、計算量の理論に基いて安全性が保証されています。また、代数学を応用したアルゴリズムでもあり、関連する理論の基礎も紹介します。実例の紹介を中心に進めて、計算をすることができるようにすることを目標にします。また、そこで使われている数学の体系の基礎的部分を理解することで、基礎学力を豊かにします。 | ||||||
| ［必要知識・準備］ | ||||||
| 情報数学基礎、アルゴリズムとデータ構造？、？、線形代数学。必要な知識は復習でも補う。 | ||||||
| ［評価基準］ | ||||||
| 期末試験１０0点 | ||||||
| ［教科書］ | ||||||
|
|
||||||
| ［参考書］ | ||||||
| ［講義項目］ | ||||||
| １．計算量の理論入門 ２．関数の漸近的性質 ３．分割統治法 ４．多項式時間と非多項式時間計算量 ５．暗号の紹介 ６．整数の性質,合同式 ７．公開鍵暗号、RSA暗号 ８．エルガマル暗号,楕円曲線暗号 ９．ディジタル署名 １０．素因数分解と離散対数問題 １１．代数系、群、環、体 １２．有限体と多項式 １３．関連するアルゴリズムの補足（1） １４．関連するアルゴリズムの補足（２）とまとめ |
||||||