著者

二村 良彦

出版者

日本ソフトウェア科学会

雑誌

コンピュータ ソフトウェア (ISSN:02896540)

巻号頁・発行日

vol.21, no.5, pp.343-351, 2004-09-28 (Released:2009-04-27)

---

インタープリタを用いて形式的に記述されたプログラミング言語のセマンティクスと現実のコンパイラとの関係およびインタープリタからコンパイラを自動的に作成する方法について述べる.この方法は計算過程の部分評価の一種である.この方法を応用してできるコンパイラ・コンパイラと既存のコンパイラ・コンパイラの相違は,プログラミング言語のセマンティクスを記述するさいに,既存のものが翻訳過程を記述しなければならないのに対して,本方式によるものは評価手順を記述すればよいことである.

著者

二村 良彦 川合 敏雄 堀越 彌 堤 正義

出版者

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

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.21, no.4, pp.259-267, 1980-07-15

---

「コーディングは流れ図の作成から始まる(Coding begins with the drawing of the flow diagrams.)」と言ったのは 1940年代のGoldsteinとNeumannだった.それ以来今日まで プログラムを書く前に流れ図 すなわちフローチャートを書くことが 多くのプログラマの習慣になってきた.ところが 高級言語が発達したり 構造化プログラミング技法が普及するにつれ フローチャートの欠点が目立つようになった.フローチャートに構造化プログラミングやプログラムの段階的改良(Stepwise Renfinement)の考えを取入れた図式としてはNSチャートやFerstlチャート等が提案された.また フローチャートを使わずに 直接 PASCAL 等の構造化プログラム言語やPDL等のシュードコードでプログラムの論理を記述することも提案されている.しかし これ等はフローチャートほどには広く使われていない.われわれは PAD(Problem Analysis Diagram すなわち問題分析図)と呼ぶ2次元木構造をした図面によりプログラムの論理を記述する方法を提案してきた.そして 多くの機種(プログラマブル電卓から大型計算機まで)に対する各種(OS アプリケーション等)のプログラムの開発を使用してきた.PADは ワーニエ図の問題点を改良するために (1)制御構造を強化し (2)図式から直接コーディングできるようにし さらに (3)ハードウェアの図面のような体裁を持つように図式を改良したものである.結果的には PADは 構造化プログラムを2次元的に展開した図式になった.特にPADが標準的に備えている制御構造はPASCALに基づいて定めてあるので PADはPASCALプログラムを2次元的に展開したような図式であり PASCAL Diagzamと言うこともできる.

著者

二村 良彦 川合 敏雄 堀越 彌 堤 正義

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.21, no.4, pp.259-267, 1980-07-15

---

「コーディングは流れ図の作成から始まる(Coding begins with the drawing of the flow diagrams.)」と言ったのは 1940年代のGoldsteinとNeumannだった.それ以来今日まで プログラムを書く前に流れ図 すなわちフローチャートを書くことが 多くのプログラマの習慣になってきた.ところが 高級言語が発達したり 構造化プログラミング技法が普及するにつれ フローチャートの欠点が目立つようになった.フローチャートに構造化プログラミングやプログラムの段階的改良(Stepwise Renfinement)の考えを取入れた図式としてはNSチャートやFerstlチャート等が提案された.また フローチャートを使わずに 直接 PASCAL 等の構造化プログラム言語やPDL等のシュードコードでプログラムの論理を記述することも提案されている.しかし これ等はフローチャートほどには広く使われていない.われわれは PAD(Problem Analysis Diagram すなわち問題分析図)と呼ぶ2次元木構造をした図面によりプログラムの論理を記述する方法を提案してきた.そして 多くの機種(プログラマブル電卓から大型計算機まで)に対する各種(OS アプリケーション等)のプログラムの開発を使用してきた.PADは ワーニエ図の問題点を改良するために (1)制御構造を強化し (2)図式から直接コーディングできるようにし さらに (3)ハードウェアの図面のような体裁を持つように図式を改良したものである.結果的には PADは 構造化プログラムを2次元的に展開した図式になった.特にPADが標準的に備えている制御構造はPASCALに基づいて定めてあるので PADはPASCALプログラムを2次元的に展開したような図式であり PASCAL Diagzamと言うこともできる.

著者

二村 良彦 雨宮 真人 山崎 利治 淵 一博

出版者

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

雑誌

情報処理 (ISSN:04478053)

巻号頁・発行日

vol.26, no.5, pp.p458-459, 1985-05

被引用文献数

10

著者

二村 良彦

出版者

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

雑誌

情報処理 (ISSN:04478053)

巻号頁・発行日

vol.44, no.3, 2003-03-15

著者

二村 良彦 二村 夏彦 遠藤貢一 平井 利治

出版者

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

雑誌

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

巻号頁・発行日

vol.1995, no.32, pp.5-12, 1995-03-17

被引用文献数

4

---

数列が整列されている度合を表す事前整列性測度Leaves(葉数),および事前整列性のよい数列については高速にソートをする適応整列法LOASとその実現法について報告する.LOASはまず与えられた数列を葉数個の区間にO()時間で分割し,次にそれをO( log葉数)時間でマージする整列法である.本稿ではまず葉数とLOASを定義し,次にLOASがLeavesに関して最適であることの証明を与える.最後にLOASの実現法およびその他の適応ソートや実用的なQUICKソート,MERGEソート等との性能比較結果を示す.We propose a new presortedness measure leaves and a new sorting algorithm LOAS (Leaves Optimal Adaptive Sort) which is optimal with respect to the measure. LOAS divides a given sequence X into Leaves (X) sorted subsequences in O(n) time. Then it merges the sequences in O(n log Leaves(X)) time. Implementation techniques and proof of the Leaves-Optimality of the algorithm are described. In order to prove that LOAS is an efficient sorting algorithm, we have conducted systematic evaluation of several sorting algorithms including Quicksort, merge sort, Skip sort and MEL sort.

著者

伍偉鴻 二村 良彦

雑誌

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

巻号頁・発行日

vol.2000, no.5(1999-AL-071), pp.73-79, 2000-01-17

---

現在,実際的に最速と考えられている整列法はBentleyのQuicksort(BQ法)である.本稿では,整列済みに近いデータに対してはBQ法の約2倍高速であり,かつ一様乱数列に対してもBQ法よりも高速な整列法LOAS (Leaves Optimal Adaptive Sort)の2つの実現法について報告する.一つは高速であるがスペースをO(N)要し、もう一方は性能は多少落ちるが、スペースをO(√<N>)要するものである。LOASは,数列の葉(数列において自分より小さい隣接要素を持たない要素)の数について最適な整列法である.即ち,数列の長さと葉数を各々Nおよびmとすると,LOASはO(N log m)時間で整列を完了する.実用に供されている4つの整列法(BQ法,GNU Quicksort,GNU Merge sort,多重分割ソートMPS)を含むいくつかの整列法と比較することにより,LOASの高速性を示す.

著者

二村 良彦

出版者

日本ソフトウェア科学会

雑誌

コンピュータ ソフトウェア (ISSN:02896540)

巻号頁・発行日

vol.10, no.3, pp.3_193-3_194, 1993-05-19 (Released:2018-11-05)

著者

矢農 正紀 二村 良彦

雑誌

全国大会講演論文集

巻号頁・発行日

vol.第56回, no.ソフトウェア科学・工学, pp.398-399, 1998-03-17

著者

二村 良彦

出版者

日本ソフトウェア科学会

雑誌

コンピュータ ソフトウェア (ISSN:02896540)

巻号頁・発行日

vol.21, no.5, pp.340-342, 2004-09-28 (Released:2009-04-27)

著者

二村 良彦 小西 善二郎 宋 立トウ

出版者

京都大学数理解析研究所

雑誌

数理解析研究所講究録 (ISSN:18802818)

巻号頁・発行日

vol.1125, pp.38-43, 2000-01

著者

二村 良彦

雑誌

情報処理

巻号頁・発行日

vol.44, no.3, pp.293, 2003-03-15

著者

河邊 昌彦 二村 良彦

出版者

一般社団法人日本ソフトウェア科学会

雑誌

コンピュータソフトウェア (ISSN:02896540)

巻号頁・発行日

vol.20, no.4, pp.363-368, 2003-07-25

---

頂点にラベルの付いた連結グラフのランダム生成は,グラフアルゴリズムの評価のために重要である.本稿では,グラフのランダム生成に必要な構成比を近似する方法を提案し,それによって高速な生成が可能であることを示す.グラフアルゴリズムの評価には,特定の性質を有してランダムに生成されたグラフが多量に必要である.また,ネットワークのシミュレーション等に関しても,テストデータとしてランダムに生成されたグラフを必要とすることがある.その際,グラフ生成が高速であることと同時に,生成されるグラフのランダムネスに関しても高精度であることが要求される.例えば,[1]において最小全域木問題を線形時間で解く確率的アルゴリズムが示されているが,このアルゴリズムの検証を実際に行うためには,テストデータとしてランダムに生成された重み付き連結無向グラフが必要となる.このようなグラフは,ランダムに生成されたラベル付き連結無向グラフから生成可能である[6].指定された頂点数nと辺数mを持ち,頂点にラベルの付いた連結無向グラフをランダムに生成する既存の方法として,以下のものが挙げられる.頂点数nの木をランダムに生成し,これにm-m+1本の辺をランダムに付け加えることによって連結グラフを生成できる(全域木法).また,m本の辺をランダムに決定して生成されたグラフが連結となるまで繰り返して,連結グラフを生成する方法もある(生成検査法).或いは,構成比というグラフ総数に関する指標を用いて,ランダムにグラフを生成することができる(構成比法).しかし,全域木法に関してはランダムネスの精度に,生成検査法と構成比法に関しては生成時間に問題があり,必ずしも実用可能ではない.また,これら以外で効率的なグラフ生成を可能とする方法は,我々の調査では見出せなかった.本稿では,構成比を高い精度で近似する単純な近似式を提案する.それにより,構成比法によるグラフ生成の時間を改善し,大規模なグラフに関しても現実的な時間で生成できることを示す.

著者

二村 良彦

出版者

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

雑誌

情報処理 (ISSN:04478053)

巻号頁・発行日

vol.8, no.4, 1967-07-15

著者

二村 良彦 大谷 啓記 青木 健一 二村 夏彦

出版者

一般社団法人日本ソフトウェア科学会

雑誌

コンピュータソフトウェア (ISSN:02896540)

巻号頁・発行日

vol.14, no.6, pp.588-605, 1997-11-17

被引用文献数

1

---

長さnの順列を等確率,即ち1/n!で生成するO(n)アルゴリズムは知られている.しかし,整列アルゴリズム等の精密な評価のためには,このような一様乱順列による評価では不十分である.例えば,一様乱順列に含まれる葉数(自分よりも小さい隣人を持たない要素の個数),ランズ,および上昇部分の個数(即ちn-ランズ)は,平均各々約(n+1)/3,(n+1)/2,および(n-1)/2である.これは一様乱順列が極めて偏った特性を有することを意味する.アルゴリズムの性能に影響を及ぼす性質(例えば葉数)を制御しながらランダムに順列を生成し,それを用いてアルゴリズムの性能を評価する必要がある.本稿では,順列から非負の整数上への関数および関数値を順列の特性指標と呼ぶ.特性指標の中でも,順列の葉数,ランズ,上昇部分数等に対応するクラスを単純指標と呼び,それを形式的に定義する.そして長さn,単純指標mを持つ乱順列をO(nm)で生成する計算機オーバーフロー(またはアンダーフロー)無しの方法を提案する.また,単純指標が葉数である場合には順列をO(n)で生成する実用的近似方式について報告する.

著者

坂本 巨樹 川本 史生 小西 善二郎 二村 良彦

出版者

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

雑誌

情報処理学会研究報告. PRO, [プログラミング]

巻号頁・発行日

vol.98, no.30, pp.159-164, 1998-03-23

---

再帰プログラムは書きやすく読みやすい場合が多いが、計算機で実行する際には手続き呼び出しとスタック操作が必要である.それゆえ, 与えられた再帰プログラムをスタックを使用せずしかも計算量も増加させずに, 反復型プログラムに変換する方法が古くから研究されている.我々は, 線形再帰プログラム(再帰呼び出しを実質的に1個所でしか行なわないプログラム)を計算量やスペース使用量を増やさずに反復型プログラムに変換する方法(再帰除去法)について先に報告した.その後, 我々はその報告に基づき, 線形再帰プログラムを能率のよい反復型プログラムに自動変換する再帰除去システムをLispを用いて実現した.本稿では, その実現法, 適用例及び問題点について報告する.

著者

二村 良彦 大谷 啓記

出版者

一般社団法人日本ソフトウェア科学会

雑誌

コンピュータソフトウェア (ISSN:02896540)

巻号頁・発行日

vol.15, no.3, pp.226-237, 1998-05-15

著者

二村 良彦

出版者

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

雑誌

情報処理 (ISSN:04478053)

巻号頁・発行日

vol.9, no.2, 1968-03-15

著者

二村 良彦 平井 利冶

雑誌

全国大会講演論文集

巻号頁・発行日

vol.50, pp.317-318, 1995-03-15

---

葉数最適整列法LOAS(Leaves-Optimal Adaptive Sort)は,基本的にはマージに基づいた整列法である.それは与えられた数列をまず葉数個の部分列に分割し,次に分割された部分列を2つづつマージする(ただし数列の葉とは,数列において隣人よりも値の小さい要素である).従ってLOASを実現するに際して,適正なマージ戦略を選択することが重要である.本稿に於いては,我々がLOASを実現する際に検討した下記3種類のマージ戦略とその性能について報告する.(1)単純マージ.(2) 2分マージ(binary merge).(3)基本的には単純マージであるが,マージする2つの数列の特徴に応じて2分法を利用したもの.例えば,一方の数列の長さが1のときのみ,その挿入個所を探索する為に2分法を利用したもの.葉数を制御したランダムな順列を用いて各種方式のキー比較回数および実行時間の比較評価をした.その結果,単純マージを利用した最も素朴な方法を陵駕する方式は,現在までには見つかっていない.LOASとその他の整列法との性能比較については報告した.以下では整列すべき数列は配列z(1),...,z(n)に格納されており,これを昇順に整列する場合について考える.

著者

伍偉鴻 二村 良彦

出版者

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

雑誌

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

巻号頁・発行日

vol.2000, no.5, pp.73-79, 2000-01-17

---

現在,実際的に最速と考えられている整列法はBentleyのQuicksort(BQ法)である.本稿では,整列済みに近いデータに対してはBQ法の約2倍高速であり,かつ一様乱数列に対してもBQ法よりも高速な整列法LOAS (Leaves Optimal Adaptive Sort)の2つの実現法について報告する.一つは高速であるがスペースをO(N)要し、もう一方は性能は多少落ちるが、スペースをO(√<N>)要するものである。LOASは,数列の葉(数列において自分より小さい隣接要素を持たない要素)の数について最適な整列法である.即ち,数列の長さと葉数を各々Nおよびmとすると,LOASはO(N log m)時間で整列を完了する.実用に供されている4つの整列法(BQ法,GNU Quicksort,GNU Merge sort,多重分割ソートMPS)を含むいくつかの整列法と比較することにより,LOASの高速性を示す.Two implementations of LOAS(Leaves Optimal Adaptive Sort) are proposed. One implementation is optimized in running time which needs O(N) extra working space and is faster than the fastest Quicksort known, Bentley's Quicksort, by a factor of 2 in practice, the other needs O(√<N>) extra working space which is more practical but loss in efficiency. LOAS runs in O(N log Leaves) time and is optimal with respect to the presortedness measure Leaves which is the number of elements smaller than their neighbors in a given sequence. Evaluation of LOAS together with four other sorting algorithms (Bently's Quicksort, GNU Quicksort, GNU Merge Sort and Multi Partition Sort MPS) is conducted to show the efficiency of LOAS.