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

科目基礎情報

学校 奈良工業高等専門学校 開講年度 令和04年度 (2022年度)
授業科目 アルゴリズムとデータ構造
科目番号 0049 科目区分 専門 / 必修
授業形態 講義 単位の種別と単位数 履修単位: 1
開設学科 電子制御工学科 対象学年 3
開設期 前期 週時間数 2
教科書/教材 アルゴリズムとデータ構造,出版社:森北出版,著者 :平田 富夫
担当教員 櫟 弘明

到達目標

1.アルゴリズムについて,必要性とその概略を説明できる.
2.線形探索,2分探索,ハッシュ法の各アルゴリズムについて説明できる.
3.スタックとキューの構造や特徴を説明できる.
4.単純交換・選択・挿入ソートの特徴を説明できる.
5.シェルソート・クイックソート・ヒープソートの特徴を説明できる.
6.木構造について説明ができる.
7.単方向,双方向,循環リスト構造を理解し,利用することができる.

ルーブリック

理想的な到達レベルの目安標準的な到達レベルの目安未到達レベルの目安
シェルソート,クイックソート,ヒープソートソートアルゴリズムついて十分に理解しコードを書くことができるソートアルゴリズムの特徴が理解できているソートアルゴリズムを一つも説明できない
線形探索,二分探索,ハッシュ法探索について十分理解し,コードを書くことができる探索あるアルゴリズムの特徴が理解できている探索アルゴリズムを一つも説明できない
スタックとキューデータ構造を理解しその応用ができるスタック,キューの説明ができるスタックとキューの違いが分からない

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

準学士課程(本科1〜5年)学習教育目標 (2) 説明 閉じる

教育方法等

概要:
社会システムの複雑化に伴い,ソフトウェアの肥大化・複雑化・高速化が求められ,ソフトウェア技術の発展の期待度は高まっている.ソフトウェア分野の一つであるアルゴリズムとデータ構造は,ソフトウェアの基礎理論であり技術者にとって重要かつ必須な知識である.本講義では,こうした基礎理論を学習し,簡単なソフトウェアを設計する能力を身につける.
授業の進め方・方法:
座学による講義が中心である.講義項目ごとに演習問題に取り組み,各自の理解度を確認する.また,定期試験返却時に解説を行い,理解が不十分な点を解消する.
注意点:
 関連科目
情報数学,プログラミング,計算機アーキテクチャ,数値解析との関係が深い.

  学習指針
計算機を使った問題解決の様々なアルゴリズムを学習する.講義内容を上手くノートにまとめ,教科書の演習問題も活用しながら理解を深めてもらいたい.

事前学習:受講前に教科書の授業範囲を事前に読んでおくこと
事後展開学習:授業に関連する教科書の章末問題を課題として設定するので,自分で解き,授業時に提出する

学修単位の履修上の注意

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

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

授業計画

授業内容 週ごとの到達目標
前期
1stQ
1週 線形探索 線形探索,番兵法について説明ができる.
2週 2分探索 2分探索について説明ができる.
3週 ハッシュ法 ハッシュ法,チェイン法,オープンアドレス法について説明ができる.
4週 スタックとキュー スタック,キュー,リングバッファによるキューの実現について説明ができる.
5週 再帰的アルゴリズム 再起的アルゴリズムの解析について説明ができる.
6週 単純ソート 単純交換・選択・挿入ソートのアルゴリズムついて説明ができる.
7週 前期中間試験 授業内容を理解し,試験問題に対して正しく解答できる.
8週 試験返却・解答 試験問題を見直し,理解が不十分な点を解消する.
2ndQ
9週 シェルソート シェルソートについて説明ができる.
10週 クイックソート クイックソートについて説明ができる.
11週 ヒープソート ヒープと配列のヒープ化について説明ができる
12週 木構造 木に関する用語,順序木と無順序木,部分木,2分木について説明ができる.
13週 線形リスト ノードや,配列とポインタを用いた線形リストの違いについて説明ができる.
14週 循環リスト 循環リストを用いた,ノードの削除,追加,探索について説明ができる.
15週 前期末間試験 授業内容を理解し,試験問題に対して正しく解答できる.
16週 試験返却・解答 試験問題を見直し,理解が不十分な点を解消する.

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

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

評価割合

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