◄ Титульный лист     ▲ Выше     ПРЕДИСЛОВИЕ ►     БЛАГОДАРНОСТИ ►

ОГЛАВЛЕНИЕ Титульная страница книги ПРЕДИСЛОВИЕ к переводу LG01.pdf на русский язык ПРЕДИСЛОВИЕ БЛАГОДАРНОСТИ 1. Введение...............................................................1 1.1 Проблематика..........................................................2 1.2 Современные подходы...................................................4 1.3 LG с первого взгляда..................................................9 1.4 Углублённое рассмотрение LG-подхода..................................13 1.5 Стратегии LG и Теория Игр............................................19 1.6 Три этапа развития LG................................................22 1.7 Этап 1: Проект ПИОНЕР................................................24 1.8 Этап 2: Математические Инструменты...................................28 1.9 Этап 3: Новейшая История.............................................32 2. Иерархии Формальных Языков............................................39 2.1 Обзор Иерархии.......................................................39 2.2 Классы Задач.........................................................40 2.3 Различные Задачи как Сложные Системы.................................45 2.4 Множество Путей: Язык Траекторий.....................................50 2.5 Расстояния на Доске и в Пространстве Состояний.......................52 2.6 Сети Путей: Языки Сетей..............................................54 2.7 Представление Движения: Переводы.....................................66 2.8 Перебор через Построение: Языки Переборов............................71 2.9 Исторические Замечания...............................................75 3. Бой Роботов в двумерной Области.......................................77 3.1 Постановка Задачи....................................................77 3.2 LG-перебор...........................................................79 3.3 Обсуждение...........................................................88 3.4 Исторические Замечания...............................................89 4. Переход в трёхмерное Пространство.....................................91 4.1 3D/4A - Бой Роботов..................................................91 4.2 LG-перебор в пределах недостаточного Горизонта.......................94 4.3 LG-перебор в пределах Горизонта 5....................................98 4.4 Переход от 2D к 3D: Изменение Времени Выполнения....................105 4.5 Исторические Замечания..............................................106 5. Более глубокий Перебор, больше Агентов...............................107 5.1 2D/8A - Воздушный бой...............................................107 5.2 Глубокий Перебор для Воздушного Боя.................................112 5.3 3D/8A - Космический Бой.............................................128 5.4 Новый Уровень Сложности: Предварительные Выводы.....................131 5.5 Исторические Замечания..............................................134 6. Параллелизм, n×n Область.............................................137 6.1 Ослабление Последовательного Режима: Частичный Параллелизм..........137 6.2 LG-перебор для Задачи с Частичным Параллелизмом.....................139 6.3 Вторая Задача с Частичным Параллелизмом.............................143 6.4 Вторая Задача: LG-перебор...........................................145 6.5 Задача с Полным Параллелизмом и n×n Областью........................150 6.6 Задача с Полным Параллелизмом: LG-перебор...........................155 6.7 Воздействие Параллелизма............................................160 6.8 Исторические Замечания..............................................162 7. Составление Расписаний: Искусственный Конфликт.......................165 7.1 Постановка Задачи...................................................165 7.2 Преобразование в Игру двух игроков..................................168 7.3 Составление Расписаний: Перебор и Решение...........................172 7.4 Формальное Представление............................................174 7.5 Оценка и Реализация.................................................177 7.6 Применимость LG.....................................................178 8. Методы Генерации.....................................................181 8.1 Грамматики Хомского.................................................181 8.2 Управляемые Грамматики: Введение....................................183 8.3 Ханойская Башня: 3 Диска............................................184 8.4 Ханойская Башня: n Дисков...........................................186 8.5 Управляемые Грамматики: Формальное Определение......................188 8.6 Исторические Замечания..............................................191 9. Язык Траекторий......................................................193 9.1 Кратчайшие Траектории: Порождающая Грамматика.......................193 9.2 Генерация Кратчайших двумерных Траекторий...........................196 9.3 Генерация Кратчайших трехмерных Траекторий..........................200 9.4 Кратчайшие Траектории: Корректность и Полнота.......................204 9.5 Допустимые Траектории: Порождающая Грамматика.......................207 9.6 Обход Препятствий: Генерация Допустимых Траекторий..................210 9.7 Допустимые Траектории: Корректность и Полнота.......................215 9.8 Траектории для Игры в Шахматы.......................................219 9.9 Траектории для Составления Расписаний...............................224 9.10 Траектории для Агентов с Переменной Скоростью......................226 9.11 Язык Траекторий: Эффективная Реализация............................232 9.12 Исторические Замечания.............................................233 10. Язык Зон............................................................235 10.1 Грамматика Зон.....................................................235 10.2 Генерация Зон......................................................238 10.3 Геометрия Зон......................................................250 10.4 Зоны для Игры в Шахматы............................................253 10.5 Зоны для Составления Расписаний....................................254 10.6 Исторические Замечания.............................................256 11. Переводы............................................................259 11.1 На пути к Решению Проблемы Отличий.................................259 11.2 Теорема о Переводах................................................265 11.3 Перебор с Переводами...............................................278 11.4 Переводы и Застывание..............................................284 11.5 Исторические Замечания.............................................286 12. Языки Перебора......................................................287 12.1 Общий Перебор......................................................287 12.2 Сокращённый Перебор................................................290 12.3 Грамматика Переводов...............................................294 12.4 Качество Траекторий и Зон..........................................297 12.5 Процедура Обхода Дерева............................................300 12.6 Исторические Замечания.............................................303 13. От Перебора к Построению............................................305 13.1 Постановка Задачи..................................................305 13.2 Обзор Алгоритма....................................................306 13.3 Предварительные Определения........................................307 13.4 Расширение Терминальных Множеств...................................308 13.5 Структура Расширенных Терминальных Множеств........................311 13.6 Диаграмма Пространства Состояний...................................319 13.7 Обзор Потенциальных Стратегий......................................323 13.8 Построение Стратегий из Начального Состояния.......................330 13.9 Стратегии для Рети-подобных задач..................................335 13.10 Обсуждение........................................................337 13.11 Исторические Замечания............................................339 14. Вычислительная Сложность............................................341 14.1 Время Выполнения: Традиционные Алгоритмы для Рети-подобных задач...341 14.2 Время Выполнения: Грамматика Кратчайших Траекторий.................347 14.3 Время Выполнения: Грамматика Зон...................................350 14.4 Время Выполнения: Разворачивание Пучков Траекторий                       и клонирование Зон................................353 14.5 Вычислительная Сложность: Рети-подобные задачи.....................357 14.6 Исторические Замечания.............................................359 Взгляд в будущее........................................................361 Литература..............................................................363 Индекс..................................................................377 Штильман Борис, (2000). "Лингвистическая Геометрия: от Перебора к Построению", Stilman Boris (2000), "Linguistic Geometry: From Search to Construction", Series: Operations Research/Computer Science Interfaces Series, Vol. 13, 2000, 416p., Hardcover, ISBN: 0-7923-7738-9, © Springer. Part of Springer Science+Business Media

▲ В начало текущей     ▲ Литература     ▲ Этюды

Последнее обновление 09.09.2005, size=16 112 bytes © 2005 г., Александр Тимофеев, г.Харьков, Украина, Об авторе eMail: atimopheyev@yahoo.com