2. Значение «теории алгоритмов» для современной теории программирования.

Алгоритм служит, как правило, для решения не одной конкретной задачи, а некоторого класса задач.

Для разработки алгоритмов и программ используется алгоритмизация— процесс систематического составления алгоритмов для решения поставленных прикладных задач. Алгоритмизация считается обязательным этапом в процессе разработки программ и решении задач на ЭВМ.

3. Интуитивное понятие алгоритма.

Человек ежедневно встречается с множеством задач, возникающих в различных областях деятельности общества, например:

а) подготовиться к уроку по математике;

б) приготовить раствор для проявления фотопленки;

в) избавиться от лишнего веса.

Для решения задач надо знать, что дано, и что следует получить. Другими словами, задача представляет собой совокупность двух объектов: исходных данных и искомых результатов. Чтобы получить результаты, необходимо знать метод решения задачи, то есть располагать предписанием (инструкцией, правилом), в котором указано, какие действия и в каком порядке следует выполнить, чтобы решить задачу (получить искомые результаты). Предписание, определяющее порядок выполнения действий над данными с целью получения искомых результатов, называется алгоритмом.

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

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

Понятие алгоритма является одним из основных понятий современной математики и является объектом исследования специального раздела математики - теории алгоритмов.

Еще на самых ранних ступенях развития математики в ней стали возникать различные вычислительные процессы чисто механического характера. С их помощью искомые величины ряда задач вычислялись последовательно из исходных величин по определенным правилам. К числу таких правил относились и правила выполнения арифметических операций над числами.

Столетия эти правила были очень сложны и не удивительно поэтому, что производить вычисления с большими числами могли только люди с высшим образованием. Так, чтобы научиться арифметическому делению в средние века требовалось закончить университет. Да еще не всякий университет мог научить этой премудрости. Нужно было непременно ехать в Италию: тамошние математики добились большого искусства в делении. Если напомнить, что в те времена пользовались непозиционной (римской) системой счисления, станет ясно, почему деление миллионных чисел было доступно лишь бородатым мужам, посвятившим этому всю свою жизнь.

С введением позиционной системы счисления все изменилось. В IX веке узбекский математик Мухаммед ибн Муса ал-Хорезми ("ал-Хорезми" означает "Хорезмиец") описал правила выполнения четырех арифметических действий в десятичной системе счисления. Новые правила были значительно проще и сейчас ими владеют уже школьники младших классов. Поразительная простота указанных правил стимулировала их повсеместное распространение. Эти правила были изложены Мухаммедом в книге по математике, изданной в 825 году, где, кроме того, приводились многочисленные рецепты решения различных задач.

По латинским переложениям арифметического трактата ал-Хорезми средневековая Европа знакомилась с индийской позиционной системой счисления и с искусством счета в этой системе. При переводе имя автора переделали в Алгоритми. Ссылки на рецепты решений из книги Мухаммеда европейские авторы начинали со слов: "Так говорил Алгоритми ...". С течением времени сами рецепты для решения математических задач стали называть алгоритмами.

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

Примеры алгоритмов:

• Алгоритмы арифметических действий с числами в двоичной системе счисления

• алгоритм нахождения НОД 2-х целых чисел, 2-х многочленов от переменной х;

• алгоритм извлечения ?n,?n?N ;

• алгоритм дифференцирования многочлена от переменной ;

• алгоритм нахождения определителя квадратной матрицы А над

Команды могут быть не пронумерованы. Все команды могут быть записаны последовательно, в виде сплошного текста. Друг от друга команды разделены либо точкой, либо точкой с запятой. При таком оформлении алгоритма исполнитель выполняет команды в порядке их естественного следования в тексте.

Такая форма записи алгоритма часто используется во всякого рода инструкциях, правилах, рецептах и т.п. Она хороша в случае, когда алгоритм небольшой и когда для описания алгоритма отводится мало места. Недостатком такого оформления является его малая наглядность .

Черты, характерные для интуитивного понятия алгоритма

Дискретность. Это свойство заключается в следующем: в начальный момент задается исходная система величин, а в каждый следующий момент система величин получается из предыдущей системы величин по определенному закону (программе).

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

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

Эффективность (результативность). Каждый шаг работы алгоритма должен заканчиваться результатом.

Массовость алгоритма. Начальная система величин может выбираться из некоторого бесконечного счетного множества Х.

Конструктивность. Объекты из Х, над которым работает алгоритм, должны быть конструктивными.