From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Date: Sat, 7 Nov 2009 23:39:00 +0300 From: Vladislav Zavjalov To: ALT Linux Team development discussions Message-ID: <20091107203900.GA3428@imap.altlinux.org> References: <20091107193402.GD10659@altlinux.org> Mime-Version: 1.0 Content-Type: text/plain; charset=koi8-r Content-Disposition: inline Content-Transfer-Encoding: 8bit In-Reply-To: <20091107193402.GD10659@altlinux.org> User-Agent: Mutt/1.4.2.3i Subject: Re: [devel] =?koi8-r?b?18/Q0s/TINDSzyDeydPMwQ==?= X-BeenThere: devel@lists.altlinux.org X-Mailman-Version: 2.1.12 Precedence: list Reply-To: ALT Linux Team development discussions List-Id: ALT Linux Team development discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sat, 07 Nov 2009 20:39:00 -0000 Archived-At: List-Archive: List-Post: On Sat, Nov 07, 2009 at 10:34:02PM +0300, Alexey Tourbin wrote: > Сгенирируем n случайных чисел из диапазона 0..2^m-1 и упорядочим их > по возрастанию. Для примера m=32, n порядка 10^3. > > Вычислить энтропию и предложить оптимальную процедуру кодирования > (сжатия) последовательности. Сколько битов на число можно получить? То есть, задача: есть n m-битных чисел, нужно проверить, что данное число находится среди них. Хранить хочется меньше, чем n*m бит. Я бы попробовал посмотреть паковку на такую тему: Делим весь диапазон пополам, сохраняем два бита: попадание чисел из множества в каждую половину. Для тех половин, где числа есть - повторяем процедуру. Но это так, первая идея без обоснования :) Слава