М.: МЦНМО, 2001 г., 78 с.
"Цель данной работы состоит в том, чтобы ознакомить читателя с основами анализа алгоритмов, причём сделать это с помощью примеров, а не систематического изложения теории. Надеюсь, что такой подход позволит читателю быстро войти в курс дела, познакомиться с идеями, используемыми в этой области, а также понять взаимосвязь анализа алгоритмов с другими математическими дисциплинами. Задача об устойчивых супружеских парах наилучшим образом соответствует этим целям: во-первых, её изучение не требует никаких предварительных знаний по алгоритмике, а во-вторых, она позволяет наглядно продемонстрировать основные методы анализа алгоритмов. Эта задача показывает, насколько интересным может быть анализ алгоритмов сам по себе, не говоря о его практической значимости." (из предисловия автора)
Оглавление:
Содержание
От переводчиков русского издания
От переводчика английского издания
Предисловие к первому изданию (на французском языке)
Введение, определения, примеры
Обобщение: задача о приеме n абитуриентов в m университетов
Обобщение: случай неполных списков
Преобразование неполных списков в полные
Упражнения
Существование устойчивого паросочетания: основной алгоритм
Описание алгоритма
Доказательство корректности алгоритма
Конфликт интересов
Доказательство теоремы 2 из лекции 1
Анализ алгоритма
Упражнения
Принцип отложенных решений: накопление купонов
Пасьянс Циферблат
Оценка среднего числа предложений
Дополнительные предположения, упрощающие задачу
Задача собирателя купонов
Выводы
Частичная амнезия
Упражнения
Теоретические основы: применение в задаче о кратчайшем пути
Теория дискретной вероятности
Производящие функции
Неравенство Чебышёва–Бьенамэ
Независимые случайные величины
Производящая функция для сумм p_k + p_{k+1}+
Дисперсия в задаче собирателя купонов
Усиление неравенства Чебышёва
Основной алгоритм: исследование наихудшего случая
Задача о кратчайшем пути в графе
Описание алгоритма
Упражнения
Поиск в хеш-таблицах: поведение основного алгоритма в среднем
Хеширование
Среднее время поиска информации
Связь с проблемой поиска паросочетаний
Асимптотическая оценка среднего числа предложений в основном алгоритме
Завершение доказательства
Заключение
Дополнительное замечание о хешировании
Реализация основного алгоритма
Небольшие модификации
Инициализация таблицы P
Поиск устойчивого паросочетания, содержащего пару Aa
Обобщение на случай нескольких вынужденных браков
Поиск справедливого устойчивого паросочетания
Поиск всех устойчивых паросочетаний
Нерекурсивная версия алгоритма поиска всех устойчивых паросочетаний
Нерешённые проблемы
Пересечение интервалов
Резюме лекций
Аннотированная библиография
Устойчивые паросочетания
Задача собирателя купонов
Задача о кратчайшем пути
Хеширование
Структуры данных и алгоритмы
Анализ алгоритмов
Приложение А Более поздние работы
Приложение B Ответы и решения
Упражнения
Указатель
"Цель данной работы состоит в том, чтобы ознакомить читателя с основами анализа алгоритмов, причём сделать это с помощью примеров, а не систематического изложения теории. Надеюсь, что такой подход позволит читателю быстро войти в курс дела, познакомиться с идеями, используемыми в этой области, а также понять взаимосвязь анализа алгоритмов с другими математическими дисциплинами. Задача об устойчивых супружеских парах наилучшим образом соответствует этим целям: во-первых, её изучение не требует никаких предварительных знаний по алгоритмике, а во-вторых, она позволяет наглядно продемонстрировать основные методы анализа алгоритмов. Эта задача показывает, насколько интересным может быть анализ алгоритмов сам по себе, не говоря о его практической значимости." (из предисловия автора)
Оглавление:
Содержание
От переводчиков русского издания
От переводчика английского издания
Предисловие к первому изданию (на французском языке)
Введение, определения, примеры
Обобщение: задача о приеме n абитуриентов в m университетов
Обобщение: случай неполных списков
Преобразование неполных списков в полные
Упражнения
Существование устойчивого паросочетания: основной алгоритм
Описание алгоритма
Доказательство корректности алгоритма
Конфликт интересов
Доказательство теоремы 2 из лекции 1
Анализ алгоритма
Упражнения
Принцип отложенных решений: накопление купонов
Пасьянс Циферблат
Оценка среднего числа предложений
Дополнительные предположения, упрощающие задачу
Задача собирателя купонов
Выводы
Частичная амнезия
Упражнения
Теоретические основы: применение в задаче о кратчайшем пути
Теория дискретной вероятности
Производящие функции
Неравенство Чебышёва–Бьенамэ
Независимые случайные величины
Производящая функция для сумм p_k + p_{k+1}+
Дисперсия в задаче собирателя купонов
Усиление неравенства Чебышёва
Основной алгоритм: исследование наихудшего случая
Задача о кратчайшем пути в графе
Описание алгоритма
Упражнения
Поиск в хеш-таблицах: поведение основного алгоритма в среднем
Хеширование
Среднее время поиска информации
Связь с проблемой поиска паросочетаний
Асимптотическая оценка среднего числа предложений в основном алгоритме
Завершение доказательства
Заключение
Дополнительное замечание о хешировании
Реализация основного алгоритма
Небольшие модификации
Инициализация таблицы P
Поиск устойчивого паросочетания, содержащего пару Aa
Обобщение на случай нескольких вынужденных браков
Поиск справедливого устойчивого паросочетания
Поиск всех устойчивых паросочетаний
Нерекурсивная версия алгоритма поиска всех устойчивых паросочетаний
Нерешённые проблемы
Пересечение интервалов
Резюме лекций
Аннотированная библиография
Устойчивые паросочетания
Задача собирателя купонов
Задача о кратчайшем пути
Хеширование
Структуры данных и алгоритмы
Анализ алгоритмов
Приложение А Более поздние работы
Приложение B Ответы и решения
Упражнения
Указатель