シラバス参照
|
シラバス参照
|
| 講義概要/Course Information |
| 科目基礎情報/General Information |
| 授業科目名 /Course title (Japanese) |
アルゴリズム論第一 | ||
|---|---|---|---|
| 英文授業科目名 /Course title (English) |
Algorithms Ⅰ | ||
| 科目番号 /Code |
|||
| 開講年度 /Academic year |
2015年度 | 開講年次 /Year offered |
3 |
| 開講学期 /Semester(s) offered |
前学期 | 開講コース・課程 /Faculty offering the course |
情報理工学部 |
| 授業の方法 /Teaching method |
講義 | 単位数 /Credits |
2 |
| 科目区分 /Category |
専門科目 | ||
| 開講類・専攻 /Cluster/Department |
情報・通信工学科 | ||
| 担当教員名 /Lecturer(s) |
村尾 裕一 | ||
| 居室 /Office |
西9-801 | ||
| 公開E-mail |
murao at cs.uec.ac.jp | ||
| 授業関連Webページ /Course website |
www.edu.cc.uec.ac.jp/cs/lecture/AlgsI | ||
| 更新日 /Last update |
2015/03/04 23:44:24 | 更新状況 /Update status |
公開中 /now open to public |
| 講義情報/Course Description |
| 主題および 達成目標（2,000文字以内） /Themes and goals（up to 2,000 letters） |
(a) 主題： 複雑なあるいは大規模なデータ処理には，洗練されたデータ構造と効率のよいアルゴリズムが不可欠である。その根幹をなす基礎的で代表的なデータ構造について，実現法と操作法，および，その実用化の方法を簡単な応用問題を用いて学ぶ。 (b) 達成目標： リスト，スタック，キューなどの線形構造の基本操作と実用に即したいくつかの実現法を身に付ける。次に，集合や辞書を表すより進んだデータ構造としてハッシュ表や木構造の性質と操作の方法を理解し，実際の応用プログラムを通して実現法を身に付ける。グラフの基礎を学び，応用問題に通して実現法を理解する。 |
|---|---|
| 前もって履修 しておくべき科目（1,000文字以内） /Prerequisites（up to 1,000 letters） |
プログラミング通論、基礎プログラミングおよび演習 |
| 前もって履修しておくこ とが望ましい科目（1,000文字以内） /Recommended prerequisites and preparation（up to 1,000 letters） |
なし |
| 教科書等（1,000文字以内） /Course textbooks and materials（up to 1,000 letters） |
教科書：指定しない。 必要に応じて資料を配布する。 参考書： ・茨木 俊秀：Ｃによるアルゴリズムとデータ構造．昭晃堂，１９９９． ・星 守：データ構造，情報系教科書シリーズ 第３巻．昭晃堂，２００２． ・A.V.エイホ・J.E.ホップクロフト・J.D.ウルマン著／大野義夫訳：「データ構造とアルゴリズム」．培風館，１９８７． ・R.セジウィック著／野下浩平・星守・佐藤創・田口東 共訳：アルゴリズムＣ・新版─基礎・データ構造・整列・探索，近代科学社，2004年． ・T.コルメン・R.リベスト・C.シュタイン・C.ライザーソン／浅野哲夫ほか訳：アルゴリズムイントロダクション第3版，第1巻：基礎・ソート・データ構造・数学，近代科学社，2012年． |
| 授業内容と その進め方（2,000文字以内） /Course outline and weekly schedule（up to 2,000 letters） |
第 1回 科目ガイダンス：講義で扱う題材と問題例の紹介 第 2回 アルゴリズムにおける抽象性：計算量、データの独立性と抽象的な操作、抽象データ型 第 3回 線形構造(1)：リストと実現法、スタックとキューの概要 第 4回 線形構造(2)：スタックとキューの詳細と実現法 第 5回 木構造(1)：基本概念と用語、色々な木、木の表現法 第 6回 木構造(2)：実現法、応用 第 7回 集合(1)：演算と操作、実現法、辞書とトライ 第 8回 集合(2)：ハッシュ表、優先度つき待ち行列 第 9回 探索木(1)：２分探索木、基数探索 第10回 探索木(2)：２－３木、AVL木 第11回 探索木(3)：２－３－４木と赤黒木 第12回 グラフと問題(1)：グラフの表現法、最短経路問題、DAGとトポロジカルソート 第13回 グラフと問題(2)：MST、グラフの連結製、マッチング 第14回：演習問題の解答と解説 第15回：まとめと復習：質疑応答 これらの題材に関して，実用に即した実現法から華麗な技までをプログラムを見ながら学ぶ。 |
| 実務経験を活かした 授業内容 (実務経験内容も含む) /Course content utilizing practical experience |
|
| 授業時間外の学習 （予習・復習等）（1,000文字以内） /Preparation and review outside class（up to 1,000 letters） |
毎回、前回の演習問題の解説をしながら復習をします。 予習はするにこしたことはありませんが、特に必要はありません。 |
| 成績評価方法 および評価基準 （最低達成基準を含む） （1,000文字以内） /Evaluation and grading （up to 1,000 letters） |
(a) 成績評価方法：10回程度の演習問題の小レポートと期末試験により評価する。小レポートによる得点を全体の最大50％までと、残りを期末試験による得点を換算した点を合算した点数をもとに評価する。 (b) 評価基準：以下の到達レベルをもって合格の最低基準とする。 (1) 各種線形構造の操作を理解しており，具体的な実現法を説明できる。 (2) 木構造の基本的な概念と操作を理解しており，実現法を説明できる。 (3) 辞書を実現する方法の原理と実現法を理解している。 (4) 探索木の原理を説明でき，操作法を理解している。 |
| オフィスアワー： 授業相談（1,000文字以内） /Office hours（up to 1,000 letters） |
水3～4限＠西9-801。この時間に都合がつかない場合には、メールや電話などにより別途アポイントメントを取ること。 |
| 学生へのメッセージ（1,000文字以内） /Message for students（up to 1,000 letters） |
講義は配布する資料をもとに，個々の話題に関して要点を示し具体的な実現法をプログラムを用いて示していきます。資料は要点だけをまとめたものですから，出席して講義を聞き，不足する部分は参考書に当たったり質問をして理解を深めましょう。 わからない事があったらどんどん質問しましょう。 また、できるだけ多く演習課題を出しますから、講義時間内に解きその場で理解することを心がけましょう。その結果、成績評価も良くなり易くなります。 本質を理解することが大事です。単に覚えたり試験の直前に勉強して何とかしようという考えはもってのほか。 |
| その他 /Others |
（特になし） |
| キーワード /Keywords |
計算量、データ構造、線形構造、木構造、ハッシング、探索木、グラフ |