アルゴリズム

2016年度 前期 情報システム学科 2年次 専門科目
平成24年度以前入学→選択科目、平成25年度以降入学→情報コース必修科目、経営コース選択科目
金曜4限 240教室 担当教員：河原

連絡

• 成績付け完了しました
• 7/29授業補足（試験範囲でもレポートでもありません）
• フィボナッチ数を求めるサンプル（時間計測付きなので実行すると違いが分かります）
• フィボナッチ数を求める（再帰版）fibo1.c
• フィボナッチ数を求める（DP版）fibo2.c
• モンテカルロ法で円周率を求めるサンプル
• C言語版：pi.c
• Excel版：pi.xlsx
• 第5回レポートについて
• 7/22 16:40 関数部分も直ってませんでした。直しました。再々すみません。結局コメントが入れ替わってただけでした^^;
• 7/22 14:10 メイン部分が直ってませんでした。再びスミマセン。直しました。
• 7/22 C言語の階乗とユークリッドの互除法のプログラムが入れ替わってました。今はは直してあります。スミマセン。
• 7/3 説明はポータルに上る予定です。CとVBの例を挙げます。
• C言語のテンプレ
1. 階乗：temp-factorial.c
2. ユークリッドの互除法：temp-gcd.c
3. ハノイの塔：temp-hanoi..c
• VBのテンプレ
1. 階乗：temp-factorial.vb
2. ユークリッドの互除法：temp-gcd.vb
3. ハノイの塔：temp-hanoi.vb
• VBの実行方法については処理演習U2のテキストを参照してください
• プロジェクトの種類ではコンソールアプリケーションを選択しています
• 第4回レポートについて
• 7/3 説明はポータルに上げてあります。CとVBの例を挙げます。<
• C言語の例
• データ作成の例：data.c
• プログラムのテンプレート：temp.c
• 時間計測の例：speed.c
  （もともと time.c としていたが、Windowsのコマンドtimeとかぶるので変更しました）
• VBの例
• データ作成の例：data.vb
• プログラムのテンプレート：temp.vb
• 時間計測の例：speed.vb
• 実行方法については処理演習U2のテキストを参照すること
• 5/27の授業でノートに書いてもらったレポートに関する質問の回答をポータルに上げました。
• 第2回中間レポートで使用するプログラム（修正済み）
  リンクをクリックしてプログラムを見るか、リンクを右クリックして名前を付けて保存する。
• C言語：furui.c (確認済)
• ※注）授業でも説明しましたが、間違いが何か所かありました。修正済みです。
• Java：furui.java (確認済)
  ※注：学校の環境では動かない可能性あり。
• JavaScript：furui.html(確認済)
  リンクをクリックすると実行されるので、プログラムを見る場合は「ソースを表示」する。
• VB：furui.vb (確認済)
  ※注：このままでは実行できない。学校の環境では動かない可能性あり。
• その他
• Small Basic：furui.sb (確認済)
  自分のPCにインストールする必要あり。
• 擬似言語シミュレータSARAでも作成可能です。入力にバグがあるようですが、実行できました。
• 河原研究室の配属時に定員を超えた場合、この科目の履修状況を参考にして選考を行います。
• 配布資料とノートをポータルサイトにて配布します。各自ダウンロードして予習してきてください。
• ノートは印刷してきてください。複数枚使うことがあるので用意しておいてください。
• 配布資料はPDFファイルで配布するので、紙に印刷してもらってもよいですが、印刷せずにノートPC、タブレット端末、スマートフォンで閲覧しても構いません。
• 出席管理システムを使用します。出席管理システムでの出席と、ノート提出とで、実際の出席とします。どちらか片側の際は遅刻、として扱います。
• D分野（コンピュータと通信）の専門科目です。平成25年度以降入学生の情報コースの人は必修科目です。それ以外は選択科目です。
• JABEE必修科目です。JABEEコースの修了を目指している・考えている人は単位取得が必要となります。
• 講義概要へのリンク

授業目的

「アルゴリズム」とは、何らかの問題を解こうとしたときの、手順を示したものである。本講義では、コンピュータを用いて問題解決を行う際の、基本的な考え方と手法について学ぶ。問題を解く手続きを与える「アルゴリズム」と、その際に用いるデータの表現形式である「データ構造」との関連を理解する。さらに、アルゴリズムの記述方法、代表的なアルゴリズムについて学び、新しい問題へ適用するための手法を学習する。

授業内容

1. (4/15) アルゴリズムとは。プログラムとの関係。基本的なアルゴリズムの例とアルゴリズムの記述方法。
2. (4/22) アルゴリズムの記述方法：フローチャート、擬似言語など。具体的なアルゴリズム例。
3. (5/06) データ構造1：プログラミングの基本。変数と配列。配列を使ったアルゴリズム。
4. (5/13) さまざまなアルゴリズム1：配列を使ったアルゴリズム
5. (5/20) データ構造2：その他のデータ構造（スタック、キュー、ツリー）と具体的なアルゴリズム例
6. (5/27) さまざまなアルゴリズム2：その他のデータ構造を使ったアルゴリズム
7. (6/03) 探索1：線形探索、二分探索
8. (6/10) 計算量：アルゴリズムの性能評価
9. (6/17) 探索2：ハッシュ法
10. (6/24) ソート1：基本的なソート
11. (7/01) ソート2：高速なソート
12. (7/08) 再帰アルゴリズム：「再帰」を使ったアルゴリズム
13. (7/15) 探索アルゴリズム：ゲーム木の探索（深さ優先探索・幅優先探索）
14. (7/22) グラフ：グラフの探索、ダイクストラ法
15. (7/29) 応用アルゴリズム：動的計画法、モンテカルロ法
16. (8/05) [期末試験]

成績評価方法

• 数回提示するレポート課題の評価点合計を60％、期末試験の評価点を40％として評価する

教科書・参考文献

• 資料をポータルサイトにて配布するので事前・事後学習に使用すること。
• 参考文献は講義中に紹介する

受講にあたっての留意事項

• 受講学生の理解度により講義の順番（日程）や分量を調整することがある。
• プログラミングに関する講義や演習を履修済みであり、プログラミングについてある程度理解していることが望ましい。
• 「数学基礎」の履修を指導された学生は，個の単位を取得していることが望ましい。
• 継続した学習が必要となるため、欠席した場合は各自で資料を取り寄せて学習することが必要となる。
• 連絡事項や追加情報はウェブページに掲示する。

学習到達目標

• アルゴリズムとデータ構造について理解する（レポート：20%，期末試験：15%）
• 与えられた問題に対し適切なアルゴリズムやデータ構造を適用できる(レポート：20%，期末試験：15%)
• 学習したアルゴリズムやデータ構造をプログラミングにより実現できる(レポート：20%，期末試験：10%)

---

河原