三重大学ウェブシラバス


シラバス表示

 シラバスの詳細な内容を表示します。

→ シラバスの一覧にもどる

科目の基本情報

開講年度 2017 年度
開講区分 工学部情報工学科 ・専門教育
受講対象学生 学部(学士課程) : 3年次
選択・必修 選択
授業科目名 データ構造・アルゴリズム論 II
でーたこうぞう・あるごりずむろん 2
Data Structure and Algorithm Theory II
単位数 2 単位
他学部・他研究科からの受講
市民開放授業 市民開放授業ではない
開講学期

後期

開講時間 木曜日 9, 10時限
開講場所

担当教員 太田 義勝

OHTA, Yoshikatsu

学習の目的と方法

授業の概要 アルゴリズムとデータ構造に関する上級コースである.すなわち,近似アルゴリズム,並列アルゴリズム等のより高度のアルゴリズム,並びにより複雑なデータ構造について学習すると共に,実行効率の良いアルゴリズムの設計技法およびならし計算量等の時間計算量の解析法を修得する.
学習の目的
学習の到達目標 より高度のアルゴリズムの設計技法,複雑なデータ構造の構築・実装技術及びならし計算量などの高度な性能解析力を修得する.
ディプロマ・ポリシー
○ 学科・コース等の教育目標
○ JABEE 関連項目

○ 全学の教育目標
感じる力
  •  感性
  •  共感
  •  倫理観
  • ○モチベーション
  •  主体的学習力
  •  心身の健康に対する意識
考える力
  •  幅広い教養
  • ○専門知識・技術
  • ○論理的思考力
  •  課題探求力
  • ○問題解決力
  •  批判的思考力
コミュニケーション力
  •  情報受発信力
  •  討論・対話力
  •  指導力・協調性
  •  社会人としての態度
  •  実践外国語力
生きる力
  •  感じる力、考える力、コミュニケーション力を総合した力

授業の方法 講義

授業の特徴

教科書 アルゴリズムとデータ構造(平田富夫,森北出版)
および自作プリント
参考書 アルゴリズムとデータ構造(茨木俊秀,昭晃堂)
アルゴリズムイントロダクション(Cormen(他)著[浅野(他)訳],近代科学社)
並列アルゴリズム(宮野悟,近代科学社)
The Design and Analysis of Algorithms(D.C.Kozen, Springer-Verlag)
成績評価方法と基準 出席は必要条件であり,3分の2以上出席した者に対して単位を与える.評価は定期試験(100点)の点数で行い,60点以上を合格とする.
オフィスアワー 授業終了後,教室又は情報工学科棟4階太田教員室で対応.
電子メールによる受付け可(E-mail:ohta@net.info.mie-u.ac.jp)
受講要件 なし
予め履修が望ましい科目 データ構造・アルゴリズム論 I を履修していることが望ましい.
発展科目
授業改善への工夫
その他

授業計画

キーワード 複雑なデータ構造,並列アルゴリズム,近似アルゴリズム,ならし計算
Key Word(s)
学習内容 第1回 アルゴリズム設計技法
第2回 グラフとネットワークのアルゴリズム(3)
       最小スパンニング木を求めるアルゴリズムおよびUNION-FIND問題
第3回 最短路を求めるアルゴリズム
       ダイクストラのアルゴリズムとワーシャル・フロイドのアルゴリズム
第4回 最大フローを求めるアルゴリズム
第5回 最大フローを求めるアルゴリズムの時間計算量
第6回 最大マッチング
第7回 最適解を求める発見的手法
第8回 高速フーリェ変換
第9回 ストリングマッチング(1) Knuth-Morris-Pratt(KMP)法
第10回 ストリングマッチング(2) Boyer-Moore法
第11回  フィボナッチヒープとならし時間解析
第12回  並列アルゴリズムとNC
第13回  スケジュール問題と近似アルゴリズム
第14回  NP完全問題(1)
第15回  NP完全問題(2)
第16回 定期試験
学習課題(予習・復習)
ナンバリングコード(試行) EN-CMPS-3

※最初の2文字は開講主体、続く4文字は分野、最後の数字は開講レベルを表します。 ナンバリングコード一覧表はこちら


Copyright (c) Mie University