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

科目基礎情報

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

到達目標

(ア)実用的な探索アルゴリズムを理解し、プログラムを作成できる。
(イ)実用的な整列アルゴリズムを理解し、プログラムを作成できる。
(ウ)線形リストをクラス定義し、オブジェクト指向プログラムを作成できる。
(エ)二分探索木をクラス定義し、オブジェクト指向プログラムを作成できる。
(オ)実用的な木構造をクラス定義し、オブジェクト指向プログラムを作成できる。
(カ)実用的なグラフをクラス定義し、オブジェクト指向プログラムを作成できる。

ルーブリック

理想的な到達レベルの目安標準的な到達レベルの目安未到達レベルの目安
評価項目1アルゴリズムの概念、および、データ構造のバリエーションを理解し、プログラムとして実現できる。アルゴリズムの概念、および、データ構造のバリエーションを理解している。アルゴリズムの概念、および、データ構造のバリエーションを理解できない。
評価項目2整列、探索など、基本的なアルゴリズムについて説明でき、プログラムとして記述できる。整列、探索など、基本的なアルゴリズムについて説明できる。整列、探索など、基本的なアルゴリズムについて説明できない。
評価項目3リスト構造、スタック、キューなどの基本的なデータ構造の概念と操作を説明でき、プログラムとして記述できる。リスト構造、スタック、キューなどの基本的なデータ構造の概念と操作を説明できる。リスト構造、スタック、キューなどの基本的なデータ構造の概念と操作を説明できない。

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

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

教育方法等

概要:
上級CプログラミングA,Bにおいては、プログラミングの知識や基本的なアルゴリズムとデータ構造を学習した。本科目では、難易度の高い実用的なアルゴリズムおよびデータ構造のプログラミング演習をすることによって、アルゴリズムの効率等の数理的理論に基づく設計やコンピュータ実装に有効なデータ構造を理解するとともに、プログラミング能力にさらに磨きをかける。また、信頼性および生産性の高いソフトウェアを設計できるようにC言語に引き続いてJava言語を利用する。さらに、Java言語を効果的に利用するために、プログラムをオブジェクト指向で記述する作法を習得する。
授業の進め方と授業内容・方法:
注意点:
プログラミングI,IIA,IIB、上級CプログラミングA,Bを修得していることが望ましい。アルゴリズムとデータ構造A,Bを並行して受講しなければならない。情報数学IIA,IIBを並行して受講するのが望ましい。適宜ノートパソコンを持参すること。「情報科学」教育プログラムの必修科目である。

授業計画

授業内容・方法 週ごとの到達目標
前期
1週 シラバスを用いた授業内容の説明、Java言語の導入、基本的なデータ構造:配列 Java言語を理解し、利用できる。
2週 シラバスを用いた授業内容の説明、Java言語の導入、基本的なデータ構造:配列 Java言語を理解し、利用できる。
3週 基本的な探索アルゴリズムの復習:線形探索と二分探索 線形探索と二分探索を説明できる。
4週 基本的な探索アルゴリズムの復習:線形探索と二分探索 線形探索と二分探索をプログラムとして記述できる。
5週 実用的な探索アルゴリズム:ハッシュ探索 ハッシュ探索を説明できる。
6週 実用的な探索アルゴリズム:ハッシュ探索 ハッシュ探索を理解し、クローズドハッシュ法のプログラムとして記述できる。
7週 基本的な整列アルゴリズムの復習:選択ソート、挿入ソート、バブルソート 選択ソート、挿入ソート、バブルソートを説明できる。
8週 基本的な整列アルゴリズムの復習:選択ソート、挿入ソート、バブルソート 選択ソート、挿入ソート、バブルソートをプログラムとして記述できる。
9週 実用的な整列アルゴリズム:シェルソート シェルソートを説明できる。
10週 実用的な整列アルゴリズム:シェルソート シェルソートを理解し、プログラムとして記述できる。
11週 実用的な整列アルゴリズム:クイックソート クイックソートを説明できる。
12週 実用的な整列アルゴリズム:クイックソート クイックソートを理解し、プログラムとして記述できる。
13週 実用的な整列アルゴリズム:ヒープソート ヒープソートを説明できる。
14週 実用的な整列アルゴリズム:ヒープソート ヒープソートを理解し、プログラムとして記述できる。
15週 実用的な整列アルゴリズム:マージソート マージソートを説明できる。
16週
後期
1週 実用的な整列アルゴリズム:マージソート マージソートを理解し、プログラムとして記述できる。
2週 オブジェクト指向の導入、クラス定義の汎化と特化 オブジェクト指向の概念をアルゴリズムとデータ構造について説明できる。
3週 オブジェクト指向の導入、クラス定義の汎化と特化 オブジェクト指向の概念を理解し、オブジェクト指向プログラミングに利用できる。
4週 基本的なデータ構造:配列の実現とそれに付するアルゴリズム、スタック、キュー 配列データ構造を理解し、スタックをプログラムとして記述できる。
5週 基本的なデータ構造:配列の実現とそれに付するアルゴリズム、スタック、キュー 配列データ構造を理解し、キューをプログラムとして記述できる。
6週 実用的なデータ構造:線形リストの実現とそれに付するアルゴリズム 線形リストを説明できる。
7週 実用的なデータ構造:線形リストの実現とそれに付するアルゴリズム 線形リストを理解し、プログラムとして記述できる。
8週 実用的なデータ構造:二分探索木の実現とそれに付するアルゴリズム 二分探索木を説明できる。
9週 実用的なデータ構造:二分探索木の実現とそれに付するアルゴリズム 二分探索木を理解し、そのデータ構造及びデータの追加、探索、削除、走査をプログラムとして記述できる。
10週 実用的なデータ構造:一般的および具体的な木構造 一般的な木構造を説明できる。
11週 実用的なデータ構造:一般的および具体的な木構造 一般的な木構造を理解し、特定の木構造プログラムとして記述できる。
12週 実用的なデータ構造:一般的および具体的なグラフ 一般的なグラフを説明できる。
13週 実用的なデータ構造:一般的および具体的なグラフ 一般的なグラフを理解し、特定のグラフプログラムとして記述できる。
14週 UMLの導入:クラス図、オブジェクト図 オブジェクト指向開発の手法として、UMLを説明できる。
15週 UMLの導入:クラス図、オブジェクト図 UMLのうち、クラス図・オブジェクト図をプログラミングに利用できる。
16週

評価割合

課題合計
総合評価割合100100
専門的能力100100