開講学期
Course Start
2015年度 前期
授業区分
Regular or Intensive
週間授業
対象学科
Department
情報電子工学系学科
情報システム学コース
コンピュータ知能学コース
対象学年
Year
2
必修・選択
Mandatory or Elective
必修
授業方法
Lecture or Seminar
講義演習
授業科目名
Course Title
データ構造とアルゴリズム
単位数
Number of Credits
2
担当教員
Lecturer
渡邉 真也
教員室番号
Office
V613
連絡先(Tel)
Telephone
内線5432
連絡先(E-mail)
E-mail
sin(at mark)csse.muroran-it.ac.jp
オフィスアワー
Office Hour
月曜日 15:00−16:00 (期間中に変更する場合がある)
授業のねらい
Learning Objectives
情報工学・科学に入門するための基本的なアルゴリズムとデータ構造について紹介し,アルゴリズムの基本設計,データ構造の設定などについての基本的な知識と運用方式を学ぶことをねらいとしている.
到達度目標
Outcomes Measured By:
1.一般的概念としてソートや探索といった基本的なアルゴリズムについてその計算量や特徴を理解し応用できる.
2.特徴的なデータ構造についてもその特性を理解し,運用することができる.
授業計画
Course Schedule
総授業時間数(実時間);22時間30分

第1回: 概論・アルゴリズムの基礎概念・計算量
第2回:データ構造の基礎(スタック,キュー)
第3回:データ構造の基礎(リスト)
第4回:ソートアルゴリズム (1) (選択ソート,挿入ソート,バブルソート)
第5回:ソートアルゴリズム (2) (マージソート,クイックソート)
第6回:ソートアルゴリズム (3) (バケットソート,ヒープソート)
第7回:探索(1) (逐次探索)
第8回:中間試験
第9回:探索(2) (2分探索)
第10回:探索(3)(AVL木)
第11回:文字列パターン照合(1)(文字列パターン照合,力まかせ法・単純法)
第12回:文字列パターン照合(2)(KMP法)
第13回:文字列パターン照合(3)(BM法)
第14回:グラフ(ダイクストラ法)
第15回:期末試験

※詳しい予定は第1週目に説明します.
※また,進度により上記スケジュールが変更になる場合があります。 

・ほぼ毎週,レポートを課します.
・教科書の該当部分(授業時間内に指示)をあらかじめ理解したうえで授業に参加してください.
教科書
Required Text
教科書:「あるごりずむ」広瀬貞樹著,近代科学社 
(必ず用意すること)
参考書
Required Materials
・アルゴリズムイントロダクション1 数学的基礎とデータ構造
 近代科学社 T.コルメン・C. ライザーソン・R. リベスト 著,浅野哲夫 他 訳
・アルゴリズム 第1巻,第2巻,R.セジウィック著 (野下他共訳) 近代科学社  
 
教科書・参考書に関する備考 データ構造とアルゴリズム,アルゴリズム基礎などのう題目の書籍は多数あります.
多くが参考になるはずです.
成績評価方法
Grading Guidelines
中間試験の得点を4割,期末試験の得点を6割に配分した計100点満点の成績評価を基準とする.ただし,この成績評価において合格点(60点)に満たないものの合格点に近くかつレポート点が十分な点に達しているものに対しては,別途追加レポートの提出を課し,課題基準に達している場合のみ合格を与えるという措置をとる.

なお各到達度目標の評価方法は,次のように行う.
目標1:中間試験,期末試験においてアルゴリズムに関する問題を出題し,その達成度を評価する.
目標2:中間試験,期末試験において基本的なデータ構造の理解度に関する問題を出題し,その達成度を評価する.
履修上の注意
Please Note
卒業研究において,情報系の卒研を希望する場合には,学生には履修を勧めます。
プログラム,解析などの数学などを習得し理解していることが求められます。
なお,不合格の場合には再履修すること.
教員メッセージ
Message from Lecturer
本講義は,プログラム設計を学ぶ上で根幹となる科目です.
必ず毎回のレポート作成を通じて予習,復習を行い,講義内容を真に理解するようにしてください.
学習・教育目標との対応
Learning and Educational
Policy
この授業科目は情報電子工学系学科の夜間主コースの学習目標の以下の項目に対応している.
[コンピュータサイエンス]情報工学の基礎知識と応用能力を身につける。
関連科目
Associated Courses
情報系の数理基礎を含む科目,プログラミング,解析などの数学系科目
備考
Remarks