シラバス参照

授業情報/Course information

科目一覧へ戻る 2020/04/02 現在

授業基本情報
科目名(和文)
/Course
データ構造とアルゴリズム
科目名(英文)
/Course
Data Structures and Algorithms
時間割コード
/Registration Code
22146201
学部(研究科)
/Faculty
情報工学部
学科(専攻)
/Department
情報システム工学科
担当教員(○:代表教員)
/Principle Instructor (○) and Instructors
菊井 玄一郎
オフィスアワー
/Office Hour
菊井 玄一郎(火曜5時限)
開講年度
/Year of the Course
2019年度
開講期間
/Term
前期
対象学生
/Eligible Students
2年次生
単位数
/Credits
2.0
授業概要情報
更新日
/Date of renewal
2019/03/02
使用言語
/Language of Instruction
日本語
オムニバス
/Omnibus
該当なし
授業概略と目的
/Cource Description and Objectives
計算機プログラムの骨格をなす2つの要素であるデータ構造とアルゴリズムの基礎を習得する.本講義では,Cなど特定のプログラミング言語への依存を極力避けて,プログラムを作成する上で基本となる考え方について講述する.具体的な目標は次の通りである.
1)アルゴリズムとは何かを計算量の概念とともに理解する.
2)リスト中の特定の値を探索するアルゴリズムを理解する
3)リストの要素を整列するアルゴリズムを理解する.
4)文字列検索,経路探索の基本的な手法を理解する
履修に必要な知識・能力・キーワード
/Prerequisites and Keywords
C言語またはほかのプログラミング言語に関する基礎知識(簡単なプログラムが組めること).
初歩的な解析学の知識(極限,オーダー).
履修上の注意
/Notes
この授業の第二回目以降はグループ単位での演習中心で行います.事前に講義資料を読んでアルゴリズムを理解しておいてください.分からなければ図書館に色々な本があるので勉強してください.ウエブ検索しても良いが時々ウソの内容があるので注意すること.
教科書
/Textbook(s)
教科書はありません.
次のサイトに資料を置いておきますので各自ダウンロードしてください.一部の内容は解説がついています.
https://iis.cse.oka-pu.ac.jp/courses/dsa/

参考文献等
/References
近藤嘉雪,”定本 Cプログラマのためのアルゴリズムとデータ構造”,ソフトバンククリエイティブ,1998.
書名に「アルゴリズムとデータ構造」(あるいは「データ構造とアルゴリズム」)ということばを含むものなら何でもよい.
自分の好みに合ったものを見つけて学習して欲しい.
少し変わったものとして,
結城浩,”数学ガール(乱択アルゴリズム)”,ソ フトバンククリエイティブ,2011.
は対話調でアルゴリズムや計算量の考え方が丁寧に書かれている(やさしく書かれている).
自主学習ガイド
/Expected Study Guide outside Coursework/Self-Directed Learning Other Than Coursework
実際にプログラムを書いて動かしてみると理解が進む.
資格等に関する事項
/Attention Relating to Professional License
情報処理技術者(基本情報,応用情報レベル)の項目である.
備考
/Notes
本科目は「実務経験のある教員による授業科目」又は「主として実践的教育から構成される授業科目」である。
その内容等については、次のアドレスの一覧表を参照。
https://www.oka-pu.ac.jp/guide/guide_detail/index/1860.html
授業計画詳細情報
No. 単元(授業回数)
/Unit (Lesson Number)
単元タイトルと概要
/Unit Title and Unit Description
時間外学習
/Preparation and Review
配付資料
/Handouts
1 1 [概論:アルゴリズムとは? ]
配列の探索を例にアルゴリズムの概念とデータ構造が密接に関係することを学ぶ.
2 2 [配列の探索(1)]
線形探索および二分探索のアルゴリズムについて学ぶ.
3 3 [計算量の概念]
時間計算量と空間計算量の概念,それを表す「オーダー記法」について理解する.
4 4 [ データ構造]
ポインタを利用する連結リストを理解する(C言語ポインタについて復習しておくこと).
5 5~6 [配列の探索(2-3)]
ハッシュ法の基本概念であるハッシュ関数と衝突,チェイン法,オープンアドレス法による実装について理解する .
6 7~11 [整列(1-4)]
整列(ソート)のアルゴリズムについて学ぶ.
1)単純ソート(選択ソート,バブルソート,挿入ソート)
2)クイックソート
3)マージソート
4)ヒープソート
最後にソートに関する総復習を行う
7 12 [経路探索]
Dijkstra法による最短経路探索について学ぶ.
8 13 [文字列の探索]
Boyer-Moore法を中心に文字列探索アルゴリズムについて考える.
9 14 [アルゴリズムの限界]
計算量的に難しい問題とはどういうものか,既に学んだアルゴリズムとどういう関係にあるのかについて理解する.
10 15 [まとめ]
この講義を振り返るとともに,扱わなかった問題などを含めてさらに学ぶだめのガイドを行う.
11 16 [定期試験]
期末定期試験を行う
授業評価詳細情報
到達目標及び観点/Learning Goal and Specific Behavioral Viewpoints
No. 到達目標
/Learning Goal
知識・理解
/Knowledge & Undestanding
技能・表現
/Skills & Expressions
思考・判断
/Thoughts & Decisions
伝達・コミュニケーション
/Communication
協働
/Cooperative Attitude
1 計算量,計算の複雑さの考え方を理解している
2 基本データ構造(配列,連結リスト,スタック,キュー,木構造)を理解し,適切な処理方法を考えることができる.
3 配列の探索と整列のデータ構造とアルゴリズムと計算量を理解している.
4 経路探索,文字列探索のデータ構造とアルゴリズムと計算量を理解している.
成績評価方法と基準/Evaluation of Achievement
※出席は2/3以上で評価対象となります。
No. 到達目標
/Learning Goal
定期試験
/Exam.
ミニテスト 受講態度(発言)
1 計算量,計算の複雑さの考え方を理解している
2 基本データ構造(配列,連結リスト,スタック,キュー,木構造)を理解し,適切な処理方法を考えることができる.
3 配列の探索と整列のデータ構造とアルゴリズムと計算量を理解している.
4 経路探索,文字列探索のデータ構造とアルゴリズムと計算量を理解している.
評価割合(%)
/Allocation of Marks
40 40 20

科目一覧へ戻る