授業情報/Course information

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

第1回:概論・アルゴリズムの基礎概念・計算量
第2回:データ構造と配列
第3回:探索(線形探索)
第4回:探索(2分探索・ハッシュ法)
第5回:スタックとキュー
第6回:ソートアルゴリズム (1) (選択ソート,挿入ソート,バブルソート)
第7回:ソートアルゴリズム (2) (マージソート,クイックソート)
第8回:ソートアルゴリズム (3) (ヒープソート)
第9回:ソートアルゴリズムのまとめおよび中間試験
第10回:再帰的アルゴリズム
第11回:文字列パターン照合(1)(文字列パターン照合,力まかせ法・単純法)
第12回:文字列パターン照合(2)(KMP法)
第13回:文字列パターン照合(3)(BM法)
第14回:線形リスト
第15回:定期試験

教科書の該当部分(授業時間内に指示する)を予め理解した上で授業に参加すること(予習はレポート内容の一部としても課されます).

ただし,新型コロナウイルス感染症の流行状況に伴い、学生への十分な周知のもと、授業計画・授業実施方法は変更する可能性があります。

各回の学修時間の目安は、事前・事後合わせて4時間必要です。
教科書
/Required Text
新・明解Pythonで学ぶアルゴリズムとデータ構造 柴田望洋 (著)(ISBN:4815603197)
参考書等
/Required Materials
アルゴリズムイントロダクション 第3版 第1巻: 基礎・ソート・データ構造・数学 (ISBN:4764904063) (ISBN:4764904063)
教科書・参考書に関する備考 授業中に適宜資料を配布する.
成績評価方法
/Grading Guidelines
中間試験の得点を4割,期末試験の得点を6割に配分した計100点満点の成績評価を基準とする.ただし,この成績評価において合格点(60点)に満たないものの合格点に近くかつレポート点が十分な点に達しているものに対しては,別途追加レポートの提出を課し,課題基準に達している場合のみ合格を与えるという措置をとる.
なお各到達度目標の評価方法は,次のように行う.
目標1:中間試験,期末試験においてアルゴリズムに関する問題を出題し,その達成度を評価する.
目標2:中間試験,期末試験において基本的なデータ構造の理解度に関する問題を出題し,その達成度を評価する

ただし,新型コロナウイルス感染症の流行状況に伴い、学生への十分な周知のもと、成績評価方法は変更する可能性があります。
履修上の注意
/Notices
・予習復習をかねたレポートをほぼ全ての回において課すので必ず提出すること.
・不合格の場合には再履修すること.
・授業の変更や緊急時の連絡は授業中またはMoodle,掲示板で通知する.
教員メッセージ
/Message from Lecturer
複数回レポートを課します.
教科書の該当部分(授業時間内に指示する)を予め理解した上で授業に参加すること.
学習・教育目標との対応
/Learning and Educational Policy
学生便覧「学習目標と授業科目との関係表」参照
関連科目
/Related course
システム理化学科共通「プログラミング演習」,数理情報コース 「情報学基礎演習A」,「情報学基礎演習B」,「基盤情報学演習」,「プログラミングA」,「プログラミングB」
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の度合い
該当なし