開講年度

2023年度

科目名

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

科目名（英語）授業情報(授業コード・クラス・授業形態)

開講学期

前期
授業種別

Exercises in Data Structure and Algorithm
A0400212 データ構造とアルゴリズム演習 [情報](再)[対面]

担当教員

田中 輝雄

単位数

1.0単位

曜日時限

キャンパス

八王子教室

月曜3限
1N-028講義室

学位授与の方針

1 基礎知識の修得 10 ％2 専門分野の知識・専門技術の修得 50 ％
3 汎用的問題解決力の修得 20 ％4 道徳的態度と社会性の修得 20 ％具体的な到達目標

データ構造がどのように有効に働き、アルゴリズムがどのように振舞うかを理解し説明できる。
データの性質、実施目的に合わせて、データ構造とアルゴリズムを選択できる。

受講にあたっての前提条件

授業の方法とねらい

AL・ICT活用

第１回

データ構造とアルゴリズム（講義）を受講することこの講義に専門科目として登録できるのは2019年度入学生のみです．2018年度以前の学生については自由科目としての登録となります．
この講義は『データ構造とアルゴリズム及び演習』の講義・演習と合同開催します．『データ構造とアルゴリズム及び演習』は２コマ連続で一体化した講義・演習を行いますので，本講義の履修では２コマに出席することを望みます．
そのため，『データ構造とアルゴリズム(再)』を併せて履修することを推奨します．
*******************
プログラムを作るときに必要になるのは，取り扱う「データ」をどのような「構造」で表現するかということ，および，それを取り扱う手順，すなわち「アルゴリズム」をどのように設計するかです．ここでは，『プログラム＝デー
タ構造＋アルゴリズム』という関係式が成り立ちます．本講義では，基本的な「データ構造とアルゴリズム」を理解することにより，プログラミング能力向上の一助とします．この講義では，プログラミングおよび演習１～４と合わせてC言語を前提としますが，データ構造とアルゴリズムの用語は，プログラミング言語とは独立に定義することを心がけます．言語に依存する場合については，その都度，説明を行います．
さらに，演習により理解を深めるとともに，基本的なアルゴリズムを実際に計算機上で動作させ実感していただきます．さらに，その動作の特徴を整理・分析することにより，実問題に対応するスキルを磨くことを目標とします．演
習では，各回に基本的な課題を実施するとともに３回程度の課題レポートを課すことを予定しています．
本演習はプログラミングが主目的ではありません．演習に必要なプログラムの基本部分は提供し，それを修正・追加することにより，いろいろなデータを用いた実験を行い，考察することを主眼とします．シームレスな実験環境の確保ならびにデータ構造とアルゴリズムを理解することに特化するために，実験環境はgoogle colaboratoryを用います．これにより，講義と同じ環境で演習室以外での予習・復習を可能とします．
言語は基本をCとし，グラフ化などのために一部Pythonを用います．ただし，Pythonの知識は前提とはしません．演
習を行う上で，必要な説明を行います．
講義及び演習を連続して教室にて行います．そのため，各自，PCを持参すること，また，PCは３時間余り稼働できるように十分充電をしておいてください．
e-ラーニング等ICTを活用した自主学習支援

授業形態

対面

事前学習

事前学習として，「アルゴリズム」という用語を調べておくこと．

授業内容

アルゴリズムとは：アルゴリズムの例，アルゴリズムの表現．

事後学習・事前学習

事後学習として，講義ノートおよび各自が作成した学習ノートを読み直し，さらに演習問題を解き直すことにより「アルゴリズムとは：アルゴリズムの例，アルゴリズムの表現」を再確認すること．
事前学習として，講義ノートを事前に読み，「データとデータ構造：配列，スタック，キュー」の用語，操作を調べておくこと．

第２回

授業形態
授業内容

演習

1時間

2時間

対面

データとデータ構造：配列，スタック，キュー．

事後学習・事前学習

事後学習として，講義ノートおよび各自が作成した学習ノートを読み直し，さらに演習問題を解き直すことにより「データとデータ構造：配列，スタック，キュー」を再確認すること．
事前学習として，講義ノートを事前に読み，「データ構造：連結リストとは，連結リスト，連結リストの宣言，連結リストの生成」の用語，操作を調べておくこと．

第3回

授業形態

対面

2時間

授業内容

データ構造：連結リストとは，連結リスト，連結リストの宣言，連結リストの生成．

事後学習・事前学習

事後学習として，講義ノートおよび各自が作成した学習ノートを読み直し，さらに演習問題を解き直すことにより「データ構造：連結リストとは，連結リスト，連結リストの宣言，連結リストの生成」を再確認すること．
事前学習として，講義ノートを事前に読み，「データ構造：連結リストの探索・挿入・削除，双方向リスト，環状リスト」の用語，操作を調べておくこと．

第４回

授業形態
授業内容

対面

データ構造：連結リストの探索・挿入・削除，双方向リスト，環状リスト．

事後学習・事前学習

事後学習，講義ノートおよび各自が作成した学習ノートを読み直し，さらに演習問題を解き直すことにより「データ構造：連結リストの探索・挿入・削除，双方向リスト，環状リスト」を再確認すること．
事前学習として，講義ノートを事前に読み，「データ構造：木とは，木の用語，木の走査，２分木，一般の木，木の操作」の用語，操作を調べておくこと．

第5回

授業形態
授業内容

データ構造：木とは，木の用語，木の走査，２分木，一般の木，木の操作．

事後学習・事前学習

第6回

授業形態

データ構造：グラフとは，グラフの用語，グラフの表現，グラフの探索，最短路問題．

事後学習・事前学習

第7回

授業形態

事後学習・事前学習

第8回

対面

事後学習，講義ノートおよび各自が作成した学習ノートを読み直し，さらに演習問題を解き直すことにより「アルゴリズムの評価：最大・平均計算量，計算量の漸近的評価」を再確認すること．

中間試験に向けての演習問題を配布するので各自で解くこと．模範解答は別途配布する．

事後学習・事前学習

中間試験に向けて，これまでの講義ノートおよび各自が作成した学習ノートを読み直し，さらに演習問題を解き直しておくこと．

第9回

授業形態
中間試験（授業内試験）

事後学習として，中間試験でできなかった問題を見直しておくこと．
事前学習として，講義ノートを事前に読み「ソーティング：バブルソート，シェーカソー
ト，選択ソート，挿入ソート，クイックソートなど」の用語，操作を調べておくこと．

第10回

授業形態

2時間

対面

ソーティング：バブルソート，シェーカソート，選択ソート，挿入ソート，クイックソートなど

事後学習・事前学習

事後学習，講義ノートおよび各自が作成した学習ノートを読み直し，さらに演習問題を解き直すことにより「ソーティング：バブルソート，シェーカソート，選択ソート，挿入ソート，クイックソートなど」を再確認すること．
事前学習として，講義ノートを事前に読み，「ソーティング：マージソート，バケットソー
ト，ヒープソートなど」の用語，操作を調べておくこと．

第11回

授業形態

事後学習・事前学習

6時間

対面

事後学習・事前学習

授業内容

2時間

遠隔（オンデマンド）

授業内容

授業内容

2時間

アルゴリズムの評価：最大・平均計算量，計算量の漸近的評価．

授業形態

授業内容

2時間

対面

事後学習，講義ノートおよび各自が作成した学習ノートを読み直し，さらに演習問題を解き直すことにより「データ構造：グラフとは，グラフの用語，グラフの表現，グラフの探索，最短路問題」を再確認すること．
事前学習として，講義ノートを事前に読み，「アルゴリズムの評価：最大・平均計算量，計算量の漸近的評価」の用語，操作を調べておくこと．

授業内容

2時間

対面

事後学習，講義ノートおよび各自が作成した学習ノートを読み直し，さらに演習問題を解き直すことにより「データ構造：木とは，木の用語，木の走査，２分木，一般の木，木の操作」を再確認すること．
事前学習として，講義ノートを事前に読み，「データ構造：グラフとは，グラフの用語，グラフの表現，グラフの探索，最短路問題」の用語，操作を調べておくこと．

授業内容

2時間

2時間

対面

ソーティング：マージソート，バケットソート，ヒープソートなど
事後学習，講義ノートおよび各自が作成した学習ノートを読み直し，さらに演習問題を解き直すことにより「ソーティング：マージソート，バケットソート，ヒープソートなど」を再確認すること．

2時間

事前学習として，講義ノートを事前に読み，「探索：線形探索，二分探索，文字列の探索」の用語，操作を調べておくこと．
第12回

授業形態

授業内容

対面

探索：線形探索，二分探索，文字列の探索．

事後学習・事前学習

事後学習，講義ノートおよび各自が作成した学習ノートを読み直し，さらに演習問題を解き直すことにより「探索：線形探索，二分探索，文字列の探索」を再確認すること．
事前学習として，講義ノートを事前に読み，「いろいろな問題に対するアルゴリズム：フィボナッチ数列，ハノイの塔，８クイーン問題など」の用語，操作を調べておくこと．

第13回

授業形態

授業内容

対面

いろいろな問題に対するアルゴリズム：フィボナッチ数列，ハノイの塔，８クイーン問題など．

事後学習・事前学習

事後学習，講義ノートおよび各自が作成した学習ノートを読み直し，さらに演習問題を解き直すことにより「いろいろな問題に対するアルゴリズム：フィボナッチ数列，ハノイの塔，８クイーン問題など」を再確認すること．
事前学習として，期末試験に備え，ここまでの講義ノートならびに講義中に説明した内容を再確認しておくこと．

第14回

授業形態

授業内容

期末試験の準備
事前学習として，期末試験に備え，ここまでの講義ノートならびに講義中に説明した内容を再確認しておくこと．

第15回

授業形態
期末試験 (講義内試験)．

事後学習

期末試験の内容を振り返り，これまでに配布した講義ノート全体を再度見直しておくこと．

期末試験の模範解答を配布する．

指定教科書はない．
講義ノートを提供する．

参考書

講義の中で，紹介する．

受講生へのメッセージ

実務家担当科目

1時間

期末試験，中間試験，確認テスト，課題レポートによって到達目標に照らして，６段階のGrade(A+，A，B，C，D，F)で評価し，D以上の者に単位を認める．

教科書

オフィスアワー

6時間

対面

授業内容

受講生へのフィードバック方法

2時間

対面

事後学習・事前学習

成績評価の方法

2時間

講義・演習を担当する教員の指示に従うこと．
関数や条件分岐やポインタなどの基礎的なプログラミング技法を覚えたり，とにかく動くプログラムを書くことに集中するのではなく，データ構造とアルゴリズムという観点からプログラムを捉え直すことを目指してください．特に，演習では，紙と鉛筆では対応できない大規模なデータを扱うことにより，実験・分析することで，データ構造とアルゴリズムの特性の理解を深めてください．将来，情報システムを扱う際，その高性能化，高機能化，高信頼化に向けて，どのようなアルゴリズムに基づいたアプリケーションプログラムを適用すべきかを検討するための基礎知識として，役立ててください．さらに，プログラミングが得意でない学生でも，この授業でアルゴリズムから理解することでプログラムに親しんで苦手意識を払しょくしていただきたいと考えます．

実務家担当科目ではない

実務経験の内容

教職課程認定該当学科
教育課程コード

情報デザイン学科
Ⅱ2c

教育課程コードの見方【例】 Ⅰ2a（Ⅰ…Ⅰ群、2…2年配当、a…必修） ※ a : 必修 b : 選択必修 c :選択※複数コードが表示されている場合には入学年度・所属学科の学生便覧を参照のこと