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

И откуда же произошло это фундаментальное понятие «алгоритм»? Я сделала попытку разобраться в этом, проследив образование современного понятия алгоритм, а также рассмотрела самые известные алгоритмы в математике.

1. Происхождение слова «алгоритм»

2. Вычесть из большего модуля меньший

3. Поставить перед полученным числом знак того слагаемого, модуль которого больше

3.4.3 Алгоритм умножения чисел с разными знаками

1. Определить, являются ли умножаемое и множитель отрицательными числами.

2. Перемножить модули этих чисел

3. Поставить перед полученным произведение знак «минус»

3.4.4 Алгоритм деления отрицательного числа на отрицательное число

1. Определить, являются ли делимое и делитель отрицательными

2. Разделить модуль делимого на модуль делителя

3.4.5 Алгоритм деления чисел с разными знаками

1. Определить, являются ли делимое и делитель числами с разными знаками

2. Разделить модуль делимого на модуль делителя

3. Поставить перед полученным числом знак «минус»

Заключение

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

Список литературы

3. В., Ш.В. (б.д.). Слово „алгоритм“: происхождение и развитие. Журнал «Потенциал».

Размещено на Allbest.ru

Подобные документы

практическая работа [12,2 K], добавлен 09.12.2009

Потоки в сетях, структура и принципы формирования алгоритма Форда-Фалкерсона, особенности его реализации программным методом. Минимальные остовные деревья. Алгоритм Борувки: понятие и назначение, сферы и специфика практического использования, реализация.

курсовая работа [311,3 K], добавлен 15.06.2015

реферат [571,1 K], добавлен 25.09.2009

Теоретико-числовая база построения СОК. Теорема о делении с остатком. Алгоритм Евклида. Китайская теорема об остатках и её роль в представлении чисел в СОК. Модели модулярного представления и параллельной обработки информации. Модульные операции.

дипломная работа [678,3 K], добавлен 24.02.2010

Алгоритм введения понятия ряда Фурье, опирающийся на моделирование физических задач в теоретическом курсе высшей математики для студентов физико-математических и инженерно-технических специальностей вузов. Функции и свойства рядов, их физический смысл.

курсовая работа [1,8 M], добавлен 20.05.2015

Алгоритм перехода к каноническому виду стандартной формы ЗЛП. Симплексные преобразования при изменении базисных переменных. Графический способ упорядочения вершин. Расчет параметров сетевого графика. Устойчивость решений ЗЛП при изменении параметров.

учебное пособие [161,1 K], добавлен 14.07.2011

Особенность метода Остроградского. Процесс вычисления производных и нахождения интегралов различных функций. Алгоритм Евклида. Интегрирование биноминальных дифференциалов. Тригонометрические и гиперболические подстановки. Основные виды рациональностей.

курсовая работа [916,8 K], добавлен 06.11.2014

Источник

История развития понятия «алгоритм» и его современное понимание и применение в информатике и математике

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

Вплоть до 1930 года понятие «алгоритм» оставалось интуитивным и имело скорее методологическое значение, а не математическое. Много ярких примеров раскрыла алгебра и теория чисел. Среди них: «алгоритм Евклида», «алгоритм Гаусса», «алгоритм Штурма» и многие другие.

Указанные выше алгоритмы были решены путем указания конкретных разрешающих процедур. Для получения результатов каждого из указанных алгоритмов интуитивного понятия вполне достаточно.

В 1930х годах в работах Гильберта, Черча, Клини, Поста, Тьюринга было определено понятие «алгоритм» в двух формах:

1) на основе понятия рекурсивной функции;

2) на основе описания алгоритмического процесса.

Эти и другие подходы подтвердили целесообразность использования тезиса Черча и тезиса Тьюринга для решения алгоритмических проблем.

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

Стимулом в развитии теории алгоритмов и в изучении алгоритмических моделей послужило применение ЭВМ. Так же ЭВМ послужило самостоятельному изучению алгоритмов с целью их сравнения по рабочим характеристикам (числу действий, расходу памяти), а так же их оптимизации. Алгоритмы стали объектом точного исследования как и те объекты, для работы с которыми они предназначены.

— изучить историю появления понятия;

— рассмотреть применение алгоритмов в математике;

— рассмотреть применение алгоритмов в информатике;

— рассмотреть свойства алгоритмов;

— рассмотреть машины Поста и Тьюринга.

Объектом исследования в данной работе является развитие, применение и современное понимание понятия «алгоритм».

Предметом исследования является само понятие алгоритма.

ИСТОРИЯ РАЗВИТИЯ ПОНЯТИЯ «АЛГОРИТМ» И ЕГО СОВРЕМЕННОЕ ПОНИМАНИЕ

1.1. История развития понятия «алгоритм».

Понятие алгоритма является базисным понятием математики. Вычисления алгоритмического характера (арифметические действия над целыми числами, нахождение наибольшего общего делителя двух чисел и т. д.) известны с глубокой древности. Однако, понятие «алгоритм» в явном виде было сформировано лишь в начале ХХ века.

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

Еще в III веке до нашей эры греческий математик Евклид изложил правило вычисления наибольшего общего делителя (НОД) двух натуральных чисел. «Алгоритм Евклида» состоит в том, чтобы вычитать из большего числа меньшее, подставляя результат на место большего числа, до тех пор, пока числа не станут равны друг другу. Эти равные числа и будут наибольшим общим делителем их разности и любого из чисел. Идея алгоритма понятна даже на интуитивном уровне и не нуждается в уточнении для применения на практике. Более конкретно «алгоритм Евклида» выглядит следующим образом:

1. Сравнить первое и второе числа. Если они равны, перейти к процедуре 4. Если нет, то перейти к процедуре 2.

2. Если первое число меньше второго, то переставить их. Перейти к процедуре 3.

Такой набор правил и является алгоритмом. Следуя ему любой человек может найти НОД.

Это правило в истории развития математики считают первым алгоритмом, хотя само слово «алгоритм» появилось гораздо позднее.

Древнегреческим ученым Эратосфеном во II веке до нашей эры был предложен способ получения простых чисел (точное название «решето Эратосфена»).

В IX веке узбекским математиком Мухаммадом Ал-Хорезми были разработны правила четырех арифметических действий над числами. В Европе эти правила стали называть алгоритмами от латинской формы написания имени автора – Alchorismi или Algorithmi. Переводы арифметического трактата Ал-Хорезми с арабского содержали описание индийской позиционной системы счисления и искусства счета в этой системе. Примером может служить алгоритм сложения «столбиком».

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

Словесное описание алгоритмов математики использовали долгое время. Множество вычислительных алгоритмов формулировалось именно в такой форме (например, алгоритмы поиска корней квадратных и кубических уравнений и даже алгебраических уравнений любых степеней).

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

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

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

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

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

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

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

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

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

1.2 Понятие «алгоритм» в математике

Понятие «алгоритм» является одним из основных понятий (категорий) математики, которое не обладает формальным определением. Таким образом, данное понятие можно представить в интуитивном виде. Алгоритмами можно назвать, например, известные из начальной школы правила сложения, вычитания, умножения и деления столбиком.

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

1) указание совокупности возможных исходных данных;

2) правило, по которому процесс признается закончившимся ввиду достижения результата.

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

Понятие «алгоритм» занимает центральное место в современной математике, прежде всего вычислительной.

Усовершенствование вычислительных машин даёт возможность реализовывать на них всё более сложные алгоритмы и выполнять с помощью ЭВМ все более сложные алгоритмические процессы. Вычислительный процесс не следует понимать в узком смысле только для цифровых вычислений. Так, уже и в школьном курсе алгебры говорят о буквенных вычислениях, но еще и в арифметических вычислениях появляются отличные от цифр символы: скобки, знак равенства, знаки арифметических действий. Пойдя дальше можно рассматривать вычисления с произвольными символами и их комбинациями. Именно такое широкое понимание пользуют при описании понятия «алгоритм». Так, можно говорить об алгоритме перевода с одного языка на другой, об алгоритме работы поездного диспетчера (перерабатывающего информацию о движении поездов в приказы) и других примерах алгоритмического описания процессов управления. Именно поэтому понятие «алгоритм» занимает одно из центральных мест и в кибернетике. Вообще, исходными данными и результатами алгоритма могут служить самые различные конструктивные объекты, например, результатами распознающих алгоритмов служат такие слова как «да» и «нет».

Алгоритмы в науке встречаются на каждом шагу. Умение решать задачу «в общем виде» всегда означает владение некоторым алгоритмом. Говоря об умении человека складывать числа, имеют в виду то, что он владеет некоторым единообразным приёмом сложения, который может быть применимым к любым двум конкретным записям чисел, то есть иными словами, человек владеет некоторым алгоритмом сложения. Понятие задачи «в общем виде» уточняется с помощью понятия массовой проблемы, которая задаётся серией отдельных, единичных проблем и состоит в требовании найти общий алгоритм (метод) их решения. Так, проблемы численного решения уравнений и автоматического перевода являются массовыми проблемами. В случае численного решения уравнений это проблемы различного типа, а в случае автоматического перевода это проблемы перевода отдельных фраз. Роль массовой проблемы определяет не только значение, но так же и сферу приложения понятия «алгоритм». Массовые проблемы очень важны для математики: например, в алгебре это проверка алгебраических равенств различных типов, а в математической логике это массовые проблемы распознавания выводимости предложении из заданных аксиом. Для математической логики понятие «алгоритм» существенно ещё и потому, что на него опирается центральное для математической логики понятие исчисления, служащее обобщением и уточнением интуитивных понятий «вывода» и «доказательства». Установление неразрешимости какой-либо массовой проблемы или проблемы распознавания истинности, а также доказуемости для какого-либо логико-математического языка, есть отсутствие единого алгоритма, который позволяет найти решение всех единичных проблем данной серии. Для решения конкретных единичных проблем принципиально необходимы специфические для каждой такой проблемы методы.

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

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

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

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

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

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

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

1) совокупность возможных исходных данных,

2) совокупность возможных результатов,

3) совокупность промежуточных результатов,

5) правило непосредственной переработки,

6) правило окончания,

Алгоритм является предметом изучения такой отрасли математики как теория алгоритмов. В результате изучения понятия «алгоритм» выделены его основные свойства:

— определенность – в любой момент времени исполнитель должен знать, какое действие нужно сделать;

— дискретность – разбиение алгоритма на некоторые действия, которые следуют друг за другом;

— результативность означает, что алгоритм всегда должен приводить к результату.

1.3 Понятие «алгоритм» в информатике

В информатике абсолютно любая программа представлена алгоритмом потому, что это последовательность определенных и продуманных действий, которые описаны в виде кода (инструкций компьютеру). К примеру, программа ввести 2 числа m и k и найти их сумму.

Write ln (‘Введите через пробел два числа ‘);

Write ln (‘Сумма чисел равна ‘, h );

Рассмотренный кусочек кода является алгоритмом. Алгоритм данной программы включает в себя такие действия:

— Запросить у пользователя два числа, которые могут быть введены с клавиатуры.

— Затем находит их сумму.

— В итоге выводит отчет.

1. 4 Машина Тьюринга

Данная машина была предложена А. Тьюрингом в 1936 году для формализации понятия «алгоритм». Машина Тьюринга является математической абстракцией, представляющей собой вычислительную машину.

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

Рисунок 1.1 – Схема машины Тьюринга

Работа машины Тьюринга задаётся перечислением элементов множества букв алфавита A, множества состояний Q и набором правил, по которым она работает. Правила имеют такой вид: qiaj→qi1aj1dk. «Другими словами, если головка находится в состоянии qi, а в обозреваемой ячейке записана буква aj, то головка переходит в состояние qi1, в ячейку вместо aj записывается aj1, головка делает движение dk, которое имеет три варианта: влево, вправо и на месте. Для каждой возможной конфигурации имеется ровно одно правило (для недетерминированной машины Тьюринга может быть большее количество правил). Правил нет только для заключительного состояния, попав в которое машина останавливается. Кроме того, необходимо указать конечное и начальное состояния, начальную конфигурацию на ленте и расположение головки машины»[7].

Этот же пример можно представить так:

Рисунок 1.4 – Пример задачи 2

Данная абстрактная машина была предложена Э. Постом в 1937 году. Эта вычислительная машина проста в применении, этим она и отличается от машины Тьюринга.

Машина поста состоит из головки и разбитой на секции бесконечной ленты либо с метками, либо без меток. За один «шаг» головка смещается на одну ячейку вправо или влево по ленте. Так же головка может либо ставить,

5) m 2

— если в ячейке нет метки, то перейти к m 2 строке программы,

иначе перейти к m 1 строке программы.

6) Стоп – конец программы (стоп).

Рисунок 1.2 – Абстрактная машина Поста

После запуска программы машина Поста имеет несколько возможных вариантов работы:

— работа может закончиться невыполнимой командой (стирание несуществующей метки или запись в помеченное поле);

— работа может закончиться командой «Стоп»;

— работа никогда не закончится.

Пример: головка стоит слева над начальной ячейкой. Нужно перейти на следующую пустую ячейку и поставить там метку.

Машина Поста также была предложена для формализации понятия алгоритм.

Источник