Алгоритмы и анализ

  • 08 дек. 2012 г.
  • 3060 Слова
Лекция 2

Алгоритмы. История. Типы алгоритмов. Машина

Тьюринга. Машина состояний и логическая структура алгоритма. Блок-схема алгоритма. Нормальный алгоритм. Программный монитор.


1. Алгоритмические проблемы.
Необходимость точного определения алгоритма возникла в 20 – 30х ХХ в. при решении чисто математической проблемы вычислимости и разрешимости множеств.
Вычислимость.Множество А(А ( М) вычислимо, если существует некоторая процедура П, порождающая все элементы а ( А и только их.
Пример 1. Задано множество действительных чисел – D и уравнение y = ax + b, определенное на четверках чисел [pic] D4 = M. Обозначим множество четверок, которое удовлетворяет уравнению, через А. Множество А вычислимо, т.к. существует процедура П(a, b, x) ( y, которая по любой тройкевычисляет [pic]. Эта процедура известна из 5–го класса средней школы. [pic] – обозначают конкретные числа.
Разрешимость. Множество А разрешимо на М (А ( М), если существует процедура (алгоритм), которая для любого m ( M определяет, принадлежит ли m к А (m ( A) или нет (m ( A).
Вообще говоря, проблема разрешимости сводится к вычислимости соответствующего предиката
Р(m)= [pic].
Пример 2. Пусть А естьмножество решений уравнения y = ax + b. Существует тривиальный алгоритм П проверки для каждой четверки ( D4 в виде подстановки этих чисел в уравнение и выполнения указанных в уравнении действий, который вычисляет предикат
П(y, a, x, b)[pic].
и таким образом решает проблему разрешимости для заданного уравнения.
Понятие алгоритма в обиход математики ввел немецкий математик Шрёдер(1912–14), назвав «достаточно простую» механическую процедуру по имени арабского математика Ал–Хорезми (IХ в.) алгоритмом.
Пример 3. Проблема Ферма.
Для уравнения xn + yn = zn, где x ,y, z, n ( N, можно ли предложить алгоритм П, порождающий все решения уравнения при заданном «[pic]»? П[pic]. Если такой алгоритм П(n) существует, то говорят, что он решает проблему вычислимости множества решенийуравнения xn + yn = zn. Решение этой проблемы может быть двух типов: а) алгоритм не существует, б) алгоритм пока не известен(не открыт). Разрешимость множества решений уравнения xn + yn = zn решается просто, т.к. имеется тривиальный алгоритм для любой четверки [pic], вычисляющий предикат
П[pic].
Например,
[pic] – истина; но
[pic] – ложь.
Множество решений уравнения xn + yn = znразрешимо, но не вычислимо (пока не известен алгоритм или он не существует).
Существует взаимосвязь между вычислимостью и разрешимостью.
Всегда 1) если А вычислимо в М, то А разрешимо в М;
2) если А разрешимо в М, то из этого не следует его
вычислимость.
Проблемы разрешимости и вычислимости множеств требуют точного определения понятия алгоритма. Точногопонятия алгоритма нет и никогда не будет сделано по причине очень «туманного» содержательного объекта, который необходимо формально определить. В этом случае математики предложили некоторый точно определенный инструмент, при помощи которого можно конструировать любые интуитивно понятные порождающие (вычисляющие) и распознающие (разрешающие) процедуры.
Алгоритм, как точно определённый инструмент, дляконструирования процедур должен обладать следующими свойствами.
1) Конструктивность. Любые А и М (интуитивно понятные и содержательные множества) должны быть конструктивно описаны в виде структур данных. Любые интуитивно понятные функции (предикаты) должны быть конструктивно (формально) описаны в терминах определения инструмента.
2) Детерминированность. Вообще говоря следует из1), т.к. интуитивно алгоритм предполагает реализацию функций и только их.
3) Результативность. Определение и распознавание начального (правильные входные данные) и конечного события (правильные выходные данные), связанного с правильным или неправильным результатом работы алгоритма.

2. Типы алгоритмов. История создания.
За...
tracking img