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

科目基礎情報

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

到達目標

(ア)アルゴリズムとデータ構造がプログラミングの要であることを理解する。
(イ)C言語およびJava言語の文法とプログラミング方法を理解し、プログラム作成に利用できる。
(ウ)アルゴリズムと効率、アルゴリズムの複雑さ、オーダの概念を理解し、各種アルゴリズムの計算量を見積もることができる。
(エ)複数の実用的な探索アルゴリズムを理解し、プログラムを作成できる。また、問題を解決していく過程を説明できる。
(オ)複数の実用的な整列アルゴリズムを理解し、プログラムを作成できる。また、問題を解決していく過程を説明できる。

ルーブリック

理想的な到達レベルの目安標準的な到達レベルの目安未到達レベルの目安
評価項目1アルゴリズムの概念、および、整列・探索アルゴリズムが問題を解決していく過程を説明でき、さらに、時間計算量や領域計算量などによってアルゴリズムを比較・評価できる。アルゴリズムの概念、および、整列・探索アルゴリズムが問題を解決していく過程を説明できる。アルゴリズムの概念、および、整列・探索アルゴリズムが問題を解決していく過程を説明できない。
評価項目2コンピュータ内部でデータを表現する方法(データ構造)にはバリエーションがあることを理解しており、探索問題に対し、選択したデータ構造によってアルゴリズムが変化しうることを理解している。コンピュータ内部でデータを表現する方法(データ構造)にはバリエーションがあることを理解している。コンピュータ内部でデータを表現する方法(データ構造)にはバリエーションがあることを理解していない。
評価項目3オブジェクト指向によるソフトウェア開発に利用する標準的なツールの種類と機能を説明でき、Java言語をソフトウェア開発に利用することができる。オブジェクト指向によるソフトウェア開発に利用する標準的なツールの種類と機能を説明できる。オブジェクト指向によるソフトウェア開発に利用する標準的なツールの種類と機能を説明できない。

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

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

教育方法等

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

授業計画

授業内容・方法 週ごとの到達目標
前期
1週 シラバスを用いた授業内容の説明、アルゴリズムと効率、アルゴリズムと複雑さ、計算量のオーダ アルゴリズムの概念を説明できる。
2週 シラバスを用いた授業内容の説明、アルゴリズムと効率、アルゴリズムと複雑さ、計算量のオーダ アルゴリズムの概念を説明できる。
3週 Java言語の習得、クラスの導入(予習・復習:Javaのインストール) ソフトウェア開発に利用する標準的なツールの種類と機能を説明できる。
4週 Java言語の習得、クラスの導入(予習・復習:Javaのインストール) ソフトウェア開発に利用する標準的なツールの種類と機能を説明できる。
5週 配列、配列を使ったアルゴリズム(復習:基本的な探索と整列) コンピュータ内部でデータを表現する方法(データ構造)にはバリエーションがあることを理解している。
6週 配列、配列を使ったアルゴリズム(復習:基本的な探索と整列) コンピュータ内部でデータを表現する方法(データ構造)にはバリエーションがあることを理解している。
7週 基本的な探索アルゴリズムの復習:線形探索と二分探索(復習:線形探索と二分探索のプログラミング) 与えられたアルゴリズムが問題を解決していく過程を説明できる。
8週 実用的な探索アルゴリズム:ハッシュ探索(復習:ハッシュ探索のプログラミング) 同一の問題に対し、選択したデータ構造によってアルゴリズムが変化しうることを理解している。
9週 基本的な整列アルゴリズムの復習:選択ソート、挿入ソート、バブルソート(復習:古典的ソートの整理) 与えられたアルゴリズムが問題を解決していく過程を説明できる。
10週 実用的な整列アルゴリズム:シェルソート(復習:シェルソートのプログラミング) 同一の問題に対し、それを解決できる複数のアルゴリズムが存在しうることを理解している。
11週 実用的な整列アルゴリズム:クイックソート(復習:クイックソートのプログラミング) 同一の問題に対し、それを解決できる複数のアルゴリズムが存在しうることを理解している。
12週 実用的な整列アルゴリズム:ヒープソート(復習:ヒープソートのプログラミング) 同一の問題に対し、それを解決できる複数のアルゴリズムが存在しうることを理解している。
13週 実用的な整列アルゴリズム:マージソート(復習:マージソートのプログラミング) 同一の問題に対し、それを解決できる複数のアルゴリズムが存在しうることを理解している。
14週 各種アルゴリズムの計算量の見積り 時間計算量や領域計算量などによってアルゴリズムを比較・評価できることを理解している。
15週 各種アルゴリズムの計算量の見積り ソースプログラムを解析することにより、計算量等のさまざまな観点から評価できる。同じ問題を解決する複数のプログラムを計算量等の観点から比較できる。
16週

評価割合

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