アルゴリズム 2015 年度 春学期 情報教育センター 情報処理副専攻 木曜 1 時限 2 単位 16-403 コンピュータ室 担当 秋山 満 1. 基本事項 テーマ ： コンピュータによる問題の解法 キーワード： データ構造 プログラミング 解法 2. 授業で育成する力・スキル 1．自ら考える力 2．情報処理力 3. 授業要旨または授業概要 コンピュータプログラムの処理の流れを、取り扱うデータの表現や構造に合うように、 基本的な制御構造(逐次処理、条件による処理の選択、反復)を組み合わせて記述する。 この授業では、データ構造とアルゴリズムについて、ほとんどのプログラムの中に頻繁 に現れる処理（分類や探索など）に適用して、信頼性や処理効率の面で優れた解法を評価、 選択できるようにし、実際にプログラムを作ることによってプログラミングの技法を習得 する。 内容は、コンピュータの基本的な知識（処理装置のしくみ、制御命令、処理のコスト、 データの内部表現など）、データ構造の基礎（スカラーと配列、ポインタ、リストなど）、 アルゴリズムの記述（再帰、分類・探索など）、その他の話題（数値計算など）である。 市販の処理システム（ライブラリプログラム、パッケージプログラム）にも言及する。 理解を深めるために、パーソナルコンピュータ上でプログラム言語とパッケージプログ ラムを使って実習する。必要な操作法、コマンドの記法については実習時に説明する。 履修のポイント、留意事項： 「プログラミング(ＣまたはＣ＃またはＪＡＶＡまたはＶＢ)」単位取得程度のプログラム の理解力があるものとして講義する。 授業の中で必要に応じてプログラム言語を使う。この授業では内容の説明のために C 言 語と C++言語を用いる。他のどの言語で課題を処理してもかまわない。 4. 学習の到達目標 1．基本的な解法と基本的なデータ構造が理解できる（スキル 2） 2．プログラム言語を使って基本的なアルゴリズムとデータ構造が検証できる （スキル 1, 2） 3．アルゴリズムの評価ができる（スキル 1, 2） 4．問題に応じた適切なアルゴリズムとデータ構造を選ぶことができる（スキル 1, 2） 授業スケジュール第 2 回‐第 13 回の内容についてそれぞれ 1‐4 を達成することが目標 である（添付資料） 。 5. 授業スケジュール 回：内容 1: ガイダンス、プログラミングの復習 2: プログラムの制御構造、分岐、反復、命令の実行回数 3: データ構造‐スカラーと配列、構造体、ポインタ 4: データ構造‐線形リスト 5: データ構造‐木構造リスト、バックトラック 6: スタックとキュー 7: 再帰 8: バブルソート、選択ソート、挿入ソート 9: シェルソート、ヒープソート 10: クイックソート 11: 線形リストのソート 12: 探索 13: 数値計算 - 実数演算の特徴、正確さと速さ 14: 数値計算 - 連立一次方程式 15: まとめと試験 ほぼ毎回、授業内容に即した宿題を課す。講義時間以外に、全体で 60 時間程度の学習 が必要となる。 6. 成績評価の基準および方法 随時、授業内容に即した宿題を課す。コンピュータを使った処理結果を提出することに なる。 評 価 に は 、 定 期 試 験 の 得 点 A(100 点 満 点 ) と 課 題 の 評 点 B(50 点 満 点 ) を 使 う 。 A+(100-A)xB/100 を、東海大学学修に関する規則に定める成績評価の基準とする。 （課題を提出しなくても定期試験の得点だけで成績評価の基準は 100 点になりうる。また 定期試験の得点が 20 点未満であれば成績評価の基準は 60 点に達することはない。 ） 7. 教科書・参考書 参考書： R.セジウィック著、野下浩平他訳「アルゴリズム C・第 1 巻 基礎・整列」近代科学社(2004) ¥3.024 疋田輝雄著「C で書くアルゴリズム」サイエンス社(1995) ¥1,512 柴田望洋、辻亮介著「新版 C 言語によるアルゴリズムとデータ構造」ソフトバンククリエ イティブ(2005) ¥2,592 B.ストラウストラップ著、株式会社ロングテール・長尾高弘訳「プログラミング言語 C++ 第 3 版」アジソン・ウェスレイ(1998) ¥7,560 8. その他の教材 授業時に配布するプリント教材 Web ページ http:/ /ictedu.u-tokai.ac.jp/akiyama/ で公開している 9. 担当教員の連絡先 研究室：5 号館 2 階情報教育センター第 10 研究室（授業日のみ在室） E-mail：上記「8. その他の教材」に示した Web ページに記載する。 10. 授業担当教員からの改善点・コメント 授業アンケートでは、内容が難しいとの指摘を受けている。実際、やさしくはないが、 アルゴリズムを学習したといえる最低限の授業内容なのでやむをえないと考えている。 8. その他の教材に示した Web ページは随時更新している。 11. 科目ＧＰＡ（科目の成績平均値） 12. 成績評価付与時のコメント アルゴリズム 目標 1 項目 講義全体 目標 2 プログラム言語を使っ 基本的な解法と基本的な て基本的なアルゴリズ 100 60 データ構造が理解できる ムとデータ構造が検証 できる プログラムの制御 構造、分岐、反復、 10 命令の実行回数 データ構造‐スカ ラーと配列、構造 10 体、ポインタ 目標 3 20 アルゴリズムの 評価ができる プログラムの制御構造が 理解できる 分岐、反復を含むプログ ラムが作成できる 配列、構造体の概念が理 解できる 配列、構造体を使ったプ ログラムが作成できる 線形リストの操作を検 証するためのプログラ ムが作成できる 木構造リストの操作を 検証するためのプログ ラムが作成できる 木構造をたどる ときのコストを 評価できる スタックやキューを使 ったプログラムが作成 できる 再帰関数を使ったプロ グラムを作成して動作 が検証できる スタックと反復 のコストの比較 ができる 再帰を使うこと の利点が理解で きる データ構造‐線形 リスト 10 線形リストの概念、特長 が理解できる データ構造‐木構 造リスト、バック トラック 10 木構造リストの概念、特 長が理解できる スタックとキュー 10 スタックおよびキューの 概念、特長が理解できる 再帰 10 再帰の意味が理解できる 命令の実行回数 を計数できる 配列要素へのア クセス回数を計 数できる 線形リストの要 素への参照のコ ストを評価でき る 目標 4 問題に応じた適切なアルゴ 10 リズムとデータ構造を選ぶ ことができる 制御命令を組み合わせて適 切なプログラムを組み立て ることができる 問題に応じて配列、構造体 を適用したプログラムを組 み立てることができる 線形リストを使うのに適し た問題であるかを判断した うえで、プログラムを実装 できる 木構造リストを使うのに適 した問題であるかを判断し たうえで、プログラムを実 装できる スタックを使うことが有利 な問題に学習結果を適用で きる 再帰が効率を落とさないこ とを確認したうえで、これ を問題に適用できる 10 10 比較とデータの交換の組 み合わせでソートが実現 されていることが理解で きる 流れ図にしたがってプ ログラムを作成できる シェルソート、ヒ ープソート 5 効率のよいソート法があ ることが理解できる 流れ図にしたがってプ ログラムを作成できる マージソート 5 マージソートの処理の概 要が理解できる 流れ図にしたがってプ ログラムを作成できる クイックソート 5 クイックソートの処理の 概要が理解できる 流れ図にしたがってプ ログラムを作成できる 5 配列以外のデータ構造に ソートを適用する例を理 解できる 流れ図にしたがってプ ログラムを作成できる プログラムの効 率を検証できる データ構造に対して適切な 解法を適用できる 10 探索の意味と特長を理解 できる 配列要素の二分探索を 行うプログラムが作成 できる 線形探索、二分探 索での比較回数 を計数できる 問題に応じて解法を選択し て適用できる バブルソート、選 択ソート、挿入ソ ート 線形リストのソー ト 探索 ソートの効率（比 較回数、移動回 数）を計数できる ソートの効率（比 較回数、移動回 数）を計数できる プログラムの効 率改善を検証で きる プログラムの効 率改善を検証で きる ソートアルゴリズムの使い 分けができる ソートアルゴリズムの使い 分けができる ソートアルゴリズムの使い 分けができる ソートアルゴリズムの使い 分けができる
© Copyright 2024 ExpyDoc
