Алгоритмизация 9 класс

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

By Мария Савенкова

9 класс

​Самый первый алгоритм

Некоторые из математических алгоритмов известны уже несколько тысячелетий. Считается, что самым древним нетривиальным алгоритмом является способ нахождения наибольшего общего делителя двух целых чисел. Он был открыт около 2300 лет тому назад и известен как алгоритм Евклида, поскольку содержится в первых предложениях седьмой книги «Начал» этого древнего математика. (Правда есть предположение, что алгоритм Евклида лишь интерпретация алгоритма, предложенного Эвдоксом за 75 лет до этого.)

От куда же появился термин алгоритм?₁

Известно, что в раннем Средневековье слово algorism использовали для обозначения способа арифметических вычислений на бумаге без применения счетных досок (абаков). Именно в таком значении оно вошло в некоторые европейские языки. Например, в авторитетном словаре английского языка «Webster’s New World Dictionary», изданном в 1957 году., оно снабжено пометкой «устаревшее» и объясняется как выполнение арифметических действий с помощью арабских цифр.

От куда же появился термин алгоритм?₂

Несмотря на то что известно, когда появился термин «алгоритм», лингвисты по-разному пытались толковать его происхождение. Одни выводили algorism из греческих «альгирос» - больной и «арифмом» - число. Правда, не понятно, почему числа «больные»? Другие склонялись к еще более экстравагантному объяснению, связывая слово с неким мифическим древним испанским правителем King Algor of Castil. Свой вариант предлагает и Энциклопедический словарь Брокгауза и Эфрона (1890 г.) В нем «алгорифм» (кстати, до революции использовалось и написание «алгори?м», через «фиту») производится от арабского слова «Аль-Горетм», т.е. корень

Но истину удалось установить не лингвистам, а историкам математики. Они доказали, что слово происходит от имени великого среднеазиатского ученого, автора популярнейшего на протяжении многих веков учебника по математике аль – Хорезми, жившего в первой половине IX века. Он написал ряд трактатов по арифметике и алгебре, в том числе книгу "Арифметика индусскими цифрами" – о счете с помощью десяти цифр и правилах арифметических действий с числами. В латинской транскрипции его имя записывается как Abu’Abd Allah Muhammad ibn Musa al-Khwarismi и означает «Мухаммад, сын Мусы, отец Абдуллы, родом из Хорезма». Хорезм – это историческая область на территории современного Узбекистана, центром которой является город Хива.

Одно из первых определений

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

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

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

​Отечественные разработки

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

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

Развитие алгоритмов

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

Развитие алгоритмов

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