Report

「アルゴリズムとデータ構造A,B」
課題レポート(2014年度)


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

課題

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

Lab1:UNIX入門(Cコンパイラの利用とレポート作成の基本)

提出方法:紙レポート(提出方法に従 うこと)
提出期限:4月14日(月)9時30分
レポートのポイント:指定した様式の通りに作成したしっかりした レポートを期限までに提出する練習をします.レポートが指定した 様式でない場合には受理されず再提出になります.表紙に書かれて いる再提出期限までに提出しない場合は未提出として扱われます.

次の4課題について,指示に従い報告せよ.

  1. ディスプレイに「Welcome to Algorithms and Data Structures!」と表示するプログラムを作成し,UNIX上でコンパイル し実行せよ. (ファイル名はlab1.cとせよ) ただし,ソースファイルの先頭にはコメントとして学籍番号と氏名を 半角英数(ローマ字)で記述すること(プログラム中にはコ メントを含めて日本語文字を含めないこと.世界で通用するのは半 角英数だけであり,日本語文字が入っているプログラムはコンパイ ルが通らないことが多い.どうしても日本語を書きたい時は,ロー マ字等を用いよ).
    このときのコンパイル手順について1手順ずつ箇条書きで詳細に報告せよ.
    (注意:Webサイト等そのまま写すのではなく,自分の言葉で説明・報 告すること.他の人と同一とみなされる場合は情報理工学を目指 すものとして著作権を軽視したものとみなし,この世界から永久に 追放されるので注意).
  2. 次に,同じプログラムをVisual Studio 2010上でもコンパイルし 実行せよ, 同様に,コンパイル手順について1手順ずつ箇条書きで詳細に報告せよ.
  3. UNIX, Windowsともに同じ動作をしたことを確認し,わかりやす く報告せよ. 確認・報告の方法は各自に任せる(画面のハードコピーや,テキス トの切り貼り等,自由に行なえ,これが本当の表現の自由である).
  4. Visual Studio 2010のメニューから印刷を指定し,lab1.cのソースファ イルを印刷したものをレポートの最後に添付せよ..
(ポイント)
レポートは単に回答だけ記述するのではなく,課題内容(問題文を 簡単にまとめたもの)も記入し,報告部分がどの問題に対するもの かわかるように記すこと.
「図を見ればわかる」等のあいまいな表現は使わず,図を使った具 体的な説明や理由を文章で詳細に記すこと.
今回だけでなく,次回以降提出するレポートについても 「指定された様式と違わず,かつ,初めて読む 人が自分がやったことと同じことを再現できるまで詳細に記載され たレポート」のみが受理される.(上記が守られていないレ ポートは再提出になる)
レポートは当然それなりのページ数になるが,読む人のことを考え たレポート作成ができるように練習した結果として提出すること.

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

提出方法:ファイルレポート(提出方法に従 うこと)
提出期限:4月21日(月)9時30分
レポートのポイント:ファイルレポートの提出方法の練習と,基本的な プログラミングの確認をします.

  1. キーボードから入力した2個の正整数a0とa1の最大公約数を計 算する関数を,単純な方法と,ユークリッドの互除法を用いて実現した場合 にわけて作成し,結果を表示するCプログラム gcd1.cおよgcd2.cを作成せよ.
  2. 次に,それぞれのプログラムを実行し確実に動作することを確 認せよ.(大きな数を入力したとき,実行時間が異なることを体感 せよ)
  3. 作成したCプログラムのソースファイルをコピーし,それらのファイル名を 「学籍番号-1.c」および「学籍番号-2.c」に変え指定の提出フォルダに置け.
  4. 2つのファイルが提出フォルダに確実に置かれたかどうかを(何度も)確認せよ.
(ポイント)
ファイルレポートはCプログラムのソースファイルだけで評価するの で,ファイルの存在がとても重要である. 指定の場所に提出されたことを何度も確認すること.誤った場所 に置いた場合等,〆切時点でファイルが存在しなかった場合には提 出が認められない.
また,提出するソースファイルの中には,各個人オリジナルのコメント 文を含めること. コメント文はプログラムの各行が何を実行しているのかを他の人が 見て十分類推できる程度に詳細に記述することが望ましい.
なお,教科書や他人のファイルをコピーし自分のファイルとしてそ のまま提出する行為は,情報技術を扱う者として著作権侵害等の観 点から絶対にしてはならない行為である.発覚した場合はこの業界 から抹殺されることを十分認識すること.

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

提出方法:ファイルレポート(提出方法に従うこと)
提出期限:5月9日(金)9時30分
レポートのポイント:配列およびポインタによって実現されたリス ト操作にかかる手間が,それぞれどれくらい必要なのかを理解します.

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

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


Lab4:再帰

提出方法:ファイルレポート(提出方法に従うこと)
提出期限:5月16日(金)09時30分

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

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


Lab5:グラフ,木構造(木の作成となぞり)

提出方法:ファイルレポート(提出方法に従うこと)
提出期限:5月23日(金)09時30分
レポートのポイント:データ構造「木」の理解と,木構造に保存さ れたデータに自由にアクセスできるようになること

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

  1. 10個の整数データを教科書p.42図2.20(a)に示す木構造に保存す るときを考える. まず,教科書p.43図2.21に従って,ポインタにより木を実現し,デー タを保存せよ.(treedata.datと言う名前のファイルから1つずつデータを読み込み,その都 度木構造の一部分を修正しながら完成させると良い.説明付きファイル例
  2. 次に,木の構造をディスプレイに表示する(再帰プログラムとすると良い.非常に簡単に記述できる). (表示例は次の通り.子がないところは表示しないくても良い.デザインは各自に任せる.)
    (再帰プログラムでないときの例)
    ----------------------
    節点0の子は 1 2である.
    節点1の子は 3 4 5である.
    節点2の子は 6 7である.
    節点3の子は である.
    節点4の子は である.
    節点5の子は である.
    節点6の子は 8 9である.
    節点7の子は である.
    節点8の子は である.
    節点9の子は である.
    ----------------------
    
    (再帰プログラムとしたときの例1:なぞりと同じ動きで,子をひとつ ずつ表示している)
    ----------------------
    節点0の子は 1である.
    節点1の子は 3である.
    節点3の子は である.
    節点1の子は 4である.
    節点4の子は である.
    節点1の子は 5である.
    節点5の子は である.
    節点0の子は 2である.
    節点2の子は 6である.
    節点6の子は 8である.
    節点8の子は である.
    節点6の子は 9である.
    節点9の子は である.
    節点2の子は 7である.
    節点7の子は である.
    ----------------------
    
    (再帰プログラムとしたときの例2:文字絵として作成するとわかりやすい)
    ----------------------
     0
      -> 1
          -> 3
          -> 4
          -> 5
      -> 2
          -> 6
              -> 8
              -> 9
          -> 7
    ----------------------
    
  3. 次に,キーボードから前順,中順,後順,プログラム終了のいずれかを選択する.
  4. そして,その選択した順で木をなぞり,その順で木に保存され たデータを表示する(必ず再帰プログラミングとすること.非常に簡単に記述できる).
    (結果は教科書p.45上側と同じ順で表示されることを確認せよ)

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

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


Lab6:単純なソートアルゴリズム(バブルソート)

提出方法:ファイルレポート(提出方法に従うこと)
提出期限:6月6日9時30分

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

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

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

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


Lab7:単純なソートアルゴリズム(挿入ソート)

提出方法:ファイルレポート(提出方法に従うこと)
提出期限:6月13日9時30分

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

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

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

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

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

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


Lab8:比較を行なわないソートアルゴリズム(バケットソート・基数ソート)

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

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

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

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


Lab9:高速なソートアルゴリズム(ヒープソート)

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

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

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

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

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

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

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

Lab11:高速なデータ探索(2分探索)

提出方法:ファイルレポート(提出方法に従うこと)
提出期限:7月14日午前9時30分
レポートのポイント:
探索(サーチ)は,整列(ソート)とともにデータ処理の基本です. しっかり理解しましょう.

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

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

Lab12:外部整列法で高速なソートアルゴリズム(マージソート)


以下のプログラム中で保存するデータは可能な限り「ポインタを用いた線形リスト」 で実現せよ.

提出方法:ファイルレポート(提出方法に従うこと)
提出期限:7月21日午前9時30分
レポートのポイント:
コンピュータのメモリに入りきらないほど多くのデータに対しても 高速に整列操作(外部整列法)が実行できるアルゴリズムであることを理解すること.

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

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

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

提出方法:紙レポート(定期試験期間中なので,直接指定教室に持参すること)
提出期限:7月25日4限811教室で回収(定期試験期間中)

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

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

レポート作成上の注意:
実験を行う上での注意:

2014.07.14.
fmiso at sist.chukyo-u.ac.jp