Что такое алгоритмы программирования: основы и применение
Какой бы язык программирования вы бы не выбрали, вам нужно разбираться в алгоритмах программирования. Они позволяют понять общую схему написания кода и лучше внедриться в программирование.
Алгоритмы – представлены набором определенных инструкций или шагов, выполняемых компьютером для решения конкретной задачи. Они играют ключевую роль в разработке программного обеспечения, так как определяют, как конкретная задача будет выполнена на компьютере. Сегодня мы поговорим об определении, типах, основах и применении алгоритмов.
Алгоритмы: что это?
Алгоритмы – это набор четко определенных инструкций или шагов, которые выполняются в определенном порядке для решения конкретной задачи или достижения определенной цели. Их применение не ограничивается программированием, они широко используются в физике, математики и информатике в общем. Алгоритм позволяет точно описать процесс решения задачи, на который не смогут повлиять входные данные.
Курс изучения C#
Можете пройти наш бесплатный курс по изучению C#
Основные типы алгоритмов
Каждый тип задачи подразумевает наличие определенного типа алгоритма. Поэтому их насчитывается достаточно большое количество. Но мы осветим главные из них:
- Сортировка – предназначены для ранжирования данных. Различают:
- пузырьком – последовательно сравнивает и меняет соседние элементы массива до тех пор, пока весь массив не будет упорядочен;
- выбором – находит наименьший элемент в массиве и помещает его в начало, а затем ищет следующий наименьший элемент и помещает его следом, и так далее;
- вставками – постепенно строит отсортированный массив, вставляя элементы в правильное положение в уже упорядоченной части массива.
- линейный поиск – проходит по всем элементам массива последовательно до нахождения искомого элемента.;
- бинарный – применяется к отсортированным массивам, рекурсивно делит массив пополам и ищет искомый элемент в соответствующей половине.
- обход в глубину – посещает все вершины графа или дерева в глубину, передвигаясь вдоль одной ветви до конца, затем возвращается к следующей ветви;
- обход в ширину – посещает все вершины графа или дерева на одной глубине, затем переходит на следующий уровень.
- задача о рюкзаке – решает задачу выбора оптимального набора предметов с ограниченной вместимостью рюкзака, чтобы максимизировать их стоимость;
- расстановка ферзей – решает задачу размещения N шахматных ферзей на доске так, чтобы они не били друг друга.
Применение алгоритмов
Алгоритмы играют решающую роль в разработке технологий и обеспечивают эффективное и инновационное функционирование различных отраслей. Несколько отраслей их применения:
- Сетевое программирование. Определяют оптимальный путь передачи данных между узлами в сети, что важно для эффективной передачи информации. Они также используются для обработки запросов от клиентов и оптимизации маршрутизации.
- Базы данных. Обеспечивают быстрый поиск данных в базах данных путем создания оптимизированных индексов. Применяются В-деревья и хеш-таблицы. Также они позволяют оптимизировать запросы к базам данных, чтобы ускорить их выполнение и уменьшить нагрузку на сервер.
- Искусственный интеллект и машинное обучение. Применяются для определения, к какому классу или категории принадлежит определенный объект или данные, а также позволяют группировать данные на основе их схожести без предварительных знаний о классах.
- Графическое программирование. Применяются для создания реалистичных изображений и анимаций в графических приложениях и играх. Кроме того, алгоритмы используются для изменения и улучшения графических данных, таких как фильтры, коррекции цветов и другие эффекты.
- Алгоритмы в играх. С их помощью создаются модели, определяются оптимальные маршруты для персонажей или объектов в компьютерных играх, а также создается имитация «умного» поведения.
- Финансы. Используются для оценки и управления рисками в финансовых операциях и инвестициях, а также анализа рыночных данных и прогнозирования будущих цен на финансовые инструменты.
Курс изучения Java
Можете пройти наш бесплатный курс по изучению Java
Заключение
Алгоритмы являются ключевыми инструментами во многих сферах и помогают решать сложные задачи, автоматизировать процессы и делать более обоснованные решения. Это мощный инструмент, которым обязательно должен овладеть каждый программист.
Больше интересных новостей
На кого учиться в сфере IT в 2023 году: ТОП профессий
Deno заменит Node.js?
7 лучших игр на движке Unreal Engine
Какая зарплата у разработчика SQL?
Что такое алгоритмы программирования: основы и применение
Какой бы язык программирования вы бы не выбрали, вам нужно разбираться в алгоритмах программирования. Они позволяют понять общую схему написания кода и лучше внедриться в программирование.
Алгоритмы – представлены набором определенных инструкций или шагов, выполняемых компьютером для решения конкретной задачи. Они играют ключевую роль в разработке программного обеспечения, так как определяют, как конкретная задача будет выполнена на компьютере. Сегодня мы поговорим об определении, типах, основах и применении алгоритмов.
Алгоритмы: что это?
Алгоритмы – это набор четко определенных инструкций или шагов, которые выполняются в определенном порядке для решения конкретной задачи или достижения определенной цели. Их применение не ограничивается программированием, они широко используются в физике, математики и информатике в общем. Алгоритм позволяет точно описать процесс решения задачи, на который не смогут повлиять входные данные.
Основные типы алгоритмов
Каждый тип задачи подразумевает наличие определенного типа алгоритма. Поэтому их насчитывается достаточно большое количество. Но мы осветим главные из них:
- Сортировка – предназначены для ранжирования данных. Различают: пузырьком – последовательно сравнивает и меняет соседние элементы массива до тех пор, пока весь массив не будет упорядочен;выбором – находит наименьший элемент в массиве и помещает его в начало, а затем ищет следующий наименьший элемент и помещает его следом, и так далее;вставками – постепенно строит отсортированный массив, вставляя элементы в правильное положение в уже упорядоченной части массива.
- Поиск – требуются для поиска конкретной информации. Различают:линейный поиск – проходит по всем элементам массива последовательно до нахождения искомого элемента.;бинарный – применяется к отсортированным массивам, рекурсивно делит массив пополам и ищет искомый элемент в соответствующей половине.
- Графы и деревья – необходимы для нахождения наиболее коротких вариантов решения и анализа. Различают:обход в глубину – посещает все вершины графа или дерева в глубину, передвигаясь вдоль одной ветви до конца, затем возвращается к следующей ветви;обход в ширину – посещает все вершины графа или дерева на одной глубине, затем переходит на следующий уровень.
- Динамическое программирование – необходимы для решения сложных задач более легким способом. Чаще всего подходит для оптимизации и разделения одной большой задачи на несколько подзадач. Например:задача о рюкзаке – решает задачу выбора оптимального набора предметов с ограниченной вместимостью рюкзака, чтобы максимизировать их стоимость;расстановка ферзей – решает задачу размещения N шахматных ферзей на доске так, чтобы они не били друг друга.
- Рекурсия – необходимы для вызова самого себя, что позволяет решить задачу.
Применение алгоритмов
Алгоритмы играют решающую роль в разработке технологий и обеспечивают эффективное и инновационное функционирование различных отраслей. Несколько отраслей их применения:
- Сетевое программирование. Определяют оптимальный путь передачи данных между узлами в сети, что важно для эффективной передачи информации. Они также используются для обработки запросов от клиентов и оптимизации маршрутизации.
- Базы данных. Обеспечивают быстрый поиск данных в базах данных путем создания оптимизированных индексов. Применяются В-деревья и хеш-таблицы. Также они позволяют оптимизировать запросы к базам данных, чтобы ускорить их выполнение и уменьшить нагрузку на сервер.
- Искусственный интеллект и машинное обучение. Применяются для определения, к какому классу или категории принадлежит определенный объект или данные, а также позволяют группировать данные на основе их схожести без предварительных знаний о классах.
- Графическое программирование. Применяются для создания реалистичных изображений и анимаций в графических приложениях и играх. Кроме того, алгоритмы используются для изменения и улучшения графических данных, таких как фильтры, коррекции цветов и другие эффекты.
- Алгоритмы в играх. С их помощью создаются модели, определяются оптимальные маршруты для персонажей или объектов в компьютерных играх, а также создается имитация «умного» поведения.
- Финансы. Используются для оценки и управления рисками в финансовых операциях и инвестициях, а также анализа рыночных данных и прогнозирования будущих цен на финансовые инструменты.
Заключение
Алгоритмы являются ключевыми инструментами во многих сферах и помогают решать сложные задачи, автоматизировать процессы и делать более обоснованные решения. Это мощный инструмент, которым обязательно должен овладеть каждый программист.
Что такое алгоритм?! Часть первая
Терзаем вместе основной кирпичик программиста — Алгоритм.
Проблема
Текущее состояние в области программирования — это обучение ремеслу по большей части личной практикой или разборами примеров стороннего кода, с которым по каким-то причинам приходится сталкиваться.
В результате программированию учишься по наитию. Лишь немного в этом труде помогают сборники алгоритмов, прикладных техник и шаблонов проектирования. Общая совокупность предлагаемых ими рецептов выстраивается длинным списком, и его длина грозит каждому из прочитанных приемов быть позабытым (как была забыта 53-яя личная группа в «телеге» до введения разбиения по каталогам). Но даже тот прием, который остался в памяти, чаще всего просто является описанием прикладной задачи, в которой было успешно его использование.
Почему конкретный прием был успешен в задаче-образце? Будет ли он успешен в твоём проекте? Какие признаки проекта дают понять, что использование приёма уместно?
В личном опыте существования в профессии не раз отмечено, что каждый Junior борется с одинаковыми ветряными мельницами и постигает методы создания программ основываясь только на своих ошибках. Но ведь такие ошибки совершили уже очень многие. Почему до сих пор не создана система правил программирования, которая поможет обойти новоиспеченному кораблю-программисту подводные прибрежные камни? Ну, например, объяснение вреда использования метода «Copy-Paste» для развития кода. Если такие правила получится объяснить малым набором причин, их сформировавшим, то это объяснение обеспечит их запоминание и последующее использование в практике, тем самым поможет уклониться от бесчисленных грабель, разложенных тут и там.
Для компактного и полезного набора объяснений нужно:
- систематизировать методы работы с кодом;
- разобрать по группам приёмы работы с алгоритмами, которые являются главной целью написания любого кода;
- выделить простые признаки применения шаблонов проектирования;
- разработать универсальные правила и наборы эффективных способов построения сложных алгоритмов.
Если обобщить, то нужны алгоритмы для написания и развития алгоритмов.
Задуманная серия статей не претендует на полное решение указанной проблемы. Предпринимается небесспорная попытка сделать первый шаг на пути к этому решению. Этот шаг состоит в выделении структуры и свойств главного кирпичика программиста — Алгоритма.
Задача
Сформулируем основную задачу, которую хочется решить. Для этого сначала запишем операции над алгоритмами, которые программист выполняет в ходе написания своего проекта:
- методы синтеза макро-алгоритма из под-алгоритмов (последовательной, параллельной и смешанной группировкой);
- методы структурной трансформации макро-алгоритмов (оптимизационной, специализирующей, стыковочной. );
- методы сохранения и переноса алгоритмов;
- методы синтеза универсального алгоритма из сходных алгоритмов разных областей исполнения;
- методы специализации универсального алгоритма в новой области исполнения;
- методы формирования и развития комплексной системы совместно работающих алгоритмов;
- методы взаимодействия одновременно исполняющихся алгоритмов;
- и другие методы, полный список которых привести сложно, да и нет необходимости.
Рассмотрим существующие на текущий момент варианты значения слова «алгоритм» в поисках подсказок, о том как можно работать с алгоритмами.
Так, например, формулировка «конечная совокупность точно заданных правил решения произвольного класса задач» говорит что есть возможность как-то «точно задать правила» из них собрать «совокупность» и этой совокупностью «решить» некоторый «класс задач».
Сразу возникает масса вопросов к этому определению:
- Что такое правило?
- Как, кому и для кого это правило можно задать?
- Что есть объединение совокупностью?
- Каким образом правила соотносятся с задачей?
- Что формирует класс задачи?
- Определяется ли способ формирования совокупности правилами и задачами?
- .
Другая формулировка «набор инструкций, описывающих порядок действий исполнителя для решения некоторой задачи» говорит что есть «исполнитель», который может выполнять некоторые «действия», и при некотором «порядке» выполнения этих «действий» «решается задача». Вопросов не стало меньше:
- Какова структура набора?
- Какие есть варианты действий и исполнителей?
- Существуют ли минимально возможное действие, минимальный набор необходимых действий?
- Каким образом действия встроены в исполнителя?
- Какие есть способы создания копии исполнителя (например, если исполнитель — человек)?
- Как действия зависят друг от друга в упорядоченном выполнении?
- Что есть задача кроме того, что она выполняется последовательностью действий?
- Как задача соотносится с исполнителем и с действиями?
- Возможно ли использовать решение задачи в качестве действия?
- Какие возможны варианты указания порядка действий?
- Если воспроизведение патефоном записи звуков леса является алгоритмом, то какова структура этой задачи?
- Если репликация ДНК является алгоритмом, то каков её исполнитель?
- Если исполнителем является Машина Тьюринга, то как с её использованием решить механическую задачу, например, воспроизведение звука?
Перечислено много вопросов, но они мало помогают в поиске методов работы с алгоритмом. Поэтому поставим себе меньшую задачу, но тоже очень нам важную. Давайте попробуем сформулировать, что делает алгоритм способом решения наших задач, и какие процессы являются для него «действиями». Даже решение этой «маленькой» задачи оказывается очень объемным для одной статьи, поэтому будем его разбивать на части. И поэтому первую статью серии целиком посвятим только «Действию» и его признакам, которые опущены в указанных выше определениях алгоритма, но являются очень важными для ответов на все заданные вопросы.
Определение алгоритма
Рассмотрим определение алгоритма, говорящее, что он — приводящая к решению задачи последовательность действий. Как программисту мне приходится писать много кода. Этот код состоит из частей. Такими частями являются и функции, и классы, и модули. Когда я пишу текст функции — я занимаюсь написанием алгоритма.
Раньше алгоритм создавали в виде блок схем и полуавтоматически компилировали в машинные коды. Сейчас я избавлен от необходимости быть художником и компилятором для написания программы. Текст моей функции — это запись алгоритма в текстовом виде — его текстовая блок-схема. Здесь можно вспомнить Scratch, где используется визуальное создание блок-схемы алгоритма без написания текста. Способ записи алгоритма сейчас не так важен.
Важно, что в написании алгоритма функции я могу использовать вызовы других функции, которые я или другой программист уже написал до этого момента. Вспоминая фразу «последовательность действий, приводящая к решению задачи», можно отметить, что функции, написанные ранее, являются моими «действиями». То есть «действия» могут быть функциями. Если обобщать, то «действия» могут быть алгоритмами.
Если «действие = алгоритм», то определение можно попробовать переписать рекурсивно «алгоритм — это приводящая к решению задачи последовательность использования существующих алгоритмов». Рекурсивные определение не самое простое, что можно записать в словаре обычного человека. Но для программиста и математика эта форма знакома. Мы умеем с ней работать, и это даёт нам преимущество в рассмотрении разных задач, разбиваемых на подобные себе подзадачи. Так давайте воспользуемся этим преимуществом.
Чтобы разрешить рекурсию нам необходимо найти:
- терминальное условие выхода из рекурсии — минимальное неделимое «действие» (атомарный алгоритм), которое можно использовать в разработке алгоритма;
- способ перехода от текущего уровня рекурсии (набора «действий») к следующему уровню (алгоритму).
Действие
Для начала рассмотрим «действие» и попробуем найти причину, обеспечивающую возможность использования существующего «действия» для создания нового алгоритма.
Этой причиной является возможность повторного использования «действия» с получением тождественного результата. Только тогда разработанный с использованием этого «действия» алгоритм решения некоторой задачи будет одинаково решать эту задачу снова и снова. Мы нащупали важные законы нашего мира, в котором:
- существуют «действия», главным свойством которых является одинаковость результатов их исполнения в разные моменты времени и в разных местах,
- существует возможность создать такую схему использования нескольких «действий», которая сформирует из них новое «действие», которое мы назвали алгоритмом.
Какие признаки «действия» кроме повторимости делают возможным его использование в создании алгоритма? Что является терминальным неделимым «действием»? Чтобы ответить на этот вопрос стоит рассмотреть разные примеры «действий» из нашего опыта. Программисты встречали их много раз. Это и сложение, и умножение, и установка цвета пикселя на экране. Но мы знакомы с ними и вне программирования. Вся наука основывается на повторяемых явлениях.
Закон гравитации, описывающий повторяющееся явление падения яблока, тоже может стать действием. Ведь любое яблоко будет падать на землю? Значит этот процесс можно использовать в качестве «действия»! Например решая задачу прогнать Ньютона от яблони, на которую Вы случайно забрались ранее.
Рассмотрим, что происходит при выполнении «действия». Например, во время падения яблока с ветки яблони на землю. В этом процессе происходит несколько изменений. Если вспомнить школьную физику и рассмотреть ситуацию в системе отсчета, привязанной к Земле, то сила гравитации вызывает изменение скорости яблока, разгоняя его. При этом в процессе отмечается еще одно важное изменение — уменьшается расстояние между яблоком и Землей.
В рамках примера процесса «Земля-Яблоко» можно отметить у «действия» следующие признаки:
- наличие процесса изменения (расстояния и параметров движения объектов);
- наличие объектов, взаимодействие которых вызывает такие изменения;
- наличие локальности процесса, то есть существование значения расстояния между объектами, с превышением которого их взаимодействие перестает вызывать процесс изменения, что делает невозможным использование «действия» (Земля и гипотетическое яблоко, находящееся вне солнечной системы).
Рассмотрим с этими признаками разные области и процессы, выделяя в них примеры «действий» и контролируя особенности указанных признаков в описании структуры «действия».
Физические процессы
Для физических систем, процессы которых мы наблюдаем в нашем мире, характерные объекты и изменения опираются на фундаментальные взаимодействия и потому их достаточно просто выделить по аналогии с гравитационным взаимодействием Земли и яблока. Например, для системы из протона и электрона или системы двух протонов.
Отдельно от этих простых взаимодействий двух объектов стоят многокомпонентные процессы, например, ядерные реакции (по структуре «действия» близки к химическим процессам, рассматриваемым далее). Сложны и процессы описываемые суммарным взаимодействием большого числа элементов, например, «идеальный газ». Пока отложим их рассмотрение и сосредоточимся на самых простых примерах.
Химические процессы
Перейдем к следующей большой области — химическим процессам. Химические реакции (например, ) по признаку своей повторимости так же являются «действиями». Объектами в них являются атомы и молекулы. Для описания происходящих изменений необходимо немного преобразовать «физические» изменения. Так изменения параметров движения в совокупности дают нам изменение температуры в ходе химической реакции. А среди изменений расстояний между молекулами мы, игнорируя броуновское движение, можем выделить фиксацию расстояния в виде повторимого формирования и разрушения связей между частями взаимодействующих молекул. Локальность для химической реакции тоже существует — это отсутствие реакции при нахождении гидроксида натрия и соляной кислоты в разных пробирках и наличие реакции при соприкосновении веществ. Конечно, в «химической» области «действий» есть особенности не сводящиеся к молекулам, например, фотохимические реакции, где к объектам необходимо добавить фотоны. Самые простые процессы выбраны для рассмотрения намеренно.
Математические процессы
Следующей областью выберем «действия» из известных нам абстрактных алгоритмов. Самые яркие их представители — математические процессы. В этой области есть действительно «сложные случаи», но для этой статьи достаточно хорошо знакомых примеров. Рассмотрим в качестве «действия» достаточно элементарную операцию — сложение. А примером этого «действия» выберем сложение математиком двух целых чисел.
В ситуации с математиком можно выделить много объектов, но с точки зрения «действия» («сложение математиком двух целых чисел»), объекта всего три: это объект «математик», объект «первое число» и объект «второе число». В отличие от всех рассмотренных ранее объектов числа являются обозначениями, то есть виртуальными объектами. И их преобразование в алгоритме более сложно устроено нежели изменение расстояния и параметров движения объектов, как это было для «химических» действий. Подробности такого преобразования — это тема отдельной увлекательной статьи. А в рамках текущей рассмотрим древнего математика, который складывает числа, используя кучки камешков (рим. ‘calculi’), и более «современного» математика, использующего абак. Абстракции таких способов вычисления суммы не так далеко отошли от физических и химических процессов, поэтому структура процессов их «действий» полностью описывается изменениями расстояний и связей.
Интересно, что на примере древнего математика становится понятен смысл слова «сложить», которое отсылает нас к действию «класть» и к фразе «положить вместе».
Сложение и древний математик
Для математика, оперирующего камешками, сумма это «действие» со следующими характеристиками.
- это сам «математик» (он взаимодействует со слагаемыми);
- лежащая отдельно кучка №1, содержащая и связывающая вместе камешки (подобно химическим связям), и обозначающая первое слагаемое;
- лежащая отдельно кучка камешков №2, обозначающая второе слагаемое.
- «математик» подходит к кучкам (физически изменяет расстояние между кучками и собой) и начинает с ними взаимодействие;
- «математик» объединяет две кучки (физически изменяет расстояние между двумя кучками или переносит все камешки одной кучки в другую, возможно, используя «действие» «Перенос по-одному» камешку)
- сформированная кучка камешков, обозначающая результат (сумму);
- «математик», отошедший от кучки результата и переставший на неё воздействовать.
Сложение и математик-абакист
У математика с абаком ситуация сложнее. Кучки разделены по значению на разрядные борозды.
Можно рассмотреть самый простой абак с двумя разрядами-бороздами. Пусть он будет десятичный. Тогда один камешек на борозде десятков соответствует десяти камешкам на борозде единиц. И 10 — это максимальное количество камешков на борозде единиц. По сравнению с действием первого математика меняется представление слагаемых. И в арсенале математика уже необходимы нескольких готовых «действий».
- «Перенос по-одному» из борозды в борозду одинакового уровня (действие, позаимствованное у первого математика);
- «Перенос в десятки», которое необходимо выполнять, если борозда единиц полностью заполняется, тогда из неё убираются все камешки кроме одного, который переносится в борозду десятков.
- это сам «математик» (он взаимодействует со слагаемыми);
- группа камешков №1, лежащих и удерживаемых двумя бороздами (единиц и десятков), и обозначающих первое слагаемое;
- группа камешков №2, лежащих и удерживаемых двумя бороздами (единиц и десятков), и обозначающих второе слагаемое;
- «математик» подходит к группам борозд (физически изменяет расстояние между ними и собой) и начинает с ними взаимодействие;
- «математик» объединяет камешки из двух борозд единиц (физически изменяет расстояние между камешками, разрушает связи со старой бороздой и создает связи с новой) с использованием действий «Перенос по-одному» и «Перенос в десятки»;
- «математик» объединяет камешки из двух борозд десятков с использованием действия «Перенос по-одному»
- сформированная группа камешков в двух бороздах (единиц и десятков), обозначающая результат (сумму);
- «математик», отошедший от группы камешков результата и переставший на них воздействовать.
Локальность в этих математических «действиях» описывается отсутствием взаимодействия двух слагаемых, находящихся далеко от математика, и запуском процессов сложения когда все три объекта сложения «близко». Повторяемое изменение в математическом «действии» выражается в изменении связей между камнями и удерживающими их локациями (кучками, бороздами).
Сложение и машина Тьюринга
Можно пойти чуть дальше и заменить математика в таких «действиях» на «управляющее устройство» машины Тьюринга. Тогда «ячейки ленты» машины Тьюринга будут содержать слагаемые.
При этом остаётся и признак локальности как возможность взаимодействия управляющего устройства только с текущей ячейкой ленты, и признак изменения параметров объектов, который можно описать как изменение состояния ячеек.
Подробное описание исходных и результирующих состояний объектов, а так же «действий» производящих эти изменения для сложения, исполняемого машиной Тьюринга, оставим за рамками этой статьи. Но упомянем, что перейдя к машине мы снижаем требования к исполнителю «действия», что является главным способом для создания формальных методов работы с алгоритмом. Можно поставить себе целью упрощение каждой составляющей алгоритма до состояния, когда её выполнение можно будет поручить компьютеру. Тогда в определении алгоритма не останется тёмных мест, и многочисленные вопросы, перечисленные в начале, найдут свои ответы. Пока формализован только исполнитель. Скажем спасибо за это Тьюрингу и вспомним про «действие», формализация которого уже на пороге.
Выводы
Соберём всё, что мы отметили рассматривая разные примеры «действия»:
- «действие» можно использовать для создания алгоритма;
- «действие» может быть элементарным;
- «действие» может быть реализовано алгоритмом;
- в «действии» обязательно участвует некоторый объект или группа объектов;
- для группы объектов «действие» происходит только тогда, когда эти объекты «достаточно близко»;
- в действии изменяются связи и параметры объектов (включая параметры их движения);
- «действие» всегда и обязательно должно быть повторимо.
Признак Повторимости помогает нам в создании наших алгоритмов. С его использованием мы из всех процессов выделяем те, что являются «действием» и на их основе создаём новые алгоритмы. Более того этот признак достаточно прост и на основе его формализации можно снизить требования к системе обнаруживающей и создающей «действия» и поручить это нашему компьютеру.
Следующая статья серии (Часть 2) будет посвящена рассмотрению способов, с использованием которых «действия» могут быть сгруппированы в алгоритм. Этих способов достаточно много и есть предпосылки, что их описание не получится уместить в одну статью. Напишем — увидим.
Спасибо Вам за внимание.
Отзывы
Буду очень благодарен за отзывы и предложения, так как они помогают мне скорректировать направление развития работы в области.
Отдельное волнение у меня есть по стилю и форматированию, используемым в статье (кавычки, абзацы, курсив). Напишите, пожалуйста, если у Вас есть замечания к ним. Можно личным сообщением.
Ссылки
- Главная страница и теория работы (GitLab GPL): Проект «Общая теория алгоритмов»
- Вводная статья работы «Разрабатываем теорию алгоритмов как проект с открытым исходным кодом». Пожалуйста, не судите строго эту наивную публикацию «сверх-идеи» устаревшей версии 2019 года.
- Статьи серии «Что такое алгоритм?!»
- №1 «Действие» (текущая)
- №2 «Жизнь»
- №3 «Синтез алгоритма запоминанием»
- №3.1 «Эволюция памяти»
- №3.14 «Обучение»
- №5 «Эволюция поведения»
- №4 «Математика»
- №4.0 «Физика»
- №3.25 «Язык»
- №5.0 «Философия»
- №5.00 «Искусственный интеллект»
- Детская сказка программисту на ночь
- Эволюция программного проекта и ООП
- Как не понимать принципы развития архитектуры SOLID
Алгоритмы и исполнители
Понятие алгоритма так же фундаментально для информатики, как и понятие информации. Существует много различных определений алгоритма, так как это понятие достаточно широкое и используется в различных областях науки, техники и повседневной жизни.
Алгоритм – понятная и точная последовательность действий, описывающая процесс преобразования объекта из начального состояния в конечное.
Исполнителем алгоритма может быть как человек (кулинарные рецепты, различные инструкции, алгоритмы математических вычислений), так и техническое устройство. Различные машины (компьютеры, промышленные роботы, современная бытовая техника) являются формальными исполнителями алгоритмов. От формального исполнителя не требуется понимание сущности решаемой задачи, но требуется точное выполнение последовательности команд.
Алгоритм можно записывать различными способами (словесное описание, графическое описание – блок схема, программа на одном из языков программирования и т.д.). Программа – это алгоритм, записанный на языке программирования.
Для создания алгоритма (программы) необходимо знать:
- полный набор исходных данных задачи (начальное состояние объекта);
- цель создания алгоритма (конечное состояние объекта);
- систему команд исполнителя (то есть набор команд, которые исполнитель понимает и может выполнить).
Полученный алгоритм (программа) должен обладать следующим набором свойств:
- дискретность(алгоритм разбит на отдельные шаги — команды);
- однозначность (каждая команда определяет единственно возможное действие исполнителя);
- понятность (все команды алгоритма входят в систему команд исполнителя);
- результативность(исполнитель должен решить задачу за конечное число шагов).
Большая часть алгоритмов обладает также свойством массовости (с помощью одного и того же алгоритма можно решать множество однотипных задач).
Выше отмечалось, что один и тот же алгоритм может быть записан по-разному. Можно записывать алгоритм естественным языком. В таком виде мы используем рецепты, инструкции и т.п. Для записи алгоритмов , предназначенных формальным исполнителям , разработаны специальные языки программирования. Любой алгоритм можно описать графически в виде блок-схемы. Для этого разработана специальная система обозначений:
Обозначение Описание Примечания Начало и конец алгоритма Ввод и вывод данных. Вывод данных иногда обозначают иначе: Приведем пример описания алгоритма суммирования двух величин в виде блок-схемы:
Такой способ описания алгоритм наиболее нагляден и понятен человеку. Поэтому, алгоритмы формальных исполнителей обычно разрабатывают сначала в виде блок-схемы, и только затем создают программу на одном из языков программирования .
Программист имеет возможность конструировать и использовать нетипичные алгоритмические структуры, однако, в этом нет необходимости. Любой сколь угодно сложный алгоритм может быть разработан на основе трёх типовых структур: следования, ветвления и повторения. При этом структуры могут располагаться последовательно друг за другом или вкладываться друг в друга.
Линейная структура (следование).
Наиболее простой алгоритмической структурой является линейная. В ней все операции выполняются один раз в том порядке, в котором они записаны.
В полном ветвлении предусмотрено два варианта действий исполнителя в зависимости от значения логического выражения (условия). Если условие истинно, то выполняться будет только первая ветвь, иначе только вторая ветвь.
Вторая ветвь может быть пустой. Такая структура называется неполным ветвлением или обходом.
Из нескольких ветвлений можно сконструировать структуру «выбор» (множественное ветвление), которая будет выбирать не из двух, а из большего количества вариантов действий исполнителя, зависящих от нескольких условий . Существенно, что выполняется только одна ветвь — в такой структуре важное значение приобретает порядок следования условий: если выполняются несколько условий, то сработает только одно из них — первое сверху.
Цикл (повторение).
Цикл позволяет организовать многократное повторение одной и той же последовательности команд — она называется телом цикла. В различных видах циклических алгоритмов количество повторений может зависеть от значения логического выражения (условия) или может быть жестко задано в самой структуре. Различают циклы : « д о» , « п ока» , циклы со счётчиком . В циклах « д о» и « п ока» логическое выражение (условие) может предшествовать телу цикла (цикл с предусловием) или завершать цикл (цикл с послеусловием).
Ц иклы « д о» — повторение тела цикла до выполнения условия :
Ц иклы « п ока» — повторение тела цикла пока условие выполняется ( истинно ):
Ц иклы со счётчиком (с параметром) – повторение тела цикла заданное число раз :
Вспомогательный алгоритм (подпрограмма, процедура).
Вспомогательный алгоритм представляет собой модуль, к которому можно многократно обращаться из основного алгоритма. Использование вспомогательных алгоритмов может существенно уменьшить размер алгоритма и упростить его разработку.
Методы разработки сложных алгоритмов.
Существует два метода разработки сложных алгоритмов:
Метод последовательной детализации задачи («сверху-вниз») состоит в том, что исходная сложная задача разбивается на подзадачи. Каждая из подзадач рассматривается и решается отдельно. Если какие-либо из подзадач сложны, они также разбиваются на подзадачи. Процесс продолжается до тех пор, пока подзадачи не сведутся к элементарным. Решения отдельных подзадач затем собираются в единый алгоритм решения исходной задачи. Метод широко используется, так как позволяет вести разработку общего алгоритма одновременно нескольким программистам, решающим локальные подзадачи. Это необходимое условие быстрой разработки программных продуктов.
Сборочный метод («снизу-вверх») заключается в создании множества программных модулей, реализующих решение типичных задач. При решении сложной задачи программист может использовать разработанные модули в качестве вспомогательных алгоритмов (процедур). Во многих системах программирования уже существуют подобные наборы модулей, что существенно упрощает и ускоряет создание сложного алгоритма.
Управление — целенаправленное взаимодействие объектов, одни из которых являются управляющими, другие — управляемыми.
В простейшем случае таких объектов два:
С точки зрения информатики управляющие воздействия можно рассматривать как управляющую информацию. Информация может передаваться в форме команд. Последовательность команд по управлению объектом, приводящая к заранее поставленной цели, называется алгоритмом управления. Следовательно, объект управления можно назвать исполнителем управляющего алгоритма. В рассмотренном примере, управляющий объект работает «не глядя» на то, что происходит с управляющим объектом (управление без обратной связи). Такая схема управления называется незамкнутой. Другая схема управления может учитывать информацию о процессах, происходящих в объекте управления:
В этом случае, алгоритм управления должен быть достаточно гибким, чтобы анализировать эту информацию и принимать решение о своих дальнейших действиях в зависимости от состояния объекта управления (управление с обратной связью). Такая схема управления называется замкнутой.
Более подробно процессы управления изучаются рассматриваются кибернетикой. Эта наука утверждает, что самые разнообразные процессы управления в обществе, природе и технике происходят сходным образом, подчиняются одним и тем же принципам.
Языки программирования
Язык программирования – набор правил записи алгоритмических структур и данных.
Вся информация в компьютере, в том числе и компьютерные программы, представляется в двоичной форме, т.е. в виде последовательности нулей и единиц. На заре компьютерной эры программисты вынуждены были составлять программы именно в таком виде. Такой способ программирования позволяет создать программу, состоящую непосредственно из команд процессора (язык машинных команд). Написание и отладка такой программы всегда были чрезвычайно сложным и трудоёмким занятием. Для облегчения труда программистов были разработаны так называемые ассемблеры – языки, которые позволяли записывать машинные команды с помощью команд, состоящих из символов обычного алфавита. Языки машинных команд и ассемблеры относятся к языкам низкого уровня.
В 60 – 70-е годы прошлого века стали появляться языки высокого уровня – формальные языки, позволяющие записывать алгоритмы в привычном для человека виде. Такие языки строились на основе использования определённого набора символов – алфавита и строгих правил построения команд – синтаксиса. Широкое распространение получили процедурные языки высоко уровня. Самые известные процедурные языки — Basic и Pascal . Они развивались длительное время, и последние версии этих языков используются и сейчас ( Qbasic , TurboPascal ). В них широко используются команды (операторы), реализующие типовые алгоритмические структуры. Для ввода и редактирования такой программы используется подобие текстового редактора. Для исполнения такой программы компьютер с помощью специальной программы – транслятора (компилятора или интерпретатора) осуществляет перевод программы с языка высокого уровня в язык машинных команд, при этом компьютер должен проверять программу на наличие ошибок и сообщать о них программисту. Таким образом, для создания компьютерной программы нужны другие компьютерные программы!
Система программирования – набор программ, необходимых для ввода, редактирования, отладки и исполнения программы, записанной с помощью одного из языков программирования.
В настоящее время наибольшей популярностью пользуются системы объектно-ориентированного визуального программирования ( Visual Basic , Delphi ). Разработка программы с помощью такой системы программирования состоит из двух этапов:
- создание в визуальном режиме элементов графического интерфейса программы;
- разработка программного кода.
Такой подход существенно облегчает создание программ, так как разработка графического интерфейса вручную (в процедурных языках) сложный и трудоёмкий процесс.