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

科目基礎情報

学校 岐阜工業高等専門学校 開講年度 令和03年度 (2021年度)
授業科目 データ構造とアルゴリズム
科目番号 0083 科目区分 専門 / 必修
授業形態 講義 単位の種別と単位数 履修単位: 1
開設学科 電気情報工学科 対象学年 4
開設期 前期 週時間数 前期:2
教科書/教材 C によるアルゴリズムとデータ構造(茨木俊秀・オーム社)
担当教員 出口 利憲

目的・到達目標

以下の各項目を到達目標とする
(1) 基本的なデータ構造について理解する
(2) 基本的なデータ構造の実現方法について理解する
(3) 基本的なアルゴリズムを理解する
(4) 基本的なアルゴリズム設計技法を理解する
(5) 効率の評価法を理解し,データ構造・アルゴリズムの違いにより効率が異なる ことを理解する
岐阜高専ディプロマポリシー:(D)

ルーブリック

理想的な到達レベルの目安標準的な到達レベルの目安未到達レベルの目安
評価項目1基本的なデータ構造を理解し,利用できる基本的なデータ構造を理解している基本的なデータ構造を理解していない
評価項目2基本的なデータ構造の実現を理解し,利用できる基本的なデータ構造の実現を理解している基本的なデータ構造の実現を理解していない る問題を解くことができない
評価項目3種々の整列・探索を理解し,状況により選択できる種々の整列・探索方法を理解している種々の整列・探索方法を理解していない
評価項目4分割統治法,動的計画法を理解し,問題解決に用いることができる分割統治法,動的計画法を理解している分割統治法,動的計画法を理解していない
評価項目5オーダー表記を理解し,時間計算量・領域計算量を求めることができるオーダー表記を理解しているオーダー表記を理解していない

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

教育方法等

概要:
様々なデータ構造とそれを取り扱うアルゴリズムを理解する
授業の進め方と授業内容・方法:
教科書に沿って授業をすすめるが,教科書の内容から離れることもあるので講義に集中すること。
(事前準備の学習)プログラミングの復習をしておくこと。
英語導入計画:Technical terms
注意点:
第2学年・第3学年のプログラミングの知識が必要なので,十分復習しておくこと。
演習には積極的に取り組み,指定された課題を提出すること。
授業の内容を確実に身につけるために、予習・復習が必須である。

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

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

授業計画

授業内容・方法 週ごとの到達目標
前期
1stQ
1週 計算量(オーダー記法)(AL のレベル C) オーダー記法を理解する
2週 基本的なデータ構造(リスト,スタック,待ち行列)(AL のレベル C) スタック・待ち行列を理解する
3週 基本的なデータ構造(グラフ,木のデータ構造,木のなぞり,2分木,集合)(AL のレベル C) 木を理解する
4週 基本的なデータ構造(辞書,ハッシュ,互いに素な集合族)(AL のレベル C) ハッシュを理解する
互いに素な集合族の実現法を理解する
5週 基本的なデータ構造(順序付集合,優先度付き待ち行列,ヒープ)(AL のレベル C) ヒープを理解する
6週 2分探索木(AL のレベル C) 2分探索木を理解する
7週 並行探索木(AVL 木)(AL のレベル C) AVL木を理解する
8週 中間のまとめ(試験) これまでの理解が不十分な点を補い理解する。
2ndQ
9週 整列アルゴリズム(バブルソート,バケットソート)(AL のレベル C) バブルソート等およびバケットソート等を理解する
10週 整列アルゴリズム(ヒープソート,クイックソート)(AL のレベル B) ヒープソート・クイックソートを理解する
決定木を理解する
11週 整列データの処理,分割統治法(マージソート)(AL のレベル C) 分割統治法を理解する
12週 動的計画法(SUBSET-SUM)(AL のレベル C) 動的計画法を理解する
13週 資源配分問題,欲張り法(Greedy Method)(AL のレベル C) 資源配分問題を理解する
欲張り法を理解する
14週 グラフ(プリム,クラスカル,ダイクストラ)(AL のレベル C) グラフの実現を理解する
最小木を求める手法を理解する
15週 文字列照合 文字列照合の方法を理解する。
これまで理解が不十分な点を補い理解する。
16週

評価割合

試験課題合計
総合評価割合20050250
得点20050250