シラバス参照
|
シラバス参照
|
| 講義概要/Course Information |
| 科目基礎情報/General Information |
| 授業科目名 /Course title (Japanese) |
アルゴリズム論第一（３クラス） | ||
|---|---|---|---|
| 英文授業科目名 /Course title (English) |
Algorithms Ⅰ | ||
| 科目番号 /Code |
COM402a COM402b COM402c COM402d | ||
| 開講年度 /Academic year |
2022年度 | 開講年次 /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 （過去のWeb）．今季は Google Classroom クラスコード 5uxki7j に掲載 | ||
| 更新日 /Last update |
2022/10/05 16:15:08 | 更新状況 /Update status |
公開中 /now open to public |
| 講義情報/Course Description |
| 主題および 達成目標（2,000文字以内） /Themes and goals（up to 2,000 letters） |
（注意： 後学期の大学の方針に基づき，この授業は対面で行います．クラス３のGoogle Classroomに今年の授業資料，宿題，筆記試験の情報を順次掲載します．クラスコードは遠隔授業の欄に掲載してありますので必ず登録してください．メール連絡はクラウドアカウントでなく直接，シラバス掲載のメールアドレスに送ってもらうと良いです） 情報の分野では，対象とする現実世界の諸問題の離散的な構造を把握・表現して効率的に扱うために，アルゴリズム・データ構造を学ぶことが必須である．本講義では，データ構造・アルゴリズムの基本と特性について， 理論的および直感的に理解し説明する方法を学び，コンピュータ上での実現方法を修得する．単純なデータ構造から始めて，ハッシュ法， 木・グラフなどを用いた問題の構造の記述・理解と効率的処理技法を修得する． 本講義によって，高校数学・大学初年次までに学んだ線形代数・確率統計・数列などの基礎数学と合わせ，情報分野で必須な基本的な数学の知見を修得することも目標とする． |
|---|---|
| 前もって履修 しておくべき科目（1,000文字以内） /Prerequisites（up to 1,000 letters） |
C言語によるプログラミングの履修が望ましい．特に，プログラミング通論．基礎プログラミングおよび演習. |
| 前もって履修しておくこ とが望ましい科目（1,000文字以内） /Recommended prerequisites and preparation（up to 1,000 letters） |
同上． |
| 教科書等（1,000文字以内） /Course textbooks and materials（up to 1,000 letters） |
資料は毎回独自のものを作成して配布しています．毎年の講義資料はほぼ安定しているので今年のGoogle Classroomに昨年の授業資料を掲載しました．今年の授業資料もクラスルームに前の週には掲載する予定です． 代表的な学部教科書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. 内容は充実している） です． |
| 授業内容と その進め方（2,000文字以内） /Course outline and weekly schedule（up to 2,000 letters） |
I類の2年後期科目として3クラスでの編成実施のうち第3クラスを大森・新谷で担当します．扱う項目はクラス間でほぼ合わせてあります．例年，初回がガイダンス，新谷が前半7回を担当し，後半７回を大森が担当．前半後半の回数は状況によって多少変動します． ------------------------------- 本授業の内容は，下記を基本として行います．項目ごとの講義の回数や順序は多少変更する可能性があります．また，前半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 |
|
| 授業時間外の学習 （予習・復習等）（1,000文字以内） /Preparation and review outside class（up to 1,000 letters） |
離散系の数学とアルゴリズム論は表裏一体であり，情報系のシステムソフトウェア設計や問題解決法を考えるときの基本的な言葉です．微積分や確率とは異なるため，情報やIT，ビッグデータなどに興味があって入学したものの「数学的な基本」の違いに戸惑う学生諸君もいるでしょう．履修学生がアルゴリズム系の教科書やネット解説を自分で読んで，そこに書かれた文章の意味を理解し，教員へ積極的に質問できる，ようになってもらうと良いです．授業時間外でも積極的に質問に来てください． |
| 成績評価方法 および評価基準 （最低達成基準を含む） （1,000文字以内） /Evaluation and grading （up to 1,000 letters） |
途中の宿題と，期末筆記試験によります． 以下の到達レベルをもって合格の最低基準としています． (1) 各種線形構造の操作を理解しており，具体的な実現法を説明できる． (2) 木構造の基本的な概念と操作を理解しており，実現法を説明できる． (3) ハッシングの原理と実現法を理解している． (4) 探索木の原理を説明でき，操作法を理解している． (5)グラフを用いた初等的な問題と解法アルゴリズムの理解 (10/5追記)初回に説明したように，宿題（必須ではない）の得点をX, 期末筆記試験の得点率をY％としたとき，総合点= X + (100-X)*Y を100点満点における最終的な成績点とします．宿題は必須とはしません．履修学生の理解度や疑問を的確に把握して授業の中で補完するためのものです． |
| オフィスアワー： 授業相談（1,000文字以内） /Office hours（up to 1,000 letters） |
平日午後なら6時までなら随時．授業終了後や電子メールで時間を相談してもらうほうが，都合は良いです．新谷・大森両方で対応します．西10号館528号室（大学院情報システム学研究科・データベース学講座（旧組織.西10・528号室）へ．zoomでも良いです． |
| 学生へのメッセージ（1,000文字以内） /Message for students（up to 1,000 letters） |
資料や授業の内容が，その解説に向き合ったとき，言語として頭に入ってこない場合があるかもしれません．そのときは，自分で読んでわかる，アルゴリズムの薄い教科書を探して，それを最初に通して読むことを勧めます．参考書で挙げたもののうち特に薄い，解説の平明な日本語教科書はそのためのものです）．アルゴリズムの基本を理解することはCプログラミングを読み書きすることとも違うので，Cで学ぶアルゴリズム，などのC言語主体のプログラミングの教科書とは違う視点からの講義として考えていただき，毎回の授業や宿題などで疑問に感じた点を積極的に質問してください． |
| その他 /Others |
2022年度は対面授業になります．初回ガイダンスは10/4（火曜4限）なので指定教室へお集りください． クラス１から３の振り分けの学籍番号は教務課指定ですが，過年次の学生はどのクラスを選択しても良い．現役学生についてもクラス3に出られない合理的理由があれば希望クラス担当教員の了解をとってもらえば他クラスを履修して良いです．人数制限の事情もあるので，この点は初回講義で解説．履修登録締め切り後のクラス変更はお断りします．遠隔実施はクラス２だけですので，事情により遠隔でしか履修できない学生はクラス２を履修してください． |
| キーワード /Keywords |
アルゴリズム，正当性，停止性，計算量，データ構造，線形構造，木構造，ハッシュ法，ヒープ，探索木，平衡探索木，グラフ |