授業科目名				担当教員
情報数学				宮本　　泉
時間割番号	単位数	コース	履修年次	期別	曜日	時限
253123	2	F	2	後期	水	IV
［概要］
プログラムを実行したときに、どれくらいの時間を必要とするかというのが時間的計算量で、どれくらいメモリーを必要とするかが空間的計算量です。このように計算量の理論はアルゴリズムの効率を調べる基本的な理論です。本講義では時間的計算量について紹介します。誰もが情報ネットワークを使って様々な社会活動を行っている現代では、手軽な方法で安全に情報を送ることが必要です。それに答えたのが公開鍵暗号です。公開鍵暗号系は、計算量の理論に基いて安全性が保証されています。また、代数学を応用したアルゴリズムでもあり、関連する理論の基礎も紹介します。実例の紹介を中心に進めて、計算をすることができるようにすることを目標にします。また、そこで使われている数学の体系の基礎的部分を理解することで、基礎学力を豊かにします。
［具体的な達成目標］
(1) 関数のオーダーを求める．<BR>　(2) 漸化式から関数のオーダーを求める．<BR>　(3) 多項式時間と非多項式時間計算量の例の学習．<BR>　(4) 合同式の計算．<BR>　(5) 公開鍵暗号に必要となる整数計算の知識とアルゴリズム．<BR>　(6) 公開鍵暗号の計算法
［必要知識・準備］
情報数学基礎、アルゴリズムとデータ構造、線形代数学。必要な知識は復習でも補う。
［評価方法・評価基準］
No 評価項目 割合 評価の観点 1 試験：期末期  80  % 達成目標がどの程度学習できているか。  2 小テスト／レポート  20  % 十分に考えたレポートを提出しているか。
［教科書］
(未登録)
［参考書］
笠原正雄、境隆一, 暗号　ネットワーク社会の安全を守る鍵, 共立出版, ISBN:4320016483, (準教科書) 守屋悦朗, コンピュータサイエンスのための　離散数学, サイエンス社, ISBN:4781906435 Ｊ．ホップクロフト、Ｊ．ウルマン, オートマトン　言語理論　計算論　２, サイエンス社, ISBN:4781910270 Ｎ．Ｂｉｇｇｓ, Discrete Mastematics, Oxford University Press, ISBN:0198507178
［講義項目］
１．暗号の紹介<BR>　　２．整数の性質,合同式<BR>　　３．代数系、群、環、体<BR>　　４．公開鍵暗号、RSA暗号<BR>　　５．エルガマル暗号,楕円曲線暗号<BR>　　６．ディジタル署名<BR>　　７．素因数分解と離散対数問題<BR>　　８．計算量の理論入門<BR>　　９．関数の漸近的性質<BR>　１０．計算量とオーダー<BR>　１１．オーダーの計算実例<BR>　１２．分割統治法<BR>　１３．多項式時間と非多項式時間計算量<BR>　１４．関連するアルゴリズムの紹介<BR>　１５．総括評価・まとめ
［教育方法］
黒板に書きながら説明して講義を進める。受講者が手を動かしてノートをとることにより集中力を養えるようにしている。授業中に簡単な質問に答えさせる，黒板に計算を書かせるなどで，学生とのコミュニケーションと授業中の気分転換を図りつつ、予備知識の確認をしている．
［JABEEプログラムの学習・教育目標との対応］
《コンピュータ・メディア工学科 コンピュータサイエンスコース》 (B)種々の型と構造をもつ情報の表現手法及び処理手法についての基本的な知識と技術を習得する． ◎ (C)問題を形式的にモデル化し，そのモデルを基に問題解決する知識と技術を習得する． ◎
［その他］
一冊で講義内容全体が含まれるような適当な教科書がありません。<BR>参考書の最初に挙げた本を「準教科書」として推奨いたします。