・「プログラム技法」 Spring U2

「プログラム技法２００８」ホームページ
（上の講義名（リンク）をクリックしてアクセスしてください）
担当　森本康彦　　

【授業の目標等】
あなたは配られたトランプのカードをどんな手順で並べ替えていますか？問題の算法・解法をアルゴリズムと呼びます．本講義ではコンピュータで実現するのに向き，様々な分野で役に立つ重要な基本アルゴリズムを解説します．計算すべき，解決すべきどのような問題も，本講義で解説するいずれかの基本アルゴリズムで効率的に解ける部分問題を含んでいます．基本アルゴリズムをよく理解し，それをあらゆる問題の解法として適用する能力をつけることで問題処理能力，プログラミング能力は飛躍的に向上するでしょう．それと同時に，あらゆる問題の本質を見抜く能力も身につきます．トランプの並べ替えひとつをとっても効率的なやり方もあれば，非効率なものもあります．日々の何気ない行動もアルゴリズムという視点でながめてみると面白いですよ．

【キーワード】
アルゴリズム，データ構造，計算量

【対象学生】 学部２年生以上

【授業の内容・計画等】
1. オリエンテーション
　　（本講義のハウスルール）
2. 基本データ構造
　　（問題解決に必要な小道具類とその役割の解説）
3. 木構造
　　（問題解法を考えるための代表的な大道具とその使い方）
4-5. 再帰呼出し
　　（問題解決手順のスマート合成法とその意義について）
6-7. アルゴリズムの解析
　　（良い解法とは何か）
8-9. 整列法
　　（データを順序に従って並び替える方法）
10. 探索法
　　（データの中でほしい物を効率的に見つける方法）
11-12. グラフアルゴリズム
　　（組み合わせ諸問題をグラフで考える）
13-14. 分割統治法
　　（難しい問題も小問題に分けて考えるとうまくいく）
15. 動的計画法
　　（少しの進歩も積み重ねれば，やがて大きな成果につながる）

番号は実際の講義の開講順序を表すものではありません．各年度の授業計画の詳細と講義資料はこの講義のホームページに公開する予定です．

【予習の目安】
各回の教科書，参考書の関連項目に目を通しておく程度の予習をしておくと良い．

【復習の目安】
1-2.　解説する基本データ構造の操作方法を十分に理解すること．身の回りにも似たようなものが結構あることに気づくと思います．
3.　木構造，とくに２分木，平衡２分木はその操作方法も含めよく復習すること．これを有効に使えれば問題解決の効率が飛躍的に向上するでしょう．
4-5.　簡単な具体的問題を再帰呼び出しの振る舞いで実際に解いてみること．
6-7.　時間計算量については，特によく復習すること．日ごろなにげなくやっている行動の計算量についても考えてみると良いでしょう．
8-9.　解説する整列法を実際に紙上であるいはプログラムを作って実行すること．
10.　 解説する探索法を実際に紙上であるいはプログラムを作って実行すること．
11-12.　簡単な最適化問題をグラフを使って実際に解いてみること．
13-15.　簡単な最適化問題を使って，分割統治法，動的計画法の振る舞いを模倣して解いてみること．難しい問題も案外簡単に解けることに気づいてください．

【成績評価の方法】
「期末試験」と「講義の中で出題する発展課題のレポート」の総合評価

【テキスト・教材・参考書等】
教科書は第1回目の講義で指示するが，講義の内容は特定の教科書には深く依存しない．また，講義の中で適宜参考書を提示する．

【履修上の注意・受講条件等】
情報科学の個々の専門科目をまだ履修していない人を想定して講義を開始します．

【メッセージ】
予習は特に求めないが，さらなる理解のため，発展課題の内容に関連する事項について時間をかけて自習すること．学習の動機付けとして「基本情報技術者」等の資格の取得も検討してみてください．（計算機関連の実験あるいはコンピュータプログラム等を受講するなどして）実際にプログラムを書くことによりさらに理解が深まります．