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

科目基礎情報

学校 群馬工業高等専門学校 開講年度 令和05年度 (2023年度)
授業科目 アルゴリズムとデータ構造
科目番号 3J016 科目区分 専門 / 必修
授業形態 授業 単位の種別と単位数 履修単位: 2
開設学科 電子情報工学科 対象学年 3
開設期 通年 週時間数 2
教科書/教材 教科書:Cによるアルゴリズムとデータ構造(松原 雅文,山田 敬三 著, 森北出版),参考書:アルゴリズムとデータ構造 第2版(藤原 暁宏 著,森北出版) / その他必要に応じて適宜参考書を指定・参照する
担当教員 川本 真一

到達目標

□基本的なアルゴリズムに関する計算量について説明できる
□基本的なデータ構造について説明できる
□基本的な整列・探索アルゴリズムを説明できる
□基本的な組み合わせ問題について説明できる
□基本的なデータ構造を使ったプログラムを作成できる
□基本的なアルゴリズムを使ったプログラムを作成できる

ルーブリック

理想的な到達レベルの目安標準的な到達レベルの目安未到達レベルの目安
評価項目1基本的なアルゴリズムに関する計算量について十分に説明できる基本的なアルゴリズムに関する計算量について説明できる基本的なアルゴリズムに関する計算量について説明できない
評価項目2基本的なデータ構造についてよく説明できる基本的なデータ構造について説明できる基本的なデータ構造について説明できない
評価項目3基本的な探索・整列アルゴリズムをよく説明できる基本的な探索・整列アルゴリズムを説明できる基本的な探索・整列アルゴリズムを説明できない
評価項目4基本的な組み合わせ問題についてよく説明できる基本的な組み合わせ問題について説明できる基本的な組み合わせ問題について説明できない
評価項目5基本的なデータ構造を使ったプログラムを作成できる基本的なデータ構造を使った簡単なプログラムを作成できる基本的なデータ構造を使った簡単なプログラムを作成できない
評価項目6基本的なアルゴリズムを使ったプログラムを作成できる基本的なアルゴリズムを使った簡単なプログラムを作成できる基本的なアルゴリズムを使った簡単なプログラムが作成できない

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

教育方法等

概要:
C言語を利用してどのように所望の処理を実現するか、また処理対象のデータをコンピュータ上でどのように扱うかについて、その基本的なものを取り上げて学ぶ。
授業の進め方・方法:
座学による講義とプログラミングの演習を併用して進める
注意点:
2年次までに学んだC言語の基礎知識については理解していることを前提とするため、プログラミング言語の復習をしっかり行なうこと。
また、授業毎の予習や復習をこまめに行なうこと。

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

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

授業計画

授業内容 週ごとの到達目標
前期
1stQ
1週 前期ガイダンス 前期の授業概要を説明し、前提知識を確認する
2週 プログラミング環境概論 授業で使用するプログラミング環境の概要を理解し、その使用方法を確認する
3週 計算量 オーダ記法の基本事項を理解する
4週 再帰処理 再帰処理の基本事項を理解する
5週 基本的なデータ構造 キューとスタックの基本事項を理解する
6週 基本的なデータ構造 連結リストの基本事項を理解する
7週 探索アルゴリズム 線形探索と2分探索の基本事項を理解する
8週 前期中間試験
2ndQ
9週 基本的なデータ構造 ここまでの内容を振り返り、整理する
10週 基本的なデータ構造 2分木の基本事項を理解する
11週 基本的なデータ構造 2分木の基本操作を理解する
12週 探索アルゴリズム 2分探索木の基本事項を理解する
13週 探索アルゴリズム 文字列探索の基本事項を理解する
14週 探索アルゴリズム ハッシュ法の基本事項を理解する
15週 前期期末試験
16週 前期まとめと振り返り
後期
3rdQ
1週 後期ガイダンス 後期の授業概要を説明し、前提知識を確認する
2週 整列アルゴリズム 基本的なソートアルゴリズム(選択法、挿入法、交換法)の基本事項を理解する
3週 整列アルゴリズム クイックソートの基本的な考え方を理解する
4週 整列アルゴリズム マージソートの基本的な考え方を理解する
5週 整列アルゴリズム ヒープ木の基本事項とヒープソートの基本的な考え方を理解する
6週 探索アルゴリズム 順列生成と組み合わせ列挙の基本事項について理解する
7週 探索アルゴリズム バックトラック法の基本事項について理解する
8週 後期中間試験
4thQ
9週 探索アルゴリズム 貪欲法の基本事項について理解する
10週 探索アルゴリズム 動的計画法の基本事項について理解する
11週 探索アルゴリズム 典型的な問題を例に、貪欲法と動的計画法の違いを比較する
12週 基本的なデータ構造 グラフの基本事項について理解する
13週 基本的なデータ構造 グラフの基本操作について理解する
14週 探索アルゴリズム グラフに関するアルゴリズムの一例(ダイクストラ法)を理解する
15週 後期期末試験
16週 後期まとめと振り返り

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

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

評価割合

試験発表相互評価態度ポートフォリオその他合計
総合評価割合80000020100
基礎的能力6000001070
専門的能力2000001030
分野横断的能力0000000