到達目標
コンピュータ内部でデータを表現する方法(データ構造)にはバリエーションがあることを理解する。同一の問題に対し,選択したデータ構造によってアルゴリズムが変化しうることを理解する。リスト構造,スタック,キューなどの基本的なデータ構造の概念と操作を説明できる。
ルーブリック
| 理想的な到達レベルの目安 | 標準的な到達レベルの目安 | 未到達レベルの目安 |
評価項目1 | コンピュータ内部でデータを表現する方法(データ構造)にはバリエーションがあることを説明できる。 | コンピュータ内部でデータを表現する方法(データ構造)にはバリエーションがあることを理解できている。 | コンピュータ内部でデータを表現する方法(データ構造)にはバリエーションがあることを理解できていない。 |
評価項目2 | 同一の問題に対し,選択したデータ構造によってアルゴリズムが変化しうることを説明できる。 | 同一の問題に対し,選択したデータ構造によってアルゴリズムが変化しうることが理解できている。 | 同一の問題に対し,選択したデータ構造によってアルゴリズムが変化しうることが理解できていない。 |
評価項目3 | リスト構造,スタック,キューなどの基本的なデータ構造の概念と操作を説明できる. | リスト構造,スタック,キューなどの基本的なデータ構造の概念と操作を理解できている。 | リスト構造,スタック,キューなどの基本的なデータ構造の概念と操作を理解できていない。 |
学科の到達目標項目との関係
(D) 専門分野の知識と情報技術を身につける。
説明
閉じる
教育方法等
概要:
プログラムを作成する上で大切なアルゴリズムとデータ構造の関係について学習します。対象となるデータの性質から,データの適切な表現方法・アルゴリズムを選択する方法を学習します。
授業の進め方・方法:
教科書および教員作成の教材を使ったe-ラーニング形式で行います。関連する授業科目にアルゴリズム演習があり,実際にプログラムを作成することで,データ構造とアルゴリズムの理解を深めることが重要です。
課題レポート40%,期末試験60%で総合評価し,60点以上を合格とします。
注意点:
C言語によるプログラミングを理解できることが望ましい。データ構造は,プログラムにおけるデータの表現方法について学ぶ学問です。知識として理解するだけでなく,プログラムを実際に動作させることで理解を深めることが大切です。
事前・事後学習、オフィスアワー
この科目は学修単位科目のため,事前・事後学習として課題レポートの提出があります。
【オフィスアワー】 授業日 15:00~17:00(遠隔授業中は,メールで対応します)
授業計画
|
|
週 |
授業内容 |
週ごとの到達目標 |
前期 |
1stQ |
1週 |
ガイダンス シラバスの説明,授業の進め方 |
シラバス,遠隔授業の進め方,コンテンツの利用方法を理解する。
|
2週 |
アルゴリズムの基礎 |
アルゴリズムの概念を説明できる。
|
3週 |
アルゴリズムの評価基準 計算量,最大計算量,平均計算量,時間計算量,領域計算量 |
アルゴリズムの複雑さを表す計算量を説明できる。アルゴリズムによって計算量が変わることを説明できる。最大計算量と平均計算量を説明できる。
|
4週 |
基本データ構造 配列,連結リスト |
配列と構造体を理解し,配列と構造体の使い分けができる。連結リストの考え方を説明できる。ポインタを使った実装方法を説明できる。循環リスト・双方向リストを説明できる。
|
5週 |
基本データ構造 スタック,キュー |
スタック,キュー,ハッシングを理解し,説明できる。スタックを使った数式評価の方法を説明できる。
|
6週 |
木構造 |
木構造に関する基本的な用語を説明できる。順序木,無順序木を説明できる。3つの代表的な方法で木を探索することができる。
|
7週 |
再帰 |
代表的な再帰アルゴリズムを説明できる。
|
8週 |
データの探索 線形探索法,2分探索法 |
表を用いた代表的探索法である線形探索法と2分探索法を説明できる。
|
2ndQ |
9週 |
データの探索 ハッシュ法 |
表を用いた代表的探索法であるハッシュ法の考え方を説明できる。ハッシュ関数に求められる性質を説明できる。
|
10週 |
ソートアルゴリズム 昇順,降順,安定なソート,内部ソート,外部ソート,バブルソート |
ソート処理の基本的な用語を説明できる。 バブルソート,挿入ソートのアルゴリズム,性質・特徴を説明できる。
|
11週 |
ソートアルゴリズム 挿入ソート,ヒープソート |
挿入ソート,ヒープソートのアルゴリズム,性質・特徴を説明できる。
|
12週 |
ソートアルゴリズム クイックソート,マージソート |
クイックソート,マージソートのアルゴリズム,性質・特徴を説明できる。
|
13週 |
アルゴリズムの設計手法 分割統治法・バックトラック法 |
分割統治法の考え方を説明できる。 バックトラック法の考え方を説明できる。
|
14週 |
正規表現 有限オートマトン |
正規表現が表す文字クラスを説明できる。正規表現によるパターンマッチを行う有限オートマトンについて説明できる。
|
15週 |
決定性有限オートマトン,非決定性有限オートマトン |
決定性有限オートマトン,非決定性有限オートマトンの特徴を説明できる。非決定性有限オートマトンを決定性有限オートマトンに変換することができる。
|
16週 |
期末試験 |
|
モデルコアカリキュラムの学習内容と到達目標
分類 | 分野 | 学習内容 | 学習内容の到達目標 | 到達レベル | 授業週 |
専門的能力 | 分野別の専門工学 | 情報系分野 | ソフトウェア | アルゴリズムの概念を説明できる。 | 4 | |
与えられたアルゴリズムが問題を解決していく過程を説明できる。 | 4 | |
同一の問題に対し、それを解決できる複数のアルゴリズムが存在しうることを説明できる。 | 4 | |
整列、探索など、基本的なアルゴリズムについて説明できる。 | 4 | |
時間計算量によってアルゴリズムを比較・評価できることを説明できる。 | 4 | |
領域計算量などによってアルゴリズムを比較・評価できることを説明できる。 | 4 | |
コンピュータ内部でデータを表現する方法(データ構造)にはバリエーションがあることを説明できる。 | 4 | |
同一の問題に対し、選択したデータ構造によってアルゴリズムが変化しうることを説明できる。 | 4 | |
リスト構造、スタック、キュー、木構造などの基本的なデータ構造の概念と操作を説明できる。 | 4 | |
システムプログラム | 形式言語の概念について説明できる。 | 4 | |
オートマトンの概念について説明できる。 | 4 | |
形式言語が制限の多さにしたがって分類されることを説明できる。 | 4 | |
正規表現と有限オートマトンの関係を説明できる。 | 4 | |
その他の学習内容 | データモデル、データベース設計法に関する基本的な概念を説明できる。 | 4 | |
データベース言語を用いて基本的なデータ問合わせを記述できる。 | 4 | |
評価割合
| 試験 | 発表 | 相互評価 | 態度 | ポートフォリオ | その他 | 合計 |
総合評価割合 | 60 | 0 | 0 | 0 | 0 | 40 | 100 |
基礎的能力 | 10 | 0 | 0 | 0 | 0 | 10 | 20 |
専門的能力 | 40 | 0 | 0 | 0 | 0 | 20 | 60 |
分野横断的能力 | 10 | 0 | 0 | 0 | 0 | 10 | 20 |