Embed Size (px)
Citation preview
Ichiro Satoh
期末レポート
n 提出： 学生課提出
n 提出日： 7月26日(木）・27日(金）
n 様式（教務担当者から要請）
n 提出は紙のみ、サイズはA4縦n レポート題目は「期末レポート」としてください。
n 備考
n 提出期間に学会出張などの公務がある場合はメールで提出でもよいがそれ以外は学生課に提出すること
n なお、就職活動・インターンシップに関しては原則として認めない（指導教員から連絡があった場合を除く）
Ichiro Satoh
期末レポート（今年も同じ）
n 設問1に答えるとともに、設問2〜20から２つを選び答えなさい。n 備考：冒頭で説明したように設問１は必ず答えること。それ以外の設問は選択。文量は指定しないが、大学院期末レポートに適切な質・量があること。他の文献を参照する場合は参照元を必ず明記すること。設問は追加することがある。最新の情報を確認すること。
1. 現在研究中のシステムの動作（または研究対象の現象）のなかで、重要となると思われるサブシステムや動作をプロセス計算またはペトリネット、時相論理で記述しなさい。その際にプロセス計算またはペトリネット、時相論理では表現力不足になった部分や動作を説明し、どのよう表現性があったら解決できるかを議論しなさい。
なお、どんな（サブ）システムであるか、そのうちの何に着目して記述したのかを日本語で説明を加えること。
Ichiro Satoh
期末課題2. チューリングマシンは最も一般的な計算モデルとされる。計算能力的な観点から、チューリングマシンと現在のコンピュータとの差異を議論しなさい
3. ラムダ計算に基づいて、チャーチ・ロッサ（Church–Rosser）を証明しなさい
4. ラムダ計算における不動点コンピネータ（Yコンビネータ）により再帰計算で表現できることを説明しなさい
5. Java言語はJava 8における言語拡張においてLambda的な記述形式が導入された。また、最大手のクラウドコンピューティングであるAmazon Web Service (AWS)では、Lambdaと呼ばれるサービスが導入されている。両者について計算モデルのLambda Calculusとの類似点及び相違点について議論しなさい
注）設問２以降は暫定、追加・削除がありえる（7月10日ぐらいまでにはフィックスする）
Ichiro Satoh
期末課題（2017年度版）6. 計算モデルやプログラミング言語の意味定義は、1990年代までは表示意味論を用いることが多かったが、1990年代後半以降は操作意味論、特に構造的意味論を用いることが多くなっている。表示意味論と操作意味論の違いを説明し、近年、操作意味論を用いることが多くなった理由を２つ以上あげ、それぞれを議論しなさい
7. プロセス計算(CCS)はその意味は操作意味論（Operational Semantics）のなかでも、構造的操作意味論(Structural Operational Semantics)が利用されている。まず構造操作的意味論について説明するとともに、プロセス計算の帰納的な証明における構造操作的意味論のメリットについて議論しなさい。
8. オートマトンでは、二つのオートマトンが同じ入力列群を受理できる場合、両オートマトンは同じと扱うが（トレース等価）、プロセス計算(CCS)では、トレース等価では本来区別すべきプロセスを同じになってしまうという問題が生じる。その事例をあげるとともに、どのようなプロセスを同じと扱うべきかを議論しなさい。
Ichiro Satoh
期末課題（2017年度版）9. CCSを含めて、多くのプロセス計算は一対一同期通信が基本であり、非同期通信やマルチキャスト通信（一斉同報通信）のための記述はもっていない。その理由を述べるとともに、仮にCCSで非同期通信やマルチキャスト通信を含むシステムを記述する際にはどのようにすればよいかを議論しなさい。
10. Jan BergstrayやJan Willem Klopらによって提案されたプロセス計算にAlgebra of Communicating Processes (ACP)がある。ACPについて、CSPまたはCCSと対比しながら説明しなさい。
11. プロセス計算を用いて、手続き型プログラミング言語の意味を定義できるか、その定義例を示しながら議論しなさい。
12. プロセス計算は通信プロトコルの仕様記述の基礎として用いられることが多いが、TCP/IPなどのセッションベースの通信プロトコルの記述では不整合が生じることがあるが、どのような問題があるのかを議論しなさい。
Ichiro Satoh
期末課題（2017年度版）13. C.Hewittらにより提案されたActor計算モデルは並行計算の記述ができる。CCSなどのプロセス計算とActor計算モデルの関係を議論し、仮にActorモデルを表現するプロセス計算を作るとしたら、どのような表現性が必要なのかを議論しなさい。
14. C.A.R.Hoareの提案した並行計算モデルCSPがあり、CSPをベースにした実用的なプログラミング言語は少なくない。CSPとCCSの違いについて説明し、どうしてCCSをベースとした実用的なプログラミング言語がCSPをベースとした言語よりも少ない理由を議論しなさい。
15. Erlangの当初の設計では通信プロトコルの記述が大きな目的だった。Erlangの通信記述を中心にプロセス計算の関わりについて議論しなさい。
16. Googleが開発した言語Goとプロセス計算の関わりについて議論し、双模倣性などのプロセス計算向けの理論をGoのプログラムに利用できるかを議論しなさい。
Ichiro Satoh
期末課題（2017年度版）17. ロボットの制御用ソフトウェアにおいて、Java 8のLambda記述及び
AWSのLambdaサービス的な手法を導入することのメリットとデメリットを議論しない。
18. DNAコンピュータは、DNAの4種類の塩基を演算素子にして計算をするコンピュータの総称である。DNAコンピュータは特定のアルゴリズムに対して、その計算能力が示されている段階で、一般化された計算モデルが定式化されているわけではない。仮にDNAコンピュータの計算モデルを構築する場合、その計算モデルの要件を、一般のコンピュータの計算モデルと対比しながらまとめなさい。
19. 情報通信システム以外、例えば物流システムや金融システムをプロセス計算で記述しなさい（比較的な大きなシステムを対象として、単体の機械などは対象にしない）
Ichiro Satoh
期末課題（2017年度版）18. DNAコンピュータは、DNAの4種類の塩基を演算素子にして計算をするコンピュータの総称である。DNAコンピュータは特定のアルゴリズムに対して、その計算能力が示されている段階で、一般化された計算モデルが定式化されているわけではない。仮にDNAコンピュータの計算モデルを構築する場合、その計算モデルの要件を、一般のコンピュータの計算モデルと対比しながらまとめなさい。
19. 生物または化学の実験手順（例えば薬品を入れる、混ぜる、熱するなど）をペトリネットで記述しなさい。
20. 情報通信システム以外、例えば物流システムや金融システムをプロセス計算で記述しなさい（比較的な大きなシステムを対象として、単体の機械などは対象にしない）
Ichiro Satoh
補足
n 文量などは規定しないが、大学院の期末レポートに値する量とクオリティであること。逆に著しく量とクオリティが不十分な場合はレポートを提出した場合でも不合格とする。
