|
授業科目名
|
担当教員
|
|||||||||||||||||
|
アルゴリズムとデータ構造演習
|
岩沼 宏治／鍋島 英知
|
|||||||||||||||||
|
時間割番号
|
単位数
|
コース
|
履修年次
|
期別
|
曜日
|
時限
|
||||||||||||
| 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>１３．分枝限定法：０−１ナップザック問題<BR>１４．オンライン試験３ | ||||||||||||||||||
| ［教育方法］ | ||||||||||||||||||
| ・プログラムを組む能力が身に付いているか判定するために，３回のオンライン試験を実施する．オンライン試験では時間内に所定の仕様を満たすプログラムの作成に取り組む．<BR>・本演習では２回のレポート課題と３回のオンライン試験を実施する．その評価においては，なるべく細かくコメントを付けて不具合のポイントなどを提示する．これによりプログラミング能力の向上，理解の促進が期待できる．<BR>・Ｃ言語の理解が不足している学生がいれば，随時Ｃ言語に関する解説も行う． | ||||||||||||||||||
| ［JABEEプログラムの学習・教育目標との対応］ | ||||||||||||||||||
| 「目標(A)情報処理技術者としての基礎的素養及び基礎的スキルの修得」に関して，情報処理技術の全ての基本であるアルゴリズムとデータ構造の基本的知識と問題解決能力およ<BR>び応用能力を習得させる．<BR>「目標(C)基礎的な国際コミュニケーション力と地球的視野の修得」に関して，C コンパイラが示すエラーメッセージなどの英語を理解させる．<BR>「目標(D)時代の変化に対応し，自律的に学習する能力の修得」に関して，演習問題を配り，自主的な勉強を誘導・推奨する．<BR>「目標(G)次の専門技術の何れか一つ以上を具備した人材の育成」における「1.ネットワークアプリケーションを開発構築・維持管理する基礎的技術」及び「2.マルチメディアコンテンツを開発処理する基礎的技術」に関して，基本的なプログラミング技術を学ぶことにより，アプリケーション開発の基礎技術を習得させる． | ||||||||||||||||||
| ［その他］ | ||||||||||||||||||
| (未登録) | ||||||||||||||||||