著者

浅野 哲夫 セルゲイ ベレグ

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告. AL, アルゴリズム研究会報告 (ISSN:09196072)

巻号頁・発行日

vol.2013, no.20, pp.1-8, 2013-05-10

---

n画素からなる2値画像が与えられたとき,連結成分ごとに異なる整数ラベルを付ける問題に対して新たなアルゴリズムの枠組みを与える.O(n)の作業領域が利用できるならO(n)時間でラベル付けは可能である.ここでの問題は,実行時間を余り増やさずに作業領域を削減できるかである.本文では,省メモリのアルゴリズムを提案する.具体的には,入力画像は読み出し専用メモリで与えられるものとし,O(√n)の作業領域だけを用いてO(n log n)時間でラベル付けを行うアルゴリズムを提案する.さらに,応用についても述べる.

著者

早川 裕真 浅野 哲夫

雑誌

研究報告アルゴリズム(AL)

巻号頁・発行日

vol.2015-AL-152, no.8, pp.1-8, 2015-02-24

---

近年では社会の複雑化に伴って,より巨大なグラフに対する最短経路問題の解決が求められるようになってきている.しかし,巨大なグラフに対する最短経路問題を実際に計算機上で解くためには,グラフの大きさに比例した多くのメモリが必要になる.本研究では,平面上の最短経路問題を解く実用的でメモリ効率の良いアルゴリズムの開発を行う.また,現場では障害物をある対価を払って通過することがあり,そのような障害物に重みがついている場合への拡張も行う.

著者

Boris Aronov 浅野哲夫 菊地洋右 SubhasC.Nandy 笹原 慎司 宇野 毅明

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.2005, no.26, pp.63-69, 2005-03-17

参考文献数

2

---

n×nの行列に整数0 ... n2-1を配置し、どの行和、列和も等しいものをsemimagic squareとよばれる。ここでは列和、行和のかわりにk×kの部分行列に含まれる要素の和を考え、この和が等しいn×n行列をzero k×k-discrepancy matrixとよぶ。そしてこのような行列はkとnがともに偶数であるとき存在し、kとnが互いに素であるとき存在しないことを示す。さらに、k m●2を整数としたときn=k*であるならばzerok×k-discrepancy matrix の存在がいえる。このzero k×k discrepancy matrixの恒星にはconstant-gap matricesを用いる。また、constant-gap matricesの特徴づけを行なう。A semimagic square of order n is an n×n matrix containning the integers 0,...,n2-1arranged in such a way that each row and column add up to the same value.We generalize this notion to that of a zero k×k-discrepancy matrix by replacing the requiremento tha the sum of each row and each column be the same by that of requiring that the sum of the entries in each k×k square contiguous sub matrix be the same.We show that such matrices exist if k and n are both even,and do not if kand n are are relatively prime.Further,the existence is also guaranteed whenever n=k ●,for some integers k,m●2. A class of matirices,called constant-gap matrices plays an important role.We give a characterization of such matrices.

著者

浅野 哲夫 ムルツァー ウォルフガング ロウテ ギュンター ワング ヤジュン

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション

巻号頁・発行日

vol.110, no.232, pp.1-7, 2010-10-08

---

本報告では定数作業領域あるいは対数記憶領域と呼ばれる制約のある計算モデル上で効率よく実行できる幾何問題に対するアルゴリズムを提案する.まず最初に平面上に与えられた点集合に対するデローネイ三角形分割を描くアルゴリズムから始め,それをボロノイ図を描く問題に応用する.これらの問題に対しては,O(n)の記憶領域を用いることができるならΘ(n log n)時間のアルゴリズムが知られているが,本報告で述べるアルゴリズムはO(1)の作業領域だけを用いてO(n^2)時間で実行できるものである.さらに,これらのアルゴリズムを用いて,平面上に与えられた点集合に対するユークリッド最小木を求める効率の良いアルゴリズムも与える.

著者

浅野 哲夫

出版者

北陸先端科学技術大学院大学 大学院教育イニシアティブセンター

雑誌

CGEIアニュアルレポート 2011

巻号頁・発行日

pp.17-22, 2012-07

---

Students are evaluated mostly by examination even in graduate courses, and thus good examinations are requested for quality assurance of the courses. However, it is not widely known what a good examination is or how to create fair and good problems. A bigger problem is that university professors have never been trained to prepare good examinations. This is a motivation for our database named Problem Database. The database is a collection of all kinds of problems related to one field, in our case, algorithms in computer science. The database encourages professors in the world to share problems for better examinations. The database was started last year and has been maintained in the past year. This reports surveys activities on the database in our center.

著者

金丸 直義 西関 隆夫 浅野 哲夫

雑誌

情報処理学会研究報告アルゴリズム(AL)

巻号頁・発行日

vol.1992, no.27(1991-AL-026), pp.25-32, 1992-03-23

---

本報告では,与えられた凸m角形内部のすべての整数格子点を列挙するO(+m+log )時間のアルゴリズムを与える.ここでKは列挙された格子点の個数であり,nは凸m角形の大きさ,すなわちm角形を包含する軸平行な長方形の垂直,水平な辺のうち短い方の長さである.さらに,m個の制約式を持つ2変数整数計画問題を解くO( log m+log )時間のアルゴリズムを与える.ここでnは計画問題の許容解空間である凸多角形の大きさを表す.このアルゴリズムは従来知られているアルゴリズムより単純であり,時間計算量も改善している.