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

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

数理工学

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



実習指導

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

チューター

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

ボランティア

なし

実施場所

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

実習内容

 前回完成させた最大フロー問題を解くアルゴリズムを用いて、畳パズルの問題サイズが非常に大きなものを解いてもらった。畳パズル問題を再帰的アルゴリズムで解いた場合に対して最大フロー問題を解くアルゴリズムを利用して解いた場合は、計算時間が大きく削減できることを解説した。畳パズル問題だけでなく、座布団パズル問題、防水シート問題、暖房マット問題や長方形への分割問題がグラフへ変換することで最大フロー問題を解くアルゴリズムを利用して解けること及びグラフに関する問題である監視カメラ配置問題をグラフを少し加工することにより最大フロー問題を解くアルゴリズムを利用して解けることを解説した。明日の発表に向けて、スライド作りを行った。

畳パズル問題を再帰的アルゴリズムで解いた場合に対して最大フロー問題を解くアルゴリズムを利用して解いた場合は、計算時間が大きく削減できることの解説。
畳パズル問題を再帰的アルゴリズムで解いた場合に対して最大フロー問題を解くアルゴリズムを利用して解いた場合は、計算時間が大きく削減できることの解説。

畳パズル問題だけでなく、座布団パズル問題、防水シート問題、暖房マット問題や長方形への分割問題がグラフへ変換することで最大フロー問題を解くアルゴリズムを利用して解けることの解説。
畳パズル問題だけでなく、座布団パズル問題、防水シート問題、暖房マット問題や長方形への分割問題がグラフへ変換することで最大フロー問題を解くアルゴリズムを利用して解けることの解説。


受講生の感想

  •  床をグラフに置き換えることで、4つのパズルが解けるのはすごいと思った。また、4つのパズルも見方を変えることで他のグラフとの関係が見えてくる。監視カメラの問題は入り口、3つと目的地2つでパズルと少し異なるが、グラフをうまく、つけ加えることで、パズルと同様に解ける。
  •  今回は、3時間ぐらいスライドを作りました。役割分担ができたので思っていたより順調です。明日は発表ですが、堂々と楽しく発表できるように頑張りたいです。今回がラストで悲しいですがとても楽しかったです。
  •  いろいろな問題がグラフの問題にできるということが分かった。最小カット・最大フローを使えば色々な問題が同値であることが分かる。
  •  今日はほとんどスライド作りだったので、自分で考えることが多く大変でした。エルキャスは、自分が今まで知らなかったことをたくさん教えてもらえてとても楽しかったです!明日の発表頑張りたいと思います。
  •  入り口が3つあるのを始点を1つにするためにどうすればよいかについて別に点をつくって入り口に矢印を伸ばせばいいことは思いついたがそれが3本だと限定要因になってしまうことの解決策は思いつかなかった。
  •  今回は畳パズル・座布団パズル問題に関連した様々な問題を取り扱い、また、Powerpoint資料の作成を行った。明日の発表会に向け、全8回の講義で学習したことを他の受講生に伝えられるように頑張りたい。
  •  畳パズルの問題の考え方が他の問題(座布団、防水ネット、…)にもそのまま応用できることが分かりました。資料作りでは慌ただしくなりましたが学んだことをきちんと伝えられるようにがんばります。
  •  最終回で、スライド作りがメインとなりました。今までやってきたことをまとめる際にも、数理最適化について再発見がありました。明日は良い発表ができればと思います。

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

年度別の実施レポート