В пособии рассмотрено понятие комбинаторной задачи, приведены
примеры таких задач, основные методы их решения и оценки
эффективности алгоритмов. Рассмотрены основные понятия теории
вычислительной сложности и приведены в кратком изложении основные
результаты теории. Рассмотрены приемы доказательства NP-полноты и
примеры NP-полных задач. Предназначено для студентов, изучающих
курс «Структуры и алгоритмы обработки данных», а также для
специалистов, разрабатывающих алгоритмы и программы решения
дискретных задач.
Дроздов С. Комбинаторные задачи и элементы теории вычислительной сложности
- формат doc
- размер 140.3 КБ
- добавлен 23 мая 2007 г.
Похожие разделы
- Академическая и специальная литература
- Информатика и вычислительная техника
- Информатика (программирование)
- Алгоритмы и структуры данных
Смотрите также
Головешкин В.А., Ульянов М.В. Теория рекурсии для программистов
- формат djvu
- размер 7.44 МБ
- добавлен 07 апреля 2010 г.
М.: ФИЗМАТЛИТ, 2006. 296 с. Книга является учебным пособием по теории рекурсии в аспекте ее применения в области проrраммирования. В ней рассматриваются основы теории рекурсии и ее использование в области разработки и анализа рекурсивных алrоритмов. Приводятся основные сведения о рекурсивных последовательностях и функциях, даны примеры рекурсивных алrоритмов, разработанных на основе рекуррентных соотношений, метода декомпозиции и метода динамичес...
Грин Д., Кнут Д. Математические методы анализа алгоритмов
- формат djvu
- размер 1.55 МБ
- добавлен 28 июля 2007 г.
1982 год, 120 страниц, 2-е издание Оригинальное и нестандартное изложение известных методов анализа алгоритмов, написанные крупным американским специалистом Д. Кнутом в соавторстве с Д. Грином. В книге представлены: комбинаторные тождества, рекуррентные соотношения, асимптотические представления. От читателя требуется знакомство с основами теории вероятностей, комбинаторного анализа и теории функций комплексного переменного. Для системных програ...
Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи
- формат djvu
- размер 11.5 МБ
- добавлен 15 января 2011 г.
Издательство: Мир Год: 1982 Страниц: 416 300 dpi Монография американских ученых, посвященная вопросам сложности решения комбинаторных задач, возникающих в дискретной оптимизации, математическом программировании, алгебре, теории чисел, теории автоматов, математической логике, теории множеств, теории графов и т. п. Книга отличается строгим и систематическим изложением теории, в приложении содержится более 300 труднорешаемых задач из различных разд...
Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи
- формат pdf
- размер 14.5 МБ
- добавлен 15 января 2011 г.
Издательство: Мир Год: 1982 Страниц: 416 300 dpi Монография американских ученых, посвященная вопросам сложности решения комбинаторных задач, возникающих в дискретной оптимизации, математическом программировании, алгебре, теории чисел, теории автоматов, математической логике, теории множеств, теории графов и т. п. Книга отличается строгим и систематическим изложением теории, в приложении содержится более 300 труднорешаемых задач из различных разд...
Козмидиади В.А., Маслов А.Н., Петри Н.В. (ред.) Сложность вычислений и алгоритмов
- формат djvu
- размер 5.87 МБ
- добавлен 23 сентября 2011 г.
Издательство Мир, 1974, -392 с. Библиотека «Кибернетического сборника» Затрагиваемые в сборнике проблемы математической логики тесно связаны с теорией вычислительных машин. В книге рассматриваются модели вычислительных устройств, их классификация, классификация языков, оценки сложности вычислений и оценки сложности программ. Развивается связанный со сложностью программ подход А. Н. Колмогорова к обоснованию теории вероятностей и теории информаци...
Кузюрин Н.Н. Фомин С.А. Сложность комбинаторных алгоритмов. Курс лекций
- формат pdf
- размер 1.62 МБ
- добавлен 21 февраля 2011 г.
Московский физико-технический институт. 2007 г. 135 стр. Элементы теории сложности Несложно о сложности. Примеры алгоритмов Формально об алгоритмах Сложность алгоритмов Вероятностные вычисления Вероятностно проверяемые доказательства Схемы и схемная сложность Коммуникационная сложность Диаграмма классов сложности Приближенные алгоритмы с гарантированными оценками точности Приближенные алгоритмы с фиксированными оценками точности Приближенные алго...
Марченков С.С. Элементарные рекурсивные функции
- формат djvu
- размер 939.59 КБ
- добавлен 31 октября 2010 г.
М.: МЦНМО, 2003. - 112 с. Книга написана на основе курсов лекций, которые автор читал на факультете Вычислительной математики и кибернетики МГУ. В книге собраны основное классы «элементарных» рекурсивных функций, изучаемые в теории алгоритмов. Приведены различные определения этих классов, установлены соотношения включения между ними. Получены разнообразные канонические представления элементарных функций, указаны эффективные операции, сохраняющие...
Носов В.А. Основы теории алгоритмов и анализа их сложности
- формат pdf
- размер 3.54 МБ
- добавлен 21 мая 2009 г.
Возможности вычислительных машин, сложность вычислений, нижние оценки сложности, оптимизация алгоритмов
Реферат - Структуры данных и алгоритмы
Реферат- формат docx
- размер 43.57 КБ
- добавлен 23 февраля 2011 г.
Теоретическая часть - "Жадные алгоритмы". Элементы жадной стратегии. Свойство жадного выбора. Оптимальная подструктура. Алгоритм Хаффмена. Практическая часть - расчет вычислительной сложности алгоритма сортировки методом вставок. 10стр.
Успенский В.А., Семенов А.Л. Теория алгоритмов: основные открытия и приложения
- формат djvu
- размер 3.55 МБ
- добавлен 01 ноября 2009 г.
М., Наука, 1987г. -288 с. Важнейшие достижения теории алгоритмов. Приложения теории алгоритмов к математической логике, теории вероятностей, теории информации и др. Влияние теории алгоритмов на алгоритмическую практику. Содержание: Основные математические приложения теории алгоритмов: 1. Исследование массовых проблем. 2. Приложения к основаниям математики. 3. Приложения к математической логике. 4. Вычислимый анализ. Нумерованные структуры. 5....