Computer Science Seminar


[ ObjectivesSchedulePast CollaborationsDept.of Info. Sci.Sci. Univ. of Tokyo日本語版 ]

o  This Seminar's Objectives


This seminar is a forum for presenting the latest research or discussing with each other in the Noda cumpus students and researchers.

Even if you don't complete your researches, you can present or discuss with us freely on the seminar.

This seminar will be held on every Tuesday.

The bachelor degree students are also welcome.

If you have any comments or suggestions, please contact to Yasushi `yas' KODAMA.


o  Schedule


*17th presentation.
12/14/99 (Tue) : From: 14:40 To: 16:40
Title: 『未定』, Speaker: Prof. M. Ohya
Place: Meeting room 3 for graduate school staffs, Computing science frontier bldg. 2F
Abstract
未定


o Past Collaborations


*1st presentation.
4/20/99 (Tue): From: 14:00 To: 16:10
Title:『岩波情報科学辞典のオンライン化』, Speaker: Prof. OKUNO
Place: Meeting room 3 for graduate school staffs, Computing science frontier bldg. 2F
Abstract
岩波情報科学辞典は、長尾真氏 (京大学長) が考案した用語の木を概念表現と して編集されている。 我々は、岩波情報科学辞典をインターネットのポータルサイト (ネットサーフィ ンの入口) として使用することを目指して研究してきた。

ここでの研究課題としては、

  1. 統一的にマークアップするためのシステムアーキテクチャの設計、
  2. ポータルサイトへの入口となる任意のテキストに対するマークアップ技法、
  3. ポータルサイトから出ていく外部参照のためのリンク作成、
  4. 情報提示方式、例えば、提示文体の変換.
などがあげられる。

これらに対して、

  1. 用語の木に基づいた任意のテキストをマークアップするルーティンの実装、
    形態素解析によるものとパターン照合によるものとの比較、
  2. 岩波情報科学辞典を用語の木で (自分自身で) マークアップして、HTML 化、
  3. UNIX マニュアルから岩波情報科学辞典への自動リンク、
  4. CPU のデータパスの説明用 Java システムから岩波情報科学辞典へのリンク、
  5. 外部参照はテーブル駆動型で実現、
  6. 文体変換 (例, 常体から丁寧体) のマクロを使用した自動化
などを行ってきた。

現状と残された問題を報告するとともに、さらには、今後の課題について議論する。

なお、本研究は佐藤理史氏(北陸先端科学技術大学院大学)と磯崎秀樹氏 (NTTコミュニケーション基礎研究所)との共同研究である。

*2nd presentation.
1999 年 4 月 27 日 (火):13:00 〜 14:30
題:『Zero-Cost Beowulf-Class Cluster の構想』、話者:奥乃、
題: 『Beowulf-Class Cluster の紹介と研究テーマ』、話者:松澤 (武田研M2)
場所: 計算科学フロンテイア棟2階大学院共通研究室3
概要
スーパコンピュータの新しい構築方法として、ワークステーションのネットワーク (Networks of Workstation, NOW) が注目を浴びている。本講演で紹介するのは、 Beowulf-Class Cluster と呼ばれる NOW である。Beowulf-Class Cluster は、 Linux を搭載した PC をノードとして、ノードを結ぶ相互結合網を Ethernet あるいは Fast Ethernet を使用したクラスターであり、 並列化には TCP/IP 上の PVM (Parallel Virtual Machine) あるいは MPI (Message Passing Interface) を用いる。

本発表では、奥乃が学内にある使われていない (少なくとも深夜) PC をノードとして、 Zero-Cost で Beowulf-Class Cluster を構築し、スーパコンピューティング、 あるいは、並列分散処理のテストベッドとする構想について述べる。

さらに、松澤が Beowulf-Class Cluster のサーベイを行い、取り組むべき研究課題について、報告する。

*3rd presentation.
1999 年 5 月 11 日 (火):13:00 〜 14:30
題: 第2回の続き:『Beowulf-Class Cluster の紹介と研究テーマ』、話者:松澤 (武田研M2)
場所: 計算科学フロンテイア棟2階大学院共通研究室3
概要
並列分散実行のための、PVM (Parallel Virtual Machine) や MPI (Message Passing Interface) の紹介.
*4th presentation.
1999 年 5 月 18 日 (火):13:00 〜 14:30
Title:『並列オブジェクト指向環境とその記述言語』、話者:児玉
Place: 計算科学フロンテイア棟2階大学院共通研究室3
Abstract
我々がこの数年をかけて構築している「やゑ」(Yet Another Window Environment) を中心としたプロジェクトの概要から、その設計方針,現状について紹介する. 「やゑ」は,現在のところ,PC上で動作する並列オブジェクト指向オペレーティング システム環境である.その記述言語(システム記述言語)もオリジナルで,並列 オブジェクト指向モデルに基づいた言語である.

更に,「やゑ」は、現在開発中の環境であるが、我々は Java を用いてその将来を 想定したシステム作りも進めている.「より柔軟なプログラミング環境を構築 する方法を模索する」ため,仮想空間の構築,提案するコンポーネントアーキ テクチャによる仮想空間の再構築などの研究についても紹介する.

  1. Yawe: Yet Another Window Environment
  2. Virtual Community
  3. Reflective Concurrent Component Architecture
  4. A Polymorphic Concurrent Object-Oriented Language
を紹介する.
*5th presentation.
1999年 5 月 25 日 (火):13:00 〜 15:00
題: エージェントの心的状態の形式化について、話者:杉本
場所: 計算科学フロンテイア棟2階大学院共通研究室3
概要
状況に応じて柔軟に動作し,他のエージェント (人間を含む) と協調的に振舞う エージェントシステムを設計するためには, エージェントの内部状態に相当する信念,意図などの心的状態の性質を よく理解する必要がある. 従来,心的状態は主に様相論理を用いて定式化されてきたが, 様相の限量化や意図などの非正則様相の扱い,非単調性など 残された課題も多い.

我々はこれらの課題に対処するために,選好 (preference) の概念を用いて 様相論理を拡張した心的態度の論理を提案した. この論理において可能世界は確からしさと望ましさという二つの尺度によって 順序付けられ,これらの順序関係を用いて信念と意図の概念が定義される. その結果,望ましい性質を満たすことが示された. さらに,この論理を使って協調的なプラン生成やプラン認識における ヒューリスティックな推論規則の分析を行った.

本発表では,この心的態度の論理について紹介し, そのプラン生成,認識への応用について述べる.

*6th presentation.
1999 年 6 月 1 日 (火):13:00 〜 15:00
題:『リフレクションを導入した並列論理型言語 RKL1 の実装と評価』、話者:武田
場所: 計算科学フロンテイア棟2階大学院共通研究室3
概要
当研究室で開発したリフレクションを導入した並列論理型言語 RKL1 の有効性 を検証するため,RKL1 コンパイラを実装しその評価を行った.

RKL1 は, 第五世代コンピュータプロジェクトで開発された並列論理型言語KL1 にリフレクションを導入したプログラミング言語である. KL1 はストリーム通信を基礎とした AND 並列の論理型言語GHCを核に,OSやア プリケーションを記述するための機能拡張を施した言語である. KL1 はデータフロー同期,小粒度並列プロセス,非決定性という特徴を備え, LSI 配線,論理シミュレーション,法的推論,定理証明系,演繹データベース などの並列アプリケーションの記述に用いられている.

並列論理型言語KL1へリフレクション機構を導入した RKL1 においては, メタレベルコードのモジュール化が可能となり,KL1プログラムの記述しやすさ が向上する.RKL1 において導入したリフレクション機構では, リフレクションをボディ実行部に制限したため, メタレベルとベースレベルに分割して記述したプログラムを, これらを合成したKL1プログラムへコンパイルすることができ,効率の良い実行 が可能である.

本発表では,KL1 の基本概念の紹介からはじめて,RKL1 コンパイラの実装方法 を示し,動的負荷分散プログラムを例に,本リフレクション機構の有用性を 評価する.

*7th presentation.
1999 年 6 月 8 日 (火):13:00 〜 15:00
題: コード移動:その効果と問題点、話者:滝本
場所: 計算科学フロンテイア棟2階大学院共通研究室3
概要
通常のコンパイラは,単にプログラムを機械語に変換すると いう役割だけ でなく,より効率的に実行可能な目的コードあるいはより小 さいサイズ の目的コードを生成するという付加的な役割をもっている. このより優れたコー ドへの変換をコード最適化という.コード最適化は古くから 研究 が行われてきたが,ここ10年の間,コード移動に基づくコー ド最適化の 重要性が注目され,この分野に関して多くの研究成果が発表 された.

本発表の前半では,コード移動に基づく様々なコード最適化 手法を紹介し,そ の効果について説明する.同時に,コード移動における共通 の問題点につ いても明らかにする.後半では,コード移動における問題へ の最近の取組 みを,滝本,原田の研究成果を交えて説明する.

*8th presentation.
1999 年 6 月 15 日 (火):13:00 〜 15:00
題: 並列実行可能な関数型言語 Linear CHAML の設計、話者:佐藤(山田研 D2)
エピソード1: 型付きλ計算の古典線形論理の計算的解釈への埋め込み
場所: 計算科学フロンテイア棟2階大学院共通研究室3
概要
Linear CHAM を Abstract Machine とした関数型言語 Linear CHAML の 設計を試みることがメインテーマであるが,研究がそこまで進んでいないので, 今回は,型付きλ計算を古典線形論理の計算的解釈へ 埋め込めることを示し,型付きλ計算の並列実行可能な評価器が 作れることを示すことにする.

Girard の古典線形論理(CLL)は 並列計算の新しい理論的基盤を与えるとして期待されている. Abramsky は古典線形論理におけるカット除去に対応して, proof expression と Linear CHemical Abstract Machine(CHAM) からなる計算体系を提案した. 一方,直観主義論理(IL)は CLL に埋め込めることが知られているので, 型付きλ計算をこの計算体系に埋め込むことができる. 本研究では,型付きλ計算の call-by-value 評価に対応する簡約が Linear CHAM によって行えることを示す. Linear CHAM の簡約は並列に実行できるので,この結果から, 型付きλ計算の並列実行可能な call-by-value 評価器の設計が 可能となる. また,関数型言語は型付きλ計算をもとにして作られていることから, 並列実行可能な関数型言語(Linear CHAML) の設計の見通しを 立てることができる.

発表の前半では,型付き関数型言語と型付きλ計算, 型付きλ計算とその性質,型付きλ計算と IL との関係, CLL と Abramsky による計算的解釈, IL を CLL に埋め込めることを説明する.

後半では,型付きλ計算の call-by-value 評価戦略におけるβ簡約が どのような形で CLL の計算的解釈に埋め込まれているのかを示す.

最後に,まだ prototype ではあるが, 型付きλ計算に定数をいくつか加えた計算体系 PCF を CLL の計算的解釈へ埋め込むという方法から設計した 関数型言語 Linear CHAML ver0.003 の紹介を行う. また,Linear CHAML をλ項の解釈器として使った場合に, どの程度の簡約を必要とするかを他の実装と比較し, Linear CHAML の性能を議論することにする.

*9th presentation.
1999 年 6 月 29 日(火):13:00 〜 15:00
Title:『コンピュータネットワークの安全性』、話者:奥乃
Place:計算科学フロンテイア棟2階大学院共通研究室3
Abstract
インターネットの利用者が増大し, さらに, 利用者層が拡大するに 伴って, さまざまなコンピュータ不正アクセスが社会的な問題を引 き起こしている. 本発表では, コンピュータネットワークの安全性 について, 現状を概観し, 問題点を議論する. この中で, 安全性と は何か, コンピュータネットワークの脆弱性はどこに潜んでいるの か, どのような対策が可能なのか, ファイアーウォールの利用法, 暗号の利用法, 新しい機密性の保持方法などにも言及する.

Bio.

  1. 1984年9月, JUNET ボランティア開始. (JUNET が点から線へ)
  2. 1992年2月には日本国憲法を html 化し, Line mode WWW で提供. (日本初)
  3. 1994年6月, 日本ソフトウェア科学会ホームページ提供開始. (日本初)
*10th presentation.
10/5/99 (Tue): From 13:00 To: 15:00
Title: 『新情報処理開発機構(RWCP)におけるクラスタシステム ソフトウェア研究』, Speaker: TAKAHASHI (RWCP)
Place: Meeting room 3 for graduate school staffs, Computing science frontier bldg. 2F
Abstract
技術研究組合 新情報処理開発機構 並列分散システムソフトウェアつくば研究 室では 1995 年より市販ワークステーションや PC によるクラスタシステム上のシ ステムソフトウェアの研究を推めている。本発表では並列分散システム研究、 クラスタ研究のトレンドについて概観したうえで、当研究室において研究開発 されたクラスタシステムソフトウェア 「SCore クラスタシステムソフトウェア」 を紹介する。

SCore クラスタシステムは、高性能通信ライブラリ PM、ギャングスケジューリ ングをサポートする並列オペレーティングシステム SCore-D、ソフトウェア分 散メモリシステム SCASH、SMP クラスタもサポートした MPI ライブラリ MPICH-PM/CLUMP、マルチスレッドプログラミングのための C++ テンプレートラ イブラリ MPC++ MTTL、並列プログラミング環境をサポートするために C++ ソー ス to ソース変換環境を提供する MPC++ コンパイラなどから構成されている。本 発表ではこれらの構成について紹介するとともに最新の成果やこれからの研究 開発についても述べる。

SCore クラスタシステムは各方面の研究所や大学に無償で配付されており、い くつかの研究グループは、このシステムを用いたうえで成果をあげている。当 機構 並列応用つくば研究室、三菱電機産業システム研究所、ドイツ ボン大学、 米国立ロスアラモス研究所 などにおける取り組みなども紹介する。

また、当研究室において、ソフトウェア研究のプラットホームとして、これま で開発し使用してきたクラスタシステム、 RWC Workstation Cluster(Sun SS20 * 36)、RWC PC Cluster I(Pentium 166MHz * 32)、RWC PC Cluster II (Pentium Pro 200MHz * 128)、RWC Alpha Cluster I(Compaq Alpha 21164 * 32)、COMPaS II(Quad Pentium Xeon 2 450MHz * 8)などや現在開発中のクラス タシステムも紹介する。

*11th presentation.
10/12/99 (Tue): From: 13:00 To: 15:00
Title: `Verification of the security protocol', Speaker: SAITO
Place: Meeting room 3 for graduate school staffs, Computing science frontier bldg. 2F
Abstract
現在、ネットワークセキュリティ技術の要となる様々な認証プロトコルが提案 されているが、我々はその認証プロトコルの安全性を検証する体系的な方法論 に興味を持っており、本発表ではその方法論の一つを紹介し、その方法論によっ て得られることを話す。

論理体系を使った認証プロトコルの検証において広く知られたものに BAN Logicのそれがある。この BAN Logic は、一般に、安全性の検証というよりむ しろ認証自体が正しく行われているかを検証する体系と見倣されている。しか し、我々はこの体系に対しある解釈を持たせたパラメタを導入することにより BAN Logic の検証の可能性を高めた。つまり、このパラメタ化した BAN Logic によりある認証プロトコルのセキュリティホールが存在する可能性を示す試み を行った。

本発表では具体的に、Needham-Shroeder 公開鍵認証プロトコルをターゲッ トに我々の手法でセキュリティホールの存在可能性を示し、G.Lowe により修 正されたプロトコルと我々が独自に修正したプロトコルの比較検討を行う。

また,時間があれば,公開鍵暗号方式に基づく技術を広範囲に用いるための技 術的および社会的基盤であるPKI(Public Key Infrastructure)の入門から現 状までを発表する。

このPKIとは、昨今の電子商取引やSSLなどの要であり、欧米などでは技術 的、法的整備などが整い政府レベルで実用化されている。 また、日本でも2000年の電子証明法制定などに向け活発な動きがある。

*12th presentation.
10/19/99 (Tue) : From: 13:00 To: 15:00
Title: 『量子コンピュータの仕組み』, Speaker: Prof. UESAKA
Place: Meeting room 3 for graduate school staffs, Computing science frontier bldg. 2F
Abstract
量子コンピュータ(QC)は超高速性を備えた 新しいタイプの計算機として期待されているが, 「量子」という形容が付いていることから, 特に情報畑の人々には, 近づきにくいという印象を与えているかも知れない. この談話会ではそうした壁を取り払うことを目的として, QCのからくりをできるだけ平易に紹介したい. 前半では
・QCと古典(現代の)コンピュータとの本質的な相違
・QCでのプログラミングの様子
をお話しし, 後半では,時間の範囲内で,QCの超高速性をかいま見ることの できる例として
・ファイル検索をするQC
・整数を因数分解するQC
を紹介する.

ちなみに,整数の因数分解は,現在知られている最も速い アルゴリズムでもほぼ指数関数のオーダの計算時間が掛かると いわれており,このことが公開鍵暗号などの安全性の 根拠になっている.ところが数年前に多項式オーダで 因数分解をするQC(のアルゴリズム)が発見され, 世間をあっと驚かせたが,これが契機となってQCの研究と 論文が爆発的に増大しているのが現状である.(以上)

*13th presentation.
10/26/99 (Tue) : From: 13:00 To: 15:00
Title: 『オブジェクト指向の進化/発展』, Speaker: Dr. Nakatani (SLagoon)
Place: Meeting room 3 for graduate school staffs, Computing science frontier bldg. 2F
Abstract
オブジェクト指向はソフトウェア工学,データベース, プログラミング言語といった様々な分野から同時発生的に提案された ソフトウェア構成法である.1990年代はJavaや高度なGUIなどの 一般化によって,オブジェクト指向の成長期となった.この10年間に, 方法論の淘汰があり,モデルの表記法の統一が進み,デザインパターン などの抽象部品の再利用も提案され,実用化されるようになった.

本講では,ソフトウェア工学的観点からオブジェクト指向の 簡単な概要を紹介し,再利用の歴史からソフトウェアパターンの 意義について議論する.さらに,ソフトウェアの進化/発展 という観点から,オブジェクトの進化を定量的に観測した 研究成果を紹介する.

話題:

  1. オブジェクト指向概要
  2. ソフトウェア工学からみたオブジェクト指向の意義
  3. 再利用の歴史からみたソフトウェアパターン
  4. 定量的進化パターンの観測
*14th presentation.
11/9/99 (Tue) : From: 13:00 To: 15:00
Title: 『実行時プログラム特化技術とその Java バイトコード上での実 現』, Speaker: H. Masuhara (Tokyo University)
Place: Meeting room 3 for graduate school staffs, Computing science frontier bldg. 2F
Abstract
一般的に書かれたプログラムから、特定の用途に特化されたより高 速なプログラムを生成する技術として部分計算(partial evaluation)が知られている。部分計算は、プログラムの一部のパ ラメータについての計算を先に実行し、残りの部分からなるプログ ラムを合成することで特化されたプログラムを生成する。

近年、プログラムの特化を(1)cogen と呼ばれる専用の特化プログ ラムを生成しておき、(2)予め用意しておいたバイナリコードの断 片を配置することで、特化プログラムを生成する実行時特化技術が 注目されている。この技術ではプログラムの実行中に得られた情報 を用いて特化することが可能になるため、より広範なプログラムを 特化できることが期待されている。

本講では部分計算と実行時特化技術の概略を紹介し、さらに、話者 が最近の研究である実行時特化の改良について紹介する。これは、 Javaバイトコード上で実行時特化を行うことで、特化されたコード の質を向上させるものである。

*15th presentation.
11/16/99 (Tue) : From: 13:00 To: 15:00
Title: 『認証プロトコルの検証とツールの紹介』, Speaker: K. Tsukimura
Place: Meeting room 3 for graduate school staffs, Computing science frontier bldg. 2F
Abstract
インターネットなどのネットワークへの依存が高まるにしたがい, 通信の盗聴や計算機への不正侵入といった脅威がとりざたされている. そういった中で計算機におけるネットワーク利用の安全性を高めるため, 認証プロトコルがある.

しかし,認証プロトコルの設計に誤りが存在した場合,その目的である 通信相手の認証ができているとはいえない.その誤りによって, 本来アクセスを許可されていない者が自分を偽ってアクセス可能にする, といったセキュリティホールが生じる.正しいと長年信じられていた 認証プロトコルに対して,後年,セキュリティホールがあることが示された. 一見,正しいと思われるプロトコルにもセキュリティホールが 存在するのである.そこで認証プロトコルに対する形式的検証・解析が 要求される.ただし,我々の検証する対象は暗号アルゴリズムや ハッシュ関数などの基礎的な要素でなく,それらを用いて構成される 認証プロトコルそのものである.

今回は,検証の手順を示し,グラフィカルユーザインターフェースを 備えた自動解析ツールの簡単な紹介をする. また,例として TMN プロトコルを検証・解析した結果を示す.

*16th presentation.
11/30/99 (Tue) : From: 13:00 To: 15:00
Title: 『モバイルエージェント』, Speaker: Prof. I. Sato
Place: Meeting room 3 for graduate school staffs, Computing science frontier bldg. 2F
Abstract
モバイルエージェントは、ネットワーク上のコンピュータを移動しながら処理 を進めるプログラムである。その特徴として、プログラムコードだけではなく、 プログラムの実行状態、つまり変数内容なども同時に移動し、その移動先では 移動前の実行状態から処理を再開することができる。このモバイルエージェン トは次世代の分散処理技術と注目され、幾つかの実現システムや応用事例が 提案・実装されている。

 本講ではモバイルエージェントの概略をデモととともに説明し、その実現技 術についても幾つか紹介する。また、談話者の最近の研究である階層的なモバ イルエージェントについても紹介する。これは、モバイルエージェントをソフ トウェアコンポーネントととして利用可能にするとともに、計算環境に対する 動的適応性を導入するものとなる。


0:0 0:0 in JST. *** since Apr 17 1999.


Last update: Sat Apr 17 11:05:34 1999 by hgo
Copyleft (C) 1999 Computer Science and Artificial Intelligence Laboratory. All wrongs reserved.