平成２４年度副テーマ

　IT技術の進歩は目を見張るばかりである．急速な進歩を遂げる携帯電話やデジタル・カメラ等には計算機なみのソフトが組み込まれている．今では顔認識はディジタルカメラでは定番となっているが，そのような高度な処理をカメラのような装置で実現されると誰が予想しただろう．携帯電話も機能的には計算機にどんどん近づいており，iPadの出現を待って，実に様々なアプリケーションが導入されるに至っている．そのような高機能端末上のプログラム開発が最近になって脚光を浴びている．

　最近までは組み込みシステムという名前の下に研究されてきたが，アンドロイドなどの組み込みOSの出現により，その守備範囲は飛躍的に拡大している．ここで問題になるのが記憶領域のサイズである．通常の計算機の環境に比べて，利用できるメモリ量はかなり制限されているのが普通である．大量のメモリを使うことに慣れてしまったプログラマにとっては制限されたメモリ環境でプログラムを開発することは苦痛ですらある．ソフトウェア工学の分野では，スモールプログラムと呼ばれる概念の下に省メモリ・プログラミングの開発法も提唱されているが，アルゴリズム設計のレベルでも積極的な取り組みがあるかというと，そうとも言えないのが現状である．経験と勘に基づいてアルゴリズムが設計されてきたと言って過言ではない．

　このような状況に鑑みて，本課題では，作業領域が制限された状況でのアルゴリズム設計について考える．
　具体的な問題として，直近上位要素発見問題を考えよう．この問題では，配列A[1..n]に格納されたn個の要素それぞれについて，自分より大きな要素の中で，自分に（インデックス差の意味で）最も近い要素の位置（インデックス）を求めたい．たとえば，入力の配列が
A[1]=8, A[2]=4, A[3]=6, A[4]=3, A[5]=2, A[6]=1, A[7]=5, A[8]=7, A[9]=9
のとき，A[1]に対する直近上位要素はA[9]=9であり，A[2]=4に対する直近上位要素はA[1]=8またはA[3]=6である．
　問題１：　この問題をO(n)の作業領域を用いてO(n)時間で解くアルゴリズムを設計せよ．
　問題２：　この問題をO(1)の作業領域を用いてO(n log n)時間で解くアルゴリズムを設計せよ．
ただし，入力データを蓄えている配列A[ ]は読み出し専用であると仮定する．

副テーマの課題
１．下記の論文を参考にして，上記２問に答え，かつプログラムを作成せよ．
Tetsuo Asano, Sergey Bereg, and David Kirkpatrick: “Finding Nearest Larger Neighbors: A Case Stgudy in Algorithm Design and Analysis,” Lecture Notes in Computer Science, “Efficient Algorithms,” editied by S. Albers, H. Alt, and S. Naeher, Springer, pp.249-260, 2009.

２．上記論文の概要をまとめたもの，開発したプログラム，さらにプログラムの実行結果をレポートの形にまとめる．

３．研究室のゼミで上記内容に関するプレゼンテーションを行う．