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

科目基礎情報

学校 旭川工業高等専門学校 開講年度 令和03年度 (2021年度)
授業科目 アルゴリズムとデータ構造
科目番号 0014 科目区分 専門 / 必修
授業形態 講義 単位の種別と単位数 履修単位: 2
開設学科 システム制御情報工学科 対象学年 3
開設期 通年 週時間数 2
教科書/教材 入門ソフトウェアシリーズ1 C言語(河西朝雄著,ナツメ社)
担当教員 戸村 豊明

目的・到達目標

1. 与えられた問題を解決するためのソースプログラムを C 言語により記述し,コンパイル・リンク・実行できる。
2. 基本的な整列・探索アルゴリズムが問題を解決してゆく過程を説明できる。
3. リスト構造,スタック,キューといった基本的なデータ構造の概念と操作を説明できる。

ルーブリック

理想的な到達レベルの目安標準的な到達レベルの目安未到達レベルの目安
評価項目1与えられた複雑な問題を解決するための無駄のないソースプログラムをC言語により記述し,コンパイル・リンク・実行できる.与えられた単純な問題を解決するためのソースプログラムをC言語により記述し,コンパイル・リンク・実行できる.与えられた単純な問題を解決するためのソースプログラムをC言語により記述できない.
評価項目2基本的な整列・探索アルゴリズムが問題を解決してゆく過程を,図と文章でわかりやすく説明し,アルゴリズムをソースプログラムに記述できる.基本的な整列・探索アルゴリズムが問題を解決してゆく過程を,図と文章で説明できる.基本的な整列・探索アルゴリズムが問題を解決してゆく過程を説明できない.
評価項目3リスト構造,スタック,キューといった基本的なデータ構造の概念と操作を図と文章でわかりやすく説明し,これらをソースプログラムに記述できる.リスト構造,スタック,キューといった基本的なデータ構造の概念と操作を図と文章で説明できる.リスト構造,スタック,キューといった基本的なデータ構造の概念と操作を説明できない.

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

学習・教育到達度目標 システム制御情報工学科の教育目標 ① 説明 閉じる
学習・教育到達度目標 本科の教育目標 ③ 説明 閉じる

教育方法等

概要:
開発ツールとして,Linux 上で動作する C コンパイラ(gcc)を使用する。前期では,C 言語を用いたより高度なプログラミングと,これを応用した基本的なデータ構造を学ぶ。後期では,CAD/CAM 技術の基礎となる平面図形の表現方法や計算幾何を 学び,これらを C 言語で記述する。最後に,基本的な整列・探索アルゴリズムを学び,計算幾何へこれらを応用する。
授業の進め方と授業内容・方法:
教科書と配布プリントを用いて内容を説明した後にプログラミングや演習を行い,その結果をレポートとして提出する.
注意点:
2 年生の情報処理で学んだ C 言語の基礎(構文や主要なライブラリ関数の使い方など)を充分理解しておくこと。プログラムを書く時は,単純な論理を一つずつ丁寧に積み重ねることを心がけること。目的に応じたプログラムを自分自身で書けるように なることを目標として,小テストを適宜実施するので,復習を欠かさないこと。

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

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

授業計画

授業内容・方法 週ごとの到達目標
前期
1stQ
1週 C言語の復習 C言語の定数,変数,データ型を説明できる.C言語で演算子を用いたプログラムを作成できる.
2週 ファイル入出力 数値や文字列を取り扱うために,バイナリファイルやテキストファイルを読み書きする方法がわかる.
3週 分割コンパイル 大きなプログラムを機能別に複数のファイルに分割することで,可読性の高いプログラムにする方法がわかる.
4週 分割コンパイル 大きなプログラムを機能別に複数のファイルに分割することで,可読性の高いプログラムにする方法がわかる.
5週 構造体 構造体の宣言方法,構造体のポインタの利用方法,構造体の1次元配列および2次元配列の利用方法がわかる.
6週 構造体 構造体の宣言方法,構造体のポインタの利用方法,構造体の1次元配列および2次元配列の利用方法がわかる.
7週 構造体
次週,中間試験を実施する.
構造体の宣言方法,構造体のポインタの利用方法,構造体の1次元配列および2次元配列の利用方法がわかる.
8週 答案返却&解説 学んだ知識の再確認&修正ができる.
2ndQ
9週 動的メモリ確保 必要に応じて,変数や配列の記憶領域を動的に確保・解放する方法がわかる.
10週 動的メモリ確保 必要に応じて,変数や配列の記憶領域を動的に確保・解放する方法がわかる.
11週 線形リスト 自己参照型構造体を応用して,基本的なデータ構造である線形リストを表現できる.
12週 線形リスト 自己参照型構造体を応用して,基本的なデータ構造である線形リストを表現できる.
13週 スタックとキュー 自己参照型構造体を応用して,基本的なデータ構造であるスタックとキューを表現できる.
14週 スタックとキュー 自己参照型構造体を応用して,基本的なデータ構造であるスタックとキューを表現できる.
15週 ツリー 自己参照型構造体を応用して,基本的なデータ構造であるツリーを表現できる.
16週 期末試験 これまで学んだ内容について,試験を通じて確認する.
後期
3rdQ
1週 ベクトル ベクトルに関する基本的な法則と演算を説明できる.
2週 ベクトル
ベクトルに関する基本的な法則と演算を説明できる.
3週 直線 直線の数学的表現や直線間の交点計算方法を説明できる.
4週 直線 直線の数学的表現や直線間の交点計算方法を説明できる.
5週 円と楕円の数学的表現や円と直線の交点計算方法を説明できる.
6週 円と楕円の数学的表現や円と直線の交点計算方法を説明できる.
7週 空間図形
次週,中間試験を実施する.
空間内の直線・平面・球の方程式を求めることができる.
8週 整列アルゴリズム 単純ソート,選択ソート,バブルソート,挿入ソートといった基本的なデータ整列アルゴリズムを説明できる.
4thQ
9週 整列アルゴリズム 単純ソート,選択ソート,バブルソート,挿入ソートといった基本的なデータ整列アルゴリズムを説明できる.
10週 探索アルゴリズム 線形探索,2分探索といった基本的なデータ探索アルゴリズムを説明できる.
11週 探索アルゴリズム 線形探索,2分探索といった基本的なデータ探索アルゴリズムを説明できる.
12週 探索アルゴリズム 線形探索,2分探索といった基本的なデータ探索アルゴリズムを説明できる.
13週 計算幾何への応用 凸包計算や三角形分割といった問題に対して,アルゴリズムとデータ構造を応用できる.
14週 計算幾何への応用 凸包計算や三角形分割といった問題に対して,アルゴリズムとデータ構造を応用できる.
15週 要求仕様に基づくソフトウェア開発 要求仕様に従って、標準的な手法により実行効率を考慮したプログラムを設計・実装できる.
16週 学年末試験 これまで学んだ内容について,試験を通じて確認する.

評価割合

試験発表相互評価態度ポートフォリオその他小テストレポート合計
総合評価割合60000002020100
基礎的能力4500000151575
専門的能力15000005525
分野横断的能力000000000