DataAlgo2020_R03.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "DataAlgo2020-R03.ipynb",
      "provenance": [],
      "authorship_tag": "ABX9TyPv5kUUcrhXfPJgJwM0SVMI",
      "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_R03.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": [
        "# データ構造とアルゴリズム 第3週課題 (2020/05/20verB)\n",
        "\n",
        "<font color=\"red\">\n",
        "ver.B: 課題3Xを訂正(追記)しました．  (発展課題をしない人は旧版のままで結構です）\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": "GRWyrzY-jxwu",
        "colab_type": "text"
      },
      "source": [
        "---\n",
        "# 必須課題3A \"Hello Foo\"\n",
        "\n",
        "<b>\n",
        "\n",
        "コマンドライン引数（１単語）を引き取って，\"Hello Esys\"の\"ESYS\"部分に表示するようなCプログラムを作成・コンパイル・実行せよ．そのために３つのコードセルを次のように使用すること．\n",
        "\n",
        "1. 一つ目のコードセルではソースコードの編集と保存\n",
        "2. 二つ目のコードセルではコンパイル\n",
        "3. 三つ目のコードセルでは実行\n",
        "\n",
        "いずれも実行結果の出力が付いた状態で提出すること．（2.はエラーがなければ出力無しでよい）\n",
        "\n",
        "</b>\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vm6Yo9W2k-5U",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "#ソースコード"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "yK0Ukzook_HP",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "#コンパイル"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "pbNmPx7Dk_RV",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "#実行"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "TjOgrYW8lAmy",
        "colab_type": "text"
      },
      "source": [
        "---\n",
        "# 必須課題3B 幅優先探索アルゴリズムの自然言語記述\n",
        "\n",
        "<b>\n",
        "\n",
        "DataAlgo2020-004(BFS)で示している幅優先探索アルゴリズムを，日本語で過不足なくかつ簡潔に記述せよ．\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",
        "# 必須課題3C 幅優先探索アルゴリズムの計算量\n",
        "\n",
        "<b>\n",
        "\n",
        "DataAlgo2020-004(BFS)で示している幅優先探索アルゴリズムの空間計算量と時間計算量について議論せよ．(授業内で言及していた内容をまとめるだけでよい）\n",
        "\n",
        "</b>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "B9Z8A8xin-Ru",
        "colab_type": "text"
      },
      "source": [
        "（議論はここに記述）"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "NTFmAWpPnnaz",
        "colab_type": "text"
      },
      "source": [
        "---\n",
        "# 発展課題3X queue使用量とその限界\n",
        "\n",
        "<b>\n",
        "\n",
        "どのような無向で連結なグラフが指定されても，queue[]に必要な領域が頂点数を超えないことを示せ．  \n",
        "また，\n",
        "どのような無向で連結なグラフが指定されると，queue[]の使用量が（一時的にとはいえ）最大となるか理由と共に示せ．ここで最大とは，qheadとqtailが最大限離れる状況を指す．つまり，どのようなグラフが来たら，待ち行列が最大限延びる（キューに溜る）か？という設問である．\n",
        "\n",
        "（余談だがではキューが最小になる，つまり全然待ち行列が延びないようなグラフは？という設問も当然ありえる．）\n",
        "\n",
        "</b>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ljT6EzOYnUZp",
        "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/19. 初版  \n",
        "2019/05/22. ver.B  \n",
        "\n"
      ]
    }
  ]
}