シラバス参照
|
シラバス参照
|
| 講義概要/Course Information |
| 科目基礎情報/General Information |
| 授業科目名 /Course title (Japanese) |
アルゴリズム論第一（３クラス） | ||
|---|---|---|---|
| 英文授業科目名 /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 |
西10-528 | ||
| 公開E-Mail |
omori[at]is.uec.ac.jp, shintani[at]is.uec.ac.jp | ||
| 授業関連Webページ /Course website |
http://home.hol.is.uec.ac.jp/algorithmsI (学内限定) | ||
| 更新日 /Last updated |
2020/03/11 12:43:50 | 更新状況 /Update status |
公開中 /now open to public |
| 講義情報/Course Description |
| 主題および 達成目標 /Topic and goals |
情報の分野では，対象とする現実世界の諸問題の離散的な構造を把握・表現して効率的に扱うために，アルゴリズム・データ構造を学ぶことが必須である．本講義では，データ構造・アルゴリズムの基本と特性について， 理論的および直感的に理解し説明する方法を学び，コンピュータ上での実現方法を修得する．単純なデータ構造から始めて，ハッシュ法， 木・グラフなどを用いた問題の構造の記述・理解と効率的処理技法を修得する． 本講義によって，高校数学・大学初年次までに学んだ線形代数・確率統計・数列などの基礎数学と合わせ，情報分野で必須な基本的な数学の知見を修得することも目標とする． |
|---|---|
| 前もって履修 しておくべき科目 /Prerequisites |
C言語によるプログラミングの履修が望ましい．特に，プログラミング通論．基礎プログラミングおよび演習. |
| 前もって履修しておくこ とが望ましい科目 /Recommended prerequisites and preparation |
同上． |
| 教科書等 /Course textbooks and materials |
資料は毎回独自のものを作成して配布します． 資料作成の元になるもの，あるいは，授業の予習・復習に使えるような代表的な学部教科書15回に相当する入門的な教科書，あるいは，詳細な専門的教科書は，授業初回に紹介します． 参考書として，最近出た学部2年・3年向け授業15回のために作られた以下の本をあげておきます： 西尾章治郎 監修，原，水田，大川著， 「アルゴリズムとデータ構造」，（未来へつなぐデジタルシリーズ10）， 共立出版 （2400円）． 他に，アルゴリズムの専門的な授業で必須とされる教科書は，以下の2種類です．上記で載っていない項目については，これらが参考に，なります．分厚いので，項目を選んで調べるのに適す： *1 (i) R.セジウィック著，「アルゴリズムC」 第１巻～第３巻．近代科学社， (ii) R.セジウィック著／野下浩平・星守・佐藤創・田口東 共訳：アルゴリズムＣ・新版─基礎・データ構造・整列・探索，近代科学社，2004年．（内容は(i)と近く，こちらのほうが新しい本です）． *2 T.コルメン他著，「アルゴリズムイントロダクション第３版」全3巻． 特に，第１巻（計算量，ヒープ，3章のデータ構造）と第２巻（VI.グラフ） 近代科学社，（2013年に，1冊にまとめた統合版が出ています）. MITの標準教科書です． 専門書は分厚いので，学部向け日本語教科書は断片的に話題をとりあげて編集されています．そのため一冊の学部向け入門書ではなかなかこの講義全体をカバーしきれません．講義のうち特に後半の，平衡探索木（2－3木），グラフのアルゴリズム，の紹介は，下記の入門書も参考になります： ＊「データ構造とアルゴリズム」（五十嵐建夫，数理工学社）（サイエンス社）． （比較的最近の新しい入門書．前半のうちハッシュやヒープ，2分探索，後半の平衡木以後，などの解説は簡潔にまとまっている．疑似コードによる解説．演習解答つき） ＊「アルゴリズムとデータ構造」（岩波講座ソフトウェア科学３）（石畑清，岩波書店） （少し古い．疑似コードがPascal. 内容は充実している） です． |
| 授業内容と その進め方 /Course outline and weekly schedule |
I類の2年後期科目として，3クラス編成実施のうち1クラスを大森・新谷で担当します．内容や採点基準はクラス間で統一しています． 内容は，下記を基本として行います．項目ごとの講義の回数や順序は多少変更する可能性があります．また，前半7回か8回目の時点で，学生の理解度を調べるため，復習まとめに相当する回を入れる場合があります．これは，最後の「先進的話題」の回も，同様です． 0．ガイダンス（第1回） 1．アルゴリズムと計算量、抽象データ型（第2回） 2．基本データ構造(第3, 4回） - 線形構造(1)：リストと様々な操作 - 線形構造(2)：スタック、キュー 3．木（第5回） - (1)：基本概念、色々な木 - (2)：実現法、応用 ４．ハッシュ法，トライなど （第6回） - 集合を扱うデータ構造 5．ヒープと優先度つき待ち行列 （第7回） 6．２分探索木 （第8回） --------------- 6'. 基数探索 (第9回） 7．平衡探索木 （第10，11回） (1)：平衡探索木の詳細(2-3木，AVL木） (2)：その他の平衡探索木(2-3-4木，B木, 赤黒木) 8．グラフのアルゴリズム （第12，13, 14回） (1)：グラフの表現法、単一出発点最短経路問題 (2): 全頂点間の最短経路問題，グラフの深さ優先探索 (3)：コスト最小極大木，二重連結問題，など応用編 9．まとめと計算量・マスタ定理など先進的な話題 （第15回） （全15回）． |
| 実務経験を活かした 授業内容 (実務経験内容も含む) /Course content utilizing practical experience |
|
| 授業時間外の学習 （予習・復習等） /Preparation and review outside class |
離散系の数学とアルゴリズム論は一体の科目であり，情報系のシステムソフトウェア設計や問題解決法を考案するときの基本になります．連続系の数学とは異なるため，わからなくなってきたら教科書・参考書を自分で読んで調べる，授業時間外でも教員へ積極的に質問に来る，などしてください． |
| 成績評価方法 および評価基準 （最低達成基準を含む） /Evaluation and grading |
途中の宿題と，期末試験によります．試験は担当クラスごとに作成・実施するが，範囲や難易度は統一しています． 以下の到達レベルをもって合格の最低基準としています． (1) 各種線形構造の操作を理解しており，具体的な実現法を説明できる． (2) 木構造の基本的な概念と操作を理解しており，実現法を説明できる． (3) ハッシングの原理と実現法を理解している． (4) 探索木の原理を説明でき，操作法を理解している． (5)グラフを用いた初等的な問題と解法アルゴリズムの理解 |
| オフィスアワー： 授業相談 /Office hours |
平日午後なら6時までなら随時．授業終了後や電子メールで時間を相談してもらうほうが，都合は良いです．新谷・大森両方で対応します．西10号館528号室（大学院情報システム学研究科・データベース学講座（旧組織.西10・528号室）へ． |
| 学生へのメッセージ /Message for students |
最初に全くわからないときは，自分で読んでわかる，日本語のアルゴリズムの薄い教科書を探して，それを最初に通して読むことを勧めます．Cプログラムだけの世界とは異なるので，プログラムの得意な学生も同様． |
| その他 /Others |
なし． |
| キーワード /Keyword(s) |
アルゴリズム，正当性，停止性，計算量，データ構造，線形構造，木構造，ハッシュ法，ヒープ，探索木，平衡探索木，グラフ |