Course title
Y01226002
Data Structure and Algorithm

 YAMAZAKI Kenichi Click to show questionnaire result at 2018
Course description
ソフトウェアの開発では効率的なアルゴリズムとデータ構造の設計・解析が必要になる。本講義では計算機を使って問題を効率的に解く際に必要となる基本的アルゴリズムとその実現に適したデータ構造、及び、計算量について解説し、現実のソフトウェアの設計・開発に応用できる能力を修得することを目指す。本科目は、「プログラミング１」「プログラミング２」を発展させた内容となっているため、それらを履修しておくことが望ましい。
Purpose of class
本授業の目的は，プログラムを用いて様々な問題を解決できるようになることである．このためには，既存のアルゴリズムを知るだけでなく，自分でアルゴリズムを考え出せるようになる必要がある．
Goals and objectives
  1. 木、ハッシュ、グラフなどのデータ構造とそれらの基本アルゴリズムについて理解でき、動作や意味を説明できる。
  2. 基本アルゴリズムの計算量解析ができる。
  3. それらのアルゴリズムとデータ構造に従ったプログラムが書ける。
Relationship between 'Goals and Objectives' and 'Course Outcomes'

 レポート 期末試験 Total.
1. 5% 30% 35%
2. 5% 30% 35%
3. 30% 0% 30%
Total. 40% 60% -
Language
Japanese
Class schedule

 Class schedule HW assignments (Including preparation and review of the class.) Amount of Time Required
1. アルゴリズムとは何か、データ構造とは何か．アルゴリズムの正当性と停止性、入出力の論理式表現． 教科書1章 190minutes
2. 二分探索木(1)　探索、挿入、削除 教科書４章 190minutes
3. 二分探索木(2) 　計算量解析 教科書４章、１０章 190minutes
4. 高度な木 B木、トライ木 教科書４章 190minutes
5. 文字列表現と文字列探索 BM法 教科書７章 190minutes
6. 文字列探索 KMP法 教科書７章 190minutes
7. 量子アルゴリズム インターネット等で自分で調査する 190minutes
8. グラフ（１）データ構造、DAG 教科書６章 190minutes
9. グラフ（２）最短経路 教科書６章 190minutes
10. 正規表現とオートマトン インターネット等で自分で調査する 190minutes
11. オートマトンと状態遷移機械 前回の授業資料の再読 190minutes
12. アルゴリズム設計論(1)　再帰、分割統治法、充足可能問題 教科書８章 190minutes
13. アルゴリズム設計論(2)　その他のアルゴリズム 教科書８章、９章 190minutes
14. 試験および試験の解説 試験準備 190minutes
Total. - - 2660minutes
Evaluation method and criteria
3回以上実施する演習レポート（40%）および期末試験（60%）の総合得点が60％以上になったものを合格とする。
授業中に出題する確認問題等が自力で解ければ，期末試験は60%である．
演習レポートは必ず提出すること。指示したことが最低限記述してあれば60%である．
レポートではプログラムを作成するため，情報処理演習やプログラミング1・2で使った開発環境を残しておくこと．
Feedback on exams, assignments, etc.
ways of feedback specific contents about "Other"
Feedback in the class
Textbooks and reference materials
参考書：浅野哲夫著「IT Textシリーズ アルゴリズム論」（オーム社）。
（参考書だが，準教科書に近い．できれば購入すること．）

その他の参考書：石畑著「アルゴリズムとデータ構造」（岩波書店）
　エイホ他著「データ構造とアルゴリズム」（培風館）
　ヴィルト著「アルゴリズムとデータ構造」（近代科学社）
Prerequisites
履修前提科目：「プログラミング1」「プログラミング2」
Office hours and How to contact professors for questions
  • 授業当日の4限終了後（16:40～）．
    それ以外の時間帯については，初回授業にて連絡する．
Regionally-oriented
Non-regionally-oriented course
Development of social and professional independence
  • Course that cultivates an ability for utilizing knowledge
  • Course that cultivates a basic problem-solving skills
Active-learning course
About half of the classes are interactive
Course by professor with work experience
Work experience Work experience and relevance to the course content if applicable
Applicable 企業にてシステム・プログラミング言語の研究・開発に従事した教員が，データ構造やアルゴリズムについて説明する．
Education related SDGs:the Sustainable Development Goals
  • 9.INDUSTRY, INNOVATION AND INFRASTRUCTURE
Last modified : Tue Sep 17 18:16:50 JST 2024