2026Year

First Semester

Data Structure and Algorithm with Exercises

Lecture and Practice

Data Structure and Algorithm with Exercises

A0400281 Data Structure and Algorithm with Exercises

KONDO Tadahisa,TANAKA Teruo

3.0Credits

前期(1Q)(Mon.2Period,Mon.3Period),前期(2Q)(Mon.2Period,Mon.3Period)

Hachioji Campus

1N-029講義室

2Year

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

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

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

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

Support for self-learning using ICT

対面

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

1時間

【データ構造とアルゴリズム事始め】
   google colab環境, クラウド領域と共有file, shell, editor
　Cの振り返りとしてのコンパイル(gcc), 出力関数printf
   python, interpreter, 出力関数print
　他

事後学習：講義ノートおよび各自が作成した学習ノートを読み直し，さらに演習問題を解き直すことにより，この科目の学びの土台となるGoolge Colaboratory(以後, google colab）の操作と課題提出方法を理解する．

事前学習：講義ノートを事前に読み，「データ構造の基本となる：Cの配列，スタック，キュー」の仕組みと操作を調べておくこと．

2時間

対面

【データ構造とアルゴリズムの基本1】配列, スタックとキュー
　Cの変数，配列，pythonのリストオブジェクト
　構文(for, while, if)
  アルゴリズムの表現

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

2時間

対面

【データ構造とアルゴリズムの基本2】
　Cの変数と配列から構造体とポインタ，pythonのdict（辞書形式）と df（データフレーム）
   関数，再帰呼び出し

事後学習：講義ノートおよび各自が作成した学習ノートを読み直し，さらに演習問題を解き直すことにより「構造体とポインタ，再帰アルゴリズム」を再確認すること．

事前学習：講義ノートを事前に読み，「連結リスト，スタックとキュー」の用語，操作を調べておくこと．

2時間

遠隔（オンデマンド）

第3回までの総復習
課題を提出すること

課題提出締め切りは，第4回の朝10時まで

2時間

対面

【スタック・キューと連結リスト】
スタック・キューの操作，連結リストの探索・挿入・削除

事後学習：講義ノートおよび各自が作成した学習ノートを読み直し，さらに演習問題を解き直すことにより「スタック・キューと連結リスト」を再確認すること．

事前学習：講義ノートを事前に読み，「木とは，木の用語，木の走査，２分木，一般の木，木の操作」の用語，操作を調べておくこと．

2時間

対面

【木】
木とは，木の用語，木の走査，２分木，一般の木，木の操作

事後学習：講義ノートおよび各自が作成した学習ノートを読み直し，さらに演習問題を解き直すことにより「木とは，木の用語，木の走査，２分木，一般の木，木の操作」を再確認すること．

事前学習：講義ノートを事前に読み，「グラフとは，グラフの用語，グラフの表現，グラフの探索，最短路問題」の用語，操作を調べておくこと．

2時間

対面

【グラフ】
グラフとは，グラフの用語，グラフの表現，グラフの探索，最短路問題

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

事前学習：講義ノートを事前に読み，「アルゴリズムの評価として，最大・平均計算量，計算量の漸近的評価」の用語，操作を調べておくこと．

2時間

対面

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

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

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

6時間

対面

【授業内試験】中間試験

試験範囲は，第1回から第6回とオンデマンドEXの全て

事後学習：中間試験で解けなかった問題を見直しておくこと．

事前学習：講義ノートを事前に読み「バブルソート，シェーカソート，選択ソート，挿入ソート，クイックソートなど」の用語，操作を調べておくこと．

2時間

対面

【ソート1】
バブルソート，シェーカソート，選択ソート，挿入ソート，クイックソートなど

事後学習：講義ノートおよび各自が作成した学習ノートを読み直し，さらに演習問題を解き直すことにより「バブルソート，シェーカソート，選択ソート，挿入ソート，クイックソートなど」を再確認すること．

事前学習：講義ノートを事前に読み，「マージソート，バケットソート，ヒープソートなど」の用語，操作を調べておくこと．

2時間

対面

【ソート2】
マージソート，バケットソート，ヒープソートなど

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

事前学習：講義ノートを事前に読み，「探索：線形探索，二分探索，ハッシュ」の用語，操作を調べておくこと．

2時間

対面

【探索】
線形探索，二分探索，文字列の探索，ハッシュ

事後学習：講義ノートおよび各自が作成した学習ノートを読み直し，さらに演習問題を解き直すことにより「線形探索，二分探索，ハッシュ」を再確認すること．

事前学習：講義ノートを事前に読み，「文字列探索」を熟読しておくこと．

2時間

対面

【文字列探索】
BF法，KMP法，BM法，bi-gram, tri-gram, n-gram

事後学習：講義ノートおよび各自が作成した学習ノートを読み直し，さらに演習問題を解き直すことにより「文字列探索」の課題を行うこと．

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

2時間

対面

【アルゴリズムを自分で考える】
　応用課題と総振り返り

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

6時間

対面

【学期末筆記試験】
　期末試験

　試験範囲は本科目で実施した内容すべて（中間試験以前もすべて含む）

期末試験の内容を振り返り，解けなかった問題を解いてみる．

1時間

期末試験と中間試験を主に，演習課題の評価を加味した総合評価により，
到達目標に照らして，６段階のGrade(A+，A，B，C，D，F)で評価し，
D以上の者に単位を認める．

中間・期末試験の解説を試験直後に行う．
演習課題の模範解答を配布し，次回授業の最初に解説を行う．

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

講義の中で，紹介する．

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

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

Not applicable

Department of Information Design

関連する科目である

Ⅱ2c