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

科目基礎情報

学校 豊田工業高等専門学校 開講年度 平成30年度 (2018年度)
授業科目 アルゴリズムとデータ構造B
科目番号 34205 科目区分 専門 / 選択
授業形態 講義 単位の種別と単位数 学修単位: 1
開設学科 情報工学科 対象学年 4
開設期 後期 週時間数 1
教科書/教材 「新・明解C言語によるアルゴリズムとデータ構造」柴田望洋、辻亮介著(ソフトバンククリエイティブ)ISBN:978-4797366242、「本格学習Java入門[改訂新版]」佐々木整著(技術評論社)ISBN:978-4774146904/「明解Javaによるアルゴリズムとデータ構造」柴田望洋著(ソフトバンククリエイティブ)ISBN:978-4797345230
担当教員 江﨑 信行

到達目標

(ア)アルゴリズムとデータ構造がプログラミングの要であることを理解する。
(イ)Javaの文法とオブジェクト指向を理解し、プログラム設計に利用できる。
(ウ)線形リスト、スタック、キューなどのデータ構造を抽象的に理解し、効果的にクラスの特化と汎化ができる。
(エ)配列および線形リストをクラス定義し、オブジェクト指向プログラムを作成できる。また、それらの対比ができる。
(オ)二分探索木をクラス定義し、オブジェクト指向プログラムを作成できる。
(カ)UMLの基礎を理解し、簡単なオブジェクト指向プログラムの設計に利用できる。

ルーブリック

理想的な到達レベルの目安標準的な到達レベルの目安未到達レベルの目安
評価項目1リスト構造、スタック、キューなどの基本的なデータ構造の概念と操作を説明でき、実際にプログラムとして実現できる。リスト構造、スタック、キューなどの基本的なデータ構造の概念と操作を説明できる。リスト構造、スタック、キューなどの基本的なデータ構造の概念と操作を説明できない。
評価項目2同一の問題に対し、選択したデータ構造によってアルゴリズムが変化しうることを理解しており、データ構造に付随するアルゴリズムをプログラムとして実現できる。同一の問題に対し、選択したデータ構造によってアルゴリズムが変化しうることを理解している。同一の問題に対し、選択したデータ構造によってアルゴリズムが変化しうることを理解していない。
評価項目3オブジェクト指向によるソフトウェア開発に利用する標準的なツールの種類と機能を説明でき、UMLをソフトウェア開発に利用することができる。オブジェクト指向によるソフトウェア開発に利用する標準的なツールの種類と機能を説明できる。オブジェクト指向によるソフトウェア開発に利用する標準的なツールの種類と機能を説明できない。

学科の到達目標項目との関係

学習・教育到達度目標 A2, JABEE d, 本校教育目標 ①

教育方法等

概要:
本科目では、実用的なデータ構造のプログラミングを中心に講義を進める。コンピュータ上で効果的にデータを扱うことができる複雑なデータ構造とそれに付するアルゴリズムを取り扱う場合、アルゴリズムとデータ構造を抽象的に取り扱うオブジェクト指向が有効である。Java言語でのデータ構造とそれらに付するアルゴリズムの実装を通して、オブジェクト指向の概念を理解するとともにJavaの文法を整理する。さらに、統一モデリング言語(UML、Unified Modeling Language)によるソフトウェア設計方法を導入する。
授業の進め方と授業内容・方法:
注意点:
プログラミングI,IIA,IIB、上級CプログラミングA,B、アルゴリズムとデータ構造A、情報数学IIAを修得していることが望ましい。アルゴリズムとデータ構造演習、情報数学IIBを並行して受講することが望ましい。継続的に授業内容の予習・復習を行うこと。適宜ノートパソコンを持参すること。「情報科学」教育プログラムの必履修科目である。

授業計画

授業内容・方法 週ごとの到達目標
後期
1週 シラバスを用いた授業内容の説明、データ構造論概要 コンピュータ内部でデータを表現する方法(データ構造)にはバリエーションがあることを理解している。
2週 Javaにおけるデータ構造の実現、クラス定義(復習:Javaによるオブジェクト指向プログラミング) クラス定義によって、Javaにおけるデータ構造を実現できる。
3週 配列の実現とそれに付するアルゴリズムの復習(予習・復習:配列によるアルゴリズムの整理、分析・設計) クラス定義によって配列の実現し、それに付するアルゴリズムを記述できる。
4週 クラス定義の汎化と特化 クラス定義の汎化と特化を理解している。
5週 線形リストの実現とそれに付するアルゴリズム(復習:線形リストの分析・設計) リスト構造の概念と操作を説明できる。
6週 線形リストの実現とそれに付するアルゴリズム(復習:線形リストの分析・設計) リスト構造の概念と操作を説明でき、プログラムとして実現できる。
7週 二分探索木の実現とそれに付するアルゴリズム(復習:二分探索木の分析・設計) 二分探索木の概念と操作を説明できる。
8週 二分探索木の実現とそれに付するアルゴリズム(復習:二分探索木の分析・設計) 二分探索木の概念と操作を説明でき、プログラムとして実現できる。
9週 一般的な木構造のクラス定義(復習:一般的な木構造の分析・設計) 木構造の概念と操作を説明できる。
10週 特化した木構造の実現:ヒープの実現、多分木の構造(復習:木構造のプログラミング) 一般的な木構造の概念と操作を説明でき、ヒープなどの特定の木構造としてプログラミングできる。
11週 一般的なグラフのクラス定義(復習:一般的なグラフの分析・設計) グラフの概念と操作を説明できる。
12週 特化したグラフ(有向/無向、重み付き/なし)の構造(復習:グラフのプログラミング) 一般的なグラフの概念と操作を説明でき、特定のグラフとしてプログラミングできる。
13週 各データ構造(リスト、木、グラフ)の関係とデータ構造の違いによるアルゴリズムの効率 同一の問題に対し、選択したデータ構造によってアルゴリズムが変化しうることを理解している。
14週 UMLの導入:クラス図、オブジェクト図(復習:クラス図、オブジェクト図の描画) UMLのうち、クラス図・オブジェクト図の記述を理解する。
15週 UMLの導入:クラス図、オブジェクト図(復習:クラス図、オブジェクト図の描画) UMLのうち、クラス図・オブジェクト図の記述を理解し、プログラミングに利用できる。
16週

評価割合

定期試験小テスト合計
総合評価割合5050100
専門的能力5050100