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

科目基礎情報

学校 東京工業高等専門学校 開講年度 令和03年度 (2021年度)
授業科目 アルゴリズムとデータ構造Ⅰ
科目番号 0097 科目区分 専門 / 必修
授業形態 講義 単位の種別と単位数 履修単位: 1
開設学科 情報工学科 対象学年 3
開設期 前期 週時間数 2
教科書/教材 Web教材使用
担当教員 坂井 良広

目的・到達目標

アルゴリズムの概念を理解し,与えられた問題に対してプログラムを作ることができる.
同じ問題に対して複数のアルゴリズムが存在することを理解し,計算量によってそれらを比較することができる.
基本的なデータ構造を理解し説明できる.またそれらのデータ構造を用いた基本的なプログラムを作ることができる.

ルーブリック

理想的な到達レベルの目安標準的な到達レベルの目安未到達レベルの目安
アルゴリズムの概念を理解し,与えられた問題に対してプログラムを作ることができるアルゴリズムの概念を理解し,自ら工夫してプログラムを作りあげることができる.アルゴリズムの概念を理解し,具体的に手順を示すとプログラムを作ることができるアルゴリズムの概念を理解していない.または,簡単なアルゴリズムを実現するプログラムが自力で書くことができない.
同じ問題に対して複数のアルゴリズムが存在することを理解し,計算量によってそれらを比較することができるアルゴリズムの計算量を数式で理論的に展開し,複数のアルゴリズムの比較を行うことができる.幾つかのアルゴリズムに関して計算量の議論を理解し,それによってアルゴリズムの比較が可能であることを理解している.計算量の概念が理解できない.または,計算量の議論の内容を理解することができない.
基本的なデータ構造を理解し説明できる.またそれらのデータ構造を用いた基本的なプログラムを作ることができる.様々なデータ構造を自ら理解し,それらのデータ構造を用いた簡単なプログラムを自力で作ることができる.与えられたデータ構造を理解し,それらを用いた簡単なプログラムを詳細な解説を見ながら作ることができる.与えられたデータ構造を理解することができない.または,基本的なデータ構造を用いた簡単なプログラムを作ることができない.

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

教育方法等

概要:
基礎事項として,ポインタおよび再帰について学習する。次にデータの表現方法や効率の良いアルゴリズムの実装能力を身につけるため,基本的かつ代表的なアルゴリズムとデータ構造について学習する.
授業の進め方と授業内容・方法:
原則として,毎回の授業で課題の説明を行い,残りの時間はプログラムを作成する演習時間とする.ただし,計算量の解説などの一部の項目では,座学中心の授業を行う.
注意点:
原則として授業の後半でC言語によるプログラミング演習を行なう.課題が授業時間内に終わらないことも予想されるので,自宅にプログラム開発環境を構築することが望ましい.また本科目の単位を修得するためには,全ての課題を期限内に提出することが必要条件となるので注意すること.

授業の属性・履修上の区分

アクティブラーニング
ICT 利用
遠隔授業対応
実務経験のある教員による授業

授業計画

授業内容・方法 週ごとの到達目標
前期
1stQ
1週 ガイダンス
データー構造・アルゴリズムとは
単純ソート
データ構造およびアルゴリズムの概要を理解できる
単純ソートのアルゴリズムとその計算量が理解できる。
2週 二分探索 二分探索のアルゴリズムを理解し、その計算量を求める過程が理解できる。
3週 再帰呼び出し 再帰呼び出しの概念を理解し、具体的な問題を再帰呼び出しによって実現する方法を考えることができる。
4週 クイックソート(1) クイックソートのアルゴリズムを理解し、再帰呼び出しによる実現が可能であることを理解する。
5週 クイックソート(2) クイックソートのアルゴリズムを理解し、その計算量の議論を理解することができる。
6週 選択ソート 選択ソートのアルゴリズムを理解し、実装することができる。
7週 挿入ソート 挿入ソートのアルゴリズムを理解し、実装することができる。
8週 試験問題解説・プログラミング演習 中間試験の解説を行うと共に、これまで説明してきた課題に取り組み課題をすべて完成させる。
2ndQ
9週 シェーカーソート シェーカーソートのアルゴリズムを理解し、実装することができる。また単純ソートとの違いを実験により確認できる。
10週 シェルソート シェルソートのアルゴリズムを理解し、実装することができる。
また挿入ソートとの違いを実験により確認できる。
11週 ヒープソート ヒープソートのアルゴリズムを理解し、実装することができる。
12週 マージソート マージソートのアルゴリズムを理解し、実装することができる。
13週 ポインタ(1) C言語におけるポインタの概念を理解し、関数にポインタ引数が渡されたときのメモリの様子を理解することができる。
14週 ポインタ(2) C言語におけるポインタの概念を理解し、メモリの動的割当や二次元ポインタの概念を理解できる。
15週
16週

評価割合

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