アルゴリズムとデータ構造

科目基礎情報

学校	津山工業高等専門学校	開講年度	令和04年度 (2022年度)
授業科目	アルゴリズムとデータ構造
科目番号	0018	科目区分	専門 / 必修
授業形態	講義	単位の種別と単位数	学修単位: 4
開設学科	情報工学科	対象学年	4
開設期	通年	週時間数	2
教科書/教材	Textbook: 紀平 拓男，春日 伸弥「プログラミングの宝箱 アルゴリズムとデータ構造」（SBクリエイティブ）
担当教員	松島 由紀子

到達目標

Learning purposes :
Students who have taken this course can explain well-known algorithms and data structures and answer the name of algorithm and data structures when they read the explanation. They also can explain basic notion and terminology of time complexity and its related notion for considering efficiency of algorithms.

Course Objectives :
1. To be able to explain what is algorithms.
2. To be able to explain typical sort algorithms and search algorithms.
3. To be able to explain typical data structures, e.g. stack, queue, tree structure and so on.
4. To be able to explain string search algorithms.
5. To be able to explain graph data structure.

ルーブリック

	Excellent	Good	Acceptable	Not acceptable
Achievement 1	Can evaluate the computational complexity of practical programs using the complexity notation and its definition.	Can evaluate the computational complexity of typical programs using the complexity notation and its definition.	Can explain the complexity notation and its definition.	Cannot explain the complexity notation and its definition.
Achievement 2	Can implement practical programs using sort and search algorithms.	Can utilize sort and search algorithms.	Can explain sort and search algorithms.	Cannot explain sort and search algorithms.
Achievement 3	Can implement practical programs using stack, queue and tree structure.	Can utilize stack, queue and tree structure.	Can explain stack, queue and tree structure.	Cannot explain stack, queue and tree structure.
Achievement 4	Can implement practical programs using string search algorithms.	Can utilize string search algorithms.	Can explain string search algorithms.	Cannot explain string search algorithms.
Achievement 5	Can evaluate the practical problems using the graph data structures.	Can evaluate the typical problems using the graph data structures.	Can explain graph data structures.	Cannot explain graph data structures.

教育方法等

概要:

General or Specialized : Specialized

Field of learning : Infromation system・Programming・Network

Foundational academic disciplines : Integrated Disciplines/Informatics/Principles of Informatics/Software

Relationship with Educational Objectives :This class is equivalent to "(3) Acquire deep foundation knowledge of the major subject area".

Course outline :Efficiency of solving a problem by computer is depend on algorithm and data structures. This course provides basic skill of choosing and designing algorithms and data structures using typical algorithms and data structures.

授業の進め方・方法:

Course method : The lessons will be centered on board writing. In order to deepen the understanding, we will proceed with the lessons while solving the exercises as appropriate.

Grade evaluation method : Regular examination scores are calculated as the average of four examinations. Retesting is not conducted in principle. If the result of the regular test is less than 60 points, the score may be changed if the understanding can be confirmed by the retest. However, the overall evaluation shall not exceed 60 points.

注意点:

Precautions on enrollment : Students must take this class (no more than one-third of the required number of class hours missed).

Course advice :This course is closely connected with programming. Implementation of algorithms that are dealt with in this course makes deeply understanding.

Foundational subjects : Fundamentals of Integrated Science and Technology(1st year), Basic Programming(2nd)

Related subjects : Database Systems(5th year), Advanced Programming(4th), Mathematical Information(4th)

Attendance advice : Delay of attendance will be counted as absence. Entry after confirmation of attendance will be delayed. If you are late, you will be treated as absent from one credit hour for two times.

授業の属性・履修上の区分

遠隔授業対応

Ｍｕｓｔ　ｃｏｍｐｌｅｔｅ　ｓｕｂｊｅｃｔｓ

授業計画

		週	授業内容	週ごとの到達目標
前期
	1stQ
		1週	Course Guidance	Understand objectives of this course
		2週	Bubble Sort	Learn Bubble Sort Algorithm and understand the program of Bubble Sort
		3週	Quicksort 1	Learn Quicksort Algorithm
		4週	Quicksort 2	Understand the program of Quicksort
		5週	Merge Sort	Learn Merge Sort Algorithm and understand the program of Merge Sort
		6週	Linear Search	Learn Linear Search Algorithm and understand the program of Linear Search
		7週	Binary Search	Learn Binary Search Algorithm and understand the program of Binary Search
		8週	1st Semester Mid-term Exam
	2ndQ
		9週	Return 1st Semester Mid-term Exam and correct mistakes	Understand mistakes
		10週	List	Learn List and understand the program of List
		11週	Stack	Learn Stack and understand the program of Stack
		12週	Queue	Learn Queue and understand the program of Queue
		13週	Recursion 1	Learn Recursion
		14週	Recursion 2	Understand the program of Recursion
		15週	(1st Semester Final Exam)
		16週	Return 1st Semester Final Exam and correct mistakes	Understand mistakes
後期
	3rdQ
		1週	Tree Structure 1	Learn Tree Structure
		2週	Tree Structure 2	Learn Tree Structure
		3週	Tree Structure 3	Understand the program of Tree Structure
		4週	Map and Hash 1	Learn Map and Hash
		5週	Map and Hash 2	Understand the program of Map and Hash
		6週	String Search Algorithm 1	Learn String Search Algorithm
		7週	String Search Algorithm 2	Understand the program of String Search
		8週	2nd Semester Mid-term Exam
	4thQ
		9週	Return 2nd Semester Mid-term Exam and correct mistakes	Understand mistakes
		10週	Tree Traversal	Learn Tree Traversal and understand the program of Tree Traversal
		11週	Graph Data Structure	Learn Graph Data Structure
		12週	Automata	Learn Automata
		13週	Regular Expression	Learn Regular Expression
		14週	Summary and prepare for the Final Exam	Review the algorithms and their programs and be able to explain them.
		15週	(2nd Semester Final Exam)
		16週	Return 2nd Semester Final Exam and correct mistakes	Understand mistakes

モデルコアカリキュラムの学習内容と到達目標

分類		分野	学習内容	学習内容の到達目標	到達レベル	授業週
専門的能力	分野別の専門工学	情報系分野	ソフトウェア	アルゴリズムの概念を説明できる。	4
				与えられたアルゴリズムが問題を解決していく過程を説明できる。	4
				同一の問題に対し、それを解決できる複数のアルゴリズムが存在しうることを説明できる。	4
				整列、探索など、基本的なアルゴリズムについて説明できる。	4
				時間計算量によってアルゴリズムを比較・評価できることを説明できる。	4
				領域計算量などによってアルゴリズムを比較・評価できることを説明できる。	4
				コンピュータ内部でデータを表現する方法(データ構造)にはバリエーションがあることを説明できる。	4
				同一の問題に対し、選択したデータ構造によってアルゴリズムが変化しうることを説明できる。	4
				リスト構造、スタック、キュー、木構造などの基本的なデータ構造の概念と操作を説明できる。	4
				リスト構造、スタック、キュー、木構造などの基本的なデータ構造を実装することができる。	4
				ソースプログラムを解析することにより、計算量等のさまざまな観点から評価できる。	4
				同じ問題を解決する複数のプログラムを計算量等の観点から比較できる。	4

評価割合

	Examination	Presentation	Mutual Evaluations between students	Behavior	Portfolio	Other	合計
総合評価割合	100	0	0	0	0	0	100
Basic Proficiency	0	0	0	0	0	0	0
Specialized Proficiency	100	0	0	0	0	0	100
Cross Area Proficiency	0	0	0	0	0	0	0