| 開講学期／Course Start | 2018年度／Academic Year 前期／First |
|---|---|
| 開講曜限／Class period | 月/Mon 5,月/Mon 6 |
| 授業区分／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 | B4211 |
| 連絡先／Contact |
渡邉真也(居室：V613 メールアドレス：sin[at]csse.muroran-it.ac.jp ([at] は@に置換)) |
| オフィスアワー／Office hours |
渡邉真也(月曜 １６：００-１７：００ 場所：Ｖ６１３) |
| 更新日／Date of renewal | 2018/03/20 |
|---|---|
| 授業のねらい ／Learning Objectives |
情報工学・科学に入門するための基本的なアルゴリズムとデータ構造について紹介し,アルゴリズムの設計,データ構造の設定についての基本的な知識を身につけ，応用する力を身につけることをねらいとしている． |
| 到達度目標 ／Outcomes Measured By: |
１．一般的概念としてソートや探索，文字列マッチングといった基本的なアルゴリズムについてその計算量や特徴を理解し応用できる． ２．特徴的なデータ構造についてもその特性を理解し,運用することができる． |
| 授業計画 ／Course Schedule |
総授業時間数（実時間）；２２時間３０分 第1回： 概論・アルゴリズムの基礎概念・計算量 第2回：データ構造の基礎（スタック,キュー） 第3回：データ構造の基礎（リスト） 第4回：ソートアルゴリズム (1) （選択ソート,挿入ソート,バブルソート） 第5回：ソートアルゴリズム (2) （マージソート,クイックソート） 第6回：ソートアルゴリズム (3) （バケットソート,ヒープソート） 第7回：ソートアルゴリズムのまとめおよび中間試験 第8回：探索(1) （逐次探索） 第9回：探索(2) （2分探索） 第10回：探索(3)（AVL木） 第11回：文字列パターン照合(1)（文字列パターン照合,力まかせ法・単純法） 第12回：文字列パターン照合(2)（KMP法） 第13回：文字列パターン照合(3)（BM法） 第14回： グラフ（ダイクストラ法） 第15回：講義全体のまとめ ※詳しい予定は第1週目に説明します． ※また,進度により上記スケジュールが変更になる場合があります。 ・ほぼ毎週,レポートを課します． ・Moodleを活用する予定です． ・教科書の該当部分（授業時間内に指示）をあらかじめ理解したうえで授業に参加してください． |
| 教科書 ／Required Text |
あるごりずむ 広瀬 貞樹 (著)(ISBN:4764903202) |
| 参考書等 ／Required Materials |
アルゴリズムイントロダクション 第3版 第1巻: 基礎・ソート・データ構造・数学 (ISBN:4764904063)
なっとく! アルゴリズム (ISBN:4798143359) |
| 成績評価方法 ／Grading Guidelines |
中間試験の得点を4割，期末試験の得点を6割に配分した計100点満点の成績評価を基準とする．ただし，この成績評価において合格点(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 ／主体的学修（予復習，反転授業，小テスト，振り返り 等） |
隔週（2週に1度程度），復習に関する課題を課している． |
|---|---|
|
Active learning 1-2 ／上記項目に係るALの度合い |
15%～50% |
|
Active learning 2-1 ／対話的学修（グループ学習，協働，調査体験 等） |
|
|
Active learning 2-2 ／上記項目に係るALの度合い |
該当なし |
|
Active learning 3-1 ／深い学修（複数科目の知識の総合化や問題解決型学修 等） |
|
|
Active learning 3-2 ／上記項目に係るALの度合い |
該当なし |