到達目標
同一の問題に対し，選択したデータ構造によってアルゴリズムが変化しうることを理解する。
リスト構造，スタック，キューなどの基本的なデータ構造の概念と操作を説明できる。
整列、探索など、基本的なアルゴリズムについて説明できる。
有限オートマトンを説明できる。
形式文法を説明できる。
データベースの設計・操作に必要な基礎知識を理解し、説明できる。
ルーブリック
| 理想的な到達レベルの目安 | 標準的な到達レベルの目安 | 未到達レベルの目安 |
| 評価項目1 | 同一の問題に対し，選択したデータ構造によってアルゴリズムが変化しうることを説明できる。 | 同一の問題に対し，選択したデータ構造によってアルゴリズムが変化しうることが理解できる。 | 同一の問題に対し，選択したデータ構造によってアルゴリズムが変化しうることが理解できない。 |
| 評価項目2 | リスト構造，スタック，キューなどの基本的なデータ構造の概念と操作を説明できる。 | リスト構造，スタック，キューなどの基本的なデータ構造の概念と操作を理解できる。 | リスト構造，スタック，キューなどの基本的なデータ構造の概念と操作を理解できない。 |
| 評価項目3 | 整列、探索など、基本的なアルゴリズムについて説明できる。 | 整列、探索など、基本的なアルゴリズムについて理解できる。 | 整列、探索など、基本的なアルゴリズムについて理解できない。 |
| 評価項目4 | 有限オートマトンを説明できる。 | 有限オートマトンを理解できる。 | 有限オートマトンを理解できない。 |
| 評価項目5 | 形式文法を説明できる。 | 形式文法を理解できる。 | 形式文法を理解できない。 |
| 評価項目6 | データベースの設計・操作に必要な基礎知識を説明できる。
| データベースの設計・操作に必要な基礎知識を理解できる。 | データベースの設計・操作に必要な基礎知識を理解できない。 |
学科の到達目標項目との関係
(D) 専門分野の知識と情報技術を身につける。
説明
閉じる
教育方法等
概要:
本授業の前半ではプログラムを作成する上で重要なアルゴリズムとデータ構造の関係について学習します。対象となるデータの性質から，適切な表現方法・アルゴリズムを選択できる能力を身につけます。
本授業の後半ではコンパイラ，文書解析，文字列のパターンマッチングなどの技術に用いられるオートマトンと形式言語を学習します。有限オートマトンの概念を理解し状態遷移図を適切に記述する能力，形式文法のクラスの階層構造について説明できる能力を身につけます。
また，データベースについても扱います。データベースシステムの種類，設計法，正規化，SQLを用いた基本的なデータ問合わせができる能力を身につけます。
授業の進め方・方法:
教科書および教員作成の教材を使った講義形式で行います。関連する授業科目に「アルゴリズム演習」があり，実際にプログラムを作成することで，データ構造とアルゴリズムの理解を深めることが重要です。
課題レポート20%，中間試験40%，期末試験40%で総合評価し，60点以上を合格とします。
注意点:
C言語によるプログラミングを理解できることが望ましい。データ構造は，プログラムにおけるデータの表現方法について学ぶ学問です。知識として理解するだけでなく，データ構造をプログラム上に実現することで理解を深めることが大切です。
事前・事後学習、オフィスアワー
この科目は学修単位科目のため，講義（30時間）＋自学自習（60時間）の前提とし，課題レポートの提出を課します。
また，データ構造，アルゴリズムの理解を深めるために３年次に履修した「プログラミング演習」の復習が必要です。
【オフィスアワー】 授業日 15:00～16:00
授業の属性・履修上の区分
授業計画
|
|
週 |
授業内容 |
週ごとの到達目標 |
| 後期 |
| 3rdQ |
| 1週 |
ガイダンス シラバス・授業の進め方の説明
アルゴリズムの基礎 |
シラバス，授業の進め方，コンテンツの利用方法を理解する。
アルゴリズムの概念を説明できる。
与えられたアルゴリズムが問題を解決していく過程を説明できる。
同一の問題に対し，それを解決できる複数のアルゴリズムが存在しうることを説明できる。
|
| 2週 |
アルゴリズムの評価基準
最良時間量，最悪時間量，平均時間計算量，領域計算量 |
アルゴリズムによって計算量が変わることを説明できる。
最悪時間計算量と平均時間計算量を説明できる。
アルゴリズムを時間計算量や領域計算量により比較・評価できる。
|
| 3週 |
基本データ構造
配列，構造体，スタック，キュー，連結リスト |
コンピュータ内部でデータを表現する方法(データ構造)にはバリエーションがあることを説明できる。
スタック，キュー，リストのデータ構造の概念と操作を説明できる。
|
| 4週 |
基本データ構造
木構造，木のなぞり
|
木構造に関する基本的な用語を説明できる。
先行順 ，中間順，後行順による木構造のデータ探索ができる。
|
| 5週 |
探索アルゴリズム
線形探索法，2分探索法，ハッシュ法 |
基本的な探索アルゴリズム（線形探索法，2分探索法，ハッシュ法）について説明できる。
同一の問題に対し，選択したデータ構造によってアルゴリズムが変化しうることを説明できる。
|
| 6週 |
整列アルゴリズム
挿入ソート，バブルソート，ヒープソート |
基本的な整列アルゴリズム（挿入ソート，バブルソート，ヒープソート）について説明できる。
時間計算量によってアルゴリズムを比較・評価できることを説明できる。
|
| 7週 |
整列アルゴリズム
クイックソート，マージソート |
基本的な整列アルゴリズム（クイックソート，マージソート）について説明できる。
|
| 8週 |
中間試験 |
|
| 4thQ |
| 9週 |
有限オートマトン
有限オートマトン，状態遷移図 |
オートマトンの概念について説明できる。
有限オートマトンの状態遷移図を記述できる。
|
| 10週 |
正規表現と有限オートマトンの関係
正規表現，有限オートマトン演習 |
正規表現の記法を適切に用いることができる。
正規表現と有限オートマトンの関係を説明できる。
|
| 11週 |
形式文法
正規文法，文脈自由文法，文法クラスによる階層構造 |
形式言語の概念について説明できる。
形式言語が制限の多さにしたがって分類されることを説明できる。
|
| 12週 |
データベースの種類
階層型データベース，網型データベース，関係データベース |
身の回りにあるデータベースの例を具体的に挙げることができる。
データベースのデータモデルに関する基本的な概念と特徴を説明できる。
|
| 13週 |
データベースの設計
概念設計，論理設計，物理設計，ER図 |
データベース設計法に関する基本的な概念を説明できる。
ER図を用いてデータどうしの関連を整理できる。
|
| 14週 |
正規化
非正規形，第１正規形，第２正規形，第３正規形
|
正規化の手順を非正規形から第３正規形まで順を追って説明できる。
|
| 15週 |
SQL言語
SELECT文，WHERE句，INNER JOIN句 |
SQL言語を用いて基本的なデータ問合わせを記述できる。
|
| 16週 |
期末試験 |
|
モデルコアカリキュラムの学習内容と到達目標
| 分類 | 分野 | 学習内容 | 学習内容の到達目標 | 到達レベル | 授業週 |
| 専門的能力 | 分野別の専門工学 | 情報系分野 | ソフトウェア | アルゴリズムの概念を説明できる。 | 4 | |
| 与えられたアルゴリズムが問題を解決していく過程を説明できる。 | 4 | |
| 同一の問題に対し、それを解決できる複数のアルゴリズムが存在しうることを説明できる。 | 4 | |
| 時間計算量によってアルゴリズムを比較・評価できることを説明できる。 | 4 | |
| 領域計算量などによってアルゴリズムを比較・評価できることを説明できる。 | 4 | |
| 整列、探索など、基本的なアルゴリズムについて説明できる。 | 4 | |
| コンピュータ内部でデータを表現する方法(データ構造)にはバリエーションがあることを説明できる。 | 4 | |
| 同一の問題に対し、選択したデータ構造によってアルゴリズムが変化しうることを説明できる。 | 4 | |
| リスト構造、スタック、キュー、木構造などの基本的なデータ構造の概念と操作を説明できる。 | 4 | |
| システムプログラム | 形式言語の概念について説明できる。 | 4 | |
| 形式言語が制限の多さにしたがって分類されることを説明できる。 | 4 | |
| オートマトンの概念について説明できる。 | 4 | |
| 正規表現と有限オートマトンの関係を説明できる。 | 4 | |
| その他の学習内容 | データモデル、データベース設計法に関する基本的な概念を説明できる。 | 4 | |
| データベース言語を用いて基本的なデータ問合わせを記述できる。 | 4 | |
評価割合
| 試験 | 発表 | 相互評価 | 態度 | ポートフォリオ | その他 | 合計 |
| 総合評価割合 | 80 | 0 | 0 | 0 | 0 | 20 | 100 |
| 基礎的能力 | 40 | 0 | 0 | 0 | 0 | 20 | 60 |
| 専門的能力 | 40 | 0 | 0 | 0 | 0 | 0 | 40 |