山梨大学電子シラバス

授業科目名

担当教員

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

美濃　英俊

時間割番号

単位数

コース

履修年次

期別

曜日

時限

263105

後期

木

III

［概要］

情報処理の幅広い場面で必要となる基本的なデータ構造とその適切な操作法（アルゴリズム）の原理、特徴、実装法、利用法を C++ 言語によるプログラミングを通じて習得する。効率的な情報処理のためには適切なデータ構造の選択が不可欠であることを学ぶ。C++言語の「クラス」を用いたプログラミングにより、ソフトウェア開発の基礎となる抽象データ型、カプセル化の意義を理解する。

［具体的な達成目標］

(1)C++言語におけるクラスを用いたプログラミングができる。 (2)ポインタを用いた動的データ構造のプログラミングができる。 (3)クラステンプレートの作成、利用ができる。 (4)既存のテンプレートライブラリを適切に用いたプログラミングができる。 (5)抽象データ型の意義が理解でき、その実装と利用ができる。 (6)静的、動的な線形データ構造の実装と適切な利用ができる。 (7)プライオリティーキュー、探索木、の実装と適切な利用ができる。 (8)ハッシュ表の実装と適切な利用ができる。 (9)グラフの表現、最短経路問題、最小スパニング木問題の解法が実装できる。

［必要知識・準備］

「プログラミング入門」、「プログラミング入門演習」の内容を習得している必要がある。「アルゴリズムとデータ構造I演習」を同期に履修することが必要である。

［評価方法・評価基準］

No	評価項目	割合	評価の観点
1	試験：定期試験	50 %	アルゴリズムの理解度とプログラミング能力
2	試験：中間試験	50 %	アルゴリズムの理解度とプログラミング能力

［教科書］

(未登録)

［参考書］

［講義項目］

1. クラスとオブジェクト（復習） 2. 動的配列、ポインタ 3. 変数寿命、デストラクタ 4. 中間試験、ポインタ 5. リンクリスト、スタック、キュー 6. クラステンプレート 7. プライオリティーキュー 8. 中間試験、演算子オーバロード 9. 探索木 10. 探索木、ハッシュ表 11. ハッシュ表 12. 中間試験、標準テンプレートライブラリ 13. グラフアルゴリズム、グラフの表現 14. グラフアルゴリズム、グラフの探索、最小スパニング木

［教育方法］

講義と演習を連携させ、演習によって講義の内容を効果的に身につけさせるようにしている。また、講義中も机上演習を多く取り入れて、学生の理解を助けている。 演習課題は最低でも授業時間の３倍の時間が必要な程度の難易度となっており、学生は主体的に自習することが強く求められる。 演習の時間とあわせて多くの中間試験（３回）を実施し、学生が「目標｣と「達成度」の確認ができるようにしている。 主体的な学習姿勢を学生に求めるため、出席はとらない。

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

目標(A) 効率的なデータ構造とアルゴリズムの開発、適用が幅広い分野の問題解決に与えるインパクトを理解させる。 目標(B) リスト、木、ハッシュ表などのデータ構造の知識とその実装技術を身に付けさせる。 目標(C)学んだデータ構造とアルゴリズムを用いて現実社会の応用問題を解く体験をさせる。 目標(D)各種データ構造とアルゴリズムの性能的な特徴や適用範囲、欠点などを理解し、問題解決において適切な選択ができるようにする。 目標(E)初歩的なデバッグ法、コーディング作法を身に付けさせる。「クラス」を用いたソフトウェアの部品化とその再利用ができるようにする。

［その他］

(未登録)