WEKO3
アイテム
対称ヒープの実現とその応用
https://ipsj.ixsq.nii.ac.jp/records/32532
https://ipsj.ixsq.nii.ac.jp/records/325329bd1f76c-70ee-40a7-b8b3-cd955e529714
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-AL92028007.pdf (1.1 MB)
|
Copyright (c) 1992 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 1992-07-17 | |||||||
| タイトル | ||||||||
| タイトル | 対称ヒープの実現とその応用 | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | IMPLEMENTATION OF SYMMETRIC HEAP AND ITS APPLICATIONS | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
| 資源タイプ | technical report | |||||||
| 著者所属 | ||||||||
| 早稲田大学理工学部情報学科 | ||||||||
| 著者所属 | ||||||||
| 早稲田大学理工学部情報学科 | ||||||||
| 著者所属 | ||||||||
| 早稲田大学理工学部情報学科 | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Department of Information and Computer Science School of Science and Engineering, Waseda University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Department of Information and Computer Science School of Science and Engineering, Waseda University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Department of Information and Computer Science School of Science and Engineering, Waseda University | ||||||||
| 著者名 |
二村, 夏彦
筧, 捷彦
二村, 良彦
× 二村, 夏彦 筧, 捷彦 二村, 良彦
|
|||||||
| 著者名(英) |
Natuhiko, Futamura
Katuhiko, Kakehi
Yoshihiko, Futamura
× Natuhiko, Futamura Katuhiko, Kakehi Yoshihiko, Futamura
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 数列に関連しかつ数の大小関係を含む広範囲のプログラム作成問題を分割統治法により解決し易くするために対称ヒープと呼ばれるデーター構造を利用する方法を提案する。まず対称ヒープとは何かを詳しく説明し，かつ与えられた長さnの数列からO（）時間（最良n?1かつ最悪2n?）で対称ヒープを作成するアルゴリズムを示す（ヒープに要するメモリー所要量は3nである）。次に対称ヒープの操作に必要な基本関数およびその計算量を示す。最後に数列に関する6つのプログラム作成問題（そのうち3つは本稿オリジナルと考えられる）を対称ヒープを用いて解決する。 | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | Solving programming problems using data structures called symmetric heaps is proposed. Symmetric heaps make the classic divide and conquer method easier to apply to a class of problems concerning number sequences. The definition of the heap and an O(n) worst case time (between n-1 and 2n-1) algorithm to generate a symmetric heap from a given sequence of length n is described. Extra memories to implement a heap is 3n pointers. Then, primitive functions on symmetric heaps and their time complexities are presented. Finally, solutions of six programming problems concerning number sequences are shown as example applications of the proposed method. Three of the problems are considered to be originated from this manuscript. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AN1009593X | |||||||
| 書誌情報 |
情報処理学会研究報告アルゴリズム（AL） 巻 1992, 号 58(1992-AL-028), p. 49-57, 発行日 1992-07-17 |
|||||||
| Notice | ||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
