データ構造とアルゴリズム (川原 憲治)
科目名: データ構造とアルゴリズム (02) Data Structure and Algorithm
担当教員: 川原 憲治 (大学院情報工学研究院電子情報工学研究系) kawahara@cse.kyutech.ac.jp
情報科目 必修科目 2単位
1年 後期 火曜3限目 火曜4限目 端末講義室
授業の概要
授業の前半は、1年前期の「プログラミング」に引続き、C言語を用いたデータ表現方法や関数の作成方法について講義する。後半は、アルゴリズムの評価方法や基本的なデータ構造と探索法やソート法の各種アルゴリズムについて講義する。
カリキュラムにおけるこの授業の位置付け
情報系科目を受講するにあたって必須であるプログラミング能力とアルゴリズムに関する基礎知識の習得を目的とする。前半部は1年前期「プログラミング」に続く内容で、「オペレーティングシステムE」におけるシステムプログラミングのための基礎となり、後半部は「プログラム設計」「アルゴリズム設計E」において展開される高度なアルゴリズム作成における基礎知識の習得を目的とする。
授業項目 (授業計画)
- (1) C言語のプログラミング演習
- 1年前期「プログラミング」の復習
- ポインタの概念
- 関数、再帰
- 構造体
- 標準関数、ファイル処理関数
- (2) データ構造とアルゴリズムに関する講義・演習
- アルゴリズムとその評価
- 配列と連結リスト
- スタックとキュー
- 探索法
- ソート法
- 二分木、ヒープ
授業の進め方
2コマの講義時間を前半と後半に区切り、前半は、教科書および配布資料をもとに講義・説明し、後半は、主に演習に充てる。
授業の達成目標 (学習・教育目標との関連)
この講義は、電子情報工学科の目標(B-1-1)に掲げられている「計算機ソフトウェアを構成するための基本アルゴリズム、データ構造を理解し、プログラミングに用いることができる」ように、講義を通してプログラミングの概念を理解させ、目標(D-3)の「構想したものを図,式,プログラム等より表現する能力の習得」のため、演習を通して問題解決手順(アルゴリズム)をプログラムで表現する能力を習得させることを目指す。具体的には以下の達成目標を掲げる。
- (1) ポインタと構造体を利用したプログラムを理解し作成する。
- (2) 関数の概念を理解し、再帰を利用した関数を作成する。
- (3) 配列や連結リストによるデータ構造を理解する。
- (4) 基本的アルゴリズム(探索、ソート)を理解し、作成する。
- (2) 関数の概念を理解し、再帰を利用した関数を作成する。
成績評価の基準および評価方法
達成目標の(1)と(2)の習熟度をみるために中間試験を、達成目標の(3)と(4)に関して期末(定期)試験を行う。また、授業前半に前回講義内容の小テストを実施し、授業後半の演習を通して(1)から(4)のプログラミング能力を確認するためにレポート提出を義務づける。以上より、中間試験:30%、期末試験:35%、小テスト:20%、レポート:15%の比重で評価する。
キーワード
C言語、プログラミング、関数、ポインタ、構造体、データ構造、アルゴリズム、探索法、ソート法
教科書
- 皆本晃弥著:やさしく学べるC言語入門ー基礎から数値計算入門まで(サイエンス社)
参考書
- B.W.カーニハン、D.M.リッチー著、石田晴久訳: プログラムング言語C 第2版(共立出版)
- 千葉 則茂、他:Cアルゴリズム全科 基礎からグラフィクスまで(近代科学社)
- 柴田望洋:定本 明解C言語 第I巻入門編(ソフトバンク)