| |
| 回数 | 授業スケジュール | 授業時間外学習・時間(分) |
|
| 1 | 基礎数理
- データ構造とアルゴリズムを学ぶ上で必要となる数学の基礎的な事項を復習する。
- 例題を通して、集合と論理演算、論理回路、確率の基礎的事項を復習する。
- 逆ポーランド記法を紹介する。
- グラフ理論の基礎的事項を紹介する。
- 2進数と基数変換を確認する。 | 【予習】集合に対する演算と確率について、既習事項をまとめること。(120分)
【復習】講義中に提示する課題を次回の講義開始時までに消化すること。(120分) |
|
| 2 | ハードウェア
- コンピュータ内部での低水準なデータの表現形式や保存方法を復習する。
- 2進数における加算と乗算をコンピュータで実現する方法を紹介し、(古典的な方法では) 乗算の方が加算より時間がかかることを説明する。
- 固定小数点表示と浮動小数点表示と演算により生じる誤差を紹介する。 | 【予習】2進数の加算と乗算の方法を復習し、具体的な数値で計算方法を確認すること。(120分)
【復習】講義中に提示する課題を次回の講義開始時までに消化すること。(120分) |
|
| 3 | データ構造
- プログラミングにおいてよく使われるデータ構造を紹介する。
- 配列、リスト構造、スタック、キュー、木を、それぞれのデータ構造で可能な基本的操作とともに紹介する。 | 【予習】Σ記法を用いた数列の和の表現方法と、漸化式で表現される数列の一般項を求める方法を復習すること。(120分)
【復習】講義中に提示する課題を次回の講義開始時までに消化すること。(120分) |
|
| 4 | アルゴリズムの記述
- アルゴリズムを他者に伝えるための表記を紹介する。
- JIS で定められている流れ図(フローチャート)、基本情報技術者試験の問題で利用される疑似言語、オブジェクト指向分析・設計で利用されるUMLを紹介する。 | 【予習】C言語かJava言語について、選択処理と繰り返し処理の構文を確認すること。(120分)
【復習】講義中に提示する課題を次回の講義開始時までに消化すること。(120分) |
|
| 5 | 基本アルゴリズム (1)
- 配列の中から条件に合致する要素を探索するアルゴリズムを紹介する。
- 線形探索、番兵、2分探索を紹介する。 | 【予習】本を何冊か用意し「情報」という文字列を探せ。ページを確認する平均の回数がどの程度になるか概算せよ。(120分)
【復習】講義中に提示する課題を次回の講義開始時までに消化すること。(120分) |
|
| 6 | 基本アルゴリズム (2)
- データを整列(ソート)するアルゴリズムを紹介する。
- バブルソート、基本選択法、マージソート、クイックソートを紹介し、いくつかの例についてそれぞれの実行時間を概算する。 | 【予習】番号がついた紙片を50枚ほど用意し、それらを番号順に並べよ。どのような手順で並べるのが楽か考えよ。(120分)
【復習】講義中に提示する課題を次回の講義開始時までに消化すること。(120分) |
|
| 7 | 基本アルゴリズム (3)
- 長い文字列の中から特定の文字列を探し出し何らかの処理を行うアルゴリズムを紹介する。
- オートマトンや正規表現についても補足説明する。 | 【予習】ハフマン符号化を調べまとめよ。(120分)
【復習】講義中に提示する課題を次回の講義開始時までに消化すること。(120分) |
|
| 8 | アルゴリズムの計算量
- アルゴリズムの性能や効率を議論する際に用いられる時間計算量や領域計算量を紹介する。
- O記法を紹介する。
- 多項式時間アルゴリズムや指数関数時間アルゴリズムというアルゴリズムの分類を紹介する。
- 問題自体がもつ難しさの概念を説明し、PとNPについて紹介する。 | 【予習】ユークリッドの互除法を復習し、いくつかの数値例について実際に最大公約数を計算せよ。(120分)
【復習】講義中に提示する課題を次回の講義開始時までに消化すること。(120分) |
|
| 9 | 木
- 2分探索で用いた2分木について、高さがバランスしているかどうかにより2分木探索の実行時間がどう変わるか等、詳しく考察する。
- 多分木の一種であるB木を紹介する。 | 【予習】クラフトの不等式を調べまとめよ。(120分)
【復習】講義中に提示する課題を次回の講義開始時までに消化すること。(120分) |
|
| 10 | ファイル処理
- ファイルに記録されているレコードを処理する際のアプローチとして、ファイルの順次処理とファイルのランダム処理を紹介する。
- ファイルの併合処理を紹介する。 | 【予習】WindowsのファイルシステムとLinuxのファイルシステムの違いを調べまとめよ。(120分)
【復習】講義中に提示する課題を次回の講義開始時までに消化すること。(120分) |
|
| 11 | プロジェクトマネジメントのためのアルゴリズム
- プロジェクトマネジメントのプロジェクトタイムマネジメントで利用される CPM について紹介する。 | 【予習】PERTについて調べ、PERT図(アローダイアグラム)を描画する規則についてまとめよ。(120分)
【復習】講義中に提示する課題を次回の講義開始時までに消化すること。(120分) |
|
| 12 | 乱択アルゴリズム
- (擬似)乱数を用いるアルゴリズムを紹介する。
- 悪い入力が与えられたときであっても乱択アルゴリズムにより性能が改善する例を示す。 | 【予習】モンテカルロ法について調べ、まとめよ。可能ならプログラムを作成し、モンテカルロ法で円周率を求めよ。(120分)
【復習】講義中に提示する課題を次回の講義開始時までに消化すること。(120分) |
|
| 13 | 近似アルゴリズム
- 貪欲法を用いたナップサック問題の解法を例に、問題を近似的に解くアルゴリズムを紹介する。 | 【予習】n個の中からr個を選ぶ組合せの数の公式を導出せよ。(120分)
【復習】講義中に提示する課題を次回の講義開始時までに消化すること。(120分) |
|
| 14 | データベース
- リレーショナルデータベースと、データベースを操作する関係代数を紹介する。
- 表の積や自然結合が高コストとなる理由を説明し、コスト推定法を紹介する。 | 【予習】SQLについて調べ、代表的な操作を行う構文をまとめよ。(120分)
【復習】講義中に提示する課題を次回の講義開始時までに消化すること。(120分) |
|
| 15 | アルゴリズムとコーディング
- アルゴリズムをプログラミング言語を用いて実装する際の注意事項を紹介する。
- 例外処理やユニットテスト、よく利用されるコーディングスタイルを紹介する。 | 【予習】どのプログラミング言語でもよいので、第14回までに紹介したアルゴリズムのうちのどれか1つを実際に自分で実装せよ。(120分)
【復習】全15回の講義の内容を振り返ること。(120分) |
|