シラバス参照
|
シラバス参照
|
| 講義概要/Course Information |
| 科目基礎情報/General Information |
| 授業科目名 /Course title (Japanese) |
アルゴリズム・データ構造および演習 | ||
|---|---|---|---|
| 英文授業科目名 /Course title (English) |
Algorithms and Data Structures with Programming Projects | ||
| 科目番号 /Code |
COM401s | ||
| 開講年度 /Academic year |
2020年度 | 開講年次 /Year offered |
2/3/4 |
| 開講学期 /Semester(s) offered |
後学期 | 開講コース・課程 /Faculty offering the course |
情報理工学域 |
| 授業の方法 /Teaching method |
講義/演習 | 単位数 /Credits |
2 |
| 科目区分 /Category |
専門科目 | ||
| 開講学科・専攻 /Cluster/Department |
先端工学基礎課程 | ||
| 担当教員名 /Lecturer(s) |
村尾 裕一 | ||
| 居室 /Office |
西9-801 | ||
| 公開E-Mail |
murao@cs.uec.ac.jp | ||
| 授業関連Webページ /Course website |
http://www.edu.cc.uec.ac.jp/cs/lecture/AlgsDS/ | ||
| 更新日 /Last updated |
2020/02/28 02:28:38 | 更新状況 /Update status |
公開中 /now open to public |
| 講義情報/Course Description |
| 主題および 達成目標 /Topic and goals |
情報の分野では，対象とする現実世界の諸問題の離散的な構造を把握・表現して効率的に扱うために，アルゴリズム・データ構造を学ぶことが必須である．本講義では，データ構造・アルゴリズムの基本と特性について， 理論的および直感的に理解し説明する方法を学び，コンピュータ上での実現方法を修得する．単純なデータ構造から始めて，ハッシュ法， 木・グラフなどを用いた問題の構造の記述・理解と効率的処理技法を修得する．演習を通じて問題の定式化能力の定着を図る． |
|---|---|
| 前もって履修 しておくべき科目 /Prerequisites |
基礎プログラミングおよび演習 |
| 前もって履修しておくこ とが望ましい科目 /Recommended prerequisites and preparation |
コンピュータの基礎知識に関する科目と、プログラミング（Ｃ言語）に関する科目． |
| 教科書等 /Course textbooks and materials |
教科書：指定しない． 必要に応じて資料を配付する． （参考書） 一般的なものを授業で紹介するが，入門書として ・石田保輝、宮崎修一．アルゴリズム図鑑 絵で見てわかる26のアルゴリズム．翔泳社．2017年． また、以下の２点はアルゴリズムの教科書の定番として紹介しておく． ・R.Sedgewick. Algorithms in C, Parts 1-4. 及び Part 5. Addison-Wesley Professional. 1997. （邦訳：Parts 1-4のみ）R.セジウィック著／野下浩平・星守・佐藤創・田口東 共訳：アルゴリズムＣ・新版─基礎・データ構造・整列・探索，近代科学社，2004年/2018年復刊． ・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回 【探索と整列】線形探索．二分探索．整列法入門 第 4回 【探索と整列】整列法の色々．遅い方法：選択法，挿入法，バブルソート 第 5回 【探索と整列】高速整列法：クイックソート．マージソート．ヒープソート予告編 第 6回 【探索と整列】アルゴリズムの高速性と計算量。ハッシング 第 7回 再帰呼出し．分割統治法．バックトラック法 第 8回 線形データ構造：リスト，スタック，キュー．再帰呼出しとスタック 第 9回 木構造：長男次弟表現．なぞり（後置形とコンパイル）．深さ優先探索と幅優先探索 第10回 2分木．完全2分木（配列による表現．親子の関係）． 第11回 2分探索木と平衡探索木（B-木, AVL木等） 第12回 ヒープ・優先度つき待ち行列．【整列】ヒープソート．選択アルゴリズムとヒープの利用 第13回 グラフ：最短経路問題とダイクストラ法．貪欲法．最小コストの全域木 第14回 様々な話題とより進んだトピックス：文字列の探索．アルゴリズムの複雑さ． 第15回 まとめと復習 期末試験 |
| 実務経験を活かした 授業内容 (実務経験内容も含む) /Course content utilizing practical experience |
|
| 授業時間外の学習 （予習・復習等） /Preparation and review outside class |
毎回，前回の演習問題の解説をしながら復習をします． 講義内容は授業中に理解する（わからないことは積極的に質問する）ことを心がけること． そのためには，予習・復習は大事である． |
| 成績評価方法 および評価基準 （最低達成基準を含む） /Evaluation and grading |
(a) 成績評価方法：演習レポートと期末試験の成績に基づいて総合評価する． (b) 評価基準：以下の到達レベルをもって合格の最低基準とする． (1) 初歩的なアルゴリズム、アルゴリズムの設計法、計算量の考え方を理解している． (2) 線形構造、木構造などの各種データ構造の操作と実現法を理解している． (3) グラフを用いた初等的な問題と解法アルゴリズムを理解している． |
| オフィスアワー： 授業相談 /Office hours |
授業終了後，もしくは，予めメールで調整． |
| 学生へのメッセージ /Message for students |
（上にも書きましたが）授業中に理解する，もしわからないことがあれば質問するように心がけましょう． アルゴリズムの理解には，その背景とどのようなアイディアで打開するのかを知ることが大事です．その思考過程やアイディアを楽しみましょう/楽しめるようになりましょう． |
| その他 /Others |
|
| キーワード /Keyword(s) |
計算量，データ構造，線形構造，木構造，ハッシング，ヒープ，探索木，平衡探索木，グラフ．バックトラック．分割統治法．貪欲法．動的計画法など |