文理学部シラバスTOP > 文理学部 > 情報科学科 > データ構造
日本大学ロゴ

データ構造

このページを印刷する

令和2年度以降入学者 データ構造
教員名 谷聖一
単位数    2 学年 3・4 開講区分 文理学部
科目群 情報科学科
学期 前期 履修区分 選択必修
授業形態 対面授業
Canvas LMSコースID・コース名称 Q065241736 2024データ構造(谷聖一・前・月2)
授業概要 データ構造の基礎を実践的に学ぶ
授業のねらい・到達目標 効率の良いプログラムを作るには,良い方法(アルゴリズム)とそれに適したデータの保持方法 (データ構造) を用いる必要がある.
本講義では,リスト,スタック,キュー,木構造,グラフ、ハッシュといった基本的なデータ構造の概念を理解するとともに Python あるいは C言語/C++ で実装できるようになる.

この科目は文理学部(学士(理学))のディプロマポリシー DP3-5及びカリキュラムポリシー CP3-5に対応している。

・仮説に基づく課題や問題を提示し,客観的な情報を基に,論理的・批判的に考察できる.(A-3-3)
・問題を分析し,複数の解決策を提示した上で,問題を解決することができる.(A-4-3)
・責任と役割を担い,新しい問題に取り組む意識を持ち,そのために必要な情報科学の知識・情報を収集することができる.(A-5-3)
授業の形式 講義
授業の方法 第1回目授業までに,本授業の Google Classroom 及び本授業用 Google Chat スペースに参加すること.
参加方法は Canvas LMS にて告知する.なお,Canvas をこの目的以外に使用することはない.

・本授業では,Google Classroom, Google Drive, Google Chat でコミュニケーション行う.(Canvas や Slack は利用しない.)
・事前学習・事後学習の一環として,Python, C言語/C++ あるい Ruby を用いたアルゴリズムの実現と性能評価実験を課題として出題する.
・課題の一部は自己評価・相互評価を行う場合がある.レポートには,総評することでフィードバックを行う.

オンライン参加が認められた場合の受講方法: 授業時間帯にZoomにて授業に参加する.
履修条件 「実践プログラミング2」の内容を理解していることを前提に講義を進める.
また,文理学部教育用アカウント (stu アカウント) と NU-Apps G アカウントを適切に使い分けられることを前提とする.
授業計画
1 再帰呼び出し復習と2分探索復習
【事前学習】「実践プログラミング2」の内容をあらかじめ復習しておく (2時間)
【事後学習】再帰呼出し・2分探索に関するプログラミング課題に取り組む (2時間)
【授業形態】対面授業
2 2分探索木の実装復習
【事前学習】2分探索木の実装について復習しておく (2時間)
【事後学習】2分探索木に関するプログラミング課題に取り組む (2時間)
【授業形態】対面授業
3 2分探索木のトラバース復習
【事前学習】2分探索木のトラバーサルについて復習しておく (2時間)
【事後学習】2分探索木のトラバーサルに関するプログラミング課題に取り組む (2時間)
【授業形態】対面授業
4 平衡木の概念
【事前学習】平衡木について事前に確認する (2時間)
【事後学習】平衡機の概念に関する課題に取り組む (2時間)
【授業形態】オンデマンド型授業
5 平衡木の実装 (AVL 木の場合)
【事前学習】平衡木の実装について事前に確認する (2時間)
【事後学習】平衡木に関するプログラミング課題に取り組む (2時間)
【授業形態】対面授業
6 ヒープ木の概念と実装
【事前学習】ヒープ木について事前に確認する (2時間)
【事後学習】ヒープ木に関するプログラミング課題に取り組む (2時間)
【授業形態】対面授業
7 工夫したヒープ木の実装
【事前学習】工夫したヒープ木の実装について事前に確認する (2時間)
【事後学習】木構造に関するプログラミング課題に取り組む (2時間)
【授業形態】対面授業
8 小テスト (1)
スタックとキュー
【事前学習】スタックとキューについて事前に確認する (2時間)
【事後学習】スタックとキューの実装方法について復習し,実装する (2時間)
【授業形態】対面授業
9 グラフのデータ構造
【事前学習】グラフのデータ構造について事前に確認する (2時間)
【事後学習】グラフのデータ構造の実装方法について復習し,実装する (2時間)
【授業形態】対面授業
10 スタックとキューの探索への応用 :深さ優先探索と幅優先探索
【事前学習】深さ優先探索について事前に確認する (2時間)
【事後学習】幅優先探索に関するプログラミング課題に取り組む (2時間)
【授業形態】対面授業
11 再帰呼び出しによる深さ優先探索
【事前学習】再帰呼出しを用いた深さ優先探索について事前に確認する (2時間)
【事後学習】再帰呼出しを用いた深さ優先探索に関するプログラミング課題に取り組む (2時間)
【授業形態】対面授業
12 探索の実践的なプログラミング
【事前学習】第8回〜第11回の内容について復習しておくこと (2時間)
【事後学習】木の探索に関するプログラミング課題に取り組む (2時間)
【授業形態】対面授業
13 ハッシュ関数と内部ハッシュ法・外部ハッシュ法
【事前学習】ハッシュ関数と内部ハッシュについて事前に確認する (2時間)
【事後学習】内部ハッシュに関するプログラミング課題に取り組む (2時間)
【授業形態】対面授業
14 外部ハッシュ法とその計算量
【事前学習】外部ハッシュについて事前に確認する (2時間)
【事後学習】外部ハッシュ法の計算量解析を自分で行い,ノートに記録する (2時間)
【授業形態】対面授業
15 まとめと小テスト (2)
【事前学習】第1回〜第14回の内容について復習しておくこと (2時間)
【事後学習】総合的なプログラミング課題に取り組む (2時間)
【授業形態】対面授業
その他
教科書 大槻 兼資 著 『問題解決力を鍛える!アルゴリズムとデータ構造 (KS情報科学専門書)』 講談社 2020年
参考書 平田富夫 『アルゴリズムとデータ構造』 2016年 第3版
米田 優峻 著 『問題解決のための「アルゴリズム×数学」が基礎からしっかり身につく本』 技術評論社 2021年 第1版
茨木 俊秀 『Cによるアルゴリズムとデータ構造(改訂2版) 』 オーム社 2019年 第2版
成績評価の方法及び基準 授業内テスト(60%)、授業参画度(40%)
・授業内テストは2回実施する.詳細は1回目の授業時に説明する.
・授業内テストは対面で実施する.
・事前学習あるいは事後学習の一環として6回程度の課題が必要な課題を課す.この評価が授業参画度の中核をなす.一部の課題では実装を伴う計算機実験を行う(実装に用いるプログラミング言語は,C, C++, Python, Ruby のいずれかとする.さらに,課題によってはプログラミング言語を指定する場合がある.).
・Google Classroom, Google Drive, Google Chat でコミュニケーション行う.この授業では,Canvas LMS や Slack は使用しない.
オフィスアワー 随時,Google Chat で受け付ける.
なお,対面を希望する場合は事前に Google Chat でで予約すること.

このページのトップ