山梨大学電子シラバス>検索結果一覧>授業データ



授業科目名
担当教官
アルゴリズムとデータ構造演習
岩沼 宏治/鍋島 英知
時間割番号
単位数
コース
履修年次
期別
曜日
時限
263612 1 2 前期 IV
[概要]
本演習では,講義「アルゴリズムとデータ構造」で学ぶ内容に関して,コンピュータを用いた演習と実習を行うことを目的とする.幾つかの重要で具体的なアルゴリズムやデータ構造,及びアルゴリズムに関する一般的な技術を理解した上で,C 言語によって実際にプログラミングすることによって理解を深めさせる.情報処理技術教育の基幹技術として,学生に十分な素養とスキルを持たせることを目標としている.

カリキュラム中での位置付け:Gコースのカリキュラム
[具体的な達成目標]
本科目を終了した学生は以下の項目を理解して,時間および空間計算量などを念頭においたより良いプログラムが行えるようになる.

 ヒープ,ヒープソート,バケットソート,基数ソート,文字列照合,最適化問題(資源再配分問題など),グラフのアルゴリズム(最小全域木など),分割統治法,動的計画法

JABEE 教育プログラムの共通基準のうち,「(c) 自然科学,情報技術に関する知識とそれらを応用できる能力,(d) 該当する分野の専門技術に関する知識とそれらを問題解決に応用できる能力」の二点が修得できる.また,配布した演習問題を自主的に解きまとめることを通じて,「(g) 自主的,継続的に学習できる能力」を修得できる.
[必要知識・準備]
講義「アルゴリズムとデータ構造」を履修済み,または本授業と同期に履修している必要がある.また,本演習を受講するために次の知識を必要とする.
1.UNIX上でのエディタ,メールなどの基本的ツールの使用法
2.C言語によるコンパイル
3.C言語の基本的文法
4.ポインタの操作
5.構造体の操作
[評価基準]
2回の実技・口頭試験(中間と期末)と4個のレポート課題とで成績を評価する.英語教育に関してはTOEICを補助的尺度として利用する.380点以上の点数Xについて,最高10点を限度に,(X/50)点を加算する.380点未満の点数については加点しない.
[教科書]
  1. 茨木 俊秀, アルゴリズムとデータ構造, 昭晃堂, ISBN:4785601191,
    (毎回の演習課題はオンライン資料として提供される.)
[参考書]
  1. ニール マシュー,リチャード ストーンズ, Linuxプログラミング―例題で学ぶUNIXプログラミング環境のすべて, ソフトバンクパブリッシング, ISBN:4797327014
[講義項目]
 1.挿入ソート,選択ソート
 2.ヒープソート
 3.バケットソート,基数ソート,第1回レポート
 4.文字列照合:素朴なアルゴリズム
 5.文字列照合:Boyer-Moore法,第2回レポート
 6.簡単な最適化問題:資源配分問題,連続ナップザック問題
 7.実技・口頭試問
 8.グラフの問題:ダイクストラの最短経路探索アルゴリズム
 9.グラフの問題:クラスカルの最小全域木アルゴリズム
10.グラフの問題:プリムの最小全域木アルゴリズム,第3回レポート
11.動的計画法:部分和問題
12.動的計画法:0-1ナップザック問題
13.分割統治法:長大数の乗算,第4回レポート
14.実技・口頭試問
[教育方法]
・演習では多くの小さな課題を与える.様々な問題に対してアルゴリズムを適用することにより,理解の促進を促す.
・アルゴリズムをより深く理解させるために,計4回のレポート課題を課す.レポートの評価においては,なるべく細かくコメントを付けて不具合のポイントなどを提示する.これによりプログラミング能力の向上,理解の促進が期待できる.
・C言語の理解が不足している学生がいれば,随時C言語に関する解説も行う.
[JABEEプログラムの学習・教育目標との対応]
「目標(A)情報処理技術者としての基礎的素養及び基礎的スキルの修得」に関して,情報処理技術の全ての基本であるアルゴリズムとデータ構造の基本的知識と問題解決能力およ
び応用能力を習得させる.
「目標(C)基礎的な国際コミュニケーション力と地球的視野の修得」に関して,C コンパイラが示すエラーメッセージなどの英語を理解させる.また補助手段としてTOEIC点数を評価の一部に利用する.
「目標(D)時代の変化に対応し,自律的に学習する能力の修得」に関して,演習問題を配り,自主的な勉強を誘導・推奨する.
「目標(G)次の専門技術の何れか一つ以上を具備した人材の育成」における「1.ネットワークアプリケーションを開発構築・維持管理する基礎的技術」及び「2.マルチメディアコンテンツを開発処理する基礎的技術」に関して,基本的なプログラミング技術を学ぶことにより,アプリケーション開発の基礎技術を習得させる.
[その他]
(未登録)