ソフトウエア科学Ⅰ

科目基礎情報

学校 佐世保工業高等専門学校 開講年度 令和02年度 (2020年度)
授業科目 ソフトウエア科学Ⅰ
科目番号 0049 科目区分 専門 / 必修
授業形態 講義 単位の種別と単位数 履修単位: 2
開設学科 電子制御工学科 対象学年 3
開設期 通年 週時間数 前期:2 後期:2
教科書/教材 C言語によるはじめてのアルゴリズム入門、河西朝雄、技術評論社
担当教員 中村 嘉男

目的・到達目標

1.アルゴリズムの効率(計算量)を理解できる。(A4)
2.基本整列法が理解でき、プログラム化できる。(A4)
3.2分探索法を理解でき、プログラム化できる。(A4)
4.再帰処理について理解でき、プログラム化できる。(A4)
5.リスト・木構造について理解でき、プログラム化できる。(A4)

ルーブリック

理想的な到達レベルの目安標準的な到達レベルの目安未到達レベルの目安
評価項目1 達成目標1アルゴリズムの効率(計算量)を理解できる。アルゴリズムの効率(計算量)大体理解できる。アルゴリズムの効率(計算量)を理解できない。
評価項目2 達成目標2基本整列法が理解でき、プログラム化できる。基本整列法がおおよそ理解でき、簡単なプログラムが作成できる。基本整列法が理解できず、プログラム化できない。
評価項目3 達成目標32分探索法を理解でき、プログラム化できる。2分探索法の考え方を大凡理解でき、簡単なプログラムが作成できる。2分探索法を理解できず、プログラム化できない。

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

教育方法等

概要:
C言語の上級コースとして、整列、探索などの基本アルゴリズムから始めて、リスト、木などのデータ構造とそのアルゴリズムにいたるまでを習得させる。その問題解決技術習得のため、C言語処理系による実習を行い、それらについてのレポートを課す。
授業の進め方と授業内容・方法:
予備知識:C言語の初級コースである1、2年次の情報処理をきちんと習得しておく必要がある。そのため、各自で復習しておくこと。 この科目は学習単位科目のため、事前・事後学習としてレポートやオンラインテスト等を実施します。
授業はICT1で行う。
授業形態:講義 およびセンターでの実習
学生が用意するもの:ノート、C言語によるアルゴリズム入門(技術評論社、河西朝雄)
注意点:
評価方法:定期の試験(4回)70%、課題レポートおよび確認テスト30%により評価、60点以上を合格とする。
自己学習の指針:授業内容を復習し、毎回配布する資料の課題を解くこと。また、プログラミング技術も理解しておくこと。

授業計画

授業内容・方法 週ごとの到達目標
前期
1stQ
1週 講義の目的、開発環境設定 開発環境の設定を行うことができる。
2週 C言語の復習(1) 演算子、制御構造 C言語の演算子、制御構造を理解し、利用できる。
3週 C言語の復習(2) 配列、関数、ポインタ C言語の配列、関数、ポインタを理解し、利用できる。
4週 アルゴリズムの効率(計算量)、設計、解析 アルゴリズムの効率を理解し、その優劣を判断できる。
5週 基礎アルゴリズム(1) 漸化式 漸化式を理解し、各種の式の計算ができる。
6週 基礎アルゴリズム(2) モンテカルロ法 モンテカルロ法を理解し、面積に応用計算できる。
7週 最大公約数(ユークリッド互除法) ユークリッド互除法を用いて、最大公約数を計算できる。
8週 中間試験
2ndQ
9週 整列アルゴリズム(1)
交換法・選択法
整列交換法・選択法を理解し、数列の整列に応用できる。
10週 整列アルゴリズム(2)
挿入法
整列挿入法の動作と高速化の原理を理解し、応用できる。
11週 整列アルゴリズム(3)
シェルソート
シェルソートの動作と高速化の原理を理解し、応用できる。
12週 整列アルゴリズム(4)
マージソート
マージソートの原理を理解し、応用できる。
13週 探索アルゴリズム(1)
逐次探索
逐次探索法を理解し、探索に応用できる。
14週 探索アルゴリズム(2)
番兵法
探索における番兵の効果を理解し、応用できる。
15週 探索アルゴリズム(3)
2分探索法
2分探索法の原理を理解し、実際の問題にに応用できる。
16週 期末試験
後期
3rdQ
1週 文字列探索アルゴリズム(1)単純法 文字列探索法の単純法を理解し、文字列探索に応用できる。
2週 文字列探索アルゴリズム(2)ボイヤ・ムーア法 文字列探索法の改良版ボイヤ・ムーア法を理解し、応用できる。
3週 文字列の置き換え 文字列の置き換えを理解し、実装できる。
4週 ハッシュ法と衝突 探索法のハッシュ法と衝突を理解し、文字列探索に応用できる。
5週 再帰処理の概要 再帰処理の考え方を理解し、再帰的な式の計算ができる。
6週 再帰解と非再帰解 いくつかの問題について再帰と非再帰による実装の得失を理解し応用できる。
7週 再帰版クイックソートの実装 再帰によるクイックソートを理解し整列に応用できる。
8週 中間試験
4thQ
9週 データ構造(1)
スタック、キュー
データ構造のスタック、キューを理解し,実装することができる.
10週 データ構造(2)
リスト構造
データ構造のリスト構造を理解し、簡単な挿入・削除ができる.
11週 データ構造(3)
リスト構造
データ構造のリスト構造を、応用することができる.
12週 逆ポーランド記法 逆ポーランド記法を理解し、式の計算に応用できる.
13週 木(1)
2分探索木
配列を用いた2分探索木を作成し、文字列の探索に応用できる。
14週 木(2)
2分探索木
2分探索木を動的に作成し、文字列探索に応用できる。
15週 木(3)
木のトラーバーサルとヒープ
再帰を用いた木のトラバーサルとヒープを理解できる。
16週 期末試験

評価割合

試験課題・確認テスト相互評価態度ポートフォリオその他合計
総合評価割合70300000100
基礎的能力0000000
専門的能力70300000100
分野横断的能力0000000