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

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

Одним из фундаментальных понятий в информатике является понятие алгоритма.

Первоначально под алгоритмом понимали только правила выполнения четырех арифметических действий над числами.

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

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

История алгоритма

Слово алгоритм происходит от имени великого среднеазиатского ученого 8–9 вв. Абу Абдуллах Мухаммеда ибн Мусса Аль-Хорезми. Из математических работ Аль-Хорезми до нас дошли только две – алгебраическая и арифметическая.

Вторая книга долгое время считалась потерянной, но в 1857 в библиотеке Кембриджского университета был найден ее перевод на латинский язык.

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

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

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

Постепенно значение слова расширялось. Учёные начинали применять его не только к сугубо вычислительным, но и к другим математическим процедурам. Например, около 1360 г. французский философ Николай Орем написал математический трактат «Algorismus proportionum» («Вычисление пропорций»), в котором впервые использовал степени с дробными показателями и фактически вплотную подошёл к идее логарифмов. Когда же на смену абаку пришёл так называемый счёт на линиях, многочисленные руководства по нему стали называть «Algorithmus linealis», то есть правила счёта на линиях.

В 1684 году Готфрид Лейбниц в сочинении «Nova Methodvs pro maximis et minimis, itemque tangentibus…» впервые использовал слово «алгоритм» (Algorithmo) в ещё более широком смысле: как систематический способ решения проблем дифференциального исчисления.

Пользовался словом алгоритм и Леонард Эйлер, одна из работ которого так и называется — «Использование нового алгоритма для решения проблемы Пелля» («De usu novi algorithmi in problemate Pelliano solvendo»). Понимание Эйлером алгоритма как синонима способа решения задачи уже очень близко к современному.

Историки датируют 1691 годом один из списков древнерусского учебника арифметики, известного как «Счётная мудрость». Это сочинение известно во многих вариантах и восходит к ещё более древним рукописям XVI в.

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

Однако его не было ни в знаменитом словаре В. И. Даля, ни спустя сто лет в «Толковом словаре русского языка» под редакцией Д. Н. Ушакова (1935 г.). Зато слово «алгорифм» можно найти и в популярном дореволюционном Энциклопедическом словаре братьев Гранат, и в первом издании Большой Советской Энциклопедии (БСЭ), изданном в 1926 г. И там, и там оно трактуется одинаково: как правило, по которому выполняется то или иное из четырёх арифметических действий в десятичной системе счисления.

Однако к началу XX в. для математиков слово «алгоритм» уже означало любой арифметический или алгебраический процесс, выполняемый по строго определённым правилам, и это объяснение также даётся в БСЭ.

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

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

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

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

Такими средствами являются языки программирования или алгоритмические языки.