2011年度 工学部 知能情報工学科 夜間主コース — [選択] 2年(前期)

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

Data Structures and Algorithms 1

准教授・泓田 正雄

2単位

目的

ソフトウェア作法の基礎として,基本的なデータ構造とそれらに関係する基本的なアルゴリズムを修得させる.

概要

本講義では,基本的なデータ構造(配列,リスト,木)の実装方法を修得させる. その後,基本的なデータ構造を用いた各種探索手法,ソート法,文字列照合法)について講述する. 本講義では,各種アルゴリズムの内容を説明するだけでなく,それらの特徴(長所短所)を理解させ,適用分野に応じたアルゴリズムを選択·設計できる力を養成する.

キーワード

リスト構造,木構造,グラフ構造,探索,ソート,文字列照合

要件

C言語の知識を前提として講義を行う

目標

1.基本的なデータ構造(配列,リスト構造,木構造)を理解できる.
2.代表的な探索·ソートのアルゴリズムを理解できる.
3.適用分野に応じてアルゴリズムを選択·設計できる.
4.代表的な文字列照合·グラフ探索のアルゴリズムを理解できる.

計画

1.データ構造とアルゴリズムとは?
2.配列構造とリスト構造
3.リスト構造
4.双方向リスト
5.スタックとキュー
6.木構造
7.探索法(線形探索·2分探索)
8.探索法(ハッシュ法)
9.探索法(2分探索木法)
10.ソート法(バブルソート·選択ソート)
11.ソート法(挿入ソート·マージソート)
12.ソート法(クイックソート)
13.ソート法(ヒープソート)
14.文字列照合
15.質問・総括
16.期末試験

評価

レポート(40%),期末試験(60%)として評価し,総合点が60%以上を合格とする.

対象学生

開講コース学生のみ履修可能

教科書

津田和彦·望月久稔·泓田正雄 著「コンピュータアルゴリズム」共立出版

参考資料

近藤嘉雪 著「Cプログラマのためのアルゴリズムとデータ構造」ソフトバンク

河西朝雄 著「C言語によるはじめてのアルゴリズム入門」技術評論社

連絡先

泓田(Dr.棟603, 088-656-7564, fuketa@is.tokushima-u.ac(no-spam).jp)
オフィスアワー: 木曜日15:00∼18:00

備考

1.再試験は実施しない
2.授業を受ける際には,2時間の授業時間毎に2時間の予習と2時間の復習をしたうえで授業を受けることが,授業の理解と単位取得のために必要である.
3.授業計画1∼14は,各講義の最後に行なわれる演習および最終試験により達成 度評価を行なう.