Информатика и ЭВМ
  • формат djvu
  • размер 10.81 МБ
  • добавлен 16 января 2012 г.
Скиена С. Алгоритмы. Руководство по разработке
2-е изд.: Пер. с англ. — СПб.: БХВ-Петербург. 2011. — 720 с.: ил.
Книга является наиболее полным руководством по разработке эффективных алгоритмов. Первая часть книги содержит практические рекомендации по разработке алгоритмов: приводятся основные понятия, дается анализ алгоритмов, рассматриваются типы структур данных, основные алгоритмы сортировки, операции обхода графов и алгоритмы для работы со взвешенными графами, примеры использования комбинаторного поиска, эвристических методов и динамического программирования. Вторая часть книги содержит обширный список литературы и каталог из 75 наиболее распространенных алгоритмических задач, для которых перечислены существующие программные реализации. Приведены многочисленные примеры задач.

Книгу можно использовать в качестве справочника по алгоритмам для программистов, исследователей и в качестве учебного пособия для студентов соответствующих специальностей.

Оглавление
Предисловие
Читателю
Преподавателю
Благодарности
Ограничение ответственности
ЧАСТЬ I. ПРАКТИЧЕСКАЯ РАЗРАБОТКА АЛГОРИТМОВ
Глава
1. Введение в разработку алгоритмов
1.1. Оптимизация маршрута робота
1.2. Задача календарного планирования
1.3. Обоснование правильности алгоритмов
1.4. Моделирование задачи
1.5. Истории из жизни
1.6. История из жизни. Моделирование проблемы ясновидения
1.7. Упражнения
Глава
2. Анализ алгоритмов
2.1. Модель вычислений RAM
2.2. Асимптотические обозначения
2.3. Скорость роста и отношения доминирования
2.4. Работа с асимптотическими обозначениями
2.4.1. Сложение функций
2.4.2. Умножение функций
2.5. Оценка эффективности
2.6. Логарифмы и их применение
2.7. Свойства логарифмов
2.8. История из жизни. Загадка пирамид
2.9. Анализ высшего уровня
2.10. Упражнения
Глава
3. Структуры данных
3.1. Смежные и связные структуры данных
3.2. Стеки и очереди
3.3. Словари
3.4. Двоичные деревья поиска
3.5. Очереди с приоритетами
3.6. История из жизни. Триангуляция
3.7. Хэширование и строки
3.8. Специализированные структуры данных
3.9. История из жизни. Геном человека
3.10. Упражнения
Глава
4. Сортировка и поиск
4.1. Применение сортировки
4.2. Практические аспекты сортировки
4.3. Пирамидальная сортировка
4.4. История из жизни. Билет на самолет
4.5. Сортировка слиянием. Метод "разделяй и властвуй"
4.6. Быстрая сортировка. Рандомизированная версия
4.7. Сортировка распределением. Метод блочной сортировки
4.8. История из жизни. Адвокат Скиена
4.9. Двоичный поиск и связанные с ним алгоритмы
4.10. Метод "разделяй и властвуй"
4
11. Упражнения
Глава
5. Обход графов
5.1 Разновидности графов
5.2. Структуры данных для графов
5.3. История из жизни. Жертва закона Мура
5.4 История из жнзни. Создание графа
5.5. Обход графа
5.6. Обход в ширину
5.7. Применение обхода в ширину
5.8. Обход в глубину
5.9. Применение обхода в глубину
5.10. Обход в глубину ориентированных графов
5.11. Упражнения
Глава
6. Алгоритмы для работы со взвешенными графами
6.1. Минимальные остовные деревья
6.2. История из жизни. И все на свете только сети
6.3. Поиск кратчайшего пути
6.4. История из жизни. Печатаем с помощью номеронабирателя
6.5. Потоки в сетях и паросочетание в двудольных графах
6.6. Разрабатывайте не алгоритмы, а графы
6.7. Упражнения
Глава
7. Комбинаторный поиск и эвристические методы
7.1. Перебор с возвратом
7.2. Отсечение вариантов поиска
7.3. Судоку
7.4. История из жизни. Покрытие шахматной доски
7.5. Эвристические методы перебора
7.6. История из жизни. Только это не радио
7.7. История из жизни. Отжиг массивов
7.8. Другие эвристические методы поиска
7.9. Параллельные алгоритмы
7.10. История из жизни. "Торопиться в никуда"
7.11. Упражнения
Глава
8. Динамическое программирование
8.1. Кэширование и вычисления
8.2. Поиск приблизительно совпадающих строк
8.3. Самая длинная возрастающая последовательность
8.4. История из жизни. Эволюция омара
8.5. Задача разбиения
8.6. Синтаксический разбор
8.7. Ограничения динамического программирования. Задача коммивояжера
8.8. История из жизни. Динамическое программирование и язык Prolog
8.9. История из жизни. Сжатие текста для штрих-кодов
8.10. Упражнения
Глава
9. Трудно решаемые задачи и аппроксимирующие алгоритмы
9.1. Сведение задач
9.2. Сведение для создания новых алгоритмов
9.3. Простые примеры сведения сложных задач
9.4. Задача выполнимости булевых формул
9.5. Нестандартные сведения
9.6. Искусство доказательства сложности
9.7. История из жизни. Наперегонки со временем
9.8. История из жизни. Полный провал
9.9. Сравнение классов сложности Р и NP
9.10. Решение NP-полных задач
9.11. Упражнения
Глава
10. Как разрабатывать алгоритмы
ЧАСТЬ II. КАТАЛОГ АЛГОРИТМИЧЕСКИХ ЗАДАЧ
Глава
11. Описание каталога
Глава
12. Структуры данных
12.1. Словарь
12.2. Очереди с приоритетами
12.3. Суффиксные деревья и массивы
12.4. Графы
12.5. Множества
12.6. Kd-деревья
Глава
13. Числепиые задачи
13.1. Решение системы линейных уравнений
13.2. Уменьшение ширины ленты матрицы
13.3. Умножение матриц
13.4. Определители и перманенты
13.5. Условная и безусловная оптимизация
13.6. Линейное программирование
13.7. Генерирование случайных чисел
13.8. Разложение на множители и проверка чисел на простоту
13.9. Арифметика произвольной точности
13.10. Задача о рюкзаке
13.11. Дискретное преобразование Фурье
Глава
14. Комбинаторные задачи
14.1. Сортировка
14.2. Поиск
14.3. Поиск медианы и выбор элементов
14.4. Генерирование перестановок
14.5. Генерирование подмножеств
14.6. Генерирование разбиений
14.7. Генерирование графов
14.8. Календарные вычисления
14.9. Календарное планирование
14.10. Выполнимость
Глава
15. Задачи на графах с полиномиальным временем исполнения
15.1. Компоненты связности
15.2. Топологическая сортировка
15.3. Минимальные остовные деревья
15.4. Поиск кратчайшего пути
15.5. Транзитивное замыкание и транзитивная редукция
15.6. Паросочетание
15.7. Задача поиска эйлерова цикла и задача китайского почтальона
15.8. Реберная и вершинная связность
15.9. Потоки в сети
15.10. Рисование графов
15.11. Рисование деревьев
15.12. Планарность
Глава
16. Сложные задачи на графах
16.1. Задача о клике
16.2. Независимое множество
16.3. Вершинное покрытие
16.4. Задача коммивояжера
16.5. Гамильтонов цикл
16
6. Разбиение графов
16.7. Вершинная раскраска
16.8. Реберная раскраска
16.9. Изоморфизм графов
16.10. Дерево Штейнера
16.11. Разрывающее множество ребер или вершин
Глава
17. Вычислительная геометрия
17.1. Элементарные задачи вычислительной геометрии
17.2. Выпуклая оболочка
17.3. Триангуляция
17.4. Диаграммы Вороного
17.5. Поиск ближайшей точки
17.6. Поиск в области
17.7. Местоположение точки
17.8. Выявление пересечений
17.9. Разложение по контейнерам
17.10. Преобразование к срединной оси
17.11. Разбиение многоугольника на части
17.12. Упрощение многоугольников
17.13. Выявление сходства фигур
17.14. Планирование перемещений
17.15. Конфигурации прямых
17.16. Сумма Минковского
Глава
18. Множества и строки
18.1. Поиск покрытия множества
18.2. Задача укладки множества
18.3. Сравнение строк
18.4. Нечеткое сравнение строк
18.5. Сжатие текста
18.6. Криптография
18.7. Минимизация конечного автомата
18.8. Максимальная общая подстрока
18.9. Поиск минимальной обшей надстроки
Глава
19. Ресурсы
19.1. Программные системы
19.2. Источники данных
19.3. Библиографические ресурсы
19.4. Профессиональные консалтинговые услуги
Список литературы
Предметный указатель
Смотрите также

Асанов М.О., Расин В.В. Комбинаторные алгоритмы

  • формат pdf
  • размер 1 МБ
  • добавлен 21 ноября 2010 г.
В книге приводятся алгоритмы дискретной оптимизации на графах и сетях. Материал, посвященный алгоритмам, содержит достаточно строгое их обоснование. При построении и анализе алгоритмов, используются основные теоретико-графовые понятия и факты. Подбор тем, поднятых в книге, во многом определен вкусами авторов. Представлено семейство алгоритмов дискретной оптимизации, наиболее часто используемых программистами. Изд. УрГУ, 2008 г. , 127 с.

Бильгаева Н.Ц. Теория алгоритмов, формальных языков, грамматик и автоматов

  • формат pdf
  • размер 528.46 КБ
  • добавлен 15 октября 2009 г.
Учебное пособие. - Улан-Удэ: Изд-во ВСГТУ, 2000 г. - 51 с. В учебном пособии рассмотрены основные понятия теории; формальные модели алгоритмов, дается классификация формальных грамматик, описаны используемые в практике программирования алгоритмы преобразования грамматик и синтеза автоматов. По каждому разделу приведен теоретический материал, даны методические рекомендации и примеры решения задач, а также задания для самостоятельной работы. Сод...

Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы

  • формат doc
  • размер 7.54 МБ
  • добавлен 06 апреля 2010 г.
В книге подробно разобрано много конкретных алгоритмов; мы старались рассказать о них понятно, но не опуская деталей и не жертвуя строгостью изложения. Алгоритмы записаны с виде «псевдокода» и прокомментированы в тексте; мы старались сделать описание алгоритма понятным людям с минимальным программистским опытом. Книга содержит более 260 рисунков, поясняющих работу различных алгоритмов. Мы обращаем особое внимание на эффективность рассматриваемых...

Кузюрин Н.Н. Фомин С.А. Сложность комбинаторных алгоритмов. Курс лекций

  • формат pdf
  • размер 1.62 МБ
  • добавлен 21 февраля 2011 г.
Московский физико-технический институт. 2007 г. 135 стр. Элементы теории сложности Несложно о сложности. Примеры алгоритмов Формально об алгоритмах Сложность алгоритмов Вероятностные вычисления Вероятностно проверяемые доказательства Схемы и схемная сложность Коммуникационная сложность Диаграмма классов сложности Приближенные алгоритмы с гарантированными оценками точности Приближенные алгоритмы с фиксированными оценками точности Приближенные алго...

Кузюрин Н.Н. Фомин С.А. Эффективные алгоритмы и сложность вычислений

  • формат pdf
  • размер 4.44 МБ
  • добавлен 16 сентября 2010 г.
Эта книга написана по материалам двух спецкурсов, читавшихся авторами в течение нескольких лет для студентов 4-го и 6-го курсов Московского физико-технического института. Она знакомит читателей как с классическими результатами в разработке эффективных алгоритмов для решения вычислительно-трудных задач, полученными еще в 1960-1970-х годах, так и с новыми результатами, полученными в последние годы. Именно в рассмотрении современных подходов к решен...

Лекции - Теория алгоритмов

Статья
  • формат pdf
  • размер 43.93 МБ
  • добавлен 04 февраля 2012 г.
Автор не известен. 136 с. Лекции в виде презентации. Содержание. - Алгоритмы в математике. Основные черты алгоритмов. Числовые функциии алгоритмы их вычисления. Примитивно рекурсивные функции. - Частично рекурсивные функции.Тезис Черча. - Машины Тьюринга и машины с неограниченными регистрами. Вычислимость частично рекурсивных функций на МНР. - Нумерации и универсальные функции. - Нормальные алгорифмы. - Алгоритмические проблемы в логике и матем...

Лекции по алгоритмам и анализу сложности

Статья
  • формат doc
  • размер 1.39 МБ
  • добавлен 26 сентября 2009 г.
Введение в теорию алгоритмов Сложность алгоритмов Сортировка и поиск Сортировка всплытия Флойда Логарифмический поиск Сортировка с вычисляемыми адресами Генетические алгоритмы Моделирование генетических операций Вычислительные эксперименты с генетическими операциямиrn

Реферат - Структуры данных и алгоритмы

Реферат
  • формат docx
  • размер 43.57 КБ
  • добавлен 23 февраля 2011 г.
Теоретическая часть - "Жадные алгоритмы". Элементы жадной стратегии. Свойство жадного выбора. Оптимальная подструктура. Алгоритм Хаффмена. Практическая часть - расчет вычислительной сложности алгоритма сортировки методом вставок. 10стр.

Шпоры

Шпаргалка
  • формат htm
  • размер 150.58 КБ
  • добавлен 27 июня 2011 г.
Ответы на вопросы: Машина Тьюринга. Конструирование МТ. Вычислимые по Тьюрингу функции: ПРФ, ЧРФ. Правильная вычислимость. Уточнение понятия алгоритма через машину с неограниченными регистрами. нормальные алгоритмы Маркова. Вычислимые функции и разрешимые множества: вычислимость, разрешимость, перечислимость, множество n-ок нат чисел, диагональная конструкция, главные универсальные функции, универсальная ОРФ, перечислимое неразрешимое множество.r...