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

科目基礎情報

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

到達目標

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

ルーブリック

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

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

教育方法等

概要:
アルゴリズムは情報工学や情報科学を学ぶ上で基礎となる重要な科目の一つである。
本講義ではソーティングと探索に関する基本的なアルゴリズムの特性を学び、当該アルゴリズムを習得する。
授業の進め方・方法:
授業は教科書「あるごりずむ」およびプリントを主にし、スライドを併用した講義とする。
適宜実践演習やレポート課題を課し、学習内容の定着と理解度の向上を図る。
注意点:
【成績評価の基準・方法】
試験の成績80 %、平素の学習状況等20 %(課題)の割合で総合的に評価する。学年の評価は前学期末の評価とする。技術者が身につけるべき専門基礎として、上記の到達目標に対する達成度を試験等において評価する。
【事前・事後学習】
事前学習として教科書の該当部分をよく読みこむこと。また、事後学習として授業内で提示した課題に取り組み、指示があれば提出すること。
【履修上の注意】
この科目を履修するにあたり、2年生科目の「プログラミング基礎」の内容を十分に理解しておくこと。

授業の属性・履修上の区分

アクティブラーニング
ICT 利用
遠隔授業対応
実務経験のある教員による授業

授業計画

授業内容 週ごとの到達目標
前期
1stQ
1週 アルゴリズムの計算量 オーダ記法による計算量の漸近的評価を行える
2週 基本的なデータ構造(スタック、キュー) 基本的なデータ構造であるスタックとキューについてを理解する
3週 プログラミング演習① スタック構造をC言語で実装できる
4週 プログラミング演習② キュー構造をC言語で実装できる
5週 基本的なデータ構造(リスト) 基本的なデータ構造であるリストについて概要と仕組みを理解する
6週 プログラミング演習③ リスト構造をC言語で実装できる
7週 基本的なソートアルゴリズム 簡単なソーティングアルゴリズムであるバブルソート、選択法、挿入法について概要と仕組みを理解する
8週 プログラミング演習④ 選択法をC言語で実装できる
2ndQ
9週 プログラミング演習⑤ 挿入法をC言語で実装できる
10週 高速なソートアルゴリズム 高速なソートアルゴリズムであるクイックソートについて概要と仕組みを理解する
11週 プログラミング演習⑥ クイックソートをC言語で実装できる
12週 集合と探索(逐次探索、2分探索法) 単純な探索アルゴリズムである逐次探索と2分探索法について概要と仕組みを理解する
13週 プログラミング演習⑦ 2分探索法をC言語で実装できる
14週 集合と探索(木構造、2分探索木) 効率的にデータの更新を行える2分探索木について概要と仕組みを理解する
15週 プログラミング演習⑧ 2分探索木をC言語で実装できる
16週

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

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

評価割合

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