シラバス参照
|
シラバス参照
|
| 講義概要/Course Information |
| 科目基礎情報/General Information |
| 授業科目名 /Course title (Japanese) |
情報領域演習第三（１クラス） | ||
|---|---|---|---|
| 英文授業科目名 /Course title (English) |
Exercise in Informatics Ⅲ | ||
| 科目番号 /Code |
COM304a COM304b COM304c COM304d | ||
| 開講年度 /Academic year |
2020年度 | 開講年次 /Year offered |
2 |
| 開講学期 /Semester(s) offered |
後学期 | 開講コース・課程 /Faculty offering the course |
情報理工学域 |
| 授業の方法 /Teaching method |
演習 | 単位数 /Credits |
1 |
| 科目区分 /Category |
専門科目 | ||
| 開講学科・専攻 /Cluster/Department |
Ⅰ類 | ||
| 担当教員名 /Lecturer(s) |
赤池 英夫 | ||
| 居室 /Office |
西 9 号館 409 室 | ||
| 公開E-Mail |
xakaike@cs.uec.ac.jp | ||
| 授業関連Webページ /Course website |
講義内で連絡する | ||
| 更新日 /Last updated |
2020/03/12 19:22:31 | 更新状況 /Update status |
公開中 /now open to public |
| 講義情報/Course Description |
| 主題および 達成目標 /Topic and goals |
効率のよいアルゴリズムを設計する上で重要となるデータ構造について詳しく学習し，実際にプログラミングを行うことで理解を深める． |
|---|---|
| 前もって履修 しておくべき科目 /Prerequisites |
基礎プログラミングおよび演習，プログラミング通論，情報領域演習第一，情報領域演習第二 |
| 前もって履修しておくこ とが望ましい科目 /Recommended prerequisites and preparation |
なし |
| 教科書等 /Course textbooks and materials |
演習問題の入手方法は講義内で指示する． また，教科書は指定しないが，以下の書籍を参考に自習するとよい． R. セジウィック著/野下浩平，星守，佐藤創，田口東 共訳： アルゴリズムC・新版─基礎・データ構造・整列・探索，近代科学社，2004年． T. コルメン，R. リベスト，C. シュタイン，C. ライザーソン/浅野哲夫ほか訳： アルゴリズムイントロダクション第3版．総合版 (分冊版もあり)，近代科学社，2013年． |
| 授業内容と その進め方 /Course outline and weekly schedule |
リスト，スタック，キューなどの線形構造や集合・辞書を表すより進んだデータ構造としてハッシュ表や木構造の性質と操作の方法を理解し，実際にプログラムを記述することで学習を進めるとともに，基本的なアルゴリズムについても学習する．主な学習内容は以下の通り． 1. 再帰関数とメモ化 2. リスト構造と操作関数の実装 3. スタック，キューの実装と応用 4. 抽象データ型を利用した実装 5. 木構造(1)：木構造と操作関数の実装 6. 木構造(2)：木構造の応用 7. 集合(1)：集合と操作関数の実装 8. 集合(2)：辞書とトライ，ハッシュ表 9. 探索木(1)：2分探索木，基数探索 10. 探索木(2)：2-3木，AVL木 11. 探索木(3)：2-3-4木と赤黒木 12. グラフと問題(1)：グラフの表現法，最短経路問題 13. グラフと問題(2)：トポロジカルソート 14. グラフと問題(3)：最小全域木 15. グラフと問題(4)：マッチング |
| 実務経験を活かした 授業内容 (実務経験内容も含む) /Course content utilizing practical experience |
なし |
| 授業時間外の学習 （予習・復習等） /Preparation and review outside class |
前学期の「プログラミング通論」と同学期に並行して実施される「アルゴリズム論第一」の講義内容を十分に理解しておくこと．また，理解を深めるために参考図書などによる自主的な学習を推奨する． |
| 成績評価方法 および評価基準 （最低達成基準を含む） /Evaluation and grading |
評価方法： 課題，レポートの内容を通じて評価する． 評価基準： 各回の課題を締切までに必ず提出すること． これまで学習したデータ構造やアルゴリズムの特徴を理解し，与えられた問題に対して適切なデータ構造やアルゴリズムを選択できることが必要となる．15 回を通した全問題の 60% に正当すれば合格できる．15 回を通した全問題の 60% に正当すれば合格できる(ただし無断欠席や他者の回答の盗用などによる大きなペナルティがある場合は，その限りではない)． |
| オフィスアワー： 授業相談 /Office hours |
授業終了後，もしくは，予めメールでアポイントをとること． |
| 学生へのメッセージ /Message for students |
本講義の目的はプログラミングを通じて，データ構造やアルゴリズムへの理解を深めることです． 完成したプログラムを単に書き写すのではなく，自分で考えながら手を動かしてプログラミングに必要な技術を習得してください．単にネット上の情報を流用したり，他者に教えてもらうだけでは力はつきません． |
| その他 /Others |
なし |
| キーワード /Keyword(s) |
再帰的手続き，スタック，キュー，線形リスト，木構造，ハッシング，ヒープ，探索木，平衡探索木，グラフ構造 |