Рейтинг@Mail.ru
   
   
   
   
Оглавление
1. История
2. Основные этапы процесса решения задачи на ПК
3. Понятие алгоритма. Сущность алгоритмизации
4. Свойства алгоритма
5. Средства описания алгоритма
6. Методы разработки алгоритмов
7. Правила оформления схем алгоритмов
8. Типовые структуры алгоритмов
Литература



Основы алгоритмизации

1. История

Понятие алгоритма является одним из основных понятий вычислительной математики, однако, оно возникло в связи с поисками общих методов решения однотипных задач задолго до появления вычислительных машин.
Еще в III веке до н.э. греческий математик Евклид изложил правило вычисления наибольшего общего делителя двух натуральных чисел. Это правило историки математики считают первым алгоритмом, хотя само слово "алгоритм" появилось гораздо позднее.

Древнегреческий ученый Эратосфен (II в. до н. э.) предложил способ получения простых чисел (т.н. "решето Эратосфена"). В IX в. узбекский математик Мухаммад Ал-Хорезми разработал правила четырех арифметических действий над числами. В Европе эти правила стали называть алгоритмами (от латинской формы написания имени автора - Alchorismi илиAlgorithmi). Переводы арифметического трактата Ал-Хорезми с арабского содержали описание индийской позиционной системы счисления и искусства счета в этой системе (например, алгоритм сложения "столбиком"). Таким образом, сначала понятие "алгоритм" обозначало десятичную позиционную арифметику  и процедуры цифровых вычислений.

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

Суть упомянутого выше алгоритма Евклида состоит в том, чтобы вычитать из большего числа меньшее, подставляя результат на место большего числа, до тех пор, пока числа не станут равны друг другу. Эти равные числа и будут наибольшим общим делителем их разности и любого из чисел. Идея алгоритма понятна, но требует уточнения для использования ее на практике. Более конкретно алгоритм выглядит следующим образом:

А. Сравнить первое и второе числа. Если они равны, перейти к п. Г.  Если нет, то перейти к п.Б.

Б. Если первое число меньше второго, то переставить их. Перейти к п.В.

В. Вычесть из первого числа второе и рассмотреть полученную разность как новое первое число. Перейти к п.А.
Г. Считать первое число результатом задачи.

Этот набор правил является алгоритмом, т.к. любой человек, следуя ему, получит наибольший общий делитель для любой пары чисел.

Математики долго пользовались такими словесными описаниями алгоритмов. Многие вычислительные алгоритмы формулировались именно в такой форме (например, алгоритмы поиска корней квадратных и кубических уравнений и даже алгебраических уравнений любых степеней). Г.Лейбниц в 17 в. даже пытался найти общий алгоритм решения любых математических задач. Уже в нашем веке эта идея приобрела более конкретную форму: найти алгоритм проверки правильности любой теоремы при любой системе аксиом, т.е. алгоритм, который  отвечал бы на вопрос, верна ли теорема, и давал бы вывод ее доказательства. Построить такие алгоритмы не удавалось, и постепенно возникло мнение, что это вообще невозможно, то есть, что рассматриваемые задачи алгоритмически неразрешимы. Но поскольку само понятие алгоритма не было строго определено, то нельзя было и доказывать невозможность алгоритмического решения задач. Требовалось построить формальное определение алгоритма.

А поскольку объектом алгоритма может оказаться все, что угодно, то начать следовало с формализации понятия объекта. Например, любые объекты реального мира можно обозначать словами в некотором алфавите. Тогда объектами действия алгоритмов могут быть только слова. В этом случае алгоритм может быть определен, как четкая конечная система правил для преобразования слов из некоторого алфавита в слова из этого же алфавита.

В начале ХХ в. алгоритм стал объектом математического изучения.

Общее понятие алгоритма как эффективной вычислительной процедуры и примеры использования такого понятия встречаются в работах француза Э.Бореля (1912 г.) и немца Г.Вейля (1921 г.). Оба они пришли к понятию вычислимой функции (термин "fonction calculable").

Одно из первых формальных определений алгоритма дал английский математик А.Тьюринг [11, 15], который в 1936 году описал схему гипотетической (абстрактной) машины и назвал алгоритмом то, что умеет делать такая машина. А если что-то не может быть сделано машиной Тьюринга, то это уже не алгоритм. Таким образом, Тьюринг формализовал правила выполнения действий при помощи описания работы некоторой конструкции. Вычислительные машины - это тоже конструкции для выполнения алгоритмов, но это реальные устройства, тогда как машина Тьюринга - это математическая модель, она является абстракцией, которая никогда не была реализована, да и вообще не может быть реализована. Польза от машины Тьюринга в том, что, говоря о воображаемой конструкции, можно доказывать существование или несуществование алгоритмов решения различных задач.

Описывая различные алгоритмы для своих машин и утверждая реализуемость всевозможных композиций алгоритмов, Тьюринг убедительно показал разнообразие возможностей предложенной им конструкции и высказал тезис: "Всякий алгоритм может быть реализован соответствующей машиной Тьюринга". Это основная гипотеза теории алгоритмов в форме Тьюринга. Одновременно этот тезис является формальным определением алгоритма.

Примерно одновременно с А.Тьюрингом английский математик Э.Пост разработал похожую, но более простую алгоритмическую схему и реализующую ее машину. Позже было предложено еще несколько общих определений понятия алгоритма, и каждый раз удавалось доказать, что, хотя новые алгоритмические схемы и выглядят иначе, они в действительности эквивалентны машинам Тьюринга: все, что реализуемо в одной из этих конструкций, можно сделать и в других.

В 1954 г. советский математик А.А. Марков[11] предложил  свою алгоритмическую схему преобразования слов, назвав ее нормальным алгоритмом. Он ввел также понятие нормализации как перехода от разных способов описания алгоритмов к эквивалентным нормальным алгоритмам. Основная гипотеза теории алгоритмов в форме Маркова звучит так: "Всякий алгоритм нормализуем". Как и машина Тьюринга, алгоритмическая схема Маркова в общем случае не может быть физически реализована, т.к. она, например, допускает неограниченно большую длину слов. А вот формулировка алгоритма по Маркову: "Алгоритм - это точное предписание, которое задает вычислительный процесс, начинающийся с произвольного (но выбранного из фиксированной для данного алгоритма совокупности) исходного данного и направленный на получение полностью опеределяемого этим исходным данным результата" [15].

Несмотря на разные принципы построения своих теорий, все авторы алгоритмических схем старались простыми средствами обеспечить возможность описания любых алгоритмов.

Наиболее общий подход к уточнению понятия алгоритма предложил советский ученый Колмогоров А.Н.[15], который дал и его "наглядное" представление: "Алгоритм, примененный ко всякому "условию" ("начальному состоянию") из некоторого множества ("области применимости" алгоритма), дает "решение" ("заключительное состояние"). Алгоритмический процесс расчленяется на отдельные шаги заранее ограниченной сложности; каждый шаг состоит в "непосредственной переработке"… (одного) состояния в (другое). Процесс переработки… продолжается до тех пор, пока либо не произойдет безрезультатная остановка, либо не появится сигнал о получении "решения". При этом не исключается возможность неограниченного продолжения процесса…" Формулировка Колмогорова содержит два существенных момента: идея итеративности алгоритмического процесса и идея локальности каждого отдельного шага.

С середины ХХ века стали разрабатываться различные способы описания алгоритмов, например, с помощью специальных языков, которые называются алгоритмическими, и графовых схем - графического изображения алгоритма. Развитие электронной вычислительной техники и методов программирования способствовало тому, что разработка алгоритмов стала необходимым этапом автоматизации. 

В настоящее время понятие "алгоритм" вышло за пределы математики. Его стали применять в самых различных областях, понимая под ним точно сформулированные инструкции, назначение которых - достижение необходимого результата.
Формирование научного понятия алгоритма, ставшее важной проблемой, не закончено и в настоящее время. Теория алгоритмов, как любая другая наука, находится в постоянном развитии. Согласно утверждению авторов [15], современная теория алгоритмов может быть разделена на две части.

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

Вторая часть представляет собой прикладную теорию, которая имеет дело с проблемами, связанными с понятиями алгоритма и исчисления в различных областях математики: в математической логике и теории моделей, в алгебре, топологии и теории чисел, в теории информации и автоматизированного управления. Эта теория алгоритмов вырабатывает практически осуществимые методы построения алгоритмов.

В настоящее время развивается новая область теории алгоритмов, которая занимается оценкой качества алгоритмов и их улучшением с помощью равносильных преобразований.
С элементами теории алгоритмов можно познакомиться в [11, 12, 15].

Вместе с математической логикой теория алгоритмов составляет теоретический фундамент современных вычислительных наук. "Понятие алгоритма является не только центральным понятием теории алгоритмов, не только одним из главных понятий математики вообще, но одним из главных понятий современной науки. Более того, с наступлением эры информатики, алгоритмы становятся одним из важнейших факторов цивилизации. Многие достижения теории алгоритмов имеют общематематический и, возможно, общечеловеческий интерес" [15].

в начало




Стань УМНЕЕ компьютера!

http://vinogradonline.ru/ob/1188

Клуб на Миллион в месяц (СТАРТ)



Главная Windows 7 Windows XP Word 2003 Word 2007 Excel 2003 Excel 2007 Алгоритмы Статистика Принцип Парето Цифровые системы
управления

Copyright © 2008-2017
Ющик Е.В. e-mail: veta@comp5.ru

All Rights Reserved

Рейтинг@Mail.ru

Реклама: