Recursos de colección

Hokkaido University Collection of Scholarly and Academic Papers (135.711 recursos)

HUSCAP (Hokkaido University Collection of Scholarly and Academic Papers) contains peer-reviewed journal articles, proceedings, educational resources and any kind of scholarly works of Hokkaido University.

2010??

Mostrando recursos 1 - 20 de 116

  1. はしがき

    湊, 真一

  2. 計算ホモロジー理論とその応用

    荒井, 迅
    位相幾何学とは、空間をぐにゃぐにゃと連続変形しても不変な性質を研究する数学であり、様々な数学の分野で重要な道具となっている。近年、より現実的な問題に位相幾何学を応用するために、計算機を用いて位相不変量を計算するアルゴリズムの開発が活発になっており、本講演ではその中の一つである計算ホモロジー理論について、その基礎とセンサーネットワークの被覆問題への応用について解説する。センサーネットワークにおいては、大量のセンサー、例えば人間の存在を感知したり、温度を測定するセンサーがあちこちにばらまかれた状況を考える。このとき、センサーたちの感知領域が、正しく目的の領域を被覆しているか、すなわちどこかに見逃しがないか、という問題が重要になる。GPSなどを用いて各センサーの位置情報を求めれば計算幾何を用いることが出来るが、消費電力を小さくおさえるためには、なるべく少ない情報で解決したい。R.Ghristらの研究により、センサーネットワークから定義されるRis複体のホモロジーを計算すれば、この被覆問題を少ない情報で綺麗に記述できる事がわかったのだが、今度は「Rips複体のホモロジーをいかに小さいコストで計算するか」という問題が生じた。この問題に対し、林和則、平岡裕章両氏との共同研究で得られた、マイヤービートリス系列を用いて分散計算をするアプローチと、Ali Jadbabaieらが進めているネットワーク上のラプラシアンを用いたアプローチを紹介する。

  3. 北大版BDD/ZDDパッケージの概要 : 北大ERATOオフィスのIT系インフラ構成の現状と今後の課題について

    湊, 真一
    ERATOセミナ2010 : No.2. 2010年5月21日

  4. Chomsky-Schützenberger-Type Characterization of Multiple Context-Free Languages

    吉仲, 亮
    It is a well-known theorem by Chomsky and Sch¨tzenberger (1963) that every contextfree language can be represented as a homomorphic image of the intersection of a Dyck language and a regular language. This paper gives a Chomsky-Sch¨tzenberger-type characterization for multiple context-free languages, which are a natural extension of context-free languages, with introducing the notion of multiple Dyck languages, which also are a generalization of Dyck languages.

  5. オンラインユニットクラスタリング問題の競合比の改良

    川原, 純
    将来の入力情報が未知である状況をモデル化した最適化問題をオンライン問題という。オンラインユニットクラスタリング問題はChan らによって提案された問題であり、以下の様に定義されている。各点はd 次元のユークリッド空間上に与えられる。それに対して、アルゴリズムは(次以降の点の発生箇所が未知の状態で)d 次元の多面体を作成しなければならない。その多面体の各辺の長さは、作成した時点では0 であり、アルゴリズムは各次元ごとに単位長まで伸ばすことが出来る。アルゴリズムの役割は新しいクラスタを作成するか、過去に作成した既存のクラスタの辺を拡張して、与えられる新しい点を被覆することである。問題の目的は作成するクラスタの数の最小化である。1 次元(すなわち、d=1)の場合に対して、我々は新しい決定性オンラインアルゴリズムである、グルーピング・アルゴリズムを考案し、競合比(アルゴリズムのコストと入力が既知であると仮定したときの最適コストの比)の上限の値を7/4 (= 1.75) から5/3 (= 1.667) に改良した。

  6. Proper Interval Graphのランダム生成と列挙

    齋藤, 寿樹
    Interval Graphは,スケジューリング問題やバイオインフォマティクスなど,いくつもの応用を持つことが知られている.そのため,Interval Graphについての研究はいくつも存在し,またInterval Graph上のアルゴリズムが開発されている.実際の応用で開発されたアルゴリズムを適用する場合,そのアルゴリズムは理論的に効率がよいだけでなく,実装上効率がよいことを実験的解析によって示す必要がある.実験的に解析をするとき,テストデータに偏りがある場合,正しい解析結果を得ることができないため,偏りのないテストデータを生成する必要がある.本発表では,IntervalGraphの部分クラスであるProper Interval Graphをランダム生成や列挙するアルゴリズムを提案する.ランダム生成アルゴリズムは数え上げを用いたアルゴリズムで,n頂点の連結なProper Interval Graphを一様ランダムに生成する.列挙アルゴリズムは逆探索に基づいたアルゴリズムで,n頂点の連結なProper Interval Graphを漏れなく,重複なく出力する.

  7. データ匿名化に関する検討

    白井, 康之
    個人情報をはじめとする機微なデータから個人が特定されないようにする技術は,近年の個人の行動履歴情報の利活用の進展に伴い,特にデータマイニングの分野で注目を集めている.k匿名性をはじめとする匿名化技術は,基本的にはデータ項目の組み合わせ問題に帰着するが,匿名化されたデータの効率的な管理という側面から見れば,ZDDをはじめとしたデータベースの効率的な管理手段が必要とされる分野である.本発表では,データの匿名化が必要とされる背景や研究動向等のサーベイを行った上で,必要とされる匿名化技術の概要ならびにZDD によるコーディング手法に関する検討結果について触れる.

  8. 効率よいVF符号の設計

    喜田, 拓也
    VF符号とは、情報源系列を可変長のブロックに分割し、各ブロックに対して固定長の符号語を割り当てることで圧縮を達成する情報源符号化の一種である。入力系列(テキスト)の分割には、主に分節木と呼ばれる木構造が用いられる。VF符号は、近年、パターン照合を高速化することのできるデータ圧縮法として見直されている。しかしながら、VF符号は、符号語長が固定であるという制約から高い圧縮率を得ることが難しく、実用的な符号化方法は存在しなかった。発表者らは、これまで、テキストに対する接尾辞木をもとに、それを刈り込んだ木を分節木とすることで圧縮率の高い符号化を提案し、その改良を行ってきた。本発表では、我々の手法とその実験的評価について紹介する。

  9. Introduction to Grover Algorithm

    山下, 茂
    ERATOセミナ2010 : No.8. 2010年8月3日

  10. Grover Search and its Applications

    Choi, Byung-Soo
    ERATOセミナ2010 : No.9. 2010年8月3日

  11. じゃばら折りの一般化とその複雑さの研究

    上原, 隆平
    日本での折紙の研究は,数学的な観点からの研究が先行してきた.しかしLang,Domain,O’Rourke といった研究者の活躍により,最近computational origami という言葉が市民権を得つつある.しかし理論計算機科学としての枠組みは,まだまだ未整備である.折紙を計算機科学の対象としたときの単純なモデルとは何だろうか.ここではごく単純な折紙モデルとして,次のものを考える.入力として与えられるのは,長さn+1 の紙と,長さn のM,V 上の文字列である.ここでM は山折り,Vは谷折りを意味している.つまり長さn+1 の紙の上に,等間隔に山/谷が指定されている.この文字列にしたがって紙を折る問題を考える.まず時間計算量に対しては,折りの回数が自然に対応すると考えることができる.この観点から,じゃばら折りとその一般化に対して,講演者らは,ほぼ最適な折りアルゴリズムを設計した.では領域計算量に対応する概念は何だろうか.これに対してはみんなが合意する概念は存在しない.講演者は,折り目に挟まる紙の枚数を基準として提案し,これに関する最適化問題を研究している.部分的な解は得られているものの,まだ残された研究課題の方が多いのが実状である.

  12. 山登りは大変なので沢登りアルゴリズム

    宇野, 毅明
    山登りアルゴリズムは非常に多くの問題に対して採用されているが、極小元を見つける場合、極小元とは関係ない高い山を登り切ってしまうという意味で無駄が多くなり、効率的でなくなる。本発表では、ハイパーグラフ双対化という極小元列挙問題に対して、極小解を山の頂上にして山登りアルゴリズムを適用するというアルゴリズムを提案し、効率的な計算方法も合わせて提案する。計算実験により、本アルゴリズムは多くの問題に対して非常に効率良く動くことを示す。

  13. 分散データベースからの 頻出飽和アイテム集合のプライバシー保護発見

    山本, 章博
    水平分割され分散配置されたトランザクションデータベースに,全体として頻出する飽和アイテム集合を暗号化と組み合わせて発見する手続きを提案する.頻出飽和アイテム集合は,頻出アイテム集合の圧縮形とみなせることから,分散配置されたデータベースからのプライバシー保護発見に有用と考えられる.本講では基本アイデアを実験結果とともに報告する.

  14. 量子回路設計とは?

    山下, 茂
    量子回路で計算を行うとは,どのようなことであるのかを基本的な内容を含め説明する.また,「量子回路設計」の意味について概説する.

  15. Topological Quantum Computer のための量子回路設計問題

    Choi, Byung-Soo
    現在,注目されている「エラーに強い」量子計算のスキームであるTopologicalQuantum Computer について,その動作原理を簡単に説明した後,その設計のために必要な最適化問題に関する定式化を行う.

  16. データインテンシブな計算方法としての分散ワークフローに関する研究の紹介


    近年、コンピュータで処理すべきデータの量がムーアの法則を超える勢いで急激に増加している。このような大量のデータを処理するのに適し、かつ並列計算をあまり意識せず記述できる並列計算の枠組みとして、ワークフローというものが知られている。本講演では次のことについて発表予定である。1. ワークフローとはどのようなものか 2. GXPmake というワークフローシステムの説明と実際のデモ(Povray) 3. ファイルアクセスログと可視化について 4. ワークフローの実際の応用例をいくつか 5. 広域に散らばる計算機を使った時のワークフローのための遅延隠蔽方法

  17. スケッチソート法による全点間類似度検索

    田部井, 靖生
    近年、画像やテキストなどのウェブデーター、化合物やタンパク質などの生物学的データーなど、ベクトルとして表現されるデーターが大量に生成され、それらを効率的に処理する手法の開発が求められている。大規模データーから近傍検索を行う代表的な手法にChariker (2002) らが提案した手法がある。これは、ベクトルデーターを2点間の距離関係を保ったままバイナリデーターへと射影した後、ソートとバイナリーサーチにより近傍点を検索する手法であるが、検索速度が遅いという欠点がある。そこで、我々は複合ソート法による全点間類似度検索法を提案する。提案手法は、ソート容量が大きくなる代わりに、近傍候補の距離計算を減少させることができ、高次元データーに対して効率的に類似度検索を行うことができる。大規模画像データーを用いた実験では、最近の近傍探索法との比較により提案手法の有効性が示を示す。

  18. Challenges for a theory of visualization: what is semantic symmetry?

    Goebel, Randy
    While there is no theory of visualization, there should be. Such a theory would provide a framework to assess a variety of information visualization techniques, to understand their comparative value in helping humans to draw inferences on large data. One simple concept related to a theory of visualization is semantic symmetry, which can be considered as the property that change in one representation space (e.g., a visual vocabulary space) can be accurately propogated to another space (e.g., a numeric tabular space). We explain the idea of semantic symmetry, and its potential role in a theory of visualization.

  19. 回転によるタイリングについて

    堀山, 貴史
    タイリングは,基本図形に平行移動,回転,すべり鏡映などの単純な操作を繰り返し適用することにより,隙間なく重なりなく平面を埋め尽くすことを指す.本発表では,回転操作によるタイリングに注目し,タイリング可能な基本図形を生成する手法を示す.具体的には,90度回転によるp4タイリングと60度回転によるp6タイリングを対象とし,それぞれpolyomino(単位正方形の辺接続による図形)およびpolyiamond(単位正三角形の辺接続による図形)を基本図形とする.

  20. ハッシュを用いた高速なグラフカーネルとZDD

    比戸, 将平
    大規模グラフにおける機械学習を目的とした、スケーラブルなグラフカーネルを紹介する。その鍵は、ラベルをビット列で表現し、近接ノード集合のラベル分布を論理演算でハッシュ値とする近傍ハッシュである。2つのグラフのノード集合間で近傍ハッシュ値を比較することで、グラフ間のカーネルを構成する。計算量は高々エッジ数に線形である。実験において、近傍ハッシュカーネルは数千ノードのグラフに適用可能であることが示され、ベンチマークにおいて既存カーネルよりも良い性能を示した。また、ZDDを用いたカーネルの高速化に関してもアイデアを述べる。

Aviso de cookies: Usamos cookies propias y de terceros para mejorar nuestros servicios, para análisis estadístico y para mostrarle publicidad. Si continua navegando consideramos que acepta su uso en los términos establecidos en la Política de cookies.