Теория алгоритмов, Матрос Д.Ш., Поднебесова Г.Б., 2008

Теория алгоритмов, Матрос Д.Ш., Поднебесова Г.Б., 2008.
   
   Учебник по курсу «Теория алгоритмов» для педагогических вузов по специальности «Информатика», полностью соответствующий стандарту.
Изложение имеет четкую логическую структуру и охватывает следующие темы: понятие алгоритма, машина Тьюринга, примитивно-рекурсивные функции, нормальные алгоритмы, вычислимость и разрешимость, сложность вычислений, NP-полные задачи. Каждая тема сопровождается тестовыми заданиями и упражнениями.
Для студентов и преподавателей педагогических вузов, учителей общеобразовательных школ.




Неформальное понятие алгоритма.
С алгоритмами, т. е. эффективными процедурами [8], однозначно приводящими к результату, математика имела дело всегда. Школьные методы умножения «столбиком» и деления «углом», метод исключения неизвестных при решении системы линейных уравнений, правило дифференцирования сложных функций, способ построения треугольника по трем заданным сторонам — все это алгоритмы. Однако пока математика имела дело в основном с числами и вычислениями и понятие алгоритма отождествлялось с понятием метода вычисления, потребности в изучении самого этого понятия не возникало. Традиции организации вычислений складывались веками и стали составной частью общей научной культуры в той же степени, что и элементарные навыки логического мышления. Все многообразие вычислений комбинировалось из 10-15 четко определенных операций арифметики, тригонометрии и анализа. Поэтому понятие метода вычисления считалось изначально ясным и не нуждалось в специальных исследованиях.

До середины XIX в. единственной областью математики, работавшей с нечисловыми объектами, была геометрия, и как раз она, не имея возможности опираться на вычислительную интуицию человека, резко отличалась от остальной математики повышенными требованиями к строгости своих рассуждений. До сих пор любой современный семиклассник, для которого математика — это мир вычислений, мучительно привыкает к понятиям доказательства и математического построения и никак не может понять, зачем доказывать равенство отрезков, когда проще измерить, и зачем строить перпендикуляр с помощью циркуля и линейки, когда есть угольник с «готовым» прямым углом или транспортир.

ОГЛАВЛЕНИЕ.
Предисловие.
Глава I. Предварительные обсуждения.
1.1. Неформальное понятие алгоритма.
1.1.1. Основные требования к алгоритмам.
1.1.2. Блок-схемы алгоритмов.
1.1.3. Подходы к уточнению понятия алгоритма.
1.2. Предварительные определения.
1.2.1. Множества и функции. 
1.2.2. Функции от натуральных чисел.
1.2.3. Отношения и предикаты. Логические обозначения.
1.3. Алгоритм как программа для компьютера.
Тестовые задания.
Глава II. Машина Тьюринга.
2.1. Основные определения.
2.2. Операции над машинами Тьюринга.
2.3. Универсальная машина Тьюринга.
2.4. Тезис Тьюринга.
2.5. Проблема остановки.
2.6. Машина фон Неймана.
Упражнения.
Тестовые задания.
Глава III. Рекурсивные функции.
3.1. Примитивно-рекурсивные функции.
3.2. Примитивно-рекурсивные операторы.
3.3. Функции Аккермана.
3.4. Частично-рекурсивные функции. Тезис Чёрча.
Упражнения.
Тестовые задания.
Глава IV. Нормальные алгоритмы Маркова.
4.1. Нормальные алгоритмы.
4.2. Операции над алгоритмами Маркова. Принцип нормализации.
Упражнения.
Тестовые задания.
Глава V. Машина с неограниченными регистрами. 
5.1. Основные определения.
5.2. МНР-вычислимые функции.
5.3. Порождение вычислимых функций.
5.3.1. Соединение программ.
5.3.2. Подстановка.
5.3.3. Рекурсия.
5.3.4. Минимизация.
5.3.5. Развилка и повторение.
5.4. Тезис Чёрча.
Упражнения.
Тестовые задания.
Глава VI. Вычислимость и разрешимость.
6.1. Эквивалентность различных теорий алгоритмов
6.2. Нумерация алгоритмов.
6.2.1. Нумерация программ.
6.2.2. Нумерация вычислимых функций.
6.3. Теоремы параметризации.
6.4. Универсальный алгоритм.
6.5. Неразрешимые проблемы в теории вычислимости.
6.6. Разрешимые и перечислимые множества.
6.7. Теорема Райса.
Тестовые задания.
Глава VII. Эффективные операции на множестве частичных функций.
7.1. Рекурсивные операторы.
7.2. Эффективные операции на вычислимых функциях.
7.3. Первая теорема о рекурсии.
7.4. Приложение к семантике языков программирования.
7.5. Вторая теорема о рекурсии.
Тестовые задания.
Глава VIII. Сложность вычисления.
8.1. Меры сложности.
8.2. Теорема об ускорении.
8.3. Элементарные функции.
Тестовые задания.
Глава IX. Введение в теорию NP-полных задач.
9.1. Формальные языки и грамматики.
9.1.1. Основные понятия.
9.1.2. Грамматики с фразовой структурой.
9.1.3. Иерархия Хомского.
9.2. Задачи распознавания, языки и кодирование.
9.3. Детерминированные машины Тьюринга и класс Р.
9.4. Недетерминированные вычисления и класс NP.
9.5. Полиномиальная сводимость и NP-полные задачи.
9.6. Примеры NP-полных задач.
Тестовые задания.
Литература.
Предметный указатель.
Обозначения.



Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Теория алгоритмов, Матрос Д.Ш., Поднебесова Г.Б., 2008 - fileskachat.com, быстрое и бесплатное скачивание.

Скачать pdf
Ниже можно купить эту книгу, если она есть в продаже, и похожие книги по лучшей цене со скидкой с доставкой по всей России.Купить книги


Скачать - pdf - Яндекс.Диск.




Теги: учебник по математике :: математика :: Матрос :: Поднебесова :: алгоритм :: машина Тьюринга