授業科目一覧
基盤科目
コース科目
卒業研究(全科履修生のみ)
夏季集中科目
メニューここまで

データ構造とプログラミング('13)

※印刷用にはシラバスPDF版新規ウィンドウ をご利用ください
主任講師
鈴木 一史 (放送大学准教授)
放送メディア
テレビ
放送時間(平成29年度)
第1学期:(水曜)11時15分~12時00分
第2学期:(火曜)16時00分~16時45分

講義概要

計算機科学において重要な“データ構造”と“プログラミング”について学習する。基本的なデータ構造の例として、配列、スタック、キュー、連結リスト、ツリー、バイナリサーチツリー、平衡木、ハッシュテーブル、ヒープ、グラフ等について解説する。また、これらのデータ構造を利用したデータの基礎的な操作(探索、挿入、削除、整列)等について学習し、各データ構造の特性や計算量の関係を知ることによって、ソフトウェアの設計やプログラミングに応用できるようにする。
※詳しくはシラバス

開設年度
平成25年度
科目区分
コース科目(情報コース(専門科目))
〔2009年度~2015年度〕専門科目(情報コース)
〔2008年度以前〕専門科目(情報コース)
科目コード
1570048
単位数
2単位
単位認定試験
試験日・時限
平成29年度 第1学期:平成29年7月27日(木曜)1時限(9時15分~10時05分)
平成29年度 第2学期:平成30年1月27日(土曜)4時限(13時15分~14時05分)
単位認定試験
平均点
(平成28年度 第1学期)79.1点
(平成28年度 第2学期)83.5点
備考
 
このページのトップへ本文ここまで

授業の目標

・ データ構造の基礎および応用について学ぶ。
・ ソフトウェア設計のために必要なデータ構造を選択できるようにする。
・ プログラミング言語における効果的なデータ構造利用法について学習する。
・ コンピュータに関する基礎概念や知識をもとに、様々な現象の本質を見極め、その知識を活用し問題解決ができるようにする。

履修上の留意点

計算機科学や情報工学の入門的科目を履修していることが望ましいが必須ではない。

シラバス

テーマ 内容 執筆担当講師名
(所属・職名)
放送担当講師名
(所属・職名)
1 コンピュータプログラム ハードウェア、ソフトウェア、プログラム、アルゴリズム、データ構造について学習する。プログラミング言語のデータ型について学ぶ。プログラミング言語における、入力・出力、条件、繰り返し、関数などの文法の仕組みを理解する。

【キーワード】
コンピュータサイエンス、ソフトウェア、プログラミング言語、コンパイラ、プログラム、アルゴリズム、データ構造
鈴木 一史
(放送大学准教授)
鈴木 一史
(放送大学准教授)
2 配列 基本的な配列の仕組みと構造について学習する。また、多次元の配列や構造体を要素にもつ応用的な配列構造について理解する。さらに、配列へのデータの挿入、削除、探索などの基本的な操作や、これらの操作に必要な計算量などについて学ぶ。

【キーワード】
配列、多次元配列、挿入、削除、探索、計算量、線形探索、二分探索、ビッグ・オー記法
鈴木 一史
(放送大学准教授)
鈴木 一史
(放送大学准教授)
3 スタックとキュー 基本的なデータ構造であるスタックとキューの仕組みについて学習する。また、スタックとキューに必要な操作や特徴、そして、スタックとキューがどのように使われるのか応用例について学ぶ。

【キーワード】
スタック、ポップ、プッシュ、ピーク、キュー、デキュー、エンキュー、挿入、削除、優先度付きキュー、双方向キュー
鈴木 一史
(放送大学准教授)
鈴木 一史
(放送大学准教授)
4 連結リスト 連結リストへのデータの探索、挿入、削除等の基本的な操作について学ぶ。また、連結リストと配列との操作効率の違いや、連結リストを拡張した環状リストや双方向連結リストの仕組みについて学習する。

【キーワード】
連結リスト、探索、挿入、削除、分割、マージ、環状リスト、双方向連結リスト
鈴木 一史
(放送大学准教授)
鈴木 一史
(放送大学准教授)
5 ツリー ツリー構造とツリーに関する用語について学ぶ。特に基本的なデータ構造であるバイナリツリーとバイナリサーチツリーの特徴や性質について学習する。

【キーワード】
ツリー、ノード、エッジ、バイナリツリー、バイナリサーチツリー、ツリーの走査、最小値、最大値
鈴木 一史
(放送大学准教授)
鈴木 一史
(放送大学准教授)
6 バイナリサーチツリー バイナリサーチツリーに対する基本的な操作、探索、挿入、削除について学ぶ。また、バイナリサーチツリーの特徴、バイナリサーチツリーの操作に関する計算量について学習する。

【キーワード】
バイナリサーチツリー、探索、挿入、削除、順序内後継者、順序内前任者、計算量、平均計算量、最悪の計算量
鈴木 一史
(放送大学准教授)
鈴木 一史
(放送大学准教授)
7 ツリーの応用 マルチウェイツリー(多分木)の特徴について学ぶ。例として、クアッドツリー(四分木)やオクトツリー(八分木)の構造を理解する。また、平衡木(バランストツリー)の仕組みと性質について学習する。

【キーワード】
マルチウェイツリー、多分木、クアッドツリー、四分木、オクトツリー、八分木、平衡木、Bツリー
鈴木 一史
(放送大学准教授)
鈴木 一史
(放送大学准教授)
8 ハッシュテーブル ハッシュ法はデータの数に関係なく定数計算量で、データの探索、挿入、削除を行うことができる最速の探索手法である。本章では、ハッシュテーブル、ハッシュ関数、ハッシュ値の衝突について学ぶ。また、連鎖法、オープンアドレス法の特徴について学習する。

【キーワード】
ハッシュ法、ハッシュ関数、ハッシュ値の衝突、連鎖法、オープンアドレス法、線形探査、平方探査、ダブルハッシング
鈴木 一史
(放送大学准教授)
鈴木 一史
(放送大学准教授)
9 再帰 再帰の仕組みと再帰プログラムについて学ぶ。再帰プログラムは自分自身を繰り返し呼び出し、そのたびに異なる引数を渡していくものである。末尾再帰、再帰とスタックの関係、末尾再帰プログラムと反復プログラムの関係について学習する。

【キーワード】
再帰、再帰呼び出し、末尾再帰、スタック、反復プログラム、フラクタル図形
鈴木 一史
(放送大学准教授)
鈴木 一史
(放送大学准教授)
10 基本的なソーティング データをキーの値の大小関係に従って並べ替える操作であるソーティング(整列)について学習する。基本的な3つのソーティング、バブルソート、選択ソート、挿入ソートの特徴について学ぶ。

【キーワード】
バブルソート、選択ソート、挿入ソート、昇順・降順、安定なソート、計算量の比較
鈴木 一史
(放送大学准教授)
鈴木 一史
(放送大学准教授)
11 高度なソーティング 高度なソーティングの例として、クイックソート、マージソートの特徴について学ぶ。

【キーワード】
クイックソート、マージソート、計算量の比較
鈴木 一史
(放送大学准教授)
鈴木 一史
(放送大学准教授)
12 ヒープ ヒープはツリーの一種であり、ノードの挿入と削除を高速に行うことができる。本章ではヒープの基本的な仕組みについて学ぶ。また、ヒープを応用した優先度つきキューとヒープソートについて学習する。

【キーワード】
ヒープ、ヒープ条件、挿入、削除、ヒープと配列、優先度付きキュー、ヒープソート
鈴木 一史
(放送大学准教授)
鈴木 一史
(放送大学准教授)
13 グラフ グラフのデータ構造について学習する。グラフに関する用語と意味、そして、コンピュータにおけるグラフの表現方法、深さ優先探索(DFS)、幅優先探索(BFS)等のグラフの探索アルゴリズムについて学ぶ。

【キーワード】
頂点、エッジ、隣接リスト、隣接行列、深さ優先探索(DFS)、幅優先探索(BFS)
鈴木 一史
(放送大学准教授)
鈴木 一史
(放送大学准教授)
14 グラフの応用 最小全域木や有向無循環グラフについて学習する。そして、最小全域木を求めるプリム法の概要を理解する。最短経路問題を解くアルゴリズムには、どのようなものがあるか学習する。

【キーワード】
最小全域木、MST、有向無循環グラフ、DAG、プリム法、クラスカル法、最短経路問題、ダイクストラ法
鈴木 一史
(放送大学准教授)
鈴木 一史
(放送大学准教授)
15 データ構造の選択とプログラミング 基本的なデータ構造の仕組みと特徴を理解する。そして、与えられた問題に対し、適切なデータ構造を選択できるようにする。代表的なソーティング手法の長所と短所について理解する。グラフのアルゴリズムに関する計算量を比較する。

【キーワード】
プログラミング、データ構造、計算量、ソーティング、オブジェクト指向、ソフトウェアエンジニアリング、抽象データ、デバッグ、最適化
鈴木 一史
(放送大学准教授)
鈴木 一史
(放送大学准教授)
このページのトップへ本文ここまで
授業科目案内 教養学部 放送大学