到達目標
１．アルゴリズムの概念と評価基準（計算量）を説明できる。
２．配列、リスト、スタック、キューを説明できる。
３．木、再帰処理を説明できる。
４．探索アルゴリズムを説明できる。
５．ソートアルゴリズムを説明できる。
６．分割統治法、グリーディー法、バックトラック法、分岐限定法を説明できる。
７．グラフを格納するデータ構造および最短経路問題を説明できる。
８．文字列照合アルゴリズムを説明できる。
９．アルゴリズムの限界を概説できる。
ルーブリック
| 理想的な到達レベルの目安 | 標準的な到達レベルの目安 | 未到達レベルの目安 |
| 到達目標
項目 1, 2, 3, 4, 5, 9 | アルゴリズムの概念と評価基準を説明でき、基本データ構造を利用した探索、整列アルゴリズムを実装できる。 | アルゴリズムの概念と評価基準、および、基本データ構造を利用した探索、整列アルゴリズムを理解し、説明できる。 | アルゴリズムの概念と評価基準、および、基本データ構造を利用した探索、整列アルゴリズムを説明できない。 |
| 到達目標
項目 6 | 各種アルゴリズムの設計手法を理解し、その具体例を説明できる。 | 各種アルゴリズムの設計手法を理解し、説明できる。 | 各種アルゴリズムの設計手法を説明できない。 |
| 到達目標
項目 7, 8 | グラフを用いた探索問題、および、文字列照合アルゴリズムを理解・説明・実装できる。 | グラフを用いた探索問題、および、文字列照合アルゴリズムを理解・説明できる。 | グラフを用いた探索問題、および、文字列照合アルゴリズムを説明できない。 |
学科の到達目標項目との関係
本科学習目標 1
説明
閉じる
本科学習目標 2
説明
閉じる
教育方法等
概要:
本講義は効率の良いアルゴリズムの構築を目的とする。そのため、各々の優れたアルゴリズムの考え方や、効率を解析するための方法論を解説し、情報系技術者として必要な基礎学力を身につけることを目標とする。アルゴリズムの課題の解決に取り組み、アルゴリズムの表記方法について学ぶ。
授業の進め方・方法:
到達目標の達成度を確認するために、随時演習課題を与える。
【関連科目】プログラミング基礎Ⅰ、プログラミング基礎Ⅱ
【MCC対応】Ⅳ-C 情報リテラシー、Ⅴ-D-2 ソフトウェア、情報教育対応科目
注意点:
計算機による演習を行うことがあるので、指示があった場合にはノートPCを持参すること。
【評価方法・評価基準】
前期中間試験、前期末試験、後期中間試験、学年末試験を実施する。 成績の評価基準として50点以上を合格とする。
前期末評価：中間試験(40%)、前期末試験(40%)、課題(20%)
後期末評価：中間試験(40%)、学年末試験(40%)、課題(20%)
学年末評価：前期末評価（50%）、後期末評価（50％）
テスト
授業の属性・履修上の区分
授業計画
|
|
週 |
授業内容 |
週ごとの到達目標 |
| 前期 |
| 1stQ |
| 1週 |
アルゴリズムの基礎(1) - アルゴリズムとは？ |
アルゴリズムの概念を説明できる。
|
| 2週 |
アルゴリズムの基礎(2) - アルゴリズムの評価基準 |
与えられたアルゴリズムが問題を解決していく過程を説明できる。
|
| 3週 |
計算量の漸近的評価(1) |
同一の問題に対し、それを解決できる複数のアルゴリズムが存在しうることや、時間計算量や領域計算量などによってアルゴリズムを比較・評価できることを理解している。
|
| 4週 |
計算量の漸近的評価(2) |
同じ問題を解決する複数のプログラムを計算量等の観点から比較でき、ソースプログラムを解析することにより、計算量等のさまざまな観点から評価できる。
|
| 5週 |
基本データ構造(1) - 配列、連結リスト |
配列、リスト構造の基本的なデータ構造の概念と操作を説明できる。
|
| 6週 |
基本データ構造(2) - スタック、キュー |
スタック、キューの基本的なデータ構造の概念と操作を説明できる。
|
| 7週 |
計算機演習 |
配列、連結リスト、スタック、キューのデータ構造を扱うソースプログラムを記述でき、要求仕様に従って、標準的な手法により実行効率を考慮したプログラムを設計できる。
|
| 8週 |
基本データ構造(3) - 木
|
木の基本的なデータ構造の概念と操作を説明できる。
|
| 2ndQ |
| 9週 |
基本データ構造(4) - 再帰 |
再帰処理の概念を説明できる。
|
| 10週 |
計算機演習 |
木のデータ構造、および、再帰処理を扱うソースプログラムを記述でき、要求仕様に従って、標準的な手法により実行効率を考慮したプログラムを設計できる。
|
| 11週 |
データの探索(1) - 探索の定義とアルゴリズム |
探索アルゴリズムの概念を説明できる。
|
| 12週 |
データの探索(2) - 線形探索、2分探索 |
線形探索、2分探索のアルゴリズムについて説明できる。
|
| 13週 |
データの探索(3) - ハッシュ法 |
ハッシュ法のアルゴリズムについて説明できる。
|
| 14週 |
計算機演習
|
線形探索、2分探索、ハッシュ法を扱うソースプログラムを記述でき、要求仕様に従って、標準的な手法により実行効率を考慮したプログラムを設計できる。
|
| 15週 |
前期復習 |
|
| 16週 |
|
|
| 後期 |
| 3rdQ |
| 1週 |
ソートアルゴリズム(1) - ソートの考え方、挿入ソート |
ソート（整列）アルゴリズムの概念を説明できる。
|
| 2週 |
ソートアルゴリズム(2) - 選択ソート、交換ソート、安定性について |
選択ソート、交換ソートのアルゴリズムの概念、および、ソートアルゴリズムの安定性について説明できる。
|
| 3週 |
ソートアルゴリズム(3) - ヒープソート |
ヒープソートのアルゴリズムについて説明できる。
|
| 4週 |
ソートアルゴリズム(4) - クイックソート |
クイックソートのアルゴリズムについて説明できる。
|
| 5週 |
アルゴリズムの設計手法(1) - 分割統治法、グリーディー法 |
アルゴリズムの設計手法である分割統治法、グリーディー法について説明できる。
|
| 6週 |
アルゴリズムの設計手法(2) - 動的計画法 |
アルゴリズムの設計手法である動的計画法について説明できる。
|
| 7週 |
計算機演習 |
分割統治統治法、グリーディー法、動的計画法を扱うソースプログラムを記述でき、要求仕様に従って、標準的な手法により実行効率を考慮したプログラムを設計できる。
|
| 8週 |
アルゴリズムの設計手法(3) - バックトラック法、分岐限定法 |
アルゴリズムの設計手法であるバックトラック法、分枝限定法について説明できる。
|
| 4thQ |
| 9週 |
グラフアルゴリズム(1) - グラフとは？ |
グラフアルゴリズムについて説明できる。
|
| 10週 |
グラフアルゴリズム(2) - 最短経路問題
|
グラフを利用した最短経路問題について説明できる。
|
| 11週 |
文字列照合(1) - 文字列照合の基本アルゴリズム |
文字列照合の基本アルゴリズムについて説明できる。
|
| 12週 |
文字列照合(2) - ボイヤー・ムーア法 |
文字列照合におけるボイヤー・ムーア法について説明できる。
|
| 13週 |
アルゴリズムの限界 |
アルゴリズムの計算量の限界について概念を説明できる。
|
| 14週 |
計算機演習 |
グラフアルゴリズム、文字列照合を扱うソースプログラムを記述でき、要求仕様に従って、標準的な手法により実行効率を考慮したプログラムを設計できる。
|
| 15週 |
後期復習 |
|
| 16週 |
|
|
モデルコアカリキュラムの学習内容と到達目標
| 分類 | 分野 | 学習内容 | 学習内容の到達目標 | 到達レベル | 授業週 |
| 専門的能力 | 分野別の専門工学 | 情報系分野 | ソフトウェア | アルゴリズムの概念を説明できる。 | 4 | |
| 与えられたアルゴリズムが問題を解決していく過程を説明できる。 | 4 | |
| 同一の問題に対し、それを解決できる複数のアルゴリズムが存在しうることを説明できる。 | 4 | |
| 整列、探索など、基本的なアルゴリズムについて説明できる。 | 4 | |
| コンピュータ内部でデータを表現する方法(データ構造)にはバリエーションがあることを説明できる。 | 4 | |
| 同一の問題に対し、選択したデータ構造によってアルゴリズムが変化しうることを説明できる。 | 4 | |
| リスト構造、スタック、キュー、木構造などの基本的なデータ構造の概念と操作を説明できる。 | 4 | |
| ソースプログラムを解析することにより、計算量等のさまざまな観点から評価できる。 | 4 | |
| 同じ問題を解決する複数のプログラムを計算量等の観点から比較できる。 | 4 | |
評価割合
| 試験 | レポート | 合計 |
| 総合評価割合 | 80 | 20 | 100 |
| 基礎的能力 | 0 | 0 | 0 |
| 専門的能力 | 80 | 20 | 100 |
| 分野横断的能力 | 0 | 0 | 0 |