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

科目基礎情報

学校 群馬工業高等専門学校 開講年度 令和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週 後期まとめと振り返り

評価割合

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