到達目標
1.計算量とO記法が理解でき,スタックやキュー,配列,木構造などいろいろなデータ構造の違いが説明できる.
2.探索の定義が理解でき,各探索アルゴリズムの違いについて理解できる.
3.再帰とそのアルゴリズムが理解できる.
4.各ソートアルゴリズムの違いと計算量が理解できる.
5.文字列処理,文字列探索法が理解できる.
6.アルゴリズムの限界,問題の複雑さ,問題のクラスを理解できる.
ルーブリック
| 理想的な到達レベルの目安 | 標準的な到達レベルの目安 | 未到達レベルの目安 |
評価項目1 | 計算量とO記法が理解でき,スタックやキュー,配列,木構造などデータ構造を問題に応じて適切に選択し,実装することができる. | 計算量とO記法が理解でき,スタックやキュー,配列,木構造などいろいろなデータ構造の違いが説明できる. | 計算量とO記法が理解できない.スタックやキュー,配列,木構造などいろいろなデータ構造の違いが説明できない. |
評価項目2 | 各探索アルゴリズムを計算量を考慮し,実装することができる. | 探索の定義が理解でき,各探索アルゴリズムの違いについて理解できる. | 探索の定義が理解できず,各探索アルゴリズムの違いについて理解できない. |
評価項目3 | 再帰が理解でき,再帰アルゴリズムを実装することができる | 再帰とそのアルゴリズムが理解できる. | 再帰とそのアルゴリズムが理解できる. |
評価項目4 | 各ソートアルゴリズムを実装し,計算量の違いについて考察することができる. | 各ソートアルゴリズムの違いと計算量が理解できる. | 各ソートアルゴリズムと計算量が理解できない. |
評価項目5 | 文字列処理,各文字列探索法を実装することができる. | 文字列処理,文字列探索法が理解できる. | 文字列処理,文字列探索法が理解できない. |
評価項目6 | 与えられた問題に対し,問題の複雑さ,問題のクラスを正しく判別できる. | アルゴリズムの限界,問題の複雑さ,問題のクラスを理解できる. | アルゴリズムの限界,問題の複雑さ,問題のクラスを理解できない. |
学科の到達目標項目との関係
準学士課程(本科1〜5年)学習教育目標 (2)
説明
閉じる
教育方法等
概要:
「データ構造」と「アルゴリズム」はプログラムを学習する上で,必ず学ばなければならない基礎の一つである.コンピュータを用いた「問題解決のための考え方」を理解し,与えられた制約を満たすための解を導くための手法を理解し,プログラミングにより「問題を解決する能力」を身に付けることを目的とする.本講では,基本的なアルゴリズムを深く理解することが必要となる.
厳選されたアルゴリズムを通して,問題に対するアプローチの方法,プログラミングのテクニック,計算時間に対する感覚などを養っていく.
授業の進め方・方法:
座学であるが,講義項目ごとに演習や課題に取り組み,各自の理解度を確認する.また,定期試験返却時には,解説を行い,理解が不十分な点を解消する.
注意点:
関連科目
基本的なプログラミング能力を前提としており,プログラミング科目と密接に関係している.また,情報科学分野の基礎科目であり問題を解決するための必須分野であるため,3年次以降情報系専門科目を履修する上で学習内容の理解が前提条件となる科目である.
学習指針
講義中は,内容を理解するように努めること.事前に教科書で予習しておき,講義中にノートをとり,配布する授業資料に書き込むやり方が有効である.
(事前学習)
教科書の次回授業範囲を読んでおくこと。ここで、分からなかった事項、専門用語などを整理しておくこと。
(事後展開学習)
授業中に配布する演習または課題を解答、提出する。
学修単位の履修上の注意
基本情報技術者試験,応用情報技術者試験の積極的な取得を推奨しており,関連課題の一部を両試験の合格を以て達成したと見なすことがあります.
授業の属性・履修上の区分
授業計画
|
|
週 |
授業内容 |
週ごとの到達目標 |
前期 |
1stQ |
1週 |
アルゴリズムとデータ構造 |
アルゴリズム,データ構造とは何か,重要性について理解できる.
|
2週 |
計算量 |
アルゴリズムの評価方法,計算量の定義,O記法について理解できる.
|
3週 |
基本データ構造1 |
配列,連結リストについて理解できる.
|
4週 |
基本データ構造2 |
スタック,キューについて理解できる.
|
5週 |
木構造1 |
木の概念について理解できる.
|
6週 |
木構造2 |
2分木について理解できる.
|
7週 |
前期中間試験 |
講義内容を理解し,試験問題に対して正しく解答することができる.
|
8週 |
試験返却・解答 再帰 |
試験問題を見直し,理解が不十分な点を解消する. 再帰アルゴリズムの基本,利用例について理解できる.
|
2ndQ |
9週 |
データ探索1 |
探索の定義と簡単な探索アルゴリズムについて理解できる.
|
10週 |
データ探索2 |
2分探索法,ハッシュ法について理解できる.
|
11週 |
データ探索3 |
探索アルゴリズムの実行速度の比較ができる.
|
12週 |
ソート1 |
ソートの定義と基本的なアルゴリズムについて理解できる.
|
13週 |
ソート2 |
挿入ソート,ヒープソート,クイックソートについて理解できる.
|
14週 |
ソート3 |
安定なソートを理解し,ソートアルゴリズムの性能比較ができる.
|
15週 |
前期末試験 |
授業内容を理解し,試験問題に対して正しく解答することができる.
|
16週 |
試験返却・解答 |
試験問題を見直し,理解が不十分な点を解消する.
|
後期 |
3rdQ |
1週 |
アルゴリズム設計1 |
分割統治法について理解できる.
|
2週 |
アルゴリズム設計2 |
貪欲法について理解できる.
|
3週 |
アルゴリズム設計3 |
動的計画法について理解できる.
|
4週 |
アルゴリズム設計4 |
バックトラック法について理解できる.
|
5週 |
アルゴリズム設計5 |
分枝限定法について理解できる.
|
6週 |
グラフアルゴリズム1 |
グラフの概念,グラフを格納するデータ構造について理解できる.
|
7週 |
後期中間試験 |
講義内容を理解し,試験問題に対して正しく解答することができる.
|
8週 |
試験返却・解答 グラフアルゴリズム2 |
試験問題を見直し,理解が不十分な点を解消する. 最短経路問題について理解できる.
|
4thQ |
9週 |
文字列処理・探索1 |
文字列処理,文字列の探索アルゴリズムについて理解できる.
|
10週 |
文字列処理・探索2 |
文字列処理,文字列の探索アルゴリズムについて理解できる.
|
11週 |
アルゴリズムの限界1 |
アルゴリズムの限界について理解できる.
|
12週 |
アルゴリズムの限界2 |
問題のクラスについて理解できる.
|
13週 |
アルゴリズムの限界3 |
解くことのできない問題について理解できる.
|
14週 |
実装演習 |
学習したアルゴリズムを実装することができる.
|
15週 |
学年末試験 |
授業内容を理解し,試験問題に対して正しく解答することができる.
|
16週 |
試験返却・解答 |
試験問題を見直し,理解が不十分な点を解消する.
|
モデルコアカリキュラムの学習内容と到達目標
分類 | 分野 | 学習内容 | 学習内容の到達目標 | 到達レベル | 授業週 |
基礎的能力 | 工学基礎 | 情報リテラシー | 情報リテラシー | 同一の問題に対し、それを解決できる複数のアルゴリズムが存在しうることを知っている。 | 3 | 前1 |
与えられた基本的な問題を解くための適切なアルゴリズムを構築することができる。 | 3 | 後14 |
専門的能力 | 分野別の専門工学 | 情報系分野 | プログラミング | 代入や演算子の概念を理解し、式を記述できる。 | 4 | 前6 |
プロシージャ(または、関数、サブルーチンなど)の概念を理解し、これらを含むプログラムを記述できる。 | 4 | 前6 |
与えられた問題に対して、それを解決するためのソースプログラムを記述できる。 | 4 | 前6 |
ソフトウェア生成に必要なツールを使い、ソースプログラムをロードモジュールに変換して実行できる。 | 4 | 前6 |
主要な言語処理プロセッサの種類と特徴を説明できる。 | 1 | 前8,後9,後10 |
ソフトウェア開発に利用する標準的なツールの種類と機能を説明できる。 | 1 | 前8,後9,後10 |
プログラミング言語は計算モデルによって分類されることを説明できる。 | 4 | 前1,後11,後12,後13 |
主要な計算モデルを説明できる。 | 4 | 前2,後11,後12,後13 |
要求仕様に従って、標準的な手法により実行効率を考慮したプログラムを設計できる。 | 3 | 前6,後14 |
評価割合
| 試験 | レポート課題 | 合計 |
総合評価割合 | 80 | 20 | 100 |
基礎的能力 | 60 | 10 | 70 |
専門的能力 | 20 | 10 | 30 |