京都大学ELCAS(エルキャス)

平成27年度以前のレポート

数理工学

数理工学の2016年2月6日の内容はこちら



実習指導

永持 仁 (離散数理研究室 教授)
Aleksandar Shurbevski (離散数理研究室 助教授)

チューター

田村 有為 (離散数理研究室 専攻)
黒木 智弘 (離散数理研究室 専攻)
須藤 浩明  (離散数理研究室 専攻)

ボランティア

なし

実施場所

吉田キャンパス  総合研究8号館講義室3 

実習内容

前回解説し、完成させたグラフの到達可能点を収集するアルゴリズムを復習した。そのアルゴリズムからグラフ上の任意の2点間の路を出力するアルゴリズムが作成できることを解説し、実際にPythonコードの穴埋め方式で実装してもらった。グラフ上の任意の2点間の路を出力するアルゴリズムを用いて、最大フロー問題のアルゴリズムを解くアルゴリズムが作成できることを解説し、実際にPythonコードの穴埋め方式で実装してもらった。実装したアルゴリズムを用いて、畳パズル問題から変換した最大フロー問題を実際に解いてもらった。「最大フローは最小カットの容量に等しい」ことを簡単に解説し、畳パズル問題から変換した最大フロー問題を解くだけで全探索しなくても解が保証されることを解説した

前回解説し、完成させたグラフの到達可能点を収集するアルゴリズムを復習。
前回解説し、完成させたグラフの到達可能点を収集するアルゴリズムを復習。


受講生の感想

  • 適当な道を、一本取ってからやっていっても、同じ道を2回通ることでもとの向きに戻すことで最後には、ちゃんとした道が分かるというのはすごいなと思った。
  • すごく理解できてよかったです。なぜ裏返すのかが最初分からなかったんですけど、TAさんに教えてもらったので理解できました。どんなところで応用されているのかが知りたいと思いました。楽しかったです。ありがとうございました。
  • タイルを2部グラフに変換することにまず驚き、見つかったパスを反転させることにさらに驚いた。こんなこと、どうやって思いつくのか…そして、改めてアルゴリズムの威力を思い知らされた。最小カット最大フローは、よく吟味してみようと思った。
  • 単純に並べていくのとアルゴリズムを使うのではこんなにも大きな時間差ができることは聞いていたが、実際にやってみると予想以上に計算速度が上がったのでアルゴリズムのすごさに驚きました。
  • 思いもしない考え方が色々出てきて理解に少し時間がかかったが面白いと思った。
  • Pythonでコードを疑似的に組み立てることで、コードの書き方が少しずつ分かるようになってきた。また、枝の向きを逆にすることで最大値に近づくという考え方が面白いと感じた。
  • 一度通った経路は逆行できるようにする→2度通る道は通っていないもとの状態のもどるという考え方で経路を割り出していく方法は鮮やかだなと思いましたが、どうしてそれで割り出せるかなと不思議にも思いました。発表では説明できるようにしたいです。
  • 離散数理の中身がかなりつかめるようになってきました。今までさっぱり分からなかった内容も。今回のプログラミング等を通して分かるようになってきました。次回のELCAS合宿に向けて、これまでに履修してきたものを整理しておきたいです。

平成27年度以前の
実施レポート

平成28年度以降の
実施レポート