|
開講学期 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) |
sin(at mark)csse.muroran-it.ac.jp |
|
オフィスアワー Office Hour |
月曜日 15:00−16:00 (期間中に変更する場合がある) |
|
授業のねらい Learning Objectives |
情報工学・科学に入門するための基本的なアルゴリズムとデータ構造について紹介し，アルゴリズムの基本設計，データ構造の設定などについての基本的な知識と運用方式を学ぶことをねらいとしている． |
|
到達度目標 Outcomes Measured By: |
１．一般的概念としてソートや探索といった基本的なアルゴリズムについてその計算量や特徴を理解し応用できる． ２．特徴的なデータ構造についてもその特性を理解し，運用することができる． |
|
授業計画 Course Schedule |
総授業時間数（実時間）；２２時間３０分 第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. リベスト 著，浅野哲夫 他 訳 ・アルゴリズム 第１巻，第２巻，R.セジウィック著 （野下他共訳） 近代科学社 |
| 教科書・参考書に関する備考 |
データ構造とアルゴリズム，アルゴリズム基礎などのう題目の書籍は多数あります． 多くが参考になるはずです． |
|
成績評価方法 Grading Guidelines |
中間試験の得点を4割，期末試験の得点を6割に配分した計100点満点の成績評価を基準とする．ただし，この成績評価において合格点(60点)に満たないものの合格点に近くかつレポート点が十分な点に達しているものに対しては，別途追加レポートの提出を課し，課題基準に達している場合のみ合格を与えるという措置をとる． なお各到達度目標の評価方法は，次のように行う． 目標1：中間試験，期末試験においてアルゴリズムに関する問題を出題し，その達成度を評価する． 目標2：中間試験，期末試験において基本的なデータ構造の理解度に関する問題を出題し，その達成度を評価する． |
|
履修上の注意 Please Note |
卒業研究において，情報系の卒研を希望する場合には，学生には履修を勧めます。 プログラム，解析などの数学などを習得し理解していることが求められます。 なお，不合格の場合には再履修すること． |
|
教員メッセージ Message from Lecturer |
本講義は，プログラム設計を学ぶ上で根幹となる科目です． 必ず毎回のレポート作成を通じて予習，復習を行い，講義内容を真に理解するようにしてください． |
|
学習・教育目標との対応 Learning and Educational Policy |
この授業科目は情報電子工学系学科の夜間主コースの学習目標の以下の項目に対応している． ［コンピュータサイエンス］情報工学の基礎知識と応用能力を身につける。 |
|
関連科目 Associated Courses |
情報系の数理基礎を含む科目，プログラミング，解析などの数学系科目 |
|
備考 Remarks |
|