シラバス参照

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

科目基礎情報/General Information
授業科目名
/Course title (Japanese)
アルゴリズム論第一(2クラス)
英文授業科目名
/Course title (English)
Algorithms Ⅰ
科目番号
/Code
COM402a COM402b COM402c COM402d
開講年度
/Academic year
2020年度 開講年次
/Year offered
2
開講学期
/Semester(s) offered
後学期 開講コース・課程
/Faculty offering the course
情報理工学域
授業の方法
/Teaching method
講義 単位数
/Credits
2
科目区分
/Category
専門科目
開講学科・専攻
/Cluster/Department
Ⅰ類
担当教員名
/Lecturer(s)
村尾 裕一
居室
/Office
西9-801
公開E-Mail
/e-mail
murao at cs.uec.ac.jp
授業関連Webページ
/Course website
www.edu.cc.uec.ac.jp/cs/lecture/AlgsI/
更新日
/Last updated
2020/02/28 02:24:10 更新状況
/Update status
公開中
/now open to public
講義情報/Course Description
主題および
達成目標
/Topic and goals
情報の分野では,対象とする現実世界の諸問題の離散的な構造を把握・表現して効率的に扱うために,アルゴリズム・データ構造を学ぶことが必須である.本講義では,データ構造・アルゴリズムの基本と特性について, 理論的および直感的に理解し説明する方法を学び,コンピュータ上での実現方法を修得する.単純なデータ構造から始めて,ハッシュ法, 木・グラフなどを用いた問題の構造の記述・理解と効率的処理技法を修得する.
前もって履修
しておくべき科目
/Prerequisites
プログラミング通論、基礎プログラミングおよび演習
前もって履修しておくこ
とが望ましい科目
/Recommended prerequisites and preparation
なし
教科書等
/Course textbooks and materials
教科書:指定しない.
必要に応じて資料を配布する.
参考書:一般的なものを授業で紹介するが,以下の2つの教科書は定番である.
・R.Sedgewick. Algorithms in C, Parts 1-4. 及び Part 5. Addison-Wesley Professional. 1997.
(邦訳:Parts 1-4のみ)R.セジウィック著/野下浩平・星守・佐藤創・田口東 共訳:アルゴリズムC・新版─基礎・データ構造・整列・探索,近代科学社,2004年. 
・T.H.Cormen他.Introduction to Algorithms, 3rd Edition. MIT Press. 2009.
(邦訳)T.コルメン・R.リベスト・C.シュタイン・C.ライザーソン/浅野哲夫ほか訳:アルゴリズムイントロダクション第3版.総合版(分冊版もあり),近代科学社,2013年.
授業内容と
その進め方
/Course outline and weekly schedule
第 1回 科目ガイダンス
第 2回 計算量.抽象データ型
第 3回 線形構造(1):リストと様々な操作
第 4回 線形構造(2):スタック,キュー
第 5回 木構造(1):基本概念,色々な木
第 6回 木構造(2):実現法,応用
第 7回 ハッシング
第 8回 ヒープ・優先度つき待ち行列
第 9回 探索法と2分探索木
第10回 平衡探索木(1):探索木の詳細
第11回 平衡探索木(2):その他の探索木
第12回 グラフと問題(1):グラフの表現法,最短経路問題等
第13回 グラフと問題(2):MST等,問題例の色々
第14回 様々な話題とより進んだトピックス:文字列の探索.アルゴリズムの色々+NP完全・NP困難などの概要
第15回 まとめと復習
実務経験を活かした
授業内容
(実務経験内容も含む)
/Course content utilizing practical experience
授業時間外の学習
(予習・復習等)
/Preparation and review outside class
毎回,前回の演習問題の解説をしながら復習をします.
講義内容は授業中に理解する(わからないことは積極的に質問する)ことを心がけること.
そのためには,予習・復習は大事である.
成績評価方法
および評価基準
(最低達成基準を含む)
/Evaluation and grading
(a) 成績評価方法:宿題と試験による.

(b) 評価基準:以下の到達レベルをもって合格の最低基準とする.
    (1) 各種線形構造の操作を理解しており,具体的な実現法を説明できる.
    (2) 木構造の基本的な概念と操作を理解しており,実現法を説明できる.
    (3) ハッシングの原理と実現法を理解している.
    (4) 探索木の原理を説明でき,操作法を理解している.
オフィスアワー:
授業相談
/Office hours
授業終了後,もしくは,予めメールで調整.
学生へのメッセージ
/Message for students
(学習法:授業時間外の学習に示したとおり)
アルゴリズムの理解には,その背景とどのようなアイディアで打開するのかを知ることが大事.
その他
/Others
(特になし)
キーワード
/Keyword(s)
計算量,データ構造,線形構造,木構造,ハッシング,ヒープ,探索木,平衡探索木,グラフ