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

科目基礎情報

学校 高知工業高等専門学校 開講年度 平成31年度 (2019年度)
授業科目 アルゴリズムとデータ構造
科目番号 I3011 科目区分 専門 / 必修
授業形態 講義 単位の種別と単位数 履修単位: 1
開設学科 SD 情報セキュリティコース 対象学年 3
開設期 前期 週時間数 2
教科書/教材 教科書:広瀬貞樹、あるごりずむ、近代科学社
担当教員 浦山 康洋

到達目標

(1) アルゴリズムの計算量をオーダによって評価できる
(2) スタック・キュー・リストなどの基本的なデータ構造を理解し、説明できる
(3) 基本的なソーティングアルゴリズムを理解し、説明できる
(4) 基本的な探索アルゴリズムを理解し、説明できる

ルーブリック

理想的な到達レベルの目安標準的な到達レベルの目安未到達レベルの目安
評価項目1任意のアルゴリズムを与えられたときに、そのアルゴリズムの計算量をオーダで求めることができるオーダ記法を理解し、計算量を求めることができるオーダ計算を行うことができない
評価項目2スタック・キュー・リストなどの基本的なデータ構造を理解し、任意のプログラミング言語で実装できるスタック・キュー・リストなどの基本的なデータ構造を理解し、説明できるスタック・キュー・リストなどの基本的なデータ構造を説明できない
評価項目3基本的なソーティングアルゴリズムを理解し、任意のプログラミング言語で実装できる基本的なソーティングアルゴリズムを理解し、説明できる基本的なソーティングアルゴリズムを説明できない
評価項目4基本的な探索アルゴリズムを理解し、任意のプログラミング言語で実装できる基本的な探索アルゴリズムを理解し、説明できる基本的な探索アルゴリズムを説明できない

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

教育方法等

概要:
アルゴリズムは情報工学や情報科学を学ぶ上で基礎となる重要な科目の一つである。
本講義ではソーティングと探索に関する基本的なアルゴリズムの特性を学び、当該アルゴリズムを習得する。
授業の進め方・方法:
授業は主に講義形式で進める。
適宜実践演習や小テストを行い、学習内容の理解を深める。
注意点:
試験の成績80 %、平素の学習状況等20 %(課題・小テスト・レポート・発表等を含む)の割合で総合的に評価する。学期末の評価は中間と期末の評価の平均とする。

授業計画

授業内容 週ごとの到達目標
前期
1stQ
1週 アルゴリズムの計算量 オーダ記法による計算量の漸近的評価を行える
2週 基本的なデータ構造① スタックの構造と仕組みを理解する
3週 基本的なデータ構造② キューの構造と仕組みを理解する
4週 基本的なデータ構造③ リストの構造と仕組みを理解する
5週 ソーティング① 簡単なソーティングアルゴリズムであるバブルソート・を理解する
6週 ソーティング② 簡単なソーティングアルゴリズムである選択法を理解する
7週 ソーティング③ 簡単なソーティングアルゴリズムである挿入法を理解する
8週 中間試験
2ndQ
9週 ソーティング④ 高速なソーティングアルゴリズムであるクイックソートを理解する
10週 集合と探索① 単純な探索手法である逐次探索を理解する
11週 集合と探索② 高速な探索手法である2分探索法を理解する
12週 集合と探索③ 探索を効率よく行うためのデータ構造として2分探索木を理解する
13週 集合と探索④ ヒープ構造を理解する
14週 ソーティング⑤ ヒープを用いたソーティングアルゴリズムであるヒープソートを理解する
15週 ソーティング⑥ ヒープを用いたソーティングアルゴリズムであるヒープソートを理解する
16週 期末試験

モデルコアカリキュラムの学習内容と到達目標

分類分野学習内容学習内容の到達目標到達レベル授業週
基礎的能力工学基礎情報リテラシー情報リテラシー同一の問題に対し、それを解決できる複数のアルゴリズムが存在しうることを知っている。4前4,前5,前6,前12,前13
与えられた基本的な問題を解くための適切なアルゴリズムを構築することができる。4前4,前5,前6,前7,前9,前10,前12,前13,前15
任意のプログラミング言語を用いて、構築したアルゴリズムを実装できる。4前7,前14
専門的能力分野別の専門工学情報系分野プログラミング代入や演算子の概念を理解し、式を記述できる。4前7,前14
プロシージャ(または、関数、サブルーチンなど)の概念を理解し、これらを含むプログラムを記述できる。4前7,前14
変数の概念を説明できる。4前7,前14
データ型の概念を説明できる。4前7,前14
制御構造の概念を理解し、条件分岐を記述できる。4前7,前14
制御構造の概念を理解し、反復処理を記述できる。4前7,前14
与えられた問題に対して、それを解決するためのソースプログラムを記述できる。4前7,前14
ソフトウェア生成に必要なツールを使い、ソースプログラムをロードモジュールに変換して実行できる。4前7,前14
与えられたソースプログラムを解析し、プログラムの動作を予測することができる。4前4,前5,前6,前7,前9,前10,前12,前13
ソフトウェアアルゴリズムの概念を説明できる。4前1,前4,前5,前6,前9,前10,前12,前13,前15
与えられたアルゴリズムが問題を解決していく過程を説明できる。4前4,前5,前6,前9,前10,前12,前13,前15
同一の問題に対し、それを解決できる複数のアルゴリズムが存在しうることを説明できる。4前4,前5,前6,前12,前13
整列、探索など、基本的なアルゴリズムについて説明できる。4前4,前5,前6,前9,前10,前12,前13
時間計算量によってアルゴリズムを比較・評価できることを説明できる。4前1,前4,前5,前6,前9,前10,前12,前13
領域計算量などによってアルゴリズムを比較・評価できることを説明できる。4前1,前4,前5,前6,前9,前10,前12,前13
コンピュータ内部でデータを表現する方法(データ構造)にはバリエーションがあることを説明できる。4前2,前3,前9,前10,前11
同一の問題に対し、選択したデータ構造によってアルゴリズムが変化しうることを説明できる。4前4,前5,前12,前13
リスト構造、スタック、キュー、木構造などの基本的なデータ構造の概念と操作を説明できる。4前2,前3,前9,前10,前11
リスト構造、スタック、キュー、木構造などの基本的なデータ構造を実装することができる。4前2,前3,前9,前10,前11,前14
ソースプログラムを解析することにより、計算量等のさまざまな観点から評価できる。4前4,前5,前6,前7,前9,前10,前12,前13,前14,前15
同じ問題を解決する複数のプログラムを計算量等の観点から比較できる。4前4,前5,前6,前7,前12,前13

評価割合

試験平素の学習状況合計
総合評価割合80200000100
基礎的能力5010000060
専門的能力3010000040
分野横断的能力0000000