Алгоритм чего либо пример

Презентация к уроку

Цель урока: Формирования у учащихся правильного понимания алгоритмов, их свойств, видов и практических навыков составления алгоритмов.

Задачи урока:

Дидактические: Обеспечить условия:

Воспитательные: Обеспечить условия:

Развивающие: Обеспечить условия:

Демонстрационный материал к уроку:

Ход урока

Понятие алгоритма

Появление алгоритмов связывают с зарождением математики.

Более 1000 лет назад (825 г.)ученый из города Хорезма Абдулла (или Абу Ждафар) Мухаммед бен Мусса аль-Хорезми создал книгу по математике, в тором описал способы выполнения арифметических действий над многозначными числами.

Алгоритм – описание последовательности действий, исполнение которых приводит к решению поставленной задачи за конечное число шагов.

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

Свойства алгоритма

Словесный способ записи алгоритмов представляет собой описание последовательных этапов обработки данных. Алгоритм задается в произвольном изложении на естественном языке.

Пример: Алгоритм «Зарядка»

При словесно-формульном способе алгоритм записывается в виде текста с формулами по пунктам, определяющим последовательность действий.

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

Словесно-формульным способом алгоритм решения этой задачи может быть записан в следующем виде:

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

Виды алгоритма

Линейный алгоритм – это такой, в котором все операции выполняются

последовательно одна за другой.

Пример: Алгоритм посадки дерева.

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

Полная форма

Неполная форма

Пример: Если на улице дождь, то останемся дома, а если нет то идем гулять.

Циклический алгоритм – действия повторяются до тех пор, пока выполняется заданное условие.

Цикл с известным числом повторений

Цикл с известным числом повторений часто называют «циклом ДЛЯ»

Пример: Алгоритм «Упражнение для глаз»

Цикл с постусловием

Цикл с неизвестным числом повторений, в тором выход из цикла осуществляется при выполнении условия, принято называть «циклом с постусловием» или «циклом ПРИ»

Цикл с предусловием

Цикл с известным числом повторений, в котором цикл продолжается, пока выполняется условие, принято называть «циклом с предусловием» или «циклом ПОКА»

Источник

Алгоритм

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

Ранее часто писали «алгорифм», сейчас такое написание используется редко, но, тем не менее, имеет место (например, Нормальный алгорифм Маркова).

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

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

Частичная формализация понятия алгоритма началась с попыток решения проблемы разрешения (нем. Entscheidungsproblem ), которую сформулировал Давид Гильберт в 1928 году. Следующие этапы формализации были необходимы для определения эффективных вычислений [1] или «эффективного метода» [2] ; среди таких формализаций — рекурсивные функции Геделя — Эрбрана — Клини 1930, 1934 и 1935 гг., λ-исчисление Алонзо Чёрча 1936 г., «Формулировка 1» Эмиля Поста 1936 года и машина Тьюринга. В методологии алгоритм является базисным понятием и получает качественно новое понятие как оптимальности по мере приближения к прогнозируемому абсолюту. В современном мире алгоритм в формализованном выражении составляет основу образования на примерах, по подобию. На основе сходства алгоритмов различных сфер деятельности была сформирована концепция (теория) экспертных систем.

Содержание

История термина

Современное формальное определение алгоритма было дано в 30—50-е годы XX века в работах Тьюринга, Поста, Чёрча (тезис Чёрча — Тьюринга), Н. Винера, А. А. Маркова.

Само слово «алгоритм» происходит от имени хорезмского учёного Абу Абдуллах Мухаммеда ибн Муса аль-Хорезми (алгоритм — аль-Хорезми). Около 825 года он написал сочинение, в котором впервые дал описание придуманной в Индии позиционной десятичной системы счисления. К сожалению, персидский оригинал книги не сохранился. Аль-Хорезми сформулировал правила вычислений в новой системе и, вероятно, впервые использовал цифру 0 для обозначения пропущенной позиции в записи числа (её индийское название арабы перевели как as-sifr или просто sifr, отсюда такие слова, как «цифра» и «шифр»). Приблизительно в это же время индийские цифры начали применять и другие арабские учёные. В первой половине XII века книга аль-Хорезми в латинском переводе проникла в Европу. Переводчик, имя которого до нас не дошло, дал ей название Algoritmi de numero Indorum («Алгоритмы о счёте индийском»). По-арабски же книга именовалась Китаб аль-джебр валь-мукабала («Книга о сложении и вычитании»). Из оригинального названия книги происходит слово Алгебра (алгебра — аль-джебр — восполнение).

Таким образом, мы видим, что латинизированное имя среднеазиатского учёного было вынесено в заглавие книги, и сегодня считается, что слово «алгоритм» попало в европейские языки именно благодаря этому сочинению. Однако вопрос о его смысле длительное время вызывал ожесточённые споры. На протяжении многих веков происхождению слова давались самые разные объяснения.

Одни выводили algorism из греческих algiros (больной) и arithmos (число). Из такого объяснения не очень ясно, почему числа именно «больные». Или же лингвистам больными казались люди, имеющие несчастье заниматься вычислениями? Своё объяснение предлагал и энциклопедический словарь Брокгауза и Ефрона. В нём алгорифм (кстати, до революции использовалось написание алгориѳм, через фиту) производится «от арабского слова Аль-Горетм, то есть корень». Разумеется, эти объяснения вряд ли можно счесть убедительными.

Упомянутый выше перевод сочинения аль-Хорезми стал первой ласточкой, и в течение нескольких следующих столетий появилось множество других трудов, посвящённых всё тому же вопросу — обучению искусству счёта с помощью цифр. И все они в названии имели слово algoritmi или algorismi.

Про аль-Хорезми позднейшие авторы ничего не знали, но поскольку первый перевод книги начинается словами: «Dixit algorizmi: …» («Аль-Хорезми говорил: …»), всё ещё связывали это слово с именем конкретного человека. Очень распространённой была версия о греческом происхождении книги. В англо-норманнской рукописи XIII века, написанной в стихах, читаем:

Алгоризм был придуман в Греции. Это часть арифметики. Придуман он был мастером по имени Алгоризм, который дал ему своё имя. И поскольку его звали Алгоризм, Он назвал свою книгу «Алгоризм».

Около 1250 года английский астроном и математик Иоанн Сакробоско написал труд по арифметике Algorismus vulgaris, на столетия ставший основным учебником по вычислениям в десятичной позиционной системе счисления во многих европейских университетах. Во введении Сакробоско назвал автором науки о счёте мудреца по имени Алгус (Algus). А в популярной средневековой поэме «Роман о Розе» (1275—1280) Жана де Мена «греческий философ Алгус» ставится в один ряд с Платоном, Аристотелем, Евклидом и Птолемеем! Встречался также вариант написания имени Аргус (Argus). И хотя, согласно древнегреческой мифологии, корабль «Арго» был построен Ясоном, именно этому Арго приписывалось строительство корабля.

«Мастер Алгус» (или Аргус) стал в средневековой литературе олицетворением счётного искусства. И в уже упоминавшейся «Романе о розе», и в известной итальянской поэме «Цветок», написанной Дуранте, имеются фрагменты, в которых говорится, что даже «mestre Argus» не сумеет подсчитать, сколько раз ссорятся и мирятся влюблённые. Английский поэт Джефри Чосер в поэме «Книга герцогини» (1369 г.) пишет, что даже «славный счётчик Аргус» (noble countour Argu) не сможет счесть чудовищ, явившихся в кошмарных видениях герою.

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

Алгоритм — это искусство счёта с помощью цифр, но поначалу слово «цифра» относилось только к нулю. Знаменитый французский трувер Готье де Куанси (Gautier de Coincy, 1177—1236) в одном из стихотворений использовал слова algorismus-cipher (которые означали цифру 0) как метафору для характеристики абсолютно никчёмного человека. Очевидно, понимание такого образа требовало соответствующей подготовки слушателей, а это означает, что новая система счисления уже была им достаточно хорошо известна.

Многие века абак был фактически единственным средством для практичных вычислений, им пользовались и купцы, и менялы, и учёные. Достоинства вычислений на счётной доске разъяснял в своих сочинениях такой выдающийся мыслитель, как Герберт Аврилакский (938—1003), ставший в 999 г. папой римским под именем Сильвестра II. Новое с огромным трудом пробивало себе дорогу, и в историю математики вошло упорное противостояние лагерей алгорисмиков и абацистов (иногда называемых гербекистами), которые пропагандировали использование для вычислений абака вместо арабских цифр. Интересно, что известный французский математик Николя Шюке (Nicolas Chuquet, 1445—1488) в реестр налогоплательщиков города Лиона был вписан как алгорисмик (algoriste). Но прошло не одно столетие, прежде чем новый способ счёта окончательно утвердился, столько времени потребовалось, чтобы выработать общепризнанные обозначения, усовершенствовать и приспособить к записи на бумаге методы вычислений. В Западной Европе учителей арифметики вплоть до XVII века продолжали называть «магистрами абака», как, например, математика Никколо Тарталью (1500—1557).

Итак, сочинения по искусству счёта назывались Алгоритмами. Из многих сотен можно выделить и такие необычные, как написанный в стихах трактат Carmen de Algorismo (латинское carmen и означает стихи) Александра де Вилла Деи (Alexander de Villa Dei, ум. 1240) или учебник венского астронома и математика Георга Пурбаха (Georg Peurbach, 1423—1461) Opus algorismi jocundissimi («Веселейшее сочинение по алгоритму»).

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

Можно обратить внимание на то, что первоначальная форма algorismi спустя какое-то время потеряла последнюю букву, и слово приобрело более удобное для европейского произношения вид algorism. Позднее и оно, в свою очередь, подверглось искажению, скорее всего, связанному со словом arithmetic.

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

В XVIII веке в одном из германских математических словарей, Vollstandiges mathematisches Lexicon (изданном в Лейпциге в 1747 г.), термин algorithmus всё ещё объясняется как понятие о четырёх арифметических операциях. Но такое значение не было единственным, ведь терминология математической науки в те времена ещё только формировалась. В частности, выражение algorithmus infinitesimalis применялось к способам выполнения действий с бесконечно малыми величинами. Пользовался словом алгоритм и Леонард Эйлер, одна из работ которого так и называется — «Использование нового алгоритма для решения проблемы Пелля» (De usu novi algorithmi in problemate Pelliano solvendo). Мы видим, что понимание Эйлером алгоритма как синонима способа решения задачи уже очень близко к современному.

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

Историки датируют 1691 годом один из списков древнерусского учебника арифметики, известного как «Счётная мудрость». Это сочинение известно во многих вариантах (самые ранние из них почти на сто лет старше) и восходит к ещё более древним рукописям XVI в. По ним можно проследить, как знание арабских цифр и правил действий с ними постепенно распространялось на Руси. Полное название этого учебника — «Сия книга, глаголемая по еллински и по гречески арифметика, а по немецки алгоризма, а по русски цифирная счётная мудрость».

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

Алгоритмы становились предметом всё более пристального внимания учёных, и постепенно это понятие заняло одно из центральных мест в современной математике. Что же касается людей, от математики далёких, то к началу сороковых годов это слово они могли услышать разве что во время учёбы в школе, в сочетании «алгоритм Евклида». Несмотря на это, алгоритм всё ещё воспринимался как термин сугубо специальный, что подтверждается отсутствием соответствующих статей в менее объёмных изданиях. В частности, его нет даже в десятитомной Малой советской энциклопедии (1957 г.), не говоря уже об однотомных энциклопедических словарях. Но зато спустя десять лет, в третьем издании Большой советской энциклопедии (1969 г.) алгоритм уже характеризуется как одна из основных категорий математики, «не обладающих формальным определением в терминах более простых понятий, и абстрагируемых непосредственно из опыта». Как мы видим, отличие даже от трактовки первым изданием БСЭ разительное! За сорок лет алгоритм превратился в одно из ключевых понятий математики, и признанием этого стало включение слова уже не в энциклопедии, а в словари. Например, оно присутствует в академическом «Словаре русского языка» (1981 г.) именно как термин из области математики.

Одновременно с развитием понятия алгоритма постепенно происходила и его экспансия из чистой математики в другие сферы. И начало ей положило появление компьютеров, благодаря которому слово «алгоритм» вошло в 1985 г. во все школьные учебники информатики и обрело новую жизнь. Вообще можно сказать, что его сегодняшняя известность напрямую связана со степенью распространения компьютеров. Например, в третьем томе «Детской энциклопедии» (1959 г.) о вычислительных машинах говорится немало, но они ещё не стали чем-то привычным и воспринимаются скорее как некий атрибут светлого, но достаточно далёкого будущего. Соответственно и алгоритмы ни разу не упоминаются на её страницах. Но уже в начале 70-х гг. прошлого столетия, когда компьютеры перестали быть экзотической диковинкой, слово «алгоритм» стремительно входит в обиход. Это чутко фиксируют энциклопедические издания. В «Энциклопедии кибернетики» (1974 г.) в статье «Алгоритм» он уже связывается с реализацией на вычислительных машинах, а в «Советской военной энциклопедии» (1976 г.) даже появляется отдельная статья «Алгоритм решения задачи на ЭВМ». За последние полтора-два десятилетия компьютер стал неотъемлемым атрибутом нашей жизни, компьютерная лексика становится всё более привычной. Слово «алгоритм» в наши дни известно, вероятно, каждому. Оно уверенно шагнуло даже в разговорную речь, и сегодня мы нередко встречаем в газетах и слышим в выступлениях политиков выражения вроде «алгоритм поведения», «алгоритм успеха» или даже «алгоритм предательства». Академик Н. Н. Моисеев назвал свою книгу «Алгоритмы развития», а известный врач Н. М. Амосов — «Алгоритм здоровья» и «Алгоритмы разума». А это означает, что слово живёт, обогащаясь всё новыми значениями и смысловыми оттенками.

Определения алгоритма

Формальное определение

Разнообразные теоретические проблемы математики и ускорение развития физики и техники поставили на повестку дня точное определение понятия алгоритма.

Первые попытки уточнения понятия алгоритма и его исследования осуществляли в первой половине XX века Алан Тьюринг, Эмиль Пост, Жак Эрбран, Курт Гедель, А. А. Марков, Алонзо Чёрч. Было разработано несколько определений понятия алгоритма, но впоследствии было выяснено, что все они определяют одно и то же понятие (см. Тезис Чёрча — Тьюринга) [3]

Источник

Что такое алгоритм?! Часть первая

Терзаем вместе основной кирпичик программиста — Алгоритм.

Проблема

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

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

Почему конкретный прием был успешен в задаче-образце? Будет ли он успешен в твоём проекте? Какие признаки проекта дают понять, что использование приёма уместно?

В личном опыте существования в профессии не раз отмечено, что каждый Junior борется с одинаковыми ветряными мельницами и постигает методы создания программ основываясь только на своих ошибках. Но ведь такие ошибки совершили уже очень многие. Почему до сих пор не создана система правил программирования, которая поможет обойти новоиспеченному кораблю-программисту подводные прибрежные камни? Ну, например, объяснение вреда использования метода «Copy-Paste» для развития кода. Если такие правила получится объяснить малым набором причин, их сформировавшим, то это объяснение обеспечит их запоминание и последующее использование в практике, тем самым поможет уклониться от бесчисленных грабель, разложенных тут и там.

Для компактного и полезного набора объяснений нужно:

Если обобщить, то нужны алгоритмы для написания и развития алгоритмов.

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

Задача

Сформулируем основную задачу, которую хочется решить. Для этого сначала запишем операции над алгоритмами, которые программист выполняет в ходе написания своего проекта:

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

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

Сразу возникает масса вопросов к этому определению:

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

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

Определение алгоритма

Рассмотрим определение алгоритма, говорящее, что он — приводящая к решению задачи последовательность действий. Как программисту мне приходится писать много кода. Этот код состоит из частей. Такими частями являются и функции, и классы, и модули. Когда я пишу текст функции — я занимаюсь написанием алгоритма.

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

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

Если «действие = алгоритм», то определение можно попробовать переписать рекурсивно «алгоритм — это приводящая к решению задачи последовательность использования существующих алгоритмов». Рекурсивные определение не самое простое, что можно записать в словаре обычного человека. Но для программиста и математика эта форма знакома. Мы умеем с ней работать, и это даёт нам преимущество в рассмотрении разных задач, разбиваемых на подобные себе подзадачи. Так давайте воспользуемся этим преимуществом.

Чтобы разрешить рекурсию нам необходимо найти:

Действие

Для начала рассмотрим «действие» и попробуем найти причину, обеспечивающую возможность использования существующего «действия» для создания нового алгоритма.

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

Какие признаки «действия» кроме повторимости делают возможным его использование в создании алгоритма? Что является терминальным неделимым «действием»? Чтобы ответить на этот вопрос стоит рассмотреть разные примеры «действий» из нашего опыта. Программисты встречали их много раз. Это и сложение, и умножение, и установка цвета пикселя на экране. Но мы знакомы с ними и вне программирования. Вся наука основывается на повторяемых явлениях.

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

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

В рамках примера процесса «Земля-Яблоко» можно отметить у «действия» следующие признаки:

Рассмотрим с этими признаками разные области и процессы, выделяя в них примеры «действий» и контролируя особенности указанных признаков в описании структуры «действия».

Физические процессы

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

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

Химические процессы

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

Математические процессы

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

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

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

Сложение и древний математик

Для математика, оперирующего камешками, сумма это «действие» со следующими характеристиками.

Сложение и математик-абакист

У математика с абаком ситуация сложнее. Кучки разделены по значению на разрядные борозды.

Можно рассмотреть самый простой абак с двумя разрядами-бороздами. Пусть он будет десятичный. Тогда один камешек на борозде десятков соответствует десяти камешкам на борозде единиц. И 10 — это максимальное количество камешков на борозде единиц. По сравнению с действием первого математика меняется представление слагаемых. И в арсенале математика уже необходимы нескольких готовых «действий».

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

Сложение и машина Тьюринга

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

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

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

Выводы

Соберём всё, что мы отметили рассматривая разные примеры «действия»:

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

Следующая статья серии (Часть 2) будет посвящена рассмотрению способов, с использованием которых «действия» могут быть сгруппированы в алгоритм. Этих способов достаточно много и есть предпосылки, что их описание не получится уместить в одну статью. Напишем — увидим.

Спасибо Вам за внимание.

Отзывы

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

Отдельное волнение у меня есть по стилю и форматированию, используемым в статье (кавычки, абзацы, курсив). Напишите, пожалуйста, если у Вас есть замечания к ним. Можно личным сообщением.

Источник