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

Algorithms and Data Structures

9963120

63CSALC305

桂田　浩一、大村　英史

Hidefumi Ohmura

2024年度後期

2024 2nd period

月曜1限

Monday 1st period

創域理工学部　情報計算科学科、数理科学科

Department of Information Sciences, Faculty of Science and Technology
Department of Mathematics Faculty of Science and Technology

2.0単位

講義

Lecture

-

① [対面]対面授業/ [On-site] On-site class

プログラムにおけるデータ構造の概念とそのアルゴリズム及びその実現法を理解する．

データ構造の概念とアルゴリズムを学ぶことにより，洗練された効率のよいプログラム記述能力を学習する．
数学科ディプロマポリシーにある「習得した専門知識や教養をもとに、自ら課題を発見し、解決する能力」を身に付けるための科目である．

１．データ型および抽象データ型の概念を習得する．
２．アルゴリズムの概念を学び，ソーティング法等の効率の良いプログラミングを習得する．
３．基本データ構造のリスト，スタック，キュー，木を習得する．
４．高度なデータ構造の２分探索木，AVL木，B-木を習得する．
５．抽象データ型の辞書を学び，辞書の木を用いた実現を習得する．
６．辞書のハッシュ法を用いた実現を学び，ハッシュ法を習得する．

リンク先の [評価項目と科目の対応一覧]から確認できます（学部対象）。
履修登録の際に参照ください。
​You can check this from “Correspondence table between grading items and subjects” by following the link(for departments).
https://www.tus.ac.jp/fd/ict_tusrubric/​​​

プログラム言語１およびプログラム言語２を既修しておくことが好ましい．

実習　Practical learning

-

配布資料を利用して，準備学習および復習をすること．

到達度評価，授業内に出題する課題に基づき総合的に成績評価を行う．

・S：到達目標を十分に達成し、極めて優秀な成果を収めている
・A：到達目標を十分に達成している
・B：到達目標を達成している
・C：到達目標を最低限達成している
・D：到達目標を達成していない
・-：学修成果の評価を判断する要件を欠格している

・S：Achieved outcomes, excellent result
・A：Achieved outcomes, good result
・B：Achieved outcomes
・C：Minimally achieved outcomes
・D：Did not achieve outcomes
・-：Failed to meet even the minimal requirements for evaluation

N

-

教科書および一部の参考書は、MyKiTS (教科書販売サイト) から検索・購入可能です。
​https://mirai.kinokuniya.co.jp/tokyorika/​​​

It is possible to search for and purchase textbooks and certain reference materials at MyKiTS (online textbook store).
​​https://mirai.kinokuniya.co.jp/tokyorika/

1.データ型：原子データ型，構造データ型，およびデータ構造の概念並びにそれらに伴うポインタ，左辺値と右辺値およびグラフ表現とデータ構造を理解する．

2.抽象データ型：データ型の階層，仕様と実現の独立性，仕様（構文と意味），実現（表現とアルゴリズム），記述例，情報隠蔽等を理解する．

3.アルゴリズムの概念：複雑さ，コスト，機械モデル（チューリングマシン，RAMマシン）を理解する．

4.ソーティング法：典型的アルゴリズムである各種ソーティング法の効率を理解する．

5.基本データ構造リスト：線形データ構造として、リストの概念，それらの仕様および記述例，表現及び実現（配列及びポインタ），各実現の効率の評価を理解する．

6.基本データ構造スタックおよび待ち行列：リストを特化した構造のスタックおよび待ち行列の概念，それらの仕様および記述例，表現及び実現，各実現の効率の評価を理解する．

7.木：木の概念，順序木および２分木並びにそれぞれの概念を理解する．

8.抽象データ型木の仕様：順序木および２分木の仕様および記述例を理解する．

9.抽象データ型木の実現：順序木および２分木の表現及び実現（配列及びポインタ），各実現の効率の評価を理解する．

10.木のポインタ表現：２分木の直接表現と子の連結リスト表現，それらの関係，並びにひもつき表現を理解する．

11.集合：集合の概念，仕様，表現（ビットベクトル，連結リスト），記述例，表現及び実現（配列及びポインタ），各実現の効率の評価を理解する．

12.辞書：辞書の概念，仕様，表現。特に，ハッシュ法による辞書の実現（オープン・クローズハッシュ法）を理解する．

13.２分探索木：２分木を改良した２分探索木のアルゴリズムと効率の評価を理解する．

14.AVL木：２分探索木をバランスさせたAVL木のアルゴリズムを理解する．

15.B-木：バランスさせた多分木のB-木の表現,アルゴリズム,効率の評価を理解する．

-

-

-

なし

-

-