2025年度

前期

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

講演

Data Structure and Algorithm with Exercises

A0400229 データ構造とアルゴリズム及び演習 [情報][連続][対面]

藤井 昭宏、近藤 公久、上原 敬太郎、西山 博泰、田中 輝雄

3.0単位

前期(1Q)(月曜2限、月曜3限)、前期(2Q)(月曜2限、月曜3限)

八王子

1N-028講義室、1N-029講義室、1N-214講義室、1N-217講義室、1N-335講義室

1 基礎知識の修得 10％
2 専門分野の知識・専門技術の修得 60％
3 汎用的問題解決力の修得 30％
4 道徳的態度と社会性の修得 0％

・基本的なデータ構造とアルゴリズムを理解する．
・データ構造がどのように有効に働き，アルゴリズムがどのように振舞うかを理解し説明できる．
・データの性質あるいは利用目的に合わせた処理効率を意識したデータ構造とアルゴリズムを選択できる．

・到達目標をよく理解し，高いレベルでの達成を目指す意欲があること
・Cコードの理解を必要とするので必修のプログラミング科目の基礎を合わせて理解しておくこと

プログラムを作るときに必要になるのは，取り扱う「データ」をどのような「構造」で表現するかということ，および，それを取り扱う手順，すなわち「アルゴリズム」をどのように設計するかです．ここでは，『プログラム＝データ構造＋アルゴリズム』という関係式が成り立ちます．本講義では，基本的な「データ構造とアルゴリズム」を理解することにより，プログラミング能力向上の一助とします．この講義では，プログラミングおよび演習１〜４と合わせてC言語を前提としますが，データ構造とアルゴリズムの用語は，プログラミング言語とは独立に定義することを心がけます．言語に依存する場合については，その都度，説明を行います．
さらに，演習により理解を深めるとともに，基本的なアルゴリズムを実際に計算機上で動作させ実感していただきます．加えて，その動作の特徴を整理・分析することにより，実問題に対応するスキルを磨くことを目標とします．演習では，各回に基本的な課題を実施するとともに３回程度の課題レポートを課すことを予定しています．
本演習はプログラミングが主目的ではありません．演習に必要なプログラムの基本部分は提供し，それを修正・追加することにより，いろいろなデータを用いた実験を行い，考察することを主眼とします．シームレスな実験環境の確保ならびにデータ構造とアルゴリズムを理解することに特化するために，実験環境はgoogle colaboratoryを用います．これにより，講義と同じ環境で教室以外での予習・復習を可能とします．
言語は基本をCとし，グラフ化などのために一部Pythonを用います．ただし，Pythonの知識は前提とはしません．演習を行う上で，必要な説明は行います．
講義及び演習を連続して教室にて行います．そのため，各自，PCを持参すること，また，PCは３時間余り稼働できるように十分充電をしておいてください．当日は他科目でもPCを使うことが予想されますので、朝方、ほぼフル充電状態にしておくことを勧めます．

e-ラーニング等ICTを活用した自主学習支援

対面

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

1時間

【アルゴリズム入門】アルゴリズムとは：アルゴリズムの例，アルゴリズムの表現，Colaboratoryの操作．

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

2時間

対面

【データ構造】配列，スタック，キュー

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

2時間

対面

【アルゴリズム】再帰アルゴリズム

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

2時間

対面

【データ構造】連結リスト：連結リストとは，連結リストの宣言，連結リストの生成，連結リストの探索・挿入・削除

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

2時間

対面

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

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

2時間

対面

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

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

2時間

対面

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

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

2時間

遠隔（オンデマンド）

【試験対策】中間試験に向けての演習問題を配布するので各自で解くこと．解答(例)は別途配布予定

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

6時間

対面

【授業内試験】中間試験

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

2時間

対面

【アルゴリズム】ソーティング１：バブルソート，シェーカソート，選択ソート，挿入ソート，クイックソートなど

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

2時間

対面

【アルゴリズム】ソーティング２：マージソート，バケットソート，ヒープソートなど

事後学習：講義ノートおよび各自が作成した学習ノートを読み直し，さらに演習問題を解き直すことにより「ソーティング２：マージソート，バケットソート，ヒープソートなど」を再確認すること．
事前学習：講義ノートを事前に読み，「探索：線形探索，二分探索，文字列の探索」の用語，操作を調べておくこと．

2時間

対面

【アルゴリズム】探索：線形探索，二分探索，文字列の探索

事後学習：講義ノートおよび各自が作成した学習ノートを読み直し，さらに演習問題を解き直すことにより「探索：線形探索，二分探索，文字列の探索」を再確認すること．
事前学習：講義ノートを事前に読み，「面白いアルゴリズム」を熟読しておくこと．

2時間

対面

【アルゴリズム】面白いアルゴリズム１

事後学習：講義ノートおよび各自が作成した学習ノートを読み直し，さらに演習問題を解き直すことにより「面白いアルゴリズム」の課題を行うこと．
事前学習：期末試験に備え，ここまでの講義ノートならびに講義中に説明した内容を再確認しておくこと．

2時間

対面

【アルゴリズム】面白いアルゴリズム２，期末試験に向けて

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

6時間

対面

【講義内試験】期末試験

期末試験の内容を振り返り，解けなかった問題を解いておくこと．

1時間

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

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

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

講義の中で，紹介する．

講義・演習を担当する教員の指示に従うこと．

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

なお，この科目は「情報学のための数理・データサイエンス・AI教育プログラム（応用基礎レベル）」の修了要件に必須の科目です．
詳しくは下記の授業一覧を参照してください．
https://drive.google.com/file/d/1t8yglmjSUw5wWSwlljYdNqwC3JN3Axug/view?usp=sharing

実務家担当科目ではない

情報デザイン学科

関連する科目である

Ⅱ2c