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

科目授業名称（和文）　Name of the subject/class (in Japanese)

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

科目授業名称（英文）　Name of the subject/class (in English)

Data Structures and Algorithms

授業コード　Class code

994627W

科目番号　Course number

46CSALC202

教員名

池辺　淑子

Instructor

Yoshiko IKEBE

開講年度学期

2023年度前期

Year/Semester

2023, 1st semester

曜日時限

水曜2限

Class hours

Wednesday, 2nd period

開講学科・専攻　Department

工学部　情報工学科

Department of Information and Computer Technology, Faculty of Engineering

単位数　Course credit

2.0単位

授業の方法　Teaching method

講義

Lecture

外国語のみの科目（使用言語）　Course in only foreign languages (languages)

-

授業の主な実施形態　Main class format

対面形式 / On-Site

概要　Description

ソートやグラフ探索などの初歩的なアルゴリズムを，リスト，ヒープ，２分木などの基本的なデータ構造とともに学ぶ．

目的　Objectives

情報工学に必要な基礎学力と専門知識，情報技術者として職業上必要な基礎知識を修得するため，さまざまなアルゴリズムについて，データ構造も含めて理解する．

到達目標　Outcomes

代表的なアルゴリズムについて，その数学的背景から実際的なプログラム作成までを習得する．

卒業認定・学位授与の方針との関係（学部科目のみ）

専門分野の応用知識（選択必修科目、実験、演習科目、卒業研究）

履修上の注意　Course notes prerequisites

プログラミング演習２で演習を行う．

アクティブ・ラーニング科目　Teaching type（Active Learning）

小テストの実施　Quiz type test

-

準備学習・復習　Preparation and review

毎回授業において指示する．

成績評価方法　Performance grading policy

到達度評価試験(80%)，および平常点(20%)による．
なお，平常点は毎回実施する小テストで評価する．
詳細は第１回の授業において説明する．

学修成果の評価　Evaluation of academic achievement

・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

教科書　Textbooks/Readings

教科書の使用有無（有=Y , 無=N）　Textbook used(Y for yes, N for no)

Y

書誌情報　Bibliographic information

-

MyKiTSのURL（教科書販売サイト）　URL for MyKiTS(textbook sales site)

教科書および一部の参考書は、MyKiTS (教科書販売サイト) から検索・購入可能です。
It is possible to search for and purchase textbooks and certain reference materials at MyKiTS (online textbook store).
https://gomykits.kinokuniya.co.jp/tokyorika/

参考書・その他資料　Reference and other materials

補助資料を毎回 LETUS にて用意する．

授業計画　Class plan

第１回：アルゴリズムと計算量
　アルゴリズムの効率の評価基準と計算量の概念について学ぶ．

第２回：リスト構造
　ポインタと線形リストについて学ぶ．

第３回：２分探索木
　２分探索木の定義と基本的な性質について学ぶ．

第４回：ヒープとヒープソート
　ヒープソートについて学ぶ．

第５回：ハッシュ法
　外部ハッシュ法，内部ハッシュ法について学ぶ．

第６回：バケット法とその応用（１）
　バケットの考え方とバケットソートについて学ぶ．

第７回：バケット法とその応用（２）
　分布数え上げソート，基数ソートについて学ぶ．

第８回：再帰呼び出しと分割統治
　再帰呼び出しを用いたアルゴリズムと分割統治のパラダイムについて学ぶ．

第９回：グラフ探索
　データ構造のキューとスタックおよびグラフの幅優先探索，深さ優先探索について学ぶ．

第１０回：最短路問題
　グラフの最短路問題とそれを解くダイクストラ法について学ぶ．

第１１回：動的計画法
　最適性の原理と動的計画法について学ぶ．

第１２回：ユニオン・ファインド森と最小木問題
　ユニオン・ファインド森のデータ構造と最小木問題について学ぶ．

第１３回：最大流問題
　最大流問題とその解法について学ぶ．

第１４回：計算の複雑さの理論
　計算量の理論とクラスP, NP，NP完全等について学ぶ．

第１５回：授業の振り返り

授業担当者の実務経験　Work experience of the instructor of the class

-

教育用ソフトウェア　Educational software

-

備考　Remarks

シラバス情報