山梨大学電子シラバス

授業科目名

担当教員

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

岩沼　宏治／山本　泰生

時間割番号

単位数

コース

履修年次

期別

曜日

時限

263612

前期

火

［概要］

本演習では，講義「アルゴリズムとデータ構造」で学ぶ内容に関して，コンピュータを用いた演習と実習を行うことを目的とする．幾つかの重要で具体的なアルゴリズムやデータ構造，及びアルゴリズムに関する一般的な技術を理解した上で，C 言語によって実際にプログラミングすることによって理解を深めさせる．情報処理技術教育の基幹技術として，学生に十分な素養とスキルを持たせることを目標としている． カリキュラム中での位置付け：<a href="http://www.cs.yamanashi.ac.jp/g/JABEE/curriculum/">Gコースのカリキュラム</a>

［具体的な達成目標］

本科目を終了した学生は以下の項目を理解して，時間および空間計算量などを念頭においたより良いプログラムが行えるようになる． 　ヒープ，ヒープソート，バケットソート，基数ソート，文字列照合，グラフのアルゴリズム（最短経路の探索など），動的計画法，分枝限定法，分割統治法 JABEE 教育プログラムの共通基準のうち，「(c) 自然科学，情報技術に関する知識とそれらを応用できる能力，(d) 該当する分野の専門技術に関する知識とそれらを問題解決に応用できる能力」の二点が修得できる．また，配布した演習問題を自主的に解きまとめることを通じて，「(g) 自主的，継続的に学習できる能力」を修得できる．

［必要知識・準備］

講義「アルゴリズムとデータ構造」を履修済み，または本授業と同期に履修している必要がある．また，本演習を受講するために次の知識を必要とする． １．UNIX上でのエディタ，メールなどの基本的ツールの使用法 ２．C言語によるコンパイル ３．C言語の基本的文法 ４．ポインタの操作 ５．構造体の操作

［評価方法・評価基準］

No	評価項目	割合	評価の観点
1	試験：中間期	60 %	３回のオンライン試験（各20点）により評価する
2	小テスト／レポート	40 %	２回のレポート（各20点）により評価する

［教科書］

茨木　俊秀, アルゴリズムとデータ構造, 昭晃堂, ISBN:4785601191,
(毎回の演習課題はオンライン資料として提供される．)

［参考書］

ニールマシュー，リチャードストーンズ, Linuxプログラミング―例題で学ぶUNIXプログラミング環境のすべて, ソフトバンクパブリッシング, ISBN:4797327014

［講義項目］

１．文字列照合：力まかせのアルゴリズム 　２．文字列照合：Boyer-Moore 法 　３．オンライン試験１及び総括評価 　４．ヒープソート 　５．バケットソート，基数ソート 　６．ヒープソート，基数ソート演習 　７．オンライン試験２及び総括評価 　８．グラフの問題：ダイクストラの最短経路探索アルゴリズム（１） 　９．グラフの問題：ダイクストラの最短経路探索アルゴリズム（２） １０．オンライン試験３及び総括評価 １１．動的計画法：０－１ナップザック問題 １２．分枝限定法：０－１ナップザック問題，レポート課題１ １３．分割統治法：長大数の乗算 (1) １４．分割統治法：長大数の乗算 (2)，レポート課題２ １５．復習とまとめ

［教育方法］

・プログラムを組む能力が身に付いているか判定するために，３回のオンライン試験を実施する．オンライン試験では時間内に所定の仕様を満たすプログラムの作成に取り組む． ・本演習では３回のオンライン試験と２回のレポート課題を実施する．その評価においては，なるべく細かくコメントを付けて不具合のポイントなどを提示する．これによりプログラミング能力の向上，理解の促進が期待できる． ・Ｃ言語の理解が不足している学生がいれば，随時Ｃ言語に関する解説も行う．

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

《コンピュータ・メディア工学科情報メディアコース》
(A) マルチメディア情報ネットワーク技術に習熟した情報処理技術者としての基盤となる基礎的素養及び基礎的スキルを修得する。	◎
(C) 科学技術が社会や自然に及ぼす影響や効果までを考慮できる多面的な地球的視野を会得し、国際的なコミュニケーションを可能とする基礎能力を修得する。	○
(G-1)ネットワークアプリケーションを開発構築・維持管理する基礎的技術	○
(G-2)マルチメディアコンテンツを開発処理する基礎的技術	○

［その他］

初回授業までにC言語の復習を行うこと