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

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

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

講義概要

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

開設年度
2018年度
科目区分
コース科目(情報コース(専門科目))※共用科目(自然と環境)
〔2009年度~2015年度〕専門科目(情報コース)※共用科目(自然と環境)
〔2008年度以前〕専門科目(情報コース)※共用科目(自然の理解)
科目コード
1570277
単位数
2単位
単位認定試験
試験日・時限
2018年度 第1学期:2018年8月5日(日曜)6時限(15時35分~16時25分)
単位認定試験
平均点
備考
「データ構造とプログラミング('13)」の単位修得者は履修不可
このページのトップへ本文ここまで

授業の目標

・データ構造の基礎について学ぶ。
・データ構造を理解し、ソフトウェア作成に応用できるようにする。

履修上の留意点

・計算機科学の入門的科目を履修しており、初歩的なプログラミング(変数、データ型、演算、条件分岐、繰り返し処理、関数、ファイル等)について知っていることが望ましい。
・自分でコンパイラのインストールやプログラミング開発環境の設定をPCにできることが望ましい。
・「データ構造とプログラミング('13)」の単位修得者は履修不可。

シラバス

テーマ 内容 執筆担当講師名
(所属・職名)
放送担当講師名
(所属・職名)
1 配列 基本的な配列の仕組みと構造について学習する。また、多次元の配列や構造体を要素にもつ応用的な配列構造について理解する。さらに、配列へのデータの挿入、削除、探索などの基本的な操作や計算量などについて学ぶ。

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

【キーワード】
スタック、プッシュ、ポップ、スタックの仕組み、スタックの実装、文字列反転、逆ポーランド記法
鈴木 一史
(放送大学准教授)
鈴木 一史
(放送大学准教授)
3 キュー 基本的なデータ構造であるキューの仕組みについて学習する。また、キューに必要な操作や特徴、そして、キューがどのように使われるのか応用例やC言語での実装について学ぶ。

【キーワード】
キュー、エンキュー、デキュー、キューの仕組み、キューの実装、優先度付きキュー
鈴木 一史
(放送大学准教授)
鈴木 一史
(放送大学准教授)
4 連結リスト 連結リストの仕組みについて学習する。連結リストに対するデータの探索、挿入、削除等の基本的な操作について学ぶ。また、連結リストと配列との操作効率の違いについて学習する。

【キーワード】
連結リストのしくみ、挿入、削除、探索、計算量、配列との比較
鈴木 一史
(放送大学准教授)
鈴木 一史
(放送大学准教授)
5 連結リストの応用 連結リストを用いたスタックとキューのデータ構造の実装例について学習する。また、連結リスト(片方向連結リスト)の構造を拡張した、双方向連結リスト、環状連結リスト、環状双方向連結リスト等について学ぶ。そして、これらのリスト構造における利点や欠点、連結リストへのデータの挿入や削除の計算量について考える。

【キーワード】
連結リスト、スタックとキューの実装、双方向連結リスト、環状連結リスト、双方向環状連結リスト、優先度付きキュー
鈴木 一史
(放送大学准教授)
鈴木 一史
(放送大学准教授)
6 バイナリサーチツリー ツリー構造とツリーに関する用語について学ぶ。特に基本的なデータ構造であるバイナリツリーとバイナリサーチツリーの特徴や性質について学習する。バイナリサーチツリーに対する走査(行きがけ順走査、通りがけ順走査、帰りがけ順走査)の仕組みとコード例について学ぶ。

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

【キーワード】
バイナリサーチツリー、探索、挿入、削除、順序内前任者、順序内後継者、計算量
鈴木 一史
(放送大学准教授)
鈴木 一史
(放送大学准教授)
8 ツリーの応用 バイナリサーチツリーに対する基本的な操作として、ノードの探索、ノードの挿入、ノードの削除、ツリーの走査などがある。この回では、その他の応用的な操作について考える。また、バイナリサーチツリーの問題点について考える。そして、平衡木の仕組みと性質について学習する。

【キーワード】
ツリー削除、ツリーのパス、ノード反転、平衡木、計算量、AVLツリー
鈴木 一史
(放送大学准教授)
鈴木 一史
(放送大学准教授)
9 ハッシュテーブルとオープンアドレス法 ハッシュ法はデータの数に関係なく定数計算量で、データの探索、挿入、削除を行うことができる最速の手法である。この回では、ハッシュ関数、ハッシュ値の衝突について学ぶ。また、オープンアドレス法の特徴について学習する。

【キーワード】
ハッシュ法、ハッシュ関数、衝突、オープンアドレス法、線形探査、平方探査、ダブルハッシング
鈴木 一史
(放送大学准教授)
鈴木 一史
(放送大学准教授)
10 ハッシュテーブルと連鎖法 ハッシュ法はデータの数に関係なく定数計算量で、データの探索、挿入、削除を行うことができる最速の手法である。この回では、ハッシュ関数、ハッシュ値の衝突について学ぶ。連鎖法の特徴について学習する。また、文字列データからのハッシュ値計算について考える。

【キーワード】
ハッシュ法、ハッシュ関数、ハッシュ値の衝突、連鎖法、文字列データとハッシュ値
鈴木 一史
(放送大学准教授)
鈴木 一史
(放送大学准教授)
11 再帰 再帰プログラムは自分自身を繰り返し呼び出し、そのたびに異なる引数を渡していく。この回では、再帰の仕組みと様々な再帰プログラムの例について学ぶ。また、再帰とスタックの関係、末尾再帰について学習する。

【キーワード】
再帰、再帰呼び出し、再帰とスタック、階乗、フィボナッチ数、GCD、フラクタル図形、末尾再帰、反復プログラム
鈴木 一史
(放送大学准教授)
鈴木 一史
(放送大学准教授)
12 ソーティング バブルソート、選択ソート、挿入ソートなどの基本的なソーティングのアルゴリズムについて学び、これらのアルゴリズムのC言語によるコード例について学習する。また、これらのソーティングアルゴリズムの計算量や特徴について考える。

【キーワード】
整列、昇順、降順、安定なソート、バブルソート、選択ソート、挿入ソート、計算量
鈴木 一史
(放送大学准教授)
鈴木 一史
(放送大学准教授)
13 ソーティングの応用 高速なソーティングの例として、クイックソート、マージソートについて学習する。クイックソートやマージソートは、再帰プログラムで実現することができる。C言語によるクイックソートやマージソートの実装について学ぶ。また、C言語のqsort関数の利用例について考える。

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

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

【キーワード】
頂点、辺、隣接、パス、隣接リスト、隣接行列、深さ優先探索(DFS)、幅優先探索(BFS)
鈴木 一史
(放送大学准教授)
鈴木 一史
(放送大学准教授)
このページのトップへ本文ここまで
授業科目案内 教養学部 放送大学