2020年度 大学院ゼミ
2020年度 スケジュール（予定）
- 2年次3月修了（渡邉君）
- 4〜6月 論文題目の決定
- 2020年6月8日（月）～2020年6月22日（月）17:00まで（予定） 学位論文計画書の提出（研究目的と研究計画は様式の9割以上を埋めること）
cf. 【大学院】2020年度3月修了予定者の学位論文計画書の提出について - 9月26日(土) 中間審査
- 9月 電気・電子・情報関係学会 東海支部連合大会（論文投稿〆切り7月中旬） cf. 令和元年度
- 1月 修士論文の提出 例年は2020/12〜
- 1月 修士論文の審査と最終試験
- 3月 学位の授与
大学院生の全体ゼミ/連絡事項
2020/02/25
- 参加者：M2矢澤，M1渡邉
- Overleaf上にプロジェクトを作成した。
- 参考文献一覧を作成することになった。
- 渡邉君は参考文献[Moge19]を読み，文章でまとめる。
2020/05/01 15:00-
- 参加者：M2矢澤，渡邉，M1田島，欠席：吉田，資料
2020/05/04 16:00-19:00 矢澤君中間審査発表練習
- 参加者：M2矢澤，M1田島，欠席：渡邉，吉田
2020/05/08 15:00-16:00 矢澤君中間審査発表練習，研究ミーティング
- 参加者：M2矢澤，M1田島，欠席：渡邉，吉田，資料
2020/05/08 17:00-17:30 矢澤君中間審査
- 参加者：M2矢澤，M1田島，B4藤田，水野，新美，竹市，青柳，吉山，B3平工，黒川
2020/05/14 15:00-16:20
- 参加者：M2矢澤，M1田島，欠席：渡邉，吉田，資料
2020/05/21 15:00-17:00
2020/05/28 15:00-16:15
- 参加者：M2矢澤，M1田島，欠席：渡邉，吉田，資料
2020/06/04 15:00-15:40
- 参加者：M2矢澤，M1田島，吉田，欠席：渡邉，資料(田島君 調査レポート)
2020/06/09 15:15-18:45
- 参加者：M2矢澤，M1田島，吉田，欠席：渡邉，資料
- 吉田君：卒論の改訂，参考文献の調査
- 南山大学図書館の右下に「電子リソースポータル」があります。
- 田島君：発表準備
- K. Lange, P. McKenzie and A. Tapp, "Reversible space equals deterministic space," Proceedings of Computational Complexity. Twelfth Annual IEEE Conference, Ulm, Germany, 1997, pp. 45-50. URL
- Klaus-Jörn Lange, Pierre McKenzie, Alain Tapp,
Reversible Space Equals Deterministic Space,
Journal of Computer and System Sciences,
Volume 60, Issue 2,
2000,
Pages 354-367,
ISSN 0022-0000,
https://doi.org/10.1006/jcss.1999.1672.
(http://www.sciencedirect.com/science/article/pii/S0022000099916720)
2020/6/11 連絡事項
理工学研究科大学院生の学生研究室の利用が可となりました。 学生研究室においてある機材や書籍を取りに来たり， 印刷を行うことができるようになりました。
ただし，Q2においてオンラインでの指導を継続することに変わりありません。当面の間は学生研究室に来る場合は事前に私に連絡をください。
【保健室からの案内】新型コロナウイルス感染防止対策・来学時留意点メモ(202006) 『うつらない工夫 うつさない配慮 人間の尊厳のために ~南山大学~』
- 通学前には体温測定するなど体調状態に気をつけること。熱があるなど体調不良の場合は通学しないこと。
- 通学、帰宅においては朝夕のラッシュアワーなど混雑時を避けること。
- 入構した場合はソーシャルディスタンスの確保や室内の換気などを行うこと。
2020/06/16 15:15-17:30
- 参加者：M2矢澤，M1田島，吉田，渡邉，資料
- 田島くん，次回発表
- 渡邉くん，Perumallaらの可逆変換の非可逆の部分の解析 ⇒ 改善を提案，評価
2020/06/23 15:15-17:15
- 参加者：M2矢澤，M1田島，吉田，渡邉，B4青柳，資料
- 田島くんの論文紹介．
- 矢澤君，TODOを7月2日(木)までに完成させて連絡ください：
- 参考文献の形式[6], [11]を修正する
- 参照エラーになっている図表を追加する
- 3.1節の節名を更新→done
- 3.1節の数式の修正→done
- 自分の言葉で書いていることのチェック
- 中間審査の時にもらった宿題をやる
- 課題解決の考え方が説明されていない．なぜ，そのように考えたか，説明が必要．
- 提案方法のJunusの拡張が可逆性を損なわないとの見通しの根拠の説明がない． delocalがlocalと対になって保証されないことは可逆性を損なう可能性があるのではないか？ 損なわれないための前提はないのか？
- 英語のAbstract
2020/06/30 15:15-17:30
- 参加者：M2矢澤，M1田島，欠席：吉田（体調不良），渡邉，資料
- 矢澤君：教務課への修士論文の提出 と 製本用の修士論文原稿提出 について，大学へ来訪の可否
- 英語のアブストラクトを要修正：スペルチェッカーを使うこと
- Research questionsの書き方: Writing Good Software Engineering Research Papers
- 田島君：
- 学会発表「令和二年度 電気・電子・情報関係学会 東海支部連合大会」について
- LMT法の改良について（TMの追加規則数O(n)→O(1)）
- 昨年度の論文集
- 論文調査：Energy-Efficient Algorithms
2020/07/07 15:15-16:15
- 参加者：M2矢澤，M1田島，吉田，欠席：渡邉，資料
- 吉田くん，Pebbling methodの紹介を近日中に．
2020/07/14 15:15-16:45
- 参加者：M2矢澤，渡邉，M1田島，吉田，資料
- 渡邉君 8月頭くらいにスライドを準備してPerumallaの論文紹介(前半)/研究紹介(後半)，吉田先生をお招きする．8月3日 or 4日が候補．
2020/07/14 15:15-16:45
- 参加者：M2矢澤，M1吉田，B4藤田，B3平工，資料
2020/07/21 15:15-15:35
- 参加者：M2渡邉，M1田島，欠席：M1吉田，資料
2020/07/28 15:15-
- 連絡事項：オンライン授業に関連して
- 参加者：M2矢澤，渡邉，M1田島，欠席：M1吉田，資料
2020/08/04 15:15-17:50 渡邉君発表練習とゼミ
- 参加者：M2渡邉，M1田島，欠席：M1吉田，資料
2020/08/18 15:15-19:00 渡邉君発表練習とゼミ
- 参加者：M2渡邉，M1田島，吉田，資料
2020/08/25 15:15-20:10
- 参加者：M2矢澤，渡邉，M1田島，吉田，資料
2020/09/01 15:15-16:40
- 参加者：M2渡邉，M1田島，欠席：吉田，資料
2020/09/08 15:15-
- 参加者：M2渡邉，M1田島，欠席：吉田，資料
渡邉君の要旨における修正点：
全体的に ・理科系文章の書き方について基本に忠実に（例．1段落に1つの内容を．事実と意見を分ける．） 1. はじめに （背景に適切な内容が入っている。研究目的・研究課題を要改善） ・研究目的・研究課題を明確に ・研究目的・研究課題を説明するに必要な背景を書く ・論理的に 2. 関連研究 ・関連付ける 7. むすび ・「はじめに」と対応づける
理科系文章の書き方については理工学基礎演習（後半）資料も参考に。
2020/09/22 15:15-16:15
- 参加者：M2渡邉，M1田島，吉田，資料
2020/09/29 15:15-16:00
- 参加者：M2渡邉，M1田島，吉田，資料
- 田島君へのコメント：メモリ使用量がΘ(n)ではないか? →O(1)にできそう．プログラムは未完成．
次にやること：完成させる，一般化，解析． - 渡邉君へのコメント：
- 研究としては，算術符号（AC, レンジコーディングかも）の方法をまとめて有用な応用例を考えて評価をする．
- 変換対象は，制御情報がACで最適化できるもの．まず静的なものを対象とすると良いと思う．
- 直近で優先させること：有用な応用例を見つける．
- 以下は中間審査ででたコメントなので反映させること．
コメント ・問題の定義をする ・PDES,シミュレーションプログラム，Perumallaの手法の関係と本研究の範囲を明確に ・Perumallaの手法はC言語の可逆性とどう問題が異なるのか？ ・最適化が課題とすれば，その範囲を明確に ・何が，どこまで出来れば本研究の目標が達成されるのかを明確に ・題名が一般的すぎるので，本研究のスコープを適切に表現する ・関連研究を充実させる．[1]との関連． ・PDES 初出でスペルアウト ・改善手法の提案という観点で説明する． ・目的に合った評価を考えること 細かいコメント ・予稿も基本的には適切であるが、不正確な表現が散見される。 5.1章で「初期値が別の変数」と書いているが、意味が通じない。 「桁あふれ」の問題は明確に「未定義」の話として説明すべき。正確な理解のうえで、正確な表現をして欲しい。
- 吉田君へのコメント：以下を来週までに行う．
- CプログラムとJanusプログラムをリポジトリにまとめる．GitHubの「横山研のorganization」にまとめると良い．
- 力任せ法について，今週に考えた方法とクリーンな方法の両方を考える．実行時間やメモリ使用量の解析を行う．
2020/10/06 15:15-16:10
- 参加者：M2渡邉，M1田島，吉田，資料
- 渡邉君：ベンチマークを検索したが，うまくプログラムを見つけられなかった → 候補：[改訂新版]C言語による標準アルゴリズム事典，TimeWarp, BackStroke, rcc, Glueck先生らの三重ループ，以前見た乱数生成のプログラム
- n回ループする場合にゴミは何ビットになるか？算術符号を用いた場合 vs ループ回数を憶える場合(ceil(log_2 n))
- 次回までにベンチマークを1つ以上評価する．
- 田島くん
- 可逆幅優先探索の漸近的計算量を見積もったO(n)≒n/2
- local/delocalは少なくとも現在の実装上はネストしないといけない．
- pre/in/post-order traversalは新美君担当
- 基本的なグラフアルゴリズムを対象にできるか要検討：可逆計算に向いたグラフ表現，グラフの深さ優先・幅優先探索，トポロジカルソート，強連結成分
- 吉田くん
- 横山研のgithub organizationに追加できるようになった
- リポジトリに追加した → 実際にデータを入力しましょう
- KMP法とBM法（ボイヤー-ムーア文字列検索アルゴリズム）のCプログラムを定評のある教科書や論文から探す→出典を付けてGitHubにコミット．その可逆アルゴリズムを疑似コードで書く．（再来週以降にJanusで実装する．）
擬似コードの参考
2020/10/13 15:15-
- 参加者：M2渡邉，M1田島，欠席：吉田（体調不良），資料
- 渡邉君：
- ループ回数を憶える場合(ceil(log_2 (n+1)))だった
- 単純な例をいくつか調べる（cf. Landuer1961 の例，ゲート）， 単純なif, ネストしたif, 単純なswitch, 固定回数のループ（n回のループ【継続】），ループ回数が変化する単純なループ
- 算術符号（AC）法が最も有効な場合を明らかにする（正確な確率分布の見積もりができ，一様分布から「ズレ」ているもの≒確率分布が偏っているもの）
- 静的・動的な算術符号⇒まずは静的なものを中心に ただし，線形探索は動的なモデルを簡単に用いられそう
- 算術符号が有効なアルゴリズム【継続】：線形探索・整列法などの単純なアルゴリズムで見積もる，アルゴリズム事典も参考に
- 本日のメモもまとめなおす
- 田島君：
- 最悪がO(n^2)であった．AVL木だとどうなるか要検討，単純に最悪を見積もってもO(n log n)
- 【継続】基本的なグラフアルゴリズムを対象にできるか要検討
2020/10/22 11:05-13:00
- 参加者：M2渡邉，M1田島，欠席：吉田，資料
- 渡邉君：
- 単純な例を要研究
- 有効なアルゴリズム（継続）
- 「入力が一様」について文章化
- 「複数のandゲートがあれば出力を圧縮できる」←例を示す
- グラフ→連続なもの（gnupolotを用いても良い）
- -n log2(n/(n+1)) の途中式 → LaTeX
- ループの部分の文章はさらに要検討
- 【発展的でやらないこと】静的/動的なモデル構築，ハイブリッドなもの（ループの回数＋他のエントロピー）
- 今までに読んだ論文/著書の中から論文紹介をやりましょう: 例
- 情報理論のテキストを要チェック
- 田島君：
- AVL木の反復深化深さ優先探索の性能の上限と下限
- 次数1で印をつけず，次数2はルート以外に印を付けないグラフにおける可逆深さ優先探索の計算量まとめ
- 次数3以上で印の種類を増やしたグラフにおける可逆深さ優先探索の計算量まとめ→探索失敗の場合にゴミが0になる
- 印をポインタの列（または他のデータ構造，ハッシュ＋短絡したグラフ）で保持する方法の性能とメモリ使用量
2020/10/27 15:15-
- 参加者：M2渡邉，M1田島，欠席：吉田，資料
- 渡邉君：以下を調査してまとめる．残りの課題は継続．
- ``Efficient Optimistic Parallel Simulations Using Reverse Computation'' のp.233の表に掲載されている表現と提案手法の比較
- Landauer p.188 の Fig.8 に関する部分
- 田島君：
- AVL木の反復深化深さ優先探索の性能の上限と下限→厳密解を
- 他は継続
2020/11/6 15:15-
- 参加者：M2渡邉，M1田島，欠席：吉田，資料
2020/11/12 11:15-12:00
- 参加者：M2渡邉，M1田島，吉田，資料
2020/11/26 15:30-17:15
- 参加者：M2渡邉，M1田島，欠席：吉田，資料
2020/12/1 15:15-
- 参加者：M2渡邉，M1田島，吉田，資料
2020/12/8 15:15-
- 参加者：M2渡邉，M1田島，欠席：吉田，資料
- M1田島
- 田島君作成のROOPL++のオンラインインタプリタ
- （非可逆/可逆の）反復深さ優先探索 を文章にまとめる ＆ 可逆のを ROOPL++ で実装する → localとdelocalの分離が必要？
- グラフの形により，可逆深さ優先探索における印の付け方・消し方が変わる → 文章にまとめる
- グラフの形：二分木，木，スター，円，完全グラフ，．．．
- 線形探索の単純な拡張になっていることの確認
- 可逆幅優先探索(可逆反復深さ優先探索が良い?)
- 木のデータ構造に何かを付加すると効率化できる？
- 強連結成分を求める → 次解くのに良さそうな問題
2020/12/16 15:15-
2021/1/12 15:15-
- 参加者：M2渡邉，M1田島，欠席：吉田
2021/1/18 19:00-
2021/1/25 19:00-
2021/02/08 12:30-
- 参加者：M1田島，欠席：M2渡邉
2021/03/02 15:00-15:17
- 参加者: M1田島
- 来年度Q1のゼミは火15:00-を基本とする．
2021/03/02 15:00-15:17
個人
参考文献など
- 修士論文に関するお知らせ
- 「可逆グラフアルゴリズム」の参考文献
- [Masu20] 増田大輝：効率的な可逆線形探索と木構造の可逆深さ優先探索の設計と解析，南山大学2019年度修士論文 (2020)．
- [AsYa19] 浅野早紀，山口春樹：可逆な深さ優先探索，南山大学2018年度卒業論文(2019)．
- [IeMi18] 家崎雄太，水野竣太郎：可逆線形探索，南山大学2017年度卒業論文(2018)．
- [Pier02] Pierce, B.C.: Types and Programming Languages, MIT Press (2002).
渡邉くん，田島くん，吉田くんが2019年度から輪読をしているプログラミング言語理論のテキスト．プログラミング言語処理系の作成や可逆プログラミング言語の研究に直接的に役立つ．2019年度に14章まで輪読した．