山梨大学電子シラバス

授業科目名

担当教員

アルゴリズムとデータ構造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. グラフアルゴリズム、グラフの探索、最小スパニング木 15. 復習と評価

［教育方法］

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

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

《コンピュータ・メディア工学科コンピュータサイエンスコース》
(A)情報処理技術者としての自らの活動が自然や社会，人に与える影響を理解し，問題解決にあたることができる知識と技術，およびコミュニケーションスキルを習得する	○
(B)種々の型と構造をもつ情報の表現手法及び処理手法についての基本的な知識と技術を習得する．	◎
(C)問題を形式的にモデル化し，そのモデルを基に問題解決する知識と技術を習得する．	○
(D)ソフトウェアの実現に必要な各種の道具や手法を習得・理解し，これらを組み合わせて問題解決を行える知識と技術，およびその自発的・継続的学習法を習得する．	◎

［その他］

(未登録)