| 科目名 |
アルゴリズムとデータ構造 |
| 担当教員 |
星野 孝総 |
| 対象学年 |
2年 |
クラス |
学部：専門002 |
| 講義室 |
Ａ１０１ |
開講学期 |
２学期 |
| 曜日・時限 |
火１,金１ |
単位区分 |
選択 |
| 授業形態 |
一般講義 |
単位数 |
2 |
| 準備事項 |
|
| 備考 |
|
| 授業の詳細1 |
授業の目的
プログラムを設計する観点から数々のアルゴリズムについて概説し，目的に合ったアルゴリズムとデータ構造の構築方法を習得することを講義の目的とする．講義ではアルゴリズムの評価指標としての計算量についての概念を学んだ後に，リスト，ツリー，ヒープなどの基本的なデータ構造とその操作アルゴリズムについて学習を行ない，それらのアルゴリズムの計算量がどの程度のものであるかを理解する．続いて，計算機の中で問題を表現する手段として用いられるグラフの概念とグラフ上での探索アルゴリズムとその応用について学習し，あわせて，再帰呼び出し，分割統治法などのアルゴリズムの設計方法と解析方法について理解する．最後に，計算量に関してＮＰ完全，ＮＰ困難と呼ばれる問題のクラスを導入し，そのようなクラスに属する問題に対しての対処法，および，その性質を利用した情報保護の技術について学ぶ． |
| 授業の詳細2 |
授業の進め方
テキスト，および，講義の際に提示するパワーポイント資料を使用して講義を行い，中間・期末試験，および，出席課題の結果の合計により成績を評価する． |
| 授業の詳細3 |
達成目標
（１）アルゴリズムとは何かを理解し，その評価指標としての計算量の概念を理解する．
（２）リスト構造，ツリー構造，ハッシュ，バケットなどの基本的なデータ構造と操作のアルゴリズムを理解する．
（３）構造化された情報を計算機内で表現する手段としてのグラフについて，必要なデータ構造と探索のためのアルゴリズムについての理解する．
（４）分割統治法，縮小法などのアルゴリズム設計法，再帰呼び出しの使用方法，および，一般的な最適な手法として動的計画法について理解する．
（５）計算量に関してＮＰ完全，ＮＰ困難というクラスが存在することを知り，対応法，および，応用としての公開鍵暗号系について知る．
|
| 授業の詳細4 |
授業計画 （１)
講義は以下のように行なう予定である．この他に３回の演習を行う予定である．また，演習は講義の進行状況に合わせて行う予定であるため，水曜日以外に行われることもあるので注意すること．
１． 講義の内容と進め方，アルゴリズムと計算量 ： 講義の内容と進め方について説明をする．
その後，アルゴリズムが与えられたデータから望みの情報を取り出すための操作手順であることを解説し，その操作手順の評価指標として計算量を導入する．また，同じ情報を取り出す場合でもアルゴリズムにより計算量が異なることがあることを解説し，アルゴリズム設計の重要性を理解する．
２．−３． リスト構造，ツリー構造 ： 基本的なデータ構造であるリスト構造とツリー構造についてその必要性と仕組みを学んだ後に，均整の取れたツリー構造であるヒープについて解説し，さらにヒープを用いたソートについて解説を行なう．また，数々のソートのアルゴリズムについての解説を行なう．
４．−５． ハッシュとバケット ： 膨大な量のデータの中から目的の情報を選び出すためのアルゴリズム，データ構造としてハッシュ法とバケット法について学び，二つの手法の特性を理解る．また，バケット法を用いたソートについても解説する．
６．−７． 再帰呼び出しと分割統治法，縮小法： 複雑な問題をより単純な小問題に分割してから解くという考え方は，古くから色々な分野で用いられている．ここでは元の問題を効率よく解くという観点から分割の手法を学ぶ．分割の方法が良いものであるかどうかは計算量を考えることで判断することが出来るので，色々な問題についての分割の方法とその場合の計算量について解説を行なう． |
| 授業の詳細5 |
授業計画（２）
８．−１１． グラフと探索 ： 計算機の中で問題を表現するための手段として用いられる構造としてのグラフについてその概念を解説し，与えられた対象の中から最良のものを探索するとい操作が，グラフとして表現された情報の構造を探索することであることを理解する．更にその用として，グラフにおける頂点間の最短路を求めるアルゴリズムについて学ぶ．
１２． 動的計画法： 多くの可能な組み合わせの中から最適なものを見つけるための手段はとして，最適ではありえない組み合せを出来るだけ早い段階で除外することで探索範囲を狭める方法がある．その方法として動的計画法について学ぶ．動的計画法は，最適な解は，その一部をとっても対応する部分問題の最適解となるような性質の問題について有効な方法である．
１３．−１４． 問題の難しさとの測り方と難問対策，講義のまとめ： ある問題について，それ以上効率の良いアルゴリズムは作れないという形で問題自体の難しさを定義し，ＮＰ完全，ＮＰ困難と呼ばれる難問のクラスを導入する．つぎに，このような難問を近似的に解くための手法について学び，つぎに，難問であるという性質を利用した情報保護の手法として公開鍵暗号系を紹介する．最後に講義全体を概観しまとめを行なう
１５． 習熟度確認：１．−１５．の内容について，習熟度の確認を行う． |
| 授業の詳細6 |
成績評価
中間・期末試験，および，出席課題の結果の合計により成績を判断する．その結果，講義の目標を達成したと認められる場合（6割程度以上の得点を得た場合），合格とする ．この水準に達しない場合は，その真意を問わず不合格とする．
AA：中間・期末試験において90％以上の得点を取り，出席課題についても優秀な内容であり，講義のすべての項目に関して応用可能なレベルで理解していると認められる場合．
Ａ：中間・期末試験において80％以上の得点を取り，出席課題についても優秀な内容であり，講義のすべての項目に関して理解していると認められる場合
Ｂ：中間・期末試験において70％以上の得点を取り，出席課題の内容から，講義の各項目に関して理解していると認められる場合
Ｃ：中間・期末試験において60％以上の得点を取り，出席課題の内容から，講義の各項目について最低限の理解をしていると認められる場合．
|
| 授業の詳細7 |
テキスト
「データ構造とアルゴリズム」 杉原 厚吉 著 （共立出版）を教科書とする．必要な情報はパワーポイント資料で提示する．
参考書
初回の講義の際に，参考となる書物，文献について説明を行う予定であるが，以下のものは本講義で扱い範囲について網羅的に書かれ，参考となる．
「アルゴリズムＣ」（第１巻から第３巻） 野下，星，佐藤，田口 共訳 （近代科学社）
「アルゴリズムイントロダクション」（第１巻から第３巻） 浅野，岩野，梅尾，和田共訳（近代科学社） |
| 授業の詳細8 |
履修上の注意
プログラミングについての基礎的な概念を理解しており，また，Ｃ（プログラミング言語）で簡単なプログラムを書き，実行できること，Ｃの基本的な文法を理解していることを前提として講義を進める． |
| 授業の詳細9 |
備 考
習熟度確認・演習・出席課題などで評価する．プログラミング自体を課題とすることはない． |
| 授業の詳細10 |
履修の前提となる科目
「コンピュータリテラシィ」，「情報科学１〜３」，「プログラミング基礎」，「プログラミング演習」
詳細な情報は，以下のHPを参照すること．
http://www.ele.kochi-tech.ac.jp/hoshino/#LocalLink |