Учебное пособие. — Ярославль: ЯрГУ, 2005. — 143 с. — ISBN
5-8397-0382-6.
В учебном пособии излагаются основы алгоритмической грамотности
(уточнение понятия алгоритма и алгоритмическая неразрешимость,
анализ сложности алгоритмов, построение и анализ алгоритмов
сортировки и поиска информации, выделение класса труднорешаемых
задач). С целью усвоения материала и развития алгоритмических
навыков в каждом разделе даются упражнения для самостоятельной
работы.
Предназначено для студентов, обучающихся по специальности 010200 Прикладная математика и информатика и направлению 510200 Прикладная математика и информатика (дисциплина Информатика, блок ЕН). Может быть использовано для других специальностей и дисциплин специализации.
Текст в файле распознан в неправильной кодировке. Настоящее учебное пособие посвящено одному из центральных понятий в образовании специалиста по прикладной математике и информатике. Компьютерная программа представляет собой выражение алгоритма решения задачи на одном из алгоритмических языков. Но всегда ли возможна разработка алгоритма? Если для решения определенной задачи возможна разработка алгоритмов, то как их сравнить и как выбрать лучший? Как определить эффективность алгоритма и трудоемкость решения задачи? Есть ли задачи, для которых не существует эффективных алгоритмов? Ответы на эти вопросы составляют основу алгоритмической грамотности, и они рассматриваются в данном пособии. Первая глава посвящена уточнению понятия «алгоритм» и существованию алгоритмически неразрешимых проблем. Во второй главе рассматриваются характеристики сложности алгоритмов и задач. Третья глава посвящена задачам поиска информации, ее сортировки и организации; здесь рассматриваются многочисленные алгоритмы для этих задач. Четвертая глава посвящена выделению класса задач, для которых построение эффективных алгоритмов, по всей видимости, невозможно.
Небольшой объем учебного пособия не позволяет подробно и полно осветить все вопросы теории алгоритмов. В конце каждой главы приведен список литературы, позволяющий студенту расширить свои знания по материалу главы.
Для усвоения и закрепления материала в конце каждой главы и многих разделов приведены упражнения, которые рекомендуется выполнить. Содержание
Предисловие
Определение алгоритма.
Проблема определения алгоритма
Машины Тьюринга
Описание машины Тьюринга. Тезис Тьюринга.
Частично-рекурсивные функции
Исходные функции. Операция суперпозиции С. Операция примитивной рекурсии Рг. Операция минимизации µ. Определение и примеры. Тезис Чёрча. Нумерация наборов. Совместная рекурсия.
Нормальные алгоритмы Маркова
Определение нормального алгоритма и его выполнение. Возможности нормальных алгоритмов и тезис Маркова.
Эквивалентность моделей алгоритма
Общие черты моделей алгоритмов. Вычисление частично-рекурсивной функции на машине Тьюринга. Арифметизация машин Тьюринга. Частичная рекурсивность вычислимой по Тьюрингу функции
Алгоритмическая неразрешимость.
Массовые алгоритмические проблемы. Метод сводимости. Проблема самоприменимости.
Сложность алгоритмов.
Характеристики сложности алгоритмов
Трудоемкость алгоритмов
Определение трудоемкости алгоритма. Оценка трудоемкости алгоритма. Анализ алгоритмов и методика оценивания трудоемкости. Характеристики временной сложности программы.
Трудоемкость задач
Определение трудоемкости задачи. Задача поиска в упорядоченном массиве. Задача сортировки массива сравнением его элементов.
Сортировка и поиск.
Способы организации информации для поиска
Сортировка массива
Виды сортировки. Основные методы внутренней сортировки. Внешняя сортировка.
Поисковые деревья
Бинарные деревья и поиск. Сбалансированные АВЛ-деревья. Сбалансированные (3-2)-деревья. Внешний поиск по дереву и В-деревья.
Функции расстановки и хеширование
Функции расстановки. Хеширование. Хеширование с открытой адресацией.
Класс NP трудоемкости задач.
Труднорешаемые задачи
Класс NP задач и недетерминированная машина Тьюринга
Взаимоотношение между классами P и NP
Полиномиальная сводимость и NP -полные задачи
Теорема Кука
Методы доказательства NP -полноты
Локальная замена и NP -полнота задачи 3-Выполнимость. Построение компонент и NP -полнота задач «Вершинное покрытие» и «Клика». Метод сужения. Список некоторых известных NP -полных задач © Ярославский государственный университет, 2005
© В.С. Рублев, 2005
Предназначено для студентов, обучающихся по специальности 010200 Прикладная математика и информатика и направлению 510200 Прикладная математика и информатика (дисциплина Информатика, блок ЕН). Может быть использовано для других специальностей и дисциплин специализации.
Текст в файле распознан в неправильной кодировке. Настоящее учебное пособие посвящено одному из центральных понятий в образовании специалиста по прикладной математике и информатике. Компьютерная программа представляет собой выражение алгоритма решения задачи на одном из алгоритмических языков. Но всегда ли возможна разработка алгоритма? Если для решения определенной задачи возможна разработка алгоритмов, то как их сравнить и как выбрать лучший? Как определить эффективность алгоритма и трудоемкость решения задачи? Есть ли задачи, для которых не существует эффективных алгоритмов? Ответы на эти вопросы составляют основу алгоритмической грамотности, и они рассматриваются в данном пособии. Первая глава посвящена уточнению понятия «алгоритм» и существованию алгоритмически неразрешимых проблем. Во второй главе рассматриваются характеристики сложности алгоритмов и задач. Третья глава посвящена задачам поиска информации, ее сортировки и организации; здесь рассматриваются многочисленные алгоритмы для этих задач. Четвертая глава посвящена выделению класса задач, для которых построение эффективных алгоритмов, по всей видимости, невозможно.
Небольшой объем учебного пособия не позволяет подробно и полно осветить все вопросы теории алгоритмов. В конце каждой главы приведен список литературы, позволяющий студенту расширить свои знания по материалу главы.
Для усвоения и закрепления материала в конце каждой главы и многих разделов приведены упражнения, которые рекомендуется выполнить. Содержание
Предисловие
Определение алгоритма.
Проблема определения алгоритма
Машины Тьюринга
Описание машины Тьюринга. Тезис Тьюринга.
Частично-рекурсивные функции
Исходные функции. Операция суперпозиции С. Операция примитивной рекурсии Рг. Операция минимизации µ. Определение и примеры. Тезис Чёрча. Нумерация наборов. Совместная рекурсия.
Нормальные алгоритмы Маркова
Определение нормального алгоритма и его выполнение. Возможности нормальных алгоритмов и тезис Маркова.
Эквивалентность моделей алгоритма
Общие черты моделей алгоритмов. Вычисление частично-рекурсивной функции на машине Тьюринга. Арифметизация машин Тьюринга. Частичная рекурсивность вычислимой по Тьюрингу функции
Алгоритмическая неразрешимость.
Массовые алгоритмические проблемы. Метод сводимости. Проблема самоприменимости.
Сложность алгоритмов.
Характеристики сложности алгоритмов
Трудоемкость алгоритмов
Определение трудоемкости алгоритма. Оценка трудоемкости алгоритма. Анализ алгоритмов и методика оценивания трудоемкости. Характеристики временной сложности программы.
Трудоемкость задач
Определение трудоемкости задачи. Задача поиска в упорядоченном массиве. Задача сортировки массива сравнением его элементов.
Сортировка и поиск.
Способы организации информации для поиска
Сортировка массива
Виды сортировки. Основные методы внутренней сортировки. Внешняя сортировка.
Поисковые деревья
Бинарные деревья и поиск. Сбалансированные АВЛ-деревья. Сбалансированные (3-2)-деревья. Внешний поиск по дереву и В-деревья.
Функции расстановки и хеширование
Функции расстановки. Хеширование. Хеширование с открытой адресацией.
Класс NP трудоемкости задач.
Труднорешаемые задачи
Класс NP задач и недетерминированная машина Тьюринга
Взаимоотношение между классами P и NP
Полиномиальная сводимость и NP -полные задачи
Теорема Кука
Методы доказательства NP -полноты
Локальная замена и NP -полнота задачи 3-Выполнимость. Построение компонент и NP -полнота задач «Вершинное покрытие» и «Клика». Метод сужения. Список некоторых известных NP -полных задач © Ярославский государственный университет, 2005
© В.С. Рублев, 2005