|
授業科目名
|
担当教員
|
|||||||||||||||||
|
アルゴリズムとデータ構造演習
|
鍋島 英知／岩沼 宏治
|
|||||||||||||||||
|
時間割番号
|
単位数
|
コース
|
履修年次
|
期別
|
曜日
|
時限
|
||||||||||||
| 263612 | 1 | G | 2 | 前期 | 月 | IV | ||||||||||||
| ［概要］ | ||||||||||||||||||
| 本演習では，講義「アルゴリズムとデータ構造」で学ぶ内容に関して，コンピュータを用いた演習と実習を行うことを目的とする．幾つかの重要で具体的なアルゴリズムやデータ構造，及びアルゴリズムに関する一般的な技術を理解した上で，C 言語によって実際にプログラミングすることによって理解を深めさせる．情報処理技術教育の基幹技術として，学生に十分な素養とスキルを持たせることを目標としている．<BR><BR>カリキュラム中での位置付け：<a href="http://www.cs.yamanashi.ac.jp/g/JABEE/curriculum/">Gコースのカリキュラム</a> | ||||||||||||||||||
| ［具体的な達成目標］ | ||||||||||||||||||
| 本科目を終了した学生は以下の項目を理解して，時間および空間計算量などを念頭においたより良いプログラムが行えるようになる．<BR><BR> ヒープ，ヒープソート，バケットソート，基数ソート，文字列照合，グラフのアルゴリズム（最短経路の探索など），動的計画法，分枝限定法，分割統治法<BR><BR>JABEE 教育プログラムの共通基準のうち，「(c) 自然科学，情報技術に関する知識とそれらを応用できる能力，(d) 該当する分野の専門技術に関する知識とそれらを問題解決に応用できる能力」の二点が修得できる．また，配布した演習問題を自主的に解きまとめることを通じて，「(g) 自主的，継続的に学習できる能力」を修得できる． | ||||||||||||||||||
| ［必要知識・準備］ | ||||||||||||||||||
| 講義「アルゴリズムとデータ構造」を履修済み，または本授業と同期に履修している必要がある．また，本演習を受講するために次の知識を必要とする．<BR>１．UNIX上でのエディタ，メールなどの基本的ツールの使用法<BR>２．C言語によるコンパイル<BR>３．C言語の基本的文法<BR>４．ポインタの操作<BR>５．構造体の操作 | ||||||||||||||||||
| ［評価方法・評価基準］ | ||||||||||||||||||
|
||||||||||||||||||
| ［教科書］ | ||||||||||||||||||
| ［参考書］ | ||||||||||||||||||
| ［講義項目］ | ||||||||||||||||||
| １．文字列照合：力まかせのアルゴリズム<BR> ２．文字列照合：Boyer-Moore 法<BR> ３．オンライン試験１<BR> ４．ヒープソート<BR> ５．バケットソート，基数ソート<BR> ６．ヒープソート，基数ソート演習<BR> ７．オンライン試験２<BR> ８．グラフの問題：ダイクストラの最短経路探索アルゴリズム（１）<BR> ９．グラフの問題：ダイクストラの最短経路探索アルゴリズム（２）<BR>１０．オンライン試験３<BR>１１．動的計画法：０−１ナップザック問題<BR>１２．分枝限定法：０−１ナップザック問題，レポート課題１<BR>１３．分割統治法：長大数の乗算 (1)<BR>１４．分割統治法：長大数の乗算 (2)，レポート課題２ | ||||||||||||||||||
| ［教育方法］ | ||||||||||||||||||
| ・プログラムを組む能力が身に付いているか判定するために，３回のオンライン試験を実施する．オンライン試験では時間内に所定の仕様を満たすプログラムの作成に取り組む．<BR>・本演習では３回のオンライン試験と２回のレポート課題を実施する．その評価においては，なるべく細かくコメントを付けて不具合のポイントなどを提示する．これによりプログラミング能力の向上，理解の促進が期待できる．<BR>・Ｃ言語の理解が不足している学生がいれば，随時Ｃ言語に関する解説も行う． | ||||||||||||||||||
| ［JABEEプログラムの学習・教育目標との対応］ | ||||||||||||||||||
|
||||||||||||||||||
| ［その他］ | ||||||||||||||||||
| (未登録) | ||||||||||||||||||