Алгоритм - точное предписание, определяющее процесс перехода от исходных данных к искомому результату.
Предписание считается алгоритмом, если оно обладает тремя следующими свойствами:
определенностью, т.е. общепонятностью и точностью, не оставляющими место произволу;
массовостью, т.е. возможностью исходить из меняющихся в известных пределах значений исходных данных;
результативностью, т.е. направленностью на получение искомого результата.
Перечисленных свойств вполне достаточно, чтобы можно было определить, является данное конкретное предписание алгоритмом или нет.
Совершенно очевидно, что хорошо известное предписание: «Пойди туда, не знаю куда, принеси то, не знаю что» - алгоритмом не является.
Примерами алгоритмов нематематического характера могут служить различные рецепты из поваренной книги. Рассмотрим алгоритм приготовления бутерброда.
Исходные данные: хлеб (белый, черный), продукт (колбаса, ветчина, сыр, масло).
Искомый результат: бутерброд (ломтик продукта, наложенный на ломтик хлеба).
Предписание:
а) отрезать ломтик продукта;
б) отрезать ломтик хлеба;
Можно легко убедиться, что это предписание обладает всеми тремя свойствами алгоритма:
определенностью (всем понятно, что значит отрезать ломтик, положить один ломтик на другой и как все это сделать);
массовостью (хлеб может быть черным или белым, продукт – колбасой, ветчиной, сыром, маслом);
результативностью (при выполнении предписания получается искомый результат - бутерброд).
При этом последовательность выполнения пунктов а) и б) не существенна. Бутерброды получаются одинаковыми в обоих случаях а) - б) - в) и б) - а) - в). Это объясняется тем, что пункты а) и б) взаимно независимы друг от друга. Пункт в) может быть выполнен только после выполнения и пункта а), и пункта б), т.е. пункт в) зависит и от а), и от б).
Если пункты предписания изображать в виде прямоугольников, а зависимости – стрелочками, направленными в сторону зависимости, то алгоритму приготовления бутерброда будет соответствовать изображенная схема. (Интересно, что если в наличии имеются два ножа и соответствующее количество рук, то пункты а) и б) можно выполнять не только в любой последовательности, но и одновременно, и время приготовления бутерброда существенно уменьшится.)
В качестве примеров алгоритмов математического характера можно привести правила выполнения арифметических операций (сложения, вычитания, умножения, деления) над многозначными числами («столбиком»), правила выполнения таких же операций над простыми дробями, алгоритм Евклида (см. Евклида алгоритм), описания решений различных задач на построение в геометрии и т.д.
Рассмотрим алгоритм деления обыкновенных дробей.
Исходные данные: первая дробь (делимое), вторая дробь (делитель).
Искомый результат: дробь (частное).
Предписание:
а) числитель первой дроби умножить на знаменатель второй;
б) знаменатель первой дроби умножить на числитель второй;
в) записать дробь, числитель которой есть результат выполнения пункта а), а знаменатель - результат выполнения пункта б).
Все сказанное про последовательность выполнения пунктов в алгоритме приготовления бутерброда относится и к этому алгоритму.
Для того чтобы можно было изучать общие свойства алгоритмов, доказывать теоремы, нужно иметь строгое математическое определение этого термина. Такое определение удалось сформулировать сравнительно недавно советским ученым А. Н. Колмогорову и А. А. Маркову.
Вопросы, связанные с понятием алгоритма, выросли в последнее время в большую «теорию алгоритмов», потребность в которой вызвана появлением электронных вычислительных машин, станков с числовым программным управлением, промышленных роботов, автоматических линий и т.д. Во всех перечисленных случаях требуется создание алгоритмов выполнения машинами тех или иных операций, притом в таком порядке, который приводит к нужной цели. Эти алгоритмы зачастую бывают чрезвычайно сложными по структуре и для их выполнения компьютер должен сделать тысячи операций.
Если алгоритм предназначен для выполнения его на вычислительной машине, то он должен быть записан на языке, понятном этой машине. Такая запись алгоритма называется программой для ЭВМ, а язык, на котором написана программа, - языком программирования.
В процессе развития теории алгоритмов выяснилось, что существуют математические задачи, для которых невозможно составить общий алгоритм решения. Такие задачи получили название алгоритмически неразрешимых. Наиболее важные результаты в этой области принадлежат советскому математику П. С. Новикову.
АНАЛИЗ МАТЕМАТИЧЕСКИЙ
В истории математики условно можно выделить два основных периода: элементарной и современной математики. Рубежом, от которого принято вести отсчет эпохи новой (иногда говорят - высшей) математики, стал XVII век – век появления математического анализа. К концу XVII в. И. Ньютоном, Г. Лейбницем и их предшественниками был создан аппарат нового дифференциального исчисления и интегрального исчисления, составляющий основу математического анализа и даже, пожалуй, математическую основу всего современного естествознания.
Математический анализ – это обширная область математики с характерным объектом изучения (переменной величиной), своеобразным методом исследования (анализом посредством бесконечно малых или посредством предельных переходов), определенной системой основных понятий (функция, предел, производная, дифференциал, интеграл, ряд) и постоянно совершенствующимся и развивающимся аппаратом, основу которого составляют дифференциальное и интегральное исчисления.
Попробуем дать представление о том, какая математическая революция произошла в XVII в., чем характеризуется связанный с рождением математического анализа переход от элементарной математики к той, что ныне составляет предмет исследований математического анализа и чем объясняется его фундаментальная роль во всей современной системе теоретических и прикладных знаний.
Представьте себе, что перед вами прекрасно выполненная цветная фотография набегающей на берег штормовой океанской волны: могучая сутуловатая спина, крутая, но чуть впалая грудь, уже наклоненная вперед и готовая упасть голова с терзаемой ветром седой гривой. Вы остановили мгновение, вам удалось поймать волну, и вы можете теперь без спешки внимательно изучать ее во всех подробностях. Волну можно измерить, и, пользуясь средствами элементарной математики, вы сделаете много важных выводов об этой волне, а значит, и всех ее океанских сестрах. Но, остановив волну, вы лишили ее движения и жизни. Ее зарождение, развитие, бег, сила, с которой она обрушивается на берег, - все это оказалось вне вашего поля зрения, потому что вы не располагаете пока ни языком, ни математическим аппаратом, пригодными для описания и изучения не статических, а развивающихся, динамических процессов, переменных величин и их взаимосвязей.
«Математический анализ не менее всеобъемлющ, чем сама природа: он определяет все ощутимые взаимосвязи, измеряет времена, пространства, силы, температуры». Ж. Фурье
Движение, переменные величины и их взаимосвязи окружают нас повсюду. Различные виды движения и их закономерности составляют основной объект изучения конкретных наук: физики, геологии, биологии, социологии и др. Поэтому точный язык и соответствующие математические методы описания и изучения переменных величин оказались необходимыми во всех областях знания примерно в той же степени, в какой числа и арифметика необходимы при описании количественных соотношений. Так вот, математический анализ и составляет основу языка и математических методов описания переменных величин и их взаимосвязей. В наши дни без математического анализа невозможно не только рассчитать космические траектории, работу ядерных реакторов, бег океанской волны и закономерности развития циклона, но и экономично управлять производством, распределением ресурсов, организацией технологических процессов, прогнозировать течение химических реакций или изменение численности различных взаимосвязанных в природе видов животных и растений, потому что все это - динамические процессы.
Элементарная математика была в основном математикой постоянных величин, она изучала главным образом соотношения между элементами геометрических фигур, арифметические свойства чисел и алгебраические уравнения. Ее отношение к действительности в какой-то мере можно сравнить с внимательным, даже тщательным и полным изучением каждого фиксированного кадра киноленты, запечатлевшей изменчивый, развивающийся живой мир в его движении, которого, однако, не видно на отдельном кадре и которое можно наблюдать, только посмотрев ленту в целом. Но как кино немыслимо без фотографии, так и современная математика невозможна без той ее части, которую мы условно называем элементарной, без идей и достижений многих выдающихся ученых, разделенных порой десятками столетий.
Математика едина, и «высшая» ее часть связана с «элементарной» примерно так же, как следующий этаж строящегося дома связан с предшествующим, и ширина горизонтов, которые математика открывает нам в окружающий мир, зависит от того, на какой этаж этого здания нам удалось подняться. Родившийся в XVII в. математический анализ открыл нам возможности для научного описания, количественного и качественного изучения переменных величин и движения в широком смысле этого слова.
Каковы же предпосылки появления математического анализа?
К концу XVII в. сложилась следующая ситуация. Во-первых, в рамках самой математики за долгие годы накопились некоторые важные классы однотипных задач (например, задачи измерения площадей и объемов нестандартных фигур, задачи проведения касательных к кривым) и появились методы их решения в различных частных случаях. Во-вторых, оказалось, что эти задачи теснейшим образом связаны с задачами описания произвольного (не обязательно равномерного) механического движения, и в частности с вычислением его мгновенных характеристик (скорости, ускорения в любой моме