DataAlgo2020_R05.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "DataAlgo2020-R05",
      "provenance": [],
      "authorship_tag": "ABX9TyNyEPEHEvNMnF3drgoiiKhw",
      "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_R05.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": [
        "# データ構造とアルゴリズム 第5週課題 (2020/06/03verA)\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",
        "# 必須課題5A topologicalsorting_J の計算量\n",
        "\n",
        "<b>\n",
        "\n",
        "(G.Colabの006中の) topologicalsorting_J の時間計算量と空間計算量について議論せよ．その計算過程（根拠）も示すこと．\n",
        "\n",
        "\n",
        "</b>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "mRLPlzcHmhiQ",
        "colab_type": "text"
      },
      "source": [
        "（議論はここに記述）"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "8NUVKBVvmvtw",
        "colab_type": "text"
      },
      "source": [
        "---\n",
        "# 必須課題5B longestpath_J の計算量\n",
        "\n",
        "<b>\n",
        "\n",
        "(G.Colabの007中の) longestpath_J の時間計算量と空間計算量について議論せよ．その計算過程（根拠）も示すこと．\n",
        "\n",
        "</b>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "B9Z8A8xin-Ru",
        "colab_type": "text"
      },
      "source": [
        "（議論はここに記述）"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "hRiIuzTTANJ_",
        "colab_type": "text"
      },
      "source": [
        "---\n",
        "# 必須課題5C トポロジカルソーティングにける閉路の存在\n",
        "\n",
        "<b>\n",
        "\n",
        "トポロジカルソーティングに与えるグラフには閉路が存在してはならない． その理由を説明せよ．\n",
        "\n",
        "</b>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "q4ZmHSMKBGDd",
        "colab_type": "text"
      },
      "source": [
        "（議論はここに記述）"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "sh-BC5I0A0ye",
        "colab_type": "text"
      },
      "source": [
        "---\n",
        "# 必須課題5D 最長経路問題のおける閉路の存在\n",
        "\n",
        "<b>\n",
        "\n",
        "最長経路問題において，与えるグラフには閉路が存在していないと仮定した．そのことに必然性があるかどうか議論せよ．\n",
        "\n",
        "</b>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ZpaHbvVwBJha",
        "colab_type": "text"
      },
      "source": [
        "（議論はここに記述）"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "NTFmAWpPnnaz",
        "colab_type": "text"
      },
      "source": [
        "---\n",
        "# 発展課題5X トポロジカルソーティングにおける閉路の扱い\n",
        "\n",
        "<b>\n",
        "\n",
        "topologicalsorting_J プログラムでは，実際には閉路が含まれるグラフを与えても実行すると結果が出てしまう．これは，閉路があるとトポロジカルソーティングができないはず，ということと矛盾する．\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/06/03. ver.A 初版  \n",
        "\n",
        "\n"
      ]
    }
  ]
}