山梨大学電子シラバス

授業科目名

担当教員

アルゴリズムとデータ構造

岩沼　宏治

時間割番号

単位数

コース

履修年次

期別

曜日

時限

263610

前期

火

［概要］

本講義では，種々の情報処理技術の根幹を成すアルゴリズムとデータ構造に関する種々の基本的理論と技術を学ぶ．具体的な講義内容としては，IEEE/ACMが設定するモデルカリキュラムCC2001の内容を（先行科目のプログラミングII，同演習と併せて）カバーする題材を取り上げる．情報処理技術教育の基幹科目として，十分な幅と深みをもった題材を取り上げ，　学生に十分な素養を持たせることを目標としている． カリキュラム中での位置付け：<a href="http://www.cs.yamanashi.ac.jp/g/JABEE/curriculum/">Gコースのカリキュラム</a>

［具体的な達成目標］

本講義では，大きく分けて以下の３つの項目について取り上げ，その基本的な理解を達成目標とする． （１）個々の具体的な問題における代表的なアルゴリズム， （２）アルゴリズムの設計において汎用的に用いられる理論と技法 （３）問題の持つ本質的な難しさとそれに起因する計算効率化の限界 また比較的長い英文を課題として出題し，その内容理解を問うテストを通して英語教育の一部を担うことを目標としている．（１）から（３）で取り上げる具体的な内容は，IEEE/ACM CC2001での必修項目を全て取り上げるように配慮してある（下記の講義の達成状況の欄を参照のこと）．本講義と同時開講される「アルゴリズムとデータ構造演習」と協力して，情報処理技術者としての十分な素養を持たせることを目標としている．

［必要知識・準備］

プログラミング I, II，および同演習，計算機アーキテクチャをしっかり復習されたい．またＣ言語の知識とプログラミング技術が必須である．

［評価方法・評価基準］

No	評価項目	割合	評価の観点
1	試験：期末期	50 %	主に講義の後半の項目の理解度と応用力の評価を行なうが，併せて前半の項目の評価も行なう．
2	試験：中間期	45 %	講義の前半の項目の理解度と応用力を評価する．
3	小テスト／レポート	5 %	適宜行い，小項目の理解度を評価する．

［教科書］

茨木俊秀, アルゴリズムとデータ構造, 昭晃堂, ISBN:4785601191

［参考書］

［講義項目］

１．序論：コンピュータサイエンス的数字と天文学的数字ではどちらが大きいのか？ 　　線形探索、2分探索、ハッシュによる探索 ２．文字列照合：　素朴なアルゴリズムとBoyer-Moore法 ３．ヒープソート：選択ソートの改良，完全2分木の埋め込みによるヒープの実現 ４．比較によるソート法の時間計算量の下界（本質的に必要な計算量）と 　　　その空間的克服：バケットソート、基底ソート ５．簡単な最適化問題：　資源配分問題、連続ナップザック問題 ６．グラフ問題その１：　木とグラフの定義，最小全域木， 　　　　　クラスカルのアルゴリズム，プリムのアルゴリズム ７．グラフ問題その２：　最短経路問題， 　　　　　ダイクストラのアルゴリズム．ワーシャルフロイドのアルゴリズム ８．前半のまとめと中間評価　 ９．動的計画法：　部分和問題、０－１ナップザック問題 １０．分割統治法：　長大数の乗算、点集合の凸包 １１．分岐限定法：　０－１ナップザック問題 １２．近似解法：　貪欲算法、ランダム法、局所探索法、緩和法 　　　進んだ話題：　分散アルゴリズム，確率的アルゴリズム １３．計算不可能性原理、計算量の無限階層、ＮＰ完全問題 １４．全般的な復習と演習 １５．まとめと総括試験

［教育方法］

•　講義の概要資料をPowerPointを利用して電子的に作成し，ホームページから配布する •　適宜，自主勉強用の演習問題プリントを配布する． •　中間試験の答案用紙の採点結果を返却する予定である．これにより自己の実力の確認を行なってもらいたい．

［JABEEプログラムの学習・教育目標との対応］

《コンピュータ・メディア工学科情報メディアコース》
(A) マルチメディア情報ネットワーク技術に習熟した情報処理技術者としての基盤となる基礎的素養及び基礎的スキルを修得する。	◎
(E) 情報化社会における要求に対して問題分析を行い、専門的知識に基づく創意工夫によってそれを解決するまでの問題発見デザイン能力を修得する。	○

［その他］

オフィスアワー：月曜４時限目