シラバス参照

講義概要/Course Information
2020/04/28 現在

科目基礎情報/General Information
授業科目名
/Course title (Japanese)
情報領域演習第三(1クラス)
英文授業科目名
/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
/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)
再帰的手続き,スタック,キュー,線形リスト,木構造,ハッシング,ヒープ,探索木,平衡探索木,グラフ構造