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

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

数理工学

数理工学の2016年1月23日の内容はこちら

実習指導

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

チューター

田村 有為 (離散数理研究室)
何 飛   (離散数理研究室)
須藤 浩明 (離散数理研究室)

ボランティア

なし

実施場所

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

実習内容

 前回解説し、Pythonで実装した畳パズル問題に対する再帰的アルゴリズムを完成させた。そのアルゴリズムを用いて色々な問題例を解いてもらい、計算時間が問題の大きさに対して指数的に増加していることを体感してもらった。次に畳パズル問題は最大フロー問題に変換できること及び最大フロー問題のアルゴリズムに必要なグラフの到達可能点を収集するアルゴリズムを解説した。解説したグラフの到達可能点を収集するアルゴリズムを実際にPythonコードの穴埋め方式で実装してもらった。

受講生の感想

  •  畳を点と矢印のグラフに置き換える考え方で、考えたアルゴリズムが他にも応用可能ということが面白いと思いました。プログラムも文法的に知らなかったところを除けば何をしてるのか分かってコードがかけたので良かったです。
  •  何を目的としてやっているのか、ということがとてもよく分かりました。プログラミングはまだまだだけど最適化の方法を簡単な所から教えてもらったので充実し達成感がありました。何より楽しかったです。後残りわずかで悲しいですが上達できるように努めたいと思います。よろしくお願いします。
  •  やっとPythonの使い方に慣れてきたかと思います。色々な「型」を応用してプログラミングすることで思い通りにいったりしますが、思いもよらないところでエラーが起こったりとまだまだな一面もあります。elcasも残すところあと2回となったので、発表に向けて着々と準備を進めていきたいです。
  •  自分が書いたプログラムでエラーばかり出て心が折れそうでした。次回は動かせるように頑張りたいと思います。
  •  畳を敷く問題が二部グラフがで表せることに感動した。畳と座布団の関係も面白いと思った。
  •  畳パズルを単縦な方法(しらみつぶし)で解こうとすると、問題のデータ量増加に伴い膨大な時間がかかるようになってしまうことが分かった。また、最大フロー問題とこれらのパズルの関連性が分かりよかった。

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

年度別の実施レポート