Report

「アルゴリズムとデータ構造Ａ，Ｂ」
課題レポート（２０１４年度）

実習課題が書かれています．所属クラスによって課題が異なる 場合がありますので，注意して下さい．

課題

1. UNIX入門（Ｃコンパイラの利用とレポート作成の基本）
2. 効率の良いアルゴリズム（ユークリッドの互除法）（データの入力と繰り返し（while文））
3. 基本データ構造（リスト・スタック・キュー）
4. グラフ，木，再帰
5. 優先度つき待ち行列（ヒープ）
6. 単純なソートアルゴリズム（バブルソート）
7. 単純なソートアルゴリズム（挿入ソート）
8. 比較を行なわないソートアルゴリズム（バケットソート・基数ソート）
9. 安定で高速なソートアルゴリズム（ヒープソート）
10. 内部整列法で実用上最高速のソートアルゴリズム（クイックソート）
11. 高速なデータ探索（２分探索）
12. 外部整列法で高速なソートアルゴリズム（マージソート）
13. ソートアルゴリズムの計算時間比較

Lab1：UNIX入門（Ｃコンパイラの利用とレポート作成の基本）

提出方法：紙レポート（提出方法に従 うこと）
提出期限：４月１４日（月）９時３０分
レポートのポイント：指定した様式の通りに作成したしっかりした レポートを期限までに提出する練習をします．レポートが指定した 様式でない場合には受理されず再提出になります．表紙に書かれて いる再提出期限までに提出しない場合は未提出として扱われます．

次の４課題について，指示に従い報告せよ．

1. ディスプレイに「Welcome to Algorithms and Data Structures!」と表示するプログラムを作成し，UNIX上でコンパイル し実行せよ． （ファイル名はlab1.cとせよ） ただし，ソースファイルの先頭にはコメントとして学籍番号と氏名を 半角英数（ローマ字）で記述すること（プログラム中にはコ メントを含めて日本語文字を含めないこと．世界で通用するのは半 角英数だけであり，日本語文字が入っているプログラムはコンパイ ルが通らないことが多い．どうしても日本語を書きたい時は，ロー マ字等を用いよ）．
   このときのコンパイル手順について１手順ずつ箇条書きで詳細に報告せよ．
   （注意：Webサイト等そのまま写すのではなく，自分の言葉で説明・報 告すること．他の人と同一とみなされる場合は情報理工学を目指 すものとして著作権を軽視したものとみなし，この世界から永久に 追放されるので注意）．
2. 次に，同じプログラムをVisual Studio 2010上でもコンパイルし 実行せよ， 同様に，コンパイル手順について１手順ずつ箇条書きで詳細に報告せよ．
3. UNIX, Windowsともに同じ動作をしたことを確認し，わかりやす く報告せよ． 確認・報告の方法は各自に任せる（画面のハードコピーや，テキス トの切り貼り等，自由に行なえ，これが本当の表現の自由である）．
4. Visual Studio 2010のメニューから印刷を指定し，lab1.cのソースファ イルを印刷したものをレポートの最後に添付せよ．．

Lab2：効率の良いアルゴリズム（ユークリッドの互除法）（データの入力と繰り返し（while文））

提出方法：ファイルレポート（提出方法に従 うこと）
提出期限：４月２１日（月）９時３０分
レポートのポイント：ファイルレポートの提出方法の練習と，基本的な プログラミングの確認をします．

1. キーボードから入力した２個の正整数a0とa1の最大公約数を計 算する関数を，単純な方法と，ユークリッドの互除法を用いて実現した場合 にわけて作成し，結果を表示するCプログラム gcd1.cおよgcd2.cを作成せよ．
2. 次に，それぞれのプログラムを実行し確実に動作することを確 認せよ．（大きな数を入力したとき，実行時間が異なることを体感 せよ）
3. 作成したCプログラムのソースファイルをコピーし，それらのファイル名を 「学籍番号-1.c」および「学籍番号-2.c」に変え指定の提出フォルダに置け．
4. ２つのファイルが提出フォルダに確実に置かれたかどうかを（何度も）確認せよ．

Lab3： 基本データ構造（配列とポインタによるリスト・スタック・キュー の実現）

提出方法：ファイルレポート（提出方法に従うこと）
提出期限：５月９日（金）９時３０分
レポートのポイント：配列およびポインタによって実現されたリス ト操作にかかる手間が，それぞれどれくらい必要なのかを理解します．

1. 配列およびポインタを用いた線形リストデータ構造を利用して， キーボードから順に入力した複数の整数値（int型）を空の「スタッ ク」および「キュー」データ構造にそれぞれ保存する．（入力終了 はマイナスの数値を入力したときとする）次に，この「スタック」 と「キュー」データ構造からデータを１つずつ取り出した時，出力 される整数値を順に表示するプログラムarraylist.cおよび pointlist.c をそれぞれ作成し，そのソースファイルを提出せよ．
2. 作成したCプログラムの２つのソースファイルをコピーし，それらのファイル名を 「学籍番号-1.c」および「学籍番号-2.c」に変え指定の提出フォルダに置け．
3. ２つのファイルが提出フォルダに確実に置かれたかどうかを（何度も）確認せよ．

   動作確認のために入力する整数値は，例えば各自の学籍番号の数字の部分 とせよ（例えばH120123なら，「1→2→0→1→2→3→-1」の順．-1で 入力終了）． 動作結果として，スタックとキューに保存されているデータがどの ような順でそれぞれ表示されたか報告し，動作を 確認せよ． （スタックの場合は「3→2→1→0→2→1」の順で出力され，キュー の場合は「1→2→0→1→2→3」の順で出力されることを確認せよ）

• 配列およびポインタを用いた線形 リストの動作をパワーポイントで作成したパラパラマンガの例

Lab4:再帰

提出方法：ファイルレポート（提出方法に従うこと）
提出期限：５月１６日（金）０９時３０分

• twoint.datと言う名前のファイル（ファイル例）から２個の正整数a0とa1を読み込み，それらの最大公約数をユークリッドの互除法（再帰版）を用いて計算し，表示するプログ ラム recurgcd.cを作成せよ．またLab2で行なったプログラムのプロ グラム量および動作結果を比較せよ（提出ファイルの先頭にコメントとして記述せよ）．

（ポイント）
ファイルからの読み込みと，再帰プログラミングを完全理解するこ と． この課題の主な部分は再帰プログラムで記述するためfor文やwhile 文を使用しないことに注意せよ．
このほか，等差数列，等比数列，階乗，べき乗等の計算を再帰プ ログラミングで実現できるように十分練習し，再帰プログラミング に慣れるまで練習しておくこと（課題が終った人は上記の各種再帰 プログラミングを実際に入力して動作させ，別ファイルとして提出 してもよい）．

Lab5:グラフ，木構造（木の作成となぞり）

提出方法：ファイルレポート（提出方法に従うこと）
提出期限：５月２３日（金）０９時３０分
レポートのポイント：データ構造「木」の理解と，木構造に保存さ れたデータに自由にアクセスできるようになること

次の手順に従ってプログラムorder.cを作成せよ．

1. 10個の整数データを教科書p.42図2.20(a)に示す木構造に保存す るときを考える． まず，教科書p.43図2.21に従って，ポインタにより木を実現し，デー タを保存せよ．（treedata.datと言う名前のファイルから１つずつデータを読み込み，その都 度木構造の一部分を修正しながら完成させると良い．説明付きファイル例）
2. 次に，木の構造をディスプレイに表示する（再帰プログラムとすると良い．非常に簡単に記述できる）． （表示例は次の通り．子がないところは表示しないくても良い．デザインは各自に任せる．）

   （再帰プログラムでないときの例）
   ----------------------
   節点0の子は 1 2である．
   節点1の子は 3 4 5である．
   節点2の子は 6 7である．
   節点3の子は である．
   節点4の子は である．
   節点5の子は である．
   節点6の子は 8 9である．
   節点7の子は である．
   節点8の子は である．
   節点9の子は である．
   ----------------------
   

   （再帰プログラムとしたときの例１：なぞりと同じ動きで，子をひとつ ずつ表示している）

   ----------------------
   節点0の子は 1である．
   節点1の子は 3である．
   節点3の子は である．
   節点1の子は 4である．
   節点4の子は である．
   節点1の子は 5である．
   節点5の子は である．
   節点0の子は 2である．
   節点2の子は 6である．
   節点6の子は 8である．
   節点8の子は である．
   節点6の子は 9である．
   節点9の子は である．
   節点2の子は 7である．
   節点7の子は である．
   ----------------------
   

   （再帰プログラムとしたときの例２：文字絵として作成するとわかりやすい）

   ----------------------
    0
     -> 1
         -> 3
         -> 4
         -> 5
     -> 2
         -> 6
             -> 8
             -> 9
         -> 7
   ----------------------
   

3. 次に，キーボードから前順，中順，後順，プログラム終了のいずれかを選択する．
4. そして，その選択した順で木をなぞり，その順で木に保存され たデータを表示する（必ず再帰プログラミングとすること．非常に簡単に記述できる）．
   （結果は教科書p.45上側と同じ順で表示されることを確認せよ）

（提出するときはソースファイル名を学籍番号.cに変え提出フォル ダに置くこと，提出ファイルの最後にコメントで実行結果を必ず付 けること）

（ポイント）
再帰プログラミングが書けるようになると，プログラミング行数が激的に 減り，複雑な処理でも簡単に誤りの少ないプログラムを作成できる ようになることを確認します． （「再帰」と 「木構造」というアルゴリズムが，「スタック」というデータ構造 と密接に関係していることを（教科書を熟読し）理解すること）

Lab6：単純なソートアルゴリズム（バブルソート）

レポートのポイント：ファイルの扱いと基本的なプログラミングを 再確認します．
中休みとして，これまで同様に，ファイルの取扱いと，２重ループ 程度のプログラミングはマスターしておくこと．
今回は使用しないが，ポインタ，木構造，再帰が理解できていない 人は比較的やさしい今回のうちに復習しておくこと．特にヒープは ベーシッククラスの人も含め確実に動作の理解とプログラミングで マスターしておくこと．

データの個数nとその個数分の整数データが保存されている ファイルがある．
次の手順で動作するプログラムbubble.cを作成し，その動作を確認せよ．

1. まずファイルから保存されているデータ数nを読み込み， その数だけデータを読み込み配列に格納する．
2. 次に，格納された配列をディスプレイ上に表示する．
3. そして，データが保存された配列についてバブルソートを実行する関数 bubblesort()を呼び出し，配列データを整列する．
4. 最後に，整列された配列をディスプレイ上に表示しプログラム を終了する．

（ポイント）
課題内容としてはやさしい「ひと休み課題」である．
すべてのテストデータについて動作を確認すること．
また，同数のランダムデータおよびソート済データについて， データの性質によらずソート時間がほぼ同程度に「遅い」ことを体感しておくこと．

Lab7：単純なソートアルゴリズム（挿入ソート）

レポートのポイント：
カードゲーム等の各種ゲームをコンピュータ上で実現する時に必ず と言って使われる整列処理について， 各種ソートアルゴリズムをプログラミングしながら体験的に学習する．
前回から，どの整列アルゴリズムも当然同じ結果（小さい順 に並ぶ）になるが，計算時間（処理時間）についてそれぞれ特徴が あるので，どのような場面で使うべきか確認しながら実行すること．

データの個数nとその個数分の整数データが保存されている ファイルがある．
次の手順で動作する挿入ソートプログラムinsert.cを作成し，その動作を確認せよ．

1. まずファイルから今から読み込むデータ数nを読み込み， その数だけデータを読み込み配列に格納する．
2. 次に，格納された配列をディスプレイ上に表示する．
3. そして，データが保存された配列について挿入ソートを実行する関数 insertionsort()を呼び出し，配列データを整列する．
4. 最後に，整列された配列をディスプレイ上に表示しプログラム を終了する．

（ポイント）
すべてのテストデータについて動作を確認すること．また，同数の ランダムデータおよびソート済データについて，ソート時間が異な ることを体感すること．

「選択ソート」と似ているので，間違えないようにすること

この課題の数回後には，再びポインタを使用したプログラミングを 行うので，ポインタについて理解が進んでいない人は今のうちに復 習しておくこと．

Lab8：比較を行なわないソートアルゴリズム（バケットソート・基数ソート）

提出方法：ファイルレポート（提出方法に従うこと）
提出期限：６月２０日９時３０分
レポートのポイント：
１行ずつプログラムをチェックし，コンピュータに何をさせている のかその都度確認すること．
人間がコンピュータに操られることのないようにすること． どこでおかしい動作になったのかわからない人は デバッガという大変便利なツールを使って原因を探せるようにしておくこと．

データの個数nとその個数分の整数データが保存されている ファイルがある． （ただし，データは５桁以下の１０進数とする）
次の手順で動作するプログラムradix.cを作成し，その動作を確認せ よ．
アルゴリズムをそのまま実現してよいが，余力のある人は教科書に 従い，「インデックス配列」を使って処理を高速化したプログラム としてもよい．

1. まずファイルから保存されているデータ数nを読み込み， その数だけデータを読み込み配列に格納する． ただし，配列は「５桁整数の各桁の数が入る配列」を列挙した配列 とせよ（教科書参照）．
2. 次に，格納された配列をディスプレイ上に表示する．
3. そして，データが保存された配列について基数ソートを実行する関数 radixsort()を呼び出し，配列データを整列する．
4. 最後に，整列された配列をディスプレイ上に表示しプログラム を終了する．

（ポイント）
ポインタやデバッガの使い方がわからない人は，ここで十分理解しておくこと．

Lab9：高速なソートアルゴリズム（ヒープソート）

提出方法：ファイルレポート（提出方法に従うこと）
提出期限：６月３０日９時３０分
レポートのポイント：
ヒープソートは人間は面倒であまりやらないアルゴリズムであるが，コンピュータ にとっては得意で，データ数が多くなったときも動作速度が急に落 ちることのない信頼のある高速アルゴリズムであることを理解すること．
実現に関しては，ヒープが木構造なので一見ポインタを使ったプロ グラムになると思われれがちだが，２分木なので配列でも実現可能 である．もちろん，木構造をすべてポインタで実現したほうがデー タ数に制限がなくなり，大量のソート処理にも耐えられることも理 解しておこう．余力のある人はポインタで実現してもよい．

データの個数nとその個数分の整数データが保存されている ファイルがある．
次の手順で動作するプログラムheapsort.cを作成し，その動作を確認せ よ．

1. まずファイルから保存されているデータ数nを読み込む．
2. データを１つ読み込み，ヒープを構成する．
3. これをn回繰り返し，その度にヒープを構成する．
4. すべてのデータを挿入し終ったらヒープが完成するので，デー タを木構造がわかるようにディスプレイ上に表示する．
5. 次に，deletemax()関数をn回呼び出し，ソート処理を 進める．
6. 最後に，整列されたデータをディスプレイ上に表示しプログラム を終了する．

Lab10：内部整列法で実用上最高速のソートアルゴリズム（クイックソート）

提出方法：ファイルレポート（提出方法に従うこと）
提出期限：７月７日９時３０分
レポートのポイント：
クイックソートは一見速そうなアルゴリズムだが，どんなデータに対しても最高速で動作するアルゴ リズムではないことを理解すること．
配列を使ったソートアルゴリズムなので，特にベーシッククラスの 人はプログラムの理解に特に時間をかけること．

データの個数nとその個数分の整数データが保存されている ファイルがある．
次の手順で動作するプログラムquicksort.cを作成し，その動作を確認せ よ．

1. まずファイルから保存されているデータ数nを読み込み， 次にその数だけデータを読み込み配列に格納する．
2. 次に，格納された配列をディスプレイ上に表示する．
3. そして，データが保存された配列についてクイックソートを実行す る関数quicksort()を呼び出し，配列データを整列する．
4. 最後に，整列された配列をディスプレイ上に表示しプログラム を終了する．

Lab11：高速なデータ探索（２分探索）

提出方法：ファイルレポート（提出方法に従うこと）
提出期限：７月１４日午前９時３０分
レポートのポイント：
探索（サーチ）は，整列（ソート）とともにデータ処理の基本です． しっかり理解しましょう．

まず，ファイルにデータの個数nと，その個数分のデータ （整数のデータ）を保存する．（ ソートアルゴリズム動作確認用データ ファイルのランダムデータを使用すると良い）
次の手順で動作するプログラムbinsearch.cを作成し，その動作を確 認せよ．

1. ランダムな整数がデータとして保存されたファイルから，まず， データの個数nを読み込み，その数だけデータを読み込み２ 分探索木に格納する．
2. 次に整数を一つだけキーボードから入力する．
3. そしてその整数が保存した２分探索木内に存在する場合にはyes， 存在しない場合にはnoを２分探索により判定し，結果をディスプレイ 上に表示する．
4. さらに，読み込んだデータの中で最小の値を表示し，プログラ ムを終了する．

Lab12：外部整列法で高速なソートアルゴリズム（マージソート）

提出方法：ファイルレポート（提出方法に従うこと）
提出期限：７月２１日午前９時３０分
レポートのポイント：
コンピュータのメモリに入りきらないほど多くのデータに対しても 高速に整列操作（外部整列法）が実行できるアルゴリズムであることを理解すること．

データの個数nとその個数分の整数データが保存されている ファイルがある．
次の手順で動作するプログラムmergesort.cを作成し，その動作を確 認せよ．

1. まずファイルから保存されているデータ数nを読み込み， 次にその数だけデータを読み込み格納する．（保存方法は所属クラ スによって異なるので注意）
2. 次に，保存されたデータについてマージソートを実行す る関数mergesort()を呼び出し，データを整列する．
3. 最後に，整列されたデータをディスプレイ上に表示しプログラム を終了する．

Lab13：ソートアルゴリズムの計算時間比較

提出方法：紙レポート（定期試験期間中なので，直接指定教室に持参すること）
提出期限：７月２５日４限８１１教室で回収（定期試験期間中）

これまで学んできた各種ソートの特徴を確認するため，計算機実験 （シミュレーション）を行う．

入力データとしてランダムなものとソート済のものについて．次の ソートアルゴリズムの実行時間をそれぞれ測定し，特徴をまとめよ．
なお，入力するデータは５桁以下の正整数とし， データファイルを利用すると良い．

• 挿入ソート
• 基数ソート
• ヒープソート
• クイックソート
• マージソート

• レポートは指定のエクセルファイル（office2007以降用 ，office2003用 ）をダウンロードし，測定結果（オーダー等）を 入力したものを印刷して提出すること．（右クリックしてファイル に保存してから記入するとよい）
• 測定は同一コンピュータで実 施すること．つまり，ログインしてログアウトするまでの間にすべ てのデータの測定をしおえること．途中でログアウトすると実験環 境が変わり結果に大きな誤差が発生する．そういうこときは測定し 直すこと．（実験を行なう時は十分時間を確保して行なうこと）
• コンピュータの高速化にともない測定した計算時間がほぼ０と 測定されてしまうことがある．その場合はエクセルファイルには入 力せず，別欄に０となったことを記載しておくこと．（対数グラフ では値として０を入力できないことを覚えておこう）
• （これが 一番重要→）上記に加えて，シミュレーションを実行した考察（各 アルゴリズムについて「エクセルに書かれた結果（ランダムデータ とソート済データでオーダー等が一致／不一致等）と，どうしてそ のようなことになったのかというアルゴリズム的な理由」）と，本 課題を実行した感想を別紙１枚程度にまとめて報告せよ．
• 「表 紙→問題の記述と実験内容（どのような環境（自宅のパソコンやソ フト等）で実験を行なったかの要約説明）１枚→EXCEL表を印刷した もの２枚→実験の考察・感想１枚」の順で綴じること．
• 上記の 指示に従って記述すること（指示に従わないレポートは受理しない ので特に注意すること）

• １つのソートアルゴリズムについて時間測定しているときは， データ数が変化する度にプログラムを修正したり，再コンパイルす ることは絶対にしないこと．（そのような行為は平等な環境で測定 が行なわれておらず，不公平な測定を行なっていることになる，中京大学の建学の精神「学術とス ポーツの真剣味の殿堂たれ」に違反する行為であるので，即刻失格とし，単位修得の保証はしない）
• プログラムによっては配列の大きさが不足したり，int型をlongint型に変更 しないと動作しない場合がある．適宜変更して実行すること．（大 きなデータでも動くプログラムを作成するにはいろいろ考慮しなけ ればならないことを学ぶこと）
• Windows上(bccやVisualStudio)ではなく必ずUNIX上(gcc)でプログラ ムをコンパイルして動作させ時間測定すること． UNIX上でのプログラムの実行時間を測定するには，timeコマンドを使うこと．timeコマンドを使 用することで他のユーザの影響を避け正確な測定ができる．timeコマン ドを使わないと，他の人が計算機を使い始めたり，複数のプログ ラムを同時に実行すると測定時間が乱れグラフの形状がギザギザに なることがある．また，先に説明した不公平な行為をした場合もグ ラフの形状がギザギザになる．そのような測定結果が観測されたと きは実験失敗である．滑らかなグラフ形状でない場合は，原因をも う一度確認してからやり直すこと．
• もしどうしても計測時間が乱れて滑らかなグラフ形状になら ない場合には，同じデータ数のデータをいくつか用意したうえで実行 し，それらの平均時間を結果とすると良い．その場合は，どのよう なデータを使って平均をとったか詳細に報告せよ．
• 時間のかかるアルゴリズムの場合，いくら待ってもプログラム からの応答がないこともある．必ずデータ数の少ないものから順に 実験すること．時間がかかるデータを使った測定をしてしまった時 は途中で実行をあきらめても良い（プログラムを途中で中断するには， Ctrl-C（Ctrlキーを押しながらCキー）を押す）．ただし，そのこと をレポートに記載し，どのような工夫をすれば実行できるようにな るか考察し記載すること．