Понятие алгоритма. Основные свойства алгоритмов. Машина Тьюринга. Построение и анализ алгоритмов

Введение в программирование

(Элементы теории алгоритмов, основные алгоритмы, структуры данных и алгоритмы, язык программирования С)

Литература

1. Ахо А.В., Хопкрофт Дж., Ульман Дж.Д. Структуры данных и алгоритмы. – М.: Издательский дом «Вильямс», 2001.
2. Керниган Б., Ритчи Д. Язык программирования Си.− СПб. «Невский Диалект», 2001.
3. Митницкий В.Я. Элементы теории алгоритмов и язык программирования С: Учебное издание.− М.: МФТИ, 2001.
4. Хусаинов Б.С. Структуры и алгоритмы обработки данных. Примеры на языке Си. Учебное пособие. − Финансы и статистика, 2004.
5. Левитин А.В. Алгоритмы: введение в разработку и анализ. – М.: Издательский дом «Вильямс», 2006.
6. Кормен Т.X., Лейзерсон Ч.И., Ривест Р.Л., Штайн К. Алгоритмы: построение и анализ. Второе издание. − М.: Издательский дом «Вильямс», 2005.
7. Шилдт Г. Полный справочник по С, 4-е издание.− М.: Издательский дом «Вильямс», 2004.
8. Кнут Д.Э. Искусство программирования. Том 1-3. − М.: Издательский дом «Вильямс», 2000.
9. Вирт Н. Алгоритмы + структуры данных = программы. – М.: Мир, 1985.

Понятие алгоритма

В любой науке имеются первичные, неопределяемые понятия (точка, прямая или множество в математике). Можно рассматривать понятие алгоритма как первичное, интуитивное, неопределяемое понятие. Можно дать интуитивное (не строгое) пояснение понятия алгоритма: Алгоритм − набор конечного числа четко и однозначно определенных правил (инструкций), задающих последовательность выполнения операций для решения задачи определенного типа.

Понятие алгоритма

• Алгоритм Евклида: НОД (а,в) (Наибольший Общий Делитель)
• Алгоритм Евклида основан на рекуррентном вычислении следующего равенства:
• gcd(m, n) = gcd(n, m mod n)
• Разделить первое число на второе. Получить остаток.
• Если остаток равен нулю, второе число и есть искомое.
• Если остаток не равен нулю, то заменить первое на второе, второе – на остаток. Возвратиться к первому шагу.

Понятие алгоритма

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

Основные свойства алгоритмов

1. Дискретность. Четкая разбивка на отдельные этапы (шаги).
2. Определенность. Каждый шаг и переход от шага к шагу должны быть точно определены.
3. Конечность. Алгоритм всегда должен заканчиваться за конечное число шагов. Хотя это число не ограничено сверху.
4. Массовость. Применимость алгоритма не к одной задаче, а к классу задач.
5. Ввод. Должны быть точно указаны диапазоны допустимых значений входных данных, которые обрабатываются с помощью алгоритма.
6. Вывод. У алгоритма есть одно или несколько выходных данных (ответ).

Науки об алгоритмах

Теория алгоритмов. Рассматривает вопросы существования или не существования алгоритмов. Методы проектирования алгоритмов. Рассматривают различные подходы, применяемые для алгоритмического решения широкого круга задач, относящихся к различным областям вычислительной техники. Анализ алгоритмов. Для заданных алгоритмов определяются их количественные характеристики. Пример. Для заданного числа в чему равно среднее число T(a) выполнения шага 1 алгоритма Евклида.

Уточнение понятия алгоритма

• При решении задач естественно возникают следующие вопросы:
• Что такое задача?
• Всегда ли возможно решить задачу?
• Что такое процесс решения задачи?
• Различные подходы:
• Теория абстрактных машин.
• Теория рекурсивных функций.
• Теория нормальных алгоритмов.

Машина Тьюринга

Любая задача может быть записана в виде некоторого предложения (условия) из символов алфавита S={S1, S2, … , Sm} . Решение задачи (ответ) также может быть записано в виде предложения из символов алфавита S. Фактически, решение задачи есть преобразование условия в ответ. Условие размещается на бесконечной ленте, разделенной на ячейки, куда заносятся символы по одному.

Машина Тьюринга

Имеется головка, которая может двигаться вдоль ленты, разделенной на ячейки, и в любой текущий момент стоит перед одной ячейкой. Головка может считывать или записывать символы. Управляющее устройство головки может находиться в одном из n состояний Q={Q1, Q2, … , Qn}, одно из которых начальное Q1, а другое конечное Qs. На элементарном шаге головка считав символ и записав новый сдвигается на одну ячейку влево (L) или вправо (R) или остается на месте (H).

Тезис Тьюринга

Для любого алгоритма, понимаемого в интуитивном смысле, можно построить машину Тьюринга, функционирование которой эквивалентно этому алгоритму. Тезис Тьюринга нельзя доказать. Его не удается также и опровергнуть. Таким образом ответ на вопрос «Что такое алгоритм?» следующий: Алгоритм – это машина Тьюринга!

Неразрешимые проблемы

• Справа от головки располагаются числа. Нужно их сложить.
• Разрешимые задачи:
• Сложить неизвестное (но конечное) количество чисел при условии