DataAlgo2020_R04.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "DataAlgo2020-R04",
      "provenance": [],
      "authorship_tag": "ABX9TyOIAqMF+m9QIEjCmjtnulx7",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/kameda-yoshinari/DataAlgo2020/blob/master/DataAlgo2020_R04.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "-SqpuNOEWS-a",
        "colab_type": "text"
      },
      "source": [
        "# データ構造とアルゴリズム 第4週課題 (2020/05/27verC)\n",
        "\n",
        "---\n",
        "\n",
        "\n",
        "\n",
        "<font color=\"red\">\n",
        "★Ver.B以降の変更記録は末尾＆githubの履歴参照してください．  \n",
        "\n",
        "★下記３要素を必ず書き換えてから提出すること．\n",
        "</font>\n",
        "\n",
        "* 学籍番号：（これを消して記入；例 202099998）\n",
        "* 氏名：（これを消して記入；例 筑波太郎）\n",
        "* Colabアカウント：（これを消して記入；例 tsukuba.taro.xs@alumni.tsukuba.ac.jp）\n",
        "\n",
        "課題提出方法については，末尾参照．\n",
        "\n",
        "なお，課題実施に当たって，学生同士の相談は妨げない．\n",
        "ただし，その場合，必ず下記の情報を提供すること．\n",
        "申告があった場合は，論述などで内容が似ていたり，プログラムが似ていても減点はしない．（コピペレベルの同一文などは処罰対象）  \n",
        "**教えた側は加点対象となる．**\n",
        "\n",
        "**[教えた側]**\n",
        "\n",
        "教えた相手：＜氏名＞　＜学籍番号＞\n",
        "\n",
        "（何名いてもよい；教えた相手の内容が浅くなってないか確認すること）\n",
        "\n",
        "**[教わった側]**\n",
        "\n",
        "教わった相手：＜氏名＞　＜学籍番号＞\n",
        "\n",
        "（何名いてもよい；必ず教えた側に自分の名前を書いてもらうこと）\n",
        "\n",
        "**[グループワーク]**\n",
        "\n",
        "一緒に行った相手：＜氏名＞　＜学籍番号＞\n",
        "\n",
        "（何名いてもよいが，必ずお互いの名前を全員記すこと）\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "TjOgrYW8lAmy",
        "colab_type": "text"
      },
      "source": [
        "---\n",
        "# 必須課題4A 深さ優先探索アルゴリズムの自然言語記述\n",
        "\n",
        "<b>\n",
        "\n",
        "DataAlgo2020-005(DFS)で示している再帰呼出関数を用いた深さ優先探索アルゴリズムを，日本語で過不足なくかつ簡潔に記述せよ．\n",
        "\n",
        "* 本講義資料に即した説明であること．\n",
        "* スタック領域をどのように利用しているかも記述に含めること．\n",
        "* スタックの図（自作に限る）も含めること．\n",
        "\n",
        "文章については，１つ目のテキストセルに入れること．\n",
        "図については，２つ目のテキストセルに入れること．\n",
        "\n",
        "図は直接の貼り込みでもよいし，Google Drive上の図形描画からのURLでもよい．\n",
        "\n",
        "</b>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "mRLPlzcHmhiQ",
        "colab_type": "text"
      },
      "source": [
        "（文章はここに記述）"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "E_IyfH8BmhvY",
        "colab_type": "text"
      },
      "source": [
        "（図はこちら）"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "8NUVKBVvmvtw",
        "colab_type": "text"
      },
      "source": [
        "---\n",
        "# 必須課題4B 深さ優先探索アルゴリズムの計算量\n",
        "\n",
        "<b>\n",
        "\n",
        "DataAlgo2020-005(DFS)で示している深さ優先探索アルゴリズムの空間計算量と時間計算量について議論せよ．(授業内で言及していた内容をまとめるだけでよい）\n",
        "\n",
        "</b>"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "3j3I4WWQ2EU0",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        ""
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "B9Z8A8xin-Ru",
        "colab_type": "text"
      },
      "source": [
        "（議論はここに記述）"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "lhHo4RtY1c_z",
        "colab_type": "text"
      },
      "source": [
        "---\n",
        "# 必須課題4C 深さを表示するプログラム\n",
        "\n",
        "<b>\n",
        "\n",
        "深さ優先探索の結果の列挙において，それぞれの頂点の深さ（開始頂点からの辺数）を合わせて表示するプログラムを作成せよ．ベースには dfs_recursive-short_J を用いること．下記はグラフG3での開始頂点0での出力例である．趣旨が同じであれば表示はこの通りで有る必要はない．\n",
        "\n",
        "★★列挙： 0 (深さ 0)  \n",
        "★★列挙： 1 (深さ 1)  \n",
        "★★列挙： 6 (深さ 2)  \n",
        "★★列挙： 2 (深さ 3)  \n",
        "★★列挙： 3 (深さ 4)  \n",
        "★★列挙： 7 (深さ 5)  \n",
        "★★列挙： 5 (深さ 3)  \n",
        "★★列挙： 4 (深さ 4)  \n",
        "\n",
        "</b>"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "rcWjNAl-2Fe7",
        "colab_type": "code",
        "outputId": "dcc538ac-d9c9-4eee-8dba-74d24b4efcba",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 33
        }
      },
      "source": [
        "%%writefile Report4C.c\n",
        "// Report 4C (base: dfs_recursive-short_J.c)\n",
        "#include <stdio.h> // printf()\n",
        "#include <stdlib.h> // atoi()\n",
        "#include \"graph3.h\"\n",
        "\n",
        "int listed[N];  // 0 未, 1 済\n",
        "\n",
        "// 深さ優先探索本体 / 再帰呼出\n",
        "void dfs(int CurrentRoom){\n",
        "    int RoomToCheck;\n",
        "\n",
        "\t// 処理済みであることを記録\n",
        "\tlisted[CurrentRoom] = 1;\n",
        "\t// 計上（列挙）を表示\n",
        "    printf(\"★★列挙： %d\\n\", CurrentRoom);\n",
        "\n",
        "    // 次にどの頂点を列挙していくか検討\n",
        "\tfor (RoomToCheck = 0; RoomToCheck < N; RoomToCheck++) {\n",
        "        if (edge[CurrentRoom][RoomToCheck] != 0 && listed[RoomToCheck] == 0) \n",
        "\t\t\tdfs(RoomToCheck);\n",
        "\t}\n",
        "\treturn;\n",
        "}\n",
        "\n",
        "int main(int argc, char *argv[]){\n",
        "    int RoomToCheck;\n",
        "\n",
        "    int startnode = 0;\n",
        "    if (argc == 1) {\n",
        "        printf(\"指定がなかったので頂点0を開始頂点にします．\\n\");\n",
        "        startnode = 0;\n",
        "    } else if (argc == 2) {\n",
        "        startnode = atoi(argv[1]);\n",
        "        if (startnode < 0 || startnode >= N) {\n",
        "            printf(\"不正な頂点指定だったので終了します．\\n\");\n",
        "            return -1;\n",
        "        }\n",
        "    }\n",
        "\n",
        "\tfor (RoomToCheck = 0; RoomToCheck < N; RoomToCheck++)\n",
        "\t\tlisted[RoomToCheck] = 0;\n",
        "\n",
        "\tdfs(startnode); // 開始頂点番号を引数にしてdfs関数を呼び出す\n",
        "\n",
        "\treturn 0;\n",
        "}"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Writing Report4C.c\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "88G_NNsW3Aud",
        "colab_type": "code",
        "outputId": "215f698f-d9ee-402b-d5c9-d105ac0078f1",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 33
        }
      },
      "source": [
        "%%writefile graph3.h\n",
        "// 8 nodes, undirected, no-weight.\n",
        "#define N 8\n",
        "int edge[N][N] = {\n",
        "//   0 1 2 3 4 5 6 7\n",
        "\t{0,1,0,0,1,0,0,0}, // 0\n",
        "\t{1,0,0,0,0,0,1,0}, // 1\n",
        "\t{0,0,0,1,0,0,1,0}, // 2\n",
        "\t{0,0,1,0,0,0,0,1}, // 3\n",
        "\t{1,0,0,0,0,1,0,0}, // 4\n",
        " \t{0,0,0,0,1,0,1,0}, // 5\n",
        "\t{0,1,1,0,0,1,0,1}, // 6\n",
        "\t{0,0,0,1,0,0,1,0}  // 7\n",
        "};"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Writing graph3.h\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "RMj0i7y32ik0",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "!gcc -Wall -o Report4C Report4C.c"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "as4G4fX22sRC",
        "colab_type": "code",
        "outputId": "2525c306-d61d-4e25-a140-eda97af177d9",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 147
        }
      },
      "source": [
        "!./Report4C 0"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "★★列挙： 0\n",
            "★★列挙： 1\n",
            "★★列挙： 6\n",
            "★★列挙： 2\n",
            "★★列挙： 3\n",
            "★★列挙： 7\n",
            "★★列挙： 5\n",
            "★★列挙： 4\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "NTFmAWpPnnaz",
        "colab_type": "text"
      },
      "source": [
        "---\n",
        "# 発展課題4X スタック使用量とその限界\n",
        "\n",
        "<b>\n",
        "\n",
        "どのような無向で連結なグラフが指定されても，プログラム dfs_recursive_J において，スタックに必要な領域が頂点数（の定数倍）を超えないことを示せ．  \n",
        "また，\n",
        "どのような無向で連結なグラフが指定されると，スタックの使用量が一時的に最大となるか理由と共に示せ．ここで一時的な最大とは，再帰呼出の積み重ねによってスタックの使用量が最大になる状況を指す．つまり，どのようなグラフが来たら，スタックが一時的とはいえ最大限高くなる（スタックに溜る）か？という設問である．\n",
        "\n",
        "\n",
        "</b>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ljT6EzOYnUZp",
        "colab_type": "text"
      },
      "source": [
        "（議論はここに記述）"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "QaF4i_OewcnU",
        "colab_type": "text"
      },
      "source": [
        "---\n",
        "# 発展課題4Y 二つのプログラムのスタックの内容のずれ\n",
        "\n",
        "<b>\n",
        "\n",
        "ここで示した２つのプログラム\n",
        "\n",
        "*    dfs_xtraCommandLine_J\n",
        "*   dfs_recursive_J\n",
        "\n",
        "において，注意深く観察すると，同じ開始頂点を与えたときに列挙結果は同じとなるものの，途中のスタックの中身は同じではない．どちらも深さ優先探索ではある．この違いが発生する原因を考察せよ．\n",
        "\n",
        "（本発展課題はやや難しい）\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "uUbvRSckx_1w",
        "colab_type": "text"
      },
      "source": [
        "（議論はここに記述）"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "c7rf54NjW5f2",
        "colab_type": "text"
      },
      "source": [
        "---\n",
        "# 課題提出法 \n",
        "\n",
        "筑波大学工学システム学類３年生向け．  \n",
        "FG24711 / FG34711．  \n",
        "\n",
        "必須課題は全て実施すること．\n",
        "発展課題はしなくともよいが，A+取得には発展課題を（全課題提出を通して）1つ以上実施していることが必要条件である．\n",
        "\n",
        "該当するmanabaに課題提出のエントリを設けるので，そこに本**Colab notebookを提出**すること．また，Google Drive上の該当する**Colab notebookへの共有リンク**を用意し合わせて提出すること．（採点時の効率を高めるために共有リンクの方を使うかもしれません）\n",
        "\n",
        "![共有可能なリンク](https://docs.google.com/drawings/d/e/2PACX-1vTDuOu8Z1nZFTqJ0yMKXedJwDnZx0hiKXoL56h21kQrDRj4C52aQX7Nn9QJZFZAgKV32lxTzuvNlory/pub?w=508&h=403)\n",
        "\n",
        "\n",
        "\n",
        "# 出典\n",
        "\n",
        "筑波大学工学システム学類  \n",
        "データ構造とアルゴリズム  \n",
        "担当：亀田能成  \n",
        "2020/05/27. 初版  \n",
        "2020/05/28. Ver.B 課題4Aの題名を「幅優先」⇒「深さ優先」に訂正．  \n",
        "2020/06/01. Ver.C 課題4Xの不明瞭さを改訂．\n",
        "\n",
        "\n"
      ]
    }
  ]
}