Проба

  • 08 апр. 2012 г.
  • 6670 Слова
1. Определение алгоритма

Слово алгоритм содержит в своем составе преобразованное географическое название Хорезм. Термин «алгоритм» обязан своим происхождением великому ученому средневекового Востока – Муххамад ибн Муса ал-Хорезми (Магомет, сын Моисея, из Хорезма). Он жил приблизительно с 783 по 850 годы, и в 1983 году отмечалось 1200-летие со дня его рождения в городе Ургенче – областномцентре современной Хорезмской области Узбекистана. В латинских переводах с арабского арифметического трактата ал-Хорезми его имя транскрибировалось как algorismi. Откуда и пошло слово «алгоритм» – сначала для обозначения алгоритмов цифровых вычислений десятичной позиционной арифметики, а затем для обозначения процессов, в которых искомые величины решаемых задач находятся последовательно из исходных данныхпо определенным правилам и инструкциям.
Во всех сферах своей деятельности, и в особенности в сфере обработки информации, человек сталкивается с различными способами или методиками решения задач. Они определяют порядок выполнения действий для получения желаемого результата – можно трактовать это как первоначальное или интуитивное определение алгоритма. Некоторые дополнительные требованияприводят к неформальному определению алгоритма.
Алгоритм – это заданное на некотором языке конечное предписание, задающее конечную последовательность выполнимых элементарных операций для решения задачи, общее для класса возможных исходных данных. Пусть D – область (множество) исходных данных задачи, а R – множество возможных результатов, тогда мы можем говорить, что алгоритм осуществляет отображение D → R.Поскольку такое отображение может быть не полным, то вводятся следующие понятия: алгоритм называется частичным алгоритмом, если мы получаем результат только для некоторых , и полным алгоритмом, если алгоритм получает правильный результат для всех .
Несмотря на все усилия исследователей, отсутствует одно исчерпывающе строгое определение понятия «алгоритм». Поэтому в теории алгоритмов были введеныразличные формальные определения алгоритма. При этом удивительным научным результатом является доказательство эквивалентности этих формальных определений в смысле их равномощности.
Варианты словесного определения алгоритма принадлежат российским ученым А.Н. Колмогорову и А.А. Маркову.
Алгоритм по Колмогорову – это всякая система вычислений, выполняемых по строго определенным правилам, которая послекакого-либо числа шагов заведомо приводит к решению поставленной задачи.
Алгоритм по Маркову – это точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных данных к искомому результату.
Следует отметить, что различные определения алгоритма, в явной или неявной форме, постулируют следующий ряд требований:
− алгоритм должен содержать конечное количество элементарно выполнимыхпредписаний, т.е. удовлетворять требованию конечности записи;
− алгоритм должен выполнять конечное количество шагов при решении задачи, т.е. удовлетворять требованию конечности действий;
− алгоритм должен быть единым для всех допустимых исходных данных, т.е. удовлетворять требованию универсальности;
− алгоритм должен приводить к правильному по отношению к поставленной задаче решению, т.е.удовлетворять требованию правильности.
Вплоть до 30-х годов прошлого столетия понятие алгоритма оставалось интуитивно понятным и имело скорее методологическое, а не математическое значение. К началу ХХ века много ярких примеров дала алгебра и теория чисел. Среди них можно упомянуть алгоритм Евклида нахождения наибольшего общего делителя двух натуральных чисел или двух целочисленных многочленов, алгоритм Гауссарешения системы линейных уравнений над полем, алгоритм нахождения рациональных корней многочленов одного переменного с рациональными коэффициентами. К ним также можно отнести алгоритм Штурма определения числа действительных корней многочлена с действительными коэффициентами на некотором отрезке действительных чисел, алгоритм разложения многочлена одного...