WEKO3
インデックスリンク
アイテム
記憶領域制限シナリオにおける計算限界の解明
https://doi.org/10.24517/00062003
https://doi.org/10.24517/00062003793228b5-1329-4cf7-8d75-0902a784587c
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
TE-PR-ASANO-T-kaken 2017-6p.pdf (228.7 kB)
|
.png)
|
| Item type | 報告書 / Research Paper(1) | |||||
|---|---|---|---|---|---|---|
| 公開日 | 2021-06-04 | |||||
| タイトル | ||||||
| タイトル | 記憶領域制限シナリオにおける計算限界の解明 | |||||
| タイトル | ||||||
| タイトル | Exploring the Limits of Computation in the Scenario of Constrained Work Space | |||||
| 言語 | en | |||||
| 言語 | ||||||
| 言語 | jpn | |||||
| 資源タイプ | ||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18ws | |||||
| 資源タイプ | research report | |||||
| ID登録 | ||||||
| ID登録 | 10.24517/00062003 | |||||
| ID登録タイプ | JaLC | |||||
| その他のタイトル | ||||||
| その他のタイトル | 多面的アプローチの統合による計算限界の解明 | |||||
| その他のタイトル | ||||||
| その他のタイトル | Exploring the Limits of Computation in the Scenario of Constrained Work Space | |||||
| 著者 |
浅野, 哲夫
× 浅野, 哲夫 |
|||||
| 提供者所属 | ||||||
| 内容記述タイプ | Other | |||||
| 内容記述 | 金沢大学 / 北陸先端科学技術大学院大学 | |||||
| 書誌情報 |
平成28(2016)年度 科学研究費補助金 新学術領域研究(研究領域提案型) 研究成果報告書 en : 2016 Fiscal Year Final Research Report 巻 2012 – 2016, p. 6p., 発行日 2017-05-30 |
|||||
| 抄録 | ||||||
| 内容記述タイプ | Abstract | |||||
| 内容記述 | 本研究では，対数領域計算モデルでの非自明な下界と上界の確立に向けて強力な解析技法の開発を行った．与えられた実数値配列上で，各要素の対して，より大きな値をもつ要素の中で直近のものを見つける直近上位要素発見問題を基本問題として考えた．線形の作業領域を許すと線形時間ですべての直近上位要素を求めることができるが，少ない作業領域でどの程度の高速化が達成できるかが問題である．本研究では，定数個のメモリを用いるだけで十分に高速なアルゴリズムを開発することに成功し，その計算時間とメモリ量との間のトレードオフについても成果を得た．同様の研究結果を計算幾何学やグラフ理論の基本的な問題についても得ることができた． | |||||
| 抄録 | ||||||
| 内容記述タイプ | Abstract | |||||
| 内容記述 | In this research we have developed powerful techniques for analysis toward establishment of nontrivial lower and upper bounds on the constrained work space. The most fundamental problem is to seek for each entry in a given array of real numbers one of nearest greater values. Using linear size of work space we can design a linear time algorithm for solving the problem. Our problem is whether we can solve the problem in an efficient way using less work space. In this research we showed that we have an efficient algorithm using only constant amount of work space. We also had results on time and space tradeoffs on the problem. We obtained other many results in basic problems in computational geometry and graph theory. | |||||
| 内容記述 | ||||||
| 内容記述タイプ | Other | |||||
| 内容記述 | 研究課題/領域番号:24106004, 研究期間(年度):2012 - 2016 | |||||
| 内容記述 | ||||||
| 内容記述タイプ | Other | |||||
| 内容記述 | 出典：「記憶領域制限シナリオにおける計算限界の解明」研究成果報告書 課題番号24106004 （KAKEN：科学研究費助成事業データベース（国立情報学研究所）） （https://kaken.nii.ac.jp/report/KAKENHI-PLANNED-24106004/24106004seika/）を加工して作成 |
|||||
| 著者版フラグ | ||||||
| 出版タイプ | AM | |||||
| 出版タイプResource | http://purl.org/coar/version/c_ab4af688f83e57aa | |||||
| 関連URI | ||||||
| 識別子タイプ | URI | |||||
| 関連識別子 | https://kaken.nii.ac.jp/search/?qm=90113133 | |||||
| 関連名称 | https://kaken.nii.ac.jp/search/?qm=90113133 | |||||
| 関連URI | ||||||
| 識別子タイプ | URI | |||||
| 関連識別子 | https://kaken.nii.ac.jp/grant/KAKENHI-PLANNED-24106004/ | |||||
| 関連名称 | https://kaken.nii.ac.jp/grant/KAKENHI-PLANNED-24106004/ | |||||
| 関連URI | ||||||
| 識別子タイプ | URI | |||||
| 関連識別子 | https://kaken.nii.ac.jp/report/KAKENHI-PLANNED-24106004/24106004seika/ | |||||
| 関連名称 | https://kaken.nii.ac.jp/report/KAKENHI-PLANNED-24106004/24106004seika/ | |||||
| 関連URI | ||||||
| 識別子タイプ | URI | |||||
| 関連識別子 | https://kaken.nii.ac.jp/report/KAKENHI-PLANNED-24106004/24106004seika/ | |||||
| 関連名称 | https://kaken.nii.ac.jp/report/KAKENHI-PLANNED-24106004/24106004seika/ | |||||
| 関連URI | ||||||
| 識別子タイプ | URI | |||||
| 関連識別子 | https://kaken.nii.ac.jp/en/report/KAKENHI-PLANNED-24106004/24106004seika/ | |||||
| 関連名称 | https://kaken.nii.ac.jp/en/report/KAKENHI-PLANNED-24106004/24106004seika/ | |||||
