シラバス参照
|
シラバス参照
|
| 講義概要/Course Information |
| 科目基礎情報/General Information |
| 授業科目名 /Course title (Japanese) |
アルゴリズム論第一（３クラス） | ||
|---|---|---|---|
| 英文授業科目名 /Course title (English) |
Algorithms Ⅰ | ||
| 科目番号 /Code |
COM402a COM402b COM402c COM402d COM402e | ||
| 開講年度 /Academic year |
2025年度 | 開講年次 /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 |
Google Classroomに資料掲載予定 | ||
| 更新日 /Last update |
2025/03/11 16:28:49 | 更新状況 /Update status |
公開中 /now open to public |
| 講義情報/Course Description |
| 主題および 達成目標（2,000文字以内） /Themes and goals（up to 2,000 letters） |
情報の分野では，対象とする現実世界の諸問題の離散的な構造を把握・表現して効率的に扱うために，アルゴリズムとデータ構造を学ぶことが最初になる．本講義では，データ構造とアルゴリズムの基本と特性について， 理論的・直観的に理解し活用する技量を学び，コンピュータ上での実現方法を修得する．単純なデータ構造から始めて，ハッシュ法， 木やグラフの定義，諸性質，制御するアルゴリズム，および，これらを用いた問題の構造の記述・理解と効率的処理技法を修得する． 本講義によって，高校数学・大学初年次までに学んだ線形代数・確率統計・数列などの基礎数学と合わせ，情報分野で必須な基本的な数学の知見を修得することも目標とする． |
|---|---|
| 前もって履修 しておくべき科目（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クラス（昨年からクラスC）を新谷・大森で担当します．扱う項目はクラス間でほぼ合わせてあります．初回がガイダンス，新谷が前半7回を担当し，後半７回を大森が担当．前半後半の回数は状況によって多少変動します． ------------------------------- 本授業の内容は，下記を基本として行います．項目ごとの講義の回数や順序は多少変更する可能性があります．途中，学生の理解度を調べるため，復習まとめに相当する宿題を入れる場合があります． 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木）(第10回） (2)：その他の平衡探索木(2-3-4木，B木, 赤黒木) （第11回） 8．グラフのアルゴリズム （第12，13, 14回） (1)：グラフの表現法、単一出発点最短経路問題 （第12回） (2): 全頂点間の最短経路問題，グラフの深さ優先探索 （第13回） (3)：コスト最小極大木，二重連結問題，など応用編 （第14回） 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)グラフを用いた初等的な問題と解法アルゴリズムの理解と事例に適用できる． 成績評点は，全15回にわたる宿題の得点をX, 期末筆記試験の得点率をY％としたとき，総合点= X + (100-X)*Y を100点満点における最終的な成績点とする．長年，定期的に出す宿題は必須でなく提出自由としていますが今年については初回に説明します．期末試験の実施も，長年，A4資料一枚のみ持ち込み可としてきましたが，今年度からは持ち込み不可として，宿題の質・量を工夫して平素の理解度を宿題側で反映するように検討しています．これも初回講義で解説予定． |
| オフィスアワー： 授業相談（1,000文字以内） /Office hours（up to 1,000 letters） |
平日午後なら6時までなら随時．授業終了後にその場で質問いただいたり，電子メールで時間を相談して居室（西10号館528号室）にて相談とします．新谷・大森どちらでも対応します． |
| 学生へのメッセージ（1,000文字以内） /Message for students（up to 1,000 letters） |
資料や授業の内容が，その解説に向き合ったとき，言語として頭に入ってこない場合があるかもしれません．そのときは，自分で読んでわかる，アルゴリズムの薄い教科書を探して，それを最初に通して読むことを勧めます．アルゴリズムの基本を理解することはCプログラミングを読み書きすることとも違う要因があり，Cで学ぶアルゴリズム，などのC言語主体のプログラミングの教科書とは違う視点から，アルゴリズムそのものの構成原理を理解する講義として本講義を考えていただき，毎回の授業や宿題などで疑問に感じた点を積極的に質問してください． |
| その他 /Others |
I類の3クラス体制の講義なので，過年次の学生はどのクラスを選択しても良い．現役学生については希望クラス担当教員の了解をとってもらえば他クラスを履修して良い．履修登録締め切り後のクラス変更はお断りします． |
| キーワード /Keywords |
アルゴリズム，正当性，停止性，計算量，データ構造，線形構造，木構造，ハッシュ法，ヒープ，探索木，平衡探索木，グラフ |