|
専門教育課程 情報工学科
| 授業科目区分 |
科目名 |
単位数 |
科目コード |
開講時期 |
履修方法 |
専門教育課程
専門科目
専門 |
データ構造とアルゴリズム
Data Structure and Algorithms
|
2 |
E508-01 |
2024年度
３期（前学期）
|
修学規程第4条を参照 |
| 授業科目の学習・教育目標 |
| キーワード |
学習・教育目標 |
| 1.データ構造
2.アルゴリズム
|
良いプログラムを書くためには，データ構造とアルゴリズムの知識が必要である．
本科目の目標は以下の２つである．
１．情報工学において基礎知識となるデータ構造とアルゴリズムを学ぶ．
２．解こうとする問題に対して適切なデータ構造およびアルゴリズムを選択できる． |
| 授業の概要および学習上の助言 |
| データ構造はデータを計算機の中で格納する形式であり，アルゴリズムはプログラムを抽象化した「問題を解く手順」である
．良いプログラムを書くためには良いデータ構造と良いアルゴリズムを使用する必要があるため本授業で学ぶ．ある問題を解
くには複数のデータ構造およびアルゴリズムが使用可能であり，それらを比較する代表的な指標である時間計算量を本授業で
学び，実際に複数のアルゴリズムを時間計算量で比較しながら理解を深める．
授業明細表に示す学習内容の順序は目安であり，詳細は担当教員の指示に従うこと．少なくとも以下の内容を扱う．
整列（ソートとも呼ばれる）のアルゴリズム：基礎的な手法および高度な手法（マージソートとクイックソートを含む）
基本的なデータ構造：配列，リスト，スタック，キュー，木，グラフ
グラフのアルゴリズム：探索
担当教員の判断で他の内容が追加される場合がある．
総合学習の内容と時期は担当教員が独自に設定するので指示に従うこと．
レポート，小テストおよび達成度確認試験の内容，回数および時期も担当教員の指示に従うこと． |
| 教科書および参考書・リザーブドブック |
| 教科書：アルゴリズムとデータ構造（第２版）[森北出版]
参考書：指定なし
ﾘｻﾞｰﾌﾞﾄﾞﾌﾞｯｸ：指定なし |
| 履修に必要な予備知識や技能 |
| 数学の知識が必要である．具体的には不等式，多項式関数，指数関数，対数関数，数列，漸化式をおおむね理解していること
． |
| 学生が達成すべき行動目標 |
| No. |
学科教育目標
（記号表記） |
|
| ① |
J-N |
各種データ構造を十分理解し、適切に使いこなせる。 |
| ② |
J-N |
各種アルゴリズムを十分理解し、適切に使いこなせる。 |
| ③ |
L,M |
計算量の観点からアルゴリズムの良し悪しを見分けることができる。 |
| ④ |
J,L-N |
問題に対して、最適なアルゴリズムとデータ構造を選択できる。 |
| ⑤ |
|
|
| ⑥ |
|
|
| 達成度評価 |
|
|
評価方法 |
| 総合評価割合 |
40 |
40 |
20 |
0 |
0 |
0 |
0 |
100 |
| 指標と評価割合 |
総合評価割合 |
40 |
40 |
20 |
0 |
0 |
0 |
0 |
100 |
| 総合力指標 |
10 |
10 |
0 |
0 |
0 |
0 |
0 |
20 |
| 25 |
25 |
5 |
0 |
0 |
0 |
0 |
55 |
| 0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
| 5 |
5 |
10 |
0 |
0 |
0 |
0 |
20 |
| 0 |
0 |
5 |
0 |
0 |
0 |
0 |
5 |
| 評価の要点 |
| 評価方法 |
行動目標 |
評価の実施方法と注意点 |
| 試験 |
① |
レ |
各種データ構造およびアルゴリズムを理解しているかどうか，および計算量の観点からアルゴリズムを比
較できるかどうかを確認する． |
| ② |
レ |
| ③ |
レ |
| ④ |
レ |
| ⑤ |
|
| ⑥ |
|
クイズ
小テスト |
① |
レ |
各種データ構造およびアルゴリズムを理解しているかどうか，および計算量の観点からアルゴリズムを比
較できるかどうかを確認する． |
| ② |
レ |
| ③ |
レ |
| ④ |
レ |
| ⑤ |
|
| ⑥ |
|
| レポート |
① |
レ |
各種データ構造およびアルゴリズムを理解しているかどうか，および計算量の観点からアルゴリズムを比
較できるかどうかを確認する．担当教員によってはプログラムの作成および実行を行う場合がある． |
| ② |
レ |
| ③ |
レ |
| ④ |
レ |
| ⑤ |
|
| ⑥ |
|
成果発表
(口頭・実技) |
① |
|
|
| ② |
|
| ③ |
|
| ④ |
|
| ⑤ |
|
| ⑥ |
|
| 作品 |
① |
|
|
| ② |
|
| ③ |
|
| ④ |
|
| ⑤ |
|
| ⑥ |
|
| ポートフォリオ |
① |
|
|
| ② |
|
| ③ |
|
| ④ |
|
| ⑤ |
|
| ⑥ |
|
| その他 |
① |
|
|
| ② |
|
| ③ |
|
| ④ |
|
| ⑤ |
|
| ⑥ |
|
| 具体的な達成の目安 |
| 理想的な達成レベルの目安 |
標準的な達成レベルの目安 |
| データの並べ替えや探索などを効率的に行うのに適したアルゴ
リズムと，そのためのデータ構造について完全に説明できる．
また，それぞれのアルゴリズムにおける計算量を論理的に評価
することができる． |
データの並べ替えや探索などを効率的に行うアルゴリズムとそ
のためのデータ構造に対し，具体的な動作例を説明できる．そ
れぞれのアルゴリズムに対する計算量を大まかに評価すること
ができる． |
| 授業明細 |
| 回数 |
学習内容 |
授業の運営方法 |
学習課題 予習・復習 |
時間：分※ |
| 第1週 |
はじめに（科目の概要，授業の進め方，予習・復習・
評価方法の説明）
計算量 |
講義（演習を含む） |
復習（詳細は授業時に指定される
。） |
200 |
| 第2週 |
アルゴリズムの基本データ構造（配列、リスト、スタ
ックとキュー） |
講義（演習を含む） |
予習
復習
いずれも詳細は授業時に指定され
る。 |
60
140 |
| 第3週 |
アルゴリズムにおける基本概念（木） |
講義（演習を含む） |
予習
復習
いずれも詳細は授業時に指定され
る。 |
60
140 |
| 第4週 |
データの探索 |
講義（演習を含む） |
予習
復習
いずれも詳細は授業時に指定され
る。 |
60
140 |
| 第5週 |
ソートアルゴリズム１（基本的なアルゴリズム） |
講義（演習を含む） |
予習
復習
いずれも詳細は授業時に指定され
る。 |
60
140 |
| 第6週 |
ソートアルゴリズム２（クイックソート、マージソー
ト、性能比較） |
講義（演習を含む） |
予習
復習
いずれも詳細は授業時に指定され
る。 |
60
140 |
| 第7週 |
総合演習１ |
講義（演習を含む） |
予習
復習
いずれも詳細は授業時に指定され
る。 |
60
140 |
| 第8週 |
基本的なデータ構造（グラフ）、小テスト |
講義（演習を含む） |
予習
復習
いずれも詳細は授業時に指定され
る。 |
60
140 |
| 第9週 |
グラフの探索（幅優先探索と深さ優先探索） |
講義（演習を含む） |
予習
復習
いずれも詳細は授業時に指定され
る。 |
60
140 |
| 第10週 |
グラフの最短経路問題 |
講義（演習を含む） |
予習
復習
いずれも詳細は授業時に指定され
る。 |
60
140 |
| 第11週 |
アルゴリズムの設計手法 |
講義（演習を含む） |
予習
復習
いずれも詳細は授業時に指定され
る。 |
60
140 |
| 第12週 |
アルゴリズムの応用、補足 |
講義（演習を含む） |
予習
復習
いずれも詳細は授業時に指定され
る。 |
60
140 |
| 第13週 |
総合演習２ |
講義（演習を含む） |
予習
復習
いずれも詳細は授業時に指定され
る。 |
60
140 |
| 第14週 |
アルゴリズムの将来展望、達成度確認試験 |
講義（演習を含む） |
予習
復習
いずれも詳細は授業時に指定され
る。 |
60
140 |
| 第15週 |
アルゴリズムとデータ構造のまとめ、総復習 |
講義 |
予習（これまでの復習と達成度確
認試験の見直し） |
200 |
|
一般に、授業あるいは課外での学習では：「知識などを取り込む」→「知識などをいろいろな角度から、場合によってはチーム活動として、考え、推論し、創造する」→「修得した内容を表現、発表、伝達する」→「総合的に評価を受ける、ＧｏｏｄＷｏｒｋ！」：のようなプロセス（一部あるいは全体）を繰り返し行いながら、応用力のある知識やスキルを身につけていくことが重要です。このような学習プロセスを大事に行動してください。
※学習課題の時間欄には、指定された学習課題に要する標準的な時間を記載してあります。日々の自学自習時間全体としては、各授業に応じた時間（例えば2単位科目の場合、予習2時間・復習2時間／週）を取るよう努めてください。詳しくは教員の指導に従って下さい。