Математика	Физика	Химия	Биология	Техника и технологии
	Задачи поиска-Альсведе Р М.: Мир, 1982, 368 с.
Альсведе Р., Вегенер И. . 57 Задачи поиска: Перев. с нем.— М.: Мир, 1982, 368 с. Монография западногерманских специалистов, посвященная теории поиска — новому направлению математики на стыке комбинаторики, математической статистики и теории информации. Книга представляет собой сравнительно элементарный обзор методов построения и оценки алгоритмов пояска, которые позволяют повысить эффективность экспериментальных исследований. Для математиков-прикладников, аспирантов и студентов, специализирующихся в области теории информации и вычислительной математики. ПРЕДИСЛОВИЕ РЕДАКТОРА ПЕРЕВОДА В этой книге рассматриваются общие принципы и отдельные примеры рационального планирования и анализа экспериментов. Цель заключается в том, чтобы минимизировать экспериментальные и вычислительные затраты. При всем различии постановок и путей решения таких задач, которые в литературе принято называть задачами поиска, имеются, однако, и общие методы. Центральный метод, образующий стержень книги, основан на теоретико-информационном подходе, который состоит в том, чтобы ввести подходящее информационное количество и оценивать сверху прирост информации в среднем за один эксперимент или такт вычислений. Если, кроме того, удается построить процедуру, при которой средний прирост информации в точности или асимптотически совпадает с предыдущей верхней оценкой, то задачу можно считать решенной. Правда, такой подход не всегда позволяет получать окончательные результаты, и чтобы точнее оценить сложность задачи, привлекаются дополнительные, более специальные соображения. Сравнительно элементарные первые две части книги (гл. 1—7) посвящены обзору комбинаторных проблем организации измерений, свободных от ошибок. Значительный интерес представляет систематическое изложение методов построения алфавитных кодов (гл. 4), до сих пор освещавшихся только в зарубежной журнальной литературе, а также содержательный, более современный, чем в третьем томе известной монографии Д. Кнута [91], обзор результатов, касающихся сортировки. Эти разделы оттенены в третьей части (гл. 9, 10) при разборе аналогичных задач для экспериментов, возмущенных случайными ошибками. Предварительно в гл. 9 дается весьма нестандартное введение в теорию информации, интересное и для специалиста. Оно во многом основано на недавних работах Р- Альсведе, имеющего замечательные достижения в этой области. Следует также отметить исследование каналов с обратной связью и произвольно меняющихся каналов. Очень интересна и последняя, четвертая часть книги (гл. ц—13)} где впервые опубликованы элегантные общие ОГЛАВЛЕНИЕ Предисловие редактора перевода ........ ........ 5 Предисловие........................7 ЧАСТЬ 1. ВВОДНЫЕ ЗАМЕЧАНИЯ И ОПРЕДЕЛЕНИЯ......9 Глава 1. Введение...................... 9 Глава 2. Пример модели поиска................12 ЧАСТЬ 2. ПРОБЛЕМА ПОИСКА ДЛЯ ТЕСТОВ, СВОБОДНЫХ ОТ ОШИБОК...................• • 16 Глава 3. Двоичная проблема поиска без ограничений на тесты ..... 16 § 1. Введение................... 16 § 2. Статические стратегии и разделяющие системы..... 17 § 3. Случайные статические стратегии.......... 19 § 4. Последовательные стратегии и префиксные коды .... 23 § 5. Неравенство Крафта и теорема кодирования в отсутствие шума..................... 25 § 6. Алгоритм Хаффмайа............... 31 § 7. Оптимальные стратегии в случае равномерного распределения на области поиска ............ 36 Глава 4. Алфавитные коды и двоичные деревья поиска....... 39 § 1. Введение................... 39 § 2. Минимизация длины поиска в наименее благоприятном случае.................... 41 § 3. Хорошие и оптимальные алфавитные коды...... 43 § 4. Построение оптимальных двоичных деревьев поиска ... 54 § 5. Эффективное построение хороших двоичных деревьев поиска ..................... 62 § 6. Нижние границы для стоимости оптимальных двоичных деревьев................... 70 § 7. Оптимальные двоичные деревья- поиска и оптимальные алфавитные коды максимальной стоимости....... 77 Глава 5. Проблемы сортировки................. 83 § 1. Введение................... 83 § 2. Сортировка множества из различных элементов .... 85 § 3. Сортировка множества, в котором не все элементы различны ..................... 91 § 4. Сортировка объединения пары непересекающихся упорядоченных множеств................. 95 § 5. Проблема медианы...............! § 6. Проблема выбора и проблема разделения.......1; § 7. Гипотеза Яо..................1: § 8. Массовое производство частичных порядков......И Глава 6. Задачи о взвешивании и геометрические проблемы......П § 1. Введение...................15 § 2. Отыскание фальшивой монеты с помощью рычажных весов.....................IS § 3. Отыскание фальшивой монеты с помощью аналитических весов.....................13 § 4. Разделяющая система из множеств не более чем с k элементами ....................13 § 5. Разделение монет различного веса . •.........13 Глава 7. Специальные проблемы поиска при использовании тестов, свободных от ошибок.................. 14 § 1. Введение...................14 § 2. Одна медицинская проблема поиска.........14 § 3. Теория вопросников ............... Щ § 4. Количество имеющихся в распоряжении стратегий . . . 15 ЧАСТЬ 3. ПРОБЛЕМЫ ПОИСКА ПРИ ИСПОЛЬЗОВАНИИ ТЕСТОВ СО СЛУЧАЙНЫМИ ОШИБКАМИ........... Глава 8. Стохастическая аппроксимация............. § 1. Введение................... § 2. Приближенное решение уравнений по методу Ныотона — Рафсона .................... § 3. Итерационный метод Мизеса и Поллачека-Гайрингера . . § 4. Метод Роббинса — Монро стохастической аппроксимации § 5. Сходимость РМ-метода почти всюду......... § 6. Аппроксимация точки максимума функции регрессии . . § 7. Аппроксимационный метод Дворецкого........ § 8. Оценки скорости сходимости РМ-процесса...... § 9. Последовательный минимаксный поиск точки максимума унимодальной функции .............. Глава 9. Проблема поиска с ответами, подверженными случайным ошибкам, и каналы с обратной связью............ § 1. Введение................... § 2. Равносильная теоретико-информационная проблема . . . § 3. Случай отсутствия ошибок............ § 4. Теорема Шеннона о кодировании.......... § 5. Обратная связь не увеличивает пропускную способность дискретных каналов без памяти.......... § 6. Один метод блокового кодирования; информация как редукция списков ............... . § 7. Робастная модель . .............. § 8. Байесовский метод.............. .-, § 9. Одно широкое обобщение «теоремы кодирования в отсутствие шума» и шэнноновской теоремы кодирования; последовательный метод............. § 10. Гауссовские каналы с обратной связью и стохастическая;: аппроксимация , s ............. Щ Ц Щ Глава 10. Проблемы идентификации и ранжирования........232 § 1. Введение...................232 § 2. Модель общей последовательной проблемы множественных решений..................237 § 3. Верхние оценки для средних потерь ........ 239 § 4. Условия конечности среднего числа наблюдений (ASN) и его высших моментов.............242 § 5. Нижняя оценка для среднего числа наблюдений (ASN) в проблеме множественных решений........245 § 6. Теорема о порядке...............247 § 7. Проблема идентификации (ПИ) и ее алгебраическая структура...................252 § 8. Основная последовательная решающая стратегия .... 256 § 9. Специальные проблемы идентификации.......260 § 10. Последовательный метод Паульсона для выбора популяции с наибольшим математическим ожиданием среди k нормально распределенных популяций........263 ЧАСТЬ 4. ПРОБЛЕМЫ, ПОИСКА С ПРОВЕРКАМИ........268 Глава 11. Минимизация средней стоимости поиска.........268 § 1. Введение...................268 § 2. Существование успешной стратегии с конечной средней стоимостью поиска...............274 § 3. Метод улучшения заданных стратегий........276 § 4. Существование и построение оптимальных стратегий . . 278 § 5. Класс псевдостратегий..............285 § 6. Построение почти оптимальных стратегий.......289 Глава 12. Максимизация вероятности успеха при ограниченных ресурсах 230 § 1. Введение...................290 § 2. Существование оптимальной распределяющей функции . . 292 § 3. Существуют ли быстрые алгоритмы для решения проблемы? ....................293 § 4. Оценки для максимальной вероятности успеха и разложение проблемы на подпроблемы...........295 § 5. Алгоритм построения оптимальной распределяющей функции .....................300 § 6. Анализ алгоритма................302 Глава 13. Обобщенная модель проблемы поиска с проверками.....306 § 1. Введение...................306 § 2. Почти-периодические стратегии..........306 § 3. Оптимальные стратегии локализации искомых объектов 309 § 4. Дискретные области поиска с бесконечным количеством элементов...................310 § 5. Непрерывные проблемы поиска с проверками.....310 § 6. Поиск одного из многих объектов....... . .316 § 7. Проблемы поиска со случайными параметрами .... 320 § 8. Проблемы поиска и остановки...........320 § 9. Проблема поиска с положительными транспортными затратами ...................326 § 10. Поиск нестационарного объекта.........327 § 11. Искать, стараясь не быть обнаруженным......329 § -12. Поиск на прямых................331 Дополнение. О теоретико-информационных методах в задачах поиска . . 334 Литература........................355 Цена: 150руб.
Назад	Заказ	На главную страницу