DataAlgo2020_R06.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "DataAlgo2020-R06",
      "provenance": [],
      "authorship_tag": "ABX9TyPD9rYgEND0dOHPTlT+c1Ry",
      "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_R06.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": [
        "# データ構造とアルゴリズム 第6週課題 (2020/06/10verA)\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",
        "# 必須課題6A 最短経路の表示の仕組み\n",
        "\n",
        "<b>\n",
        "\n",
        "shortest_dijkstra プログラムにおいて，それぞれの頂点への最小経路値を実現する経路を表示する仕組みを説明せよ． このとき，構造体CostFromのメンバ from に格納されている値について言及すること．\n",
        "\n",
        "\n",
        "\n",
        "</b>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "j_LNv7qr2Jcq",
        "colab_type": "text"
      },
      "source": [
        "（議論はここに記述；必要があれば図も）"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "8NUVKBVvmvtw",
        "colab_type": "text"
      },
      "source": [
        "---\n",
        "# 必須課題6B Dijkstraアルゴリズムの計算量\n",
        "\n",
        "<b>\n",
        "\n",
        "shortest_diskstra プログラムの時間計算量と空間計算量を議論せよ．\n",
        "\n",
        "</b>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "B9Z8A8xin-Ru",
        "colab_type": "text"
      },
      "source": [
        "[リンクテキスト](https://)（議論はここに記述）"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "hRiIuzTTANJ_",
        "colab_type": "text"
      },
      "source": [
        "---\n",
        "# 必須課題6C 最短経路の表示の仕組み\n",
        "\n",
        "<b>\n",
        "\n",
        "shortest_floyd Cプログラムにおいて，全ての頂点対の最小経路を表示する部分には再帰呼出関数を用いている．これについて，本プログラムが最小経路を表示している仕組みを説明せよ．特に，via[][]が格納している値について言及しながら説明すること．\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",
        "# 必須課題6D Floyd アルゴリズムの計算量\n",
        "\n",
        "<b>\n",
        "\n",
        "shortest_floyd プログラムの時間計算量と空間計算量を議論せよ．\n",
        "\n",
        "</b>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ZpaHbvVwBJha",
        "colab_type": "text"
      },
      "source": [
        "（議論はここに記述）"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "kkDbcMn8z_At",
        "colab_type": "text"
      },
      "source": [
        "---\n",
        "# 必須課題6E Dijkstraのプログラムを再利用したN対N最短経路推定プログラム\n",
        "\n",
        "<b>\n",
        "\n",
        "N対Nの最短経路問題を解くにあたって，shortest_diskstra プログラムを改良して実現して見よ．プログラム内で開始頂点を1からNまで変更しながら，dijkstraのアルゴリズムを実行するという方針である．改良したプログラムについて，時間計算量と空間計算量を議論せよ．\n",
        "\n",
        "</b>\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "dSRJ1rYt1HUe",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "%%writefile Repor6E.c\n",
        "//(プログラムをここに)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "5UaRDftA1PLC",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "!echo \"コンパイルと実行コマンドをここに（提出時に出力をつけておくこと）\""
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "jN9E7gBF2BUJ",
        "colab_type": "text"
      },
      "source": [
        "(議論はここに記述）"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "NTFmAWpPnnaz",
        "colab_type": "text"
      },
      "source": [
        "---\n",
        "# 発展課題6X 十分大きな数NC\n",
        "\n",
        "<b>\n",
        "\n",
        "shortest_diskstra プログラムや shortest_floyd プログラムにおいて，\n",
        "あるグラフが与えられた時，暫定経路値の一時的最大値と最大重み辺が分かれば，NCを決めることができる．これを正確に求めることは難しいが，アルゴリズムの趣旨を考えれば，これは正確な値である必要はない．そこで，グラフの隣接行列が与えられたとして，NCの近似値として役に立つ数字を 時間計算量 O(N^2) で求める簡単な方法を考えてみよ．\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/10. ver.A 初版  \n",
        "\n",
        "\n"
      ]
    }
  ]
}