Носов В.А. Основы теории алгоритмов и анализа их сложности

В учебном пособии излагаются основы теории алгоритмов и теории формальных грамматик, рассматриваются различные алгоритмические системы, методы оценки и преобразования алгоритмов, связь теории алгоритмов с теорией формальных грамматик, классификация грамматик, связь теории формальных грамматик с теорией автоматов. Пособие предназначено для студентов вузов, специализирующихся по механизированной обработке экономической информации. Им могут пользова...

Екатеринбург: ГОУ ВПО УГТУ-УПИ, 2006. - 17 с. Методическое пособие по дисциплине «Математическая логика и теория алгоритмов». Приводится формализация понятия «алгоритм». Обсуждаются два способа формального описания алгоритма –с помощью нормальных алгоритмов Маркова и через машины Тьюринга. Приводятся меры сложности алгоритмов, определяются легко и трудноразрешимые задачи, классы задач P и NP, алгоритмически неразрешимые проблемы.

Головешкин В. А., Ульянов М. В., Теория рекурсии - ФИЗМАТЛИТ, 2006. - 296с. Книга является учебным пособием по теории рекурсии в аспекте ее применения в области программирования. В ней рассматриваются основы теории рекурсии и ее использование в области разработки и анализа рекурсивных алгоритмов. Приводятся основные сведения о рекурсивных последовательностях и функциях, даны примеры рекурсивных алгоритмов, разработанных на основе рекуррентных со...

М.: ФИЗМАТЛИТ, 2006. 296 с. Книга является учебным пособием по теории рекурсии в аспекте ее применения в области проrраммирования. В ней рассматриваются основы теории рекурсии и ее использование в области разработки и анализа рекурсивных алrоритмов. Приводятся основные сведения о рекурсивных последовательностях и функциях, даны примеры рекурсивных алrоритмов, разработанных на основе рекуррентных соотношений, метода декомпозиции и метода динамичес...

1982 год, 120 страниц, 2-е издание Оригинальное и нестандартное изложение известных методов анализа алгоритмов, написанные крупным американским специалистом Д. Кнутом в соавторстве с Д. Грином. В книге представлены: комбинаторные тождества, рекуррентные соотношения, асимптотические представления. От читателя требуется знакомство с основами теории вероятностей, комбинаторного анализа и теории функций комплексного переменного. Для системных програ...

В пособии рассмотрено понятие комбинаторной задачи, приведены примеры таких задач, основные методы их решения и оценки эффективности алгоритмов. Рассмотрены основные понятия теории вычислительной сложности и приведены в кратком изложении основные результаты теории. Рассмотрены приемы доказательства NP-полноты и примеры NP-полных задач. Предназначено для студентов, изучающих курс «Структуры и алгоритмы обработки данных», а также для специалистов,...

Издательство Мир, 1974, -392 с. Библиотека «Кибернетического сборника» Затрагиваемые в сборнике проблемы математической логики тесно связаны с теорией вычислительных машин. В книге рассматриваются модели вычислительных устройств, их классификация, классификация языков, оценки сложности вычислений и оценки сложности программ. Развивается связанный со сложностью программ подход А. Н. Колмогорова к обоснованию теории вероятностей и теории информаци...

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

Новосибирск: НГУ, 2005. - 130 с. Курс по теории алгоритмов является составной частью дисциплины "Математическая логика", читаемого на 2-3 курсах механико-математического факультета НГУ. В настоящем курсе подробно рассматриваются конечные автоматы и языки, рекурсивные функции и понятие вычислимости, вопросы сложности вычислений.

М., Наука, 1987г. -288 с. Важнейшие достижения теории алгоритмов. Приложения теории алгоритмов к математической логике, теории вероятностей, теории информации и др. Влияние теории алгоритмов на алгоритмическую практику. Содержание: Основные математические приложения теории алгоритмов: 1. Исследование массовых проблем. 2. Приложения к основаниям математики. 3. Приложения к математической логике. 4. Вычислимый анализ. Нумерованные структуры. 5....