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

科目基礎情報

学校 沼津工業高等専門学校 開講年度 2017
授業科目 データ構造とアルゴリズム
科目番号 0003 科目区分 専門 / 必修
授業形態 授業 単位の種別と単位数 履修単位: 2
開設学科 制御情報工学科 対象学年 3
開設期 通年 週時間数 2
教科書/教材 新・明解C言語によるアルゴリズムとデータ構造(柴田/辻,ソフトバンククリエイティブ)
担当教員 鈴木 康人

到達目標

前期ではC言語の機能である構造体や自己参照構造体、関数、ファイル分割を利用した簡単なプログラムが作成でき、gdbデバッガを利用して変数の値等をトレースできることを目標とする。後期では構造化プログラミングとデータ構造について復習した後、様々なアルゴリズムへの適用方法を学習し、C言語を用いてソートや探索などのプログラムに適用できることを目標とする。具体的には
1.構造体、関数を使用したソースコードを読み、動作を理解することができる。
2.ファイル分割に関わるヘッダファイルの役割を理解できる。
3.デバッガをマニュアル等を読みながら扱うことができる。
4.構造化プログラミングの3構造と各構文について説明でき,配列,リスト構造,スタック,キュー,木構造などデータ構造について説明できる。
5.ソートにおいて単純交換・選択・挿入ソートに加えシェル・クイック・マージ・ヒープ・度数ソートについて説明できる。
6.探索において線形探索,2分探索,ハッシュ法,チェイン法,オープンアドレス法,2分探索木について説明できる。

ルーブリック

理想的な到達レベルの目安標準的な到達レベルの目安未到達レベルの目安
評価項目1□自己参照構造体、関数を使用したコードを作成できる□構造体、関数を使用したコードを読み、動作を理解することができる□構造体、関数を使用したコードを与えられても、動作を理解できない。
評価項目2□ヘッダファイルの重複読み込みを防止するプリプロセス命令を使用してコードを作成できる□ファイル分割に関わるヘッダファイルの役割を理解できる。□ファイル分割に関わるヘッダファイルの役割を説明できない。
評価項目3□デバッガを利用して様々なコードの変数の遷移をトレースできる。□デバッガをマニュアル等を読みながら扱うことができる。□デバッガを扱うことができない。
評価項目4□構造化プログラミングの3構造と各構文について正確に説明できる □配列,リスト構造,スタック,キュー,木構造などデータ構造について正確に説明できる。□構造化プログラミングの3構造と各構文について概ね説明できる □配列,リスト構造,スタック,キュー,木構造などデータ構造について概ね説明できる。□構造化プログラミングの3構造と各構文について説明できない。 □配列,リスト構造,スタック,キュー,木構造などデータ構造について説明できない。
評価項目5□ソートにおいて単純交換・選択・挿入ソートに加えシェル・クイック・マージ・ヒープ・度数ソートについて正確に説明できる。□ソートにおいて単純交換・選択・挿入ソートに加えシェル・クイック・マージ・ヒープ・度数ソートについて概ね説明できる。□ソートにおいて単純交換・選択・挿入ソートに加えシェル・クイック・マージ・ヒープ・度数ソートについて説明できない。
評価項目6□探索において線形探索,2分探索,ハッシュ法,チェイン法,オープンアドレス法,2分探索木について正確に説明できる。□探索において線形探索,2分探索,ハッシュ法,チェイン法,オープンアドレス法,2分探索木について概ね説明できる。□探索において線形探索,2分探索,ハッシュ法,チェイン法,オープンアドレス法,2分探索木について説明できない。

学科の到達目標項目との関係

【本校学習・教育目標(本科のみ)】 3 説明 閉じる

教育方法等

概要:
コンピュータにおけるデータの処理方法はデータの保存形式に大きく左右される。現在のプログラミングで基礎となるデータの保存形式とその処理方法--データ構造とアルゴリズムはある程度確立しており、それについて学習することはプログラミングを学ぶ上で欠かせない事項である。
前期はC言語の高度な機能--ポインタ、構造体、関数呼び出し、ファイル分割とデバッガによる実行状況の確認方法を学習する。後期は構造化プログラミングとデータ構造の基本を学び、様々なアルゴルズムへの各種データ構造の適用例について学習する。
授業の進め方・方法:
前期は例題の入力と実行確認、指定された実技を達成できたかどうかをルーブリック形式の評価シートにて記録、集計し成績評価とする。前期は実技試験により年間成績の50%分を評価する。
後期は講義形式でデータ構造やソートやヒープなどのアルゴリズムについて詳しく説明する。講義中には説明後に例を示し、学生を指名して答えてもらうインタラクティブな内容を多く取り入れる。講義の最後に二分探索木のプログラムについて演習を行い、レポートとして提出する。
注意点:
1.試験や課題レポート等は、JABEE 、大学評価・学位授与機構、文部科学省の教育実施検査に使用することがあります。
2.授業参観される教員は当該授業が行われる少なくとも1週間前に教科目担当教員へ連絡してください。
3.前期は例題の入力と実行確認、指定された実技を達成できたかどうかをルーブリック形式の評価シートにて記録、集計し成績評価とする。前期は実技試験により年間成績の50%分を評価する。
4.前期中、実技試験による到達目標を指定された期日までに達成できない場合補習時間を設け筆記による達成度調査に切り替える。
5.後期は試験を30%、レポートを20%として50%分を評価する。

授業計画

授業内容 週ごとの到達目標
前期
1stQ
1週 ガイダンス 端末によるファイル操作、エディタの起動、コンパイル方法の確認、適切に変数名を設定できる
2週 キャスト、デバッガ キャストによる型変換の効果を理解し利用できる、デバッガにより変数の値をトレースできる
3週 配列(1) 整数配列と実数配列上の処理ができる、整数配列と実数配列の初期値設定ができる
4週 配列(2) 文字配列による文字列の実現、ヌル文字の効果を理解できる、文字配列の初期値を設定できる
5週 ポインタ変数(1) ポインタ変数宣言ができる、ポインタ変数に何が代入されているか理解できる、ポインタ変数を開放できる
6週 ポインタ変数(2) 動的記憶確保ができる、ポインタ変数と配列変数の表現形式を了解し利用できる
7週 構造体とファイル分割(1) 構造体を宣言できる、構造体の型について説明できる、構造体のメンバ変数にアクセスできる
8週 構造体とファイル分割(2) ファイル分割ができる、ヘッダファイルを適切に利用できる
2ndQ
9週 共用体と自己参照構造体(1) 共用体を宣言できる、共用体を利用できる
10週 共用体と自己参照構造体(2) 自己参照構造体を宣言できる、アロー演算子を利用できる
11週 関数(1) 関数プロトタイプ宣言ができる
12週 関数(2) 関数に適切な変数を渡し返り値を受け取ることができる
13週 関数(3) 再帰関数を定義できる
14週 ファイル入出力(1) ファイル入出力を行える
15週 ファイル入出力(2) エラーハンドリングの意義を理解できる、makeを利用できる
16週
後期
3rdQ
1週 基本的なデータ構造 配列、多次元配列、構造体、スタック、キュー、リスト、リングリスト、ツリーの概要を説明できる
2週 構造化プログラミング 構成要素(順次/反復/分岐)とインデントについて説明できる
3週 (演習) 演習により、プログラム構造を理解する
4週 スタックとキュー スタックとキューについて説明できる
5週 (演習) 演習により、スタックとキューを理解する
6週 後期中間試験
7週 探索 探索アルゴリズの基本について理解する
8週 線形探索と2分探索とハッシュについて理解する
4thQ
9週 ソート 単純変換ソート、選択ソート、挿入ソートについて理解する
10週 クイックソート、マージソートについて理解する
11週 ヒープソート、度数ソートについて理解する
12週 木構造 木構造、2分木と2分探索木について理解する
13週 総合演習 二分探索木のプログラム構造を理解する
14週 横探索のプログラムを作成する
15週 後期末試験
16週 後期試験の解説 (演習と試験解説)

モデルコアカリキュラムの学習内容と到達目標

分類分野学習内容学習内容の到達目標到達レベル授業週

評価割合

試験実技試験相互評価態度ポートフォリオその他合計
総合評価割合30700000100
基礎的能力050000050
専門的能力300000030
分野横断的能力020000020