| 概要： |
ＩＴ技術の進歩により最近のディジタルカメラやiPadに代表される端末には非常に高度な機能が組み込まれている．そのようなソフトは組み込みソフトという名前で研究されてきたが，アルゴリズムを改良するというよりはメモリ節約の技術開発が主眼であった．計算機が誕生した頃には省メモリのテクニックが色々と開発されたが，メモリが安価になるにつれ，そのようなテクニックが忘れ去られようとしている．本講演では，非常に限定された作業領域だけで問題を解くためのアルゴリズム技法を紹介したい．対数メモリアルゴリズムのような理論研究もあるが，本講演では実用的な観点からの省メモリアルゴリズム設計技法について述べる．
Recent progress in computer systems has provided programmers with virtually unlimited amount of work storage for their programs. This leads to space-inefficient programs that use too much storage and become too slow if sufficiently large memory is not available. Thus, I believe that space-efficient algorithms or memory-constrained algorithms deserve more attention. Constant-work-space algorithms have been extensively studied under a different name, log-space algorithms. Input data are given on a read-only array of $n$ elements, each having O(log n) bits, and work space is limited to O(log n) bits, in other words, a constant number of pointers and counters, each of O(log n) bits. This memory constraint in the log-space algorithms may be too severe for practice applications. For problems related to an image with n pixels, for example, it is quite reasonable to use work space of the order of square root of n, which amounts to a constant number of rows and columns. I will start my talk with a simple algorithm for detecting a cycle in a graph using only some constant amount of work space (more exactly, O(log n) bits in total) and then its applications. Then, I will introduce some paradigms for designing such memory-constrained algorithms and their applications to interesting problems including those in computational geometry and computer vision.
|