| 授業のねらい |
| 問題を解くための具体的な手順がアルゴリズムであり、アルゴリズム論の対象となる問題は非常に多様である。この授業では、基本的で実用上も重要な問題として「グラフに関するアルゴリズム」を題材に、アルゴリズム中に存在する戦略や証明法からアルゴリズムのソースコード化までを具体的に学ぶ．また，新しいタイプのアルゴリズムとして，量子暗号の概要について学ぶ． |
|
| 授業の目標 |
１．グラフに関する主要なアルゴリズムを理解する．
２．アルゴリズム中に存在する戦略や証明法について理解する． |
|
| 授業計画 |
第 １週 グラフの定義・用語とその表現法・データ構造について
第 ２週 グラフの探索法（深さ優先探索） （１）
第 ３週 グラフの探索法（深さ優先探索）（２）
第 ４週 グラフの探索法（幅優先探索）
第 ５週 グラフの連結性の判定（連結成分，二重連結性，関節点検出）（１）
第 ６週 グラフの連結性の判定（連結成分，二重連結性，関節点検出）（２）
第 ７週 グラフの連結性の判定（強連結性）
第 ８週 最短路の問題解法（DijkstraのアルゴリズムとFloydのアルゴリズム）
第 ９週 最小木の問題（PrimのアルゴリズムとKruskalのアルゴリズム）
第１０週 レポート課題の提示，通信セキュリティと暗号処理に関する概要
第１１週 量子論の概要と不確定性関係について
第１２週 BB84 量子鍵生成アルゴリズム（１）
第１３週 BB84 量子鍵生成アルゴリズム（２）
第１４週 レポート課題に対するプレゼンテーション（１）
第１５週 レポート課題に対するプレゼンテーション（２） |
|
| 教科書及び教材 |
「グラフに関するアルゴリズム」の講義資料は、下記Webサーバで公開済み。各自、ネットワーク経由で入手して下さい。http://www.wil.csse.muroran-it.ac.jp/member/hatanaka/Algorithms_Graph.pdf
（本資料はPDF形式になっており、PDFfilereader(AcrobatReader)が必要です。） |
|
| 参考書 |
石畑 清「岩波講座ソフトウェア科学３アルゴリズムとデータ構造」岩波書店 [付属図書館蔵]
Jozef Gruska (伊藤正美， 今井克暢，岩本宙造，外山政文，森田憲一 共訳)「量子コンピューティング」森北出版 |
|
| 成績評価方法 |
| レポート課題に対するプレゼンテーションおよび出席状況を考慮して、総合的に評価する。 |
|
| 履修条件等 |
|
| 教員からのメッセージ |
レポート課題の実施においては，C言語やJava言語などによるプログラミングの知識が必要ですが，授業時間でプログラミングそのものの学習は行いません。
|
|
| その他 |
|