到達目標
【授業目標】
□ アルゴリズムの基本概念を理解し、フローチャートを描くことができる
□ サーチやソートなどの基本的なアルゴリズムおよび再帰の考え方を理解し、簡単な例題を解くことができる。
□ グラフアルゴリズムや乱択アルゴリズムなどのやや進んだアルゴリズム技法を理解し応用できる。
□ チューリングマシンとそれに関連する計算論の基本事項を理解し、簡単な問題に応用できる。
ルーブリック
| 理想的な到達レベルの目安 | 標準的な到達レベルの目安 | 未到達レベルの目安 |
| 評価項目1 | アルゴリズムとデータ構造の基本を充分に身に付けている | アルゴリズムとデータ構造の基本を身に付けている | アルゴリズムとデータ構造の基本が身に付いていない |
| 評価項目2 | ソートなどの重要なアルゴリズムを充分に身に付けている | ソートなどの重要なアルゴリズムを身に付けている | ソートなどの重要なアルゴリズムを身に付けていない |
| 評価項目3 | 計算論の基本事項を充分に身に付けている | 計算論の基本事項を身に付けている | 計算論の基本事項を身に付けていない |
学科の到達目標項目との関係
教育方法等
概要:
この講義ではアルゴリズムの基本事項からはじめてさまざまなアルゴリズムの技法を学び、
併せて計算可能性やＮＰ完全性など「計算論」の初歩を紹介する。
プログラム言語についてある程度の知識があることが望ましいが、必須ではない。
授業の進め方・方法:
テキストに沿って講義と問題演習を行う。
随時研究課題を紹介する。
注意点:
各年開講のため、令和３年度は開講されない。
本科目は、授業時間30時間に加えて、自学自習時間60時間が授業の前後に必要となります。具体的には、下記の学修内容に関連する宿題を毎回出題します。
各授業は前回までの宿題を済ませていることを前提に進めます。必ず次回授業までに済ませるようにして下さい。
アルゴリズム論は「計算論の基礎」という理論的な側面と「プログラミング技法」という実用的な側面があります。
基礎と応用をバランス良く身につけるよう努力して下さい。
授業は宿題を前提に進められます。毎回必ず自分で解くようにして下さい。
授業の属性・履修上の区分
授業計画
|
|
週 |
授業内容 |
週ごとの到達目標 |
| 前期 |
| 1stQ |
| 1週 |
アルゴリズムとデータ構造（１） |
授業概要とアルゴリズムの基本事項
|
| 2週 |
アルゴリズムとデータ構造（２） |
変数と配列
|
| 3週 |
アルゴリズムとデータ構造（３） |
スタックとキュー
|
| 4週 |
サーチとソート （１） |
線形探索
|
| 5週 |
サーチとソート （２） |
２分探索
|
| 6週 |
サーチとソート （３） |
基本ソート
|
| 7週 |
サーチとソート （４） |
応用ソート
|
| 8週 |
グラフアルゴリズム（１） |
グラフ探索
|
| 2ndQ |
| 9週 |
グラフアルゴリズム（２） |
ダイクストラ法
|
| 10週 |
乱択アルゴリズム |
アルゴリズムにおける乱数の利用
|
| 11週 |
計算論（１） |
チューリングマシンと計算可能性
|
| 12週 |
計算論（２） |
NP完全問題
|
| 13週 |
計算論（３） |
PｖｓNP問題
|
| 14週 |
計算論（４） |
近似アルゴリズム
|
| 15週 |
問題演習 |
総復習
|
| 16週 |
定期試験 |
|
評価割合
| 試験 | 発表 | 相互評価 | 態度 | ポートフォリオ | その他 | 合計 |
| 総合評価割合 | 100 | 0 | 0 | 0 | 0 | 0 | 100 |
| 基礎的能力 | 40 | 0 | 0 | 0 | 0 | 0 | 40 |
| 専門的能力 | 40 | 0 | 0 | 0 | 0 | 0 | 40 |
| 分野横断的能力 | 20 | 0 | 0 | 0 | 0 | 0 | 20 |