授業情報/Course information

開講学期/Course Start 2019年度/Academic Year  前期/First
開講曜限/Class period 月/Mon 14,月/Mon 15
授業区分/Regular or Intensive 週間授業
対象学科/Department 情報電子工学系学科 夜間主コース
対象学年/Year 2年,3年,4年
授業科目区分/Category 教育課程 主専門教育科目
必修・選択/Mandatory or Elective 選択
授業方法/Lecture or Seminar 講義科目
授業科目名/Course Title データ構造とアルゴリズム/Data Structures and Algorithms
単位数/Number of Credits 2.0
担当教員名/Lecturer 渡邉真也
時間割コード/Registration Code B8205
連絡先/Contact 渡邉真也(居室:V613
メールアドレス:sin[at]csse.muroran-it.ac.jp  ([at] は@に置換))
オフィスアワー/Office hours 渡邉真也(月曜 16:00-17:00
場所:V613)
実務経験/Work experience
更新日/Date of renewal 2019/02/14
授業のねらい
/Learning Objectives
情報工学・科学に入門するための基本的なアルゴリズムとデータ構造について紹介し,アルゴリズムの基本設計,データ構造の設定などについての基本的な知識と運用方式を学ぶことをねらいとしている.
到達度目標
/Outcomes Measured By:
1.一般的概念としてソートや探索といった基本的なアルゴリズムについてその計算量や特徴を理解し応用できる.
2.特徴的なデータ構造についてもその特性を理解し,運用することができる.
授業計画
/Course Schedule
総授業時間数(実時間):22時間30分

第1回: ガイダンス、アルゴリズム概論
第2回: アルゴリズムの基礎概念・計算量
第3回:基本的な探索アルゴリズム
第4回:配列を使ったデータ構造(1)(ハッシュ法)
第5回:配列を使ったデータ構造(2)(スタック,キュー)
第6回:前半に関する復習,中間試験
第7回:連結リスト構造
第8回:木構造とグラフ
第9回:探索木(1) 二分探索木
第10回:探索木(2) AVL木
第11回:グラフ探索(ダイクストラ法)
第12回:ソートアルゴリズム (1) (選択ソート,挿入ソート,バブルソート)
第13回:ソートアルゴリズム (2) (マージソート,クイックソート)
第14回:ソートアルゴリズム (3) (ヒープソート,基数整列法)
第15回:文字列パターン照合、他のいろいろなアルゴリズム
第16回:期末試験

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

・教科書の該当部分(授業時間内に指示)をあらかじめ理解したうえで授業に参加してください.
教科書
/Required Text
あるごりずむ 広瀬貞樹著 近代科学社 2006(ISBN:9784764903203)
参考書等
/Required Materials
アルゴリズム 伏見正則, 鎌田宗憲著 実教出版 200-(ISBN:4407301082)
アルゴリズムイントロダクション 第3版 第1巻: 基礎・ソート・データ構造・数学 (ISBN:4764904063)
なっとく! アルゴリズム(ISBN:4798143359)
教科書・参考書に関する備考 アルゴリズムの基礎および応用に関する書籍は多数あります.
成績評価方法
/Grading Guidelines
中間試験の得点を4割,期末試験の得点を6割に配分した計100点満点の評点結果に基づいて成績を評価する.
合計が合格点に満たない者に対して,再試験を1度に限り実施する.ただし,この試験で合格した者の成績の上限を「可(60点)」とする.

なお各到達度目標の評価方法は,次のように行う.
目標1:中間試験,期末試験においてアルゴリズムに関する問題を出題し,その達成度を評価する.
目標2:中間試験,期末試験において基本的なデータ構造の理解度に関する問題を出題し,その達成度を評価する
履修上の注意
/Notices
卒業研究において,情報系の卒研を希望する場合は必ず履修してください。

プログラム・解析などの数学などを習得し理解していることが求められます。

不合格の場合には再履修すること.
教員メッセージ
/Message from Lecturer
本講義は,プログラム設計を学ぶ上で根幹となる科目です.
予習,復習を行い,講義内容を理解するようにしてください.

本演習内では時間を取れませんが,アルゴリズムやデータ構造はプログラムを作成し,実際に動きを見ることも大事です.サンプルは参考書やインターネット上で入手可能ですので自主的な学習を薦めます.
学習・教育目標との対応
/Learning and Educational Policy
この授業科目は情報電子工学系学科の夜間主コースの学習目標の以下の項目に対応している.
[コンピュータサイエンス]情報工学の基礎知識と応用能力を身につける。
関連科目
/Related course
情報系の数理基礎を含む科目,プログラミング,解析などの数学系科目
No. 回(日時)
/Time (date and time)
主題と位置付け(担当)
/Subjects and instructor's position
学習方法と内容
/Methods and contents
備考
/Notes
該当するデータはありません
Active learning 1-1
/主体的学修(反転授業,小テスト,振り返り 等)
Active learning 1-2
/上記項目に係るALの度合い
該当なし
Active learning 2-1
/対話的学修(グループ学習,協働,調査体験 等)
Active learning 2-2
/上記項目に係るALの度合い
該当なし
Active learning 3-1
/深い学修(複数科目の知識の総合化や問題解決型学修 等)
Active learning 3-2
/上記項目に係るALの度合い
該当なし