Блок-схемы. Алгоритмы

Решение задачи при помощи ЭВМ начинается с составления алгоритма. Что же такое алгоритм?

Происхождение термина «алгоритм» связывают с именем великого математика Мухаммеда аль-Хорезми (763–850 гг.), который разработал правила выполнения четырех арифметических действий.

Согласно ГОСТ 19781-74:

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

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

Разработать алгоритм означает разбить задачу на определенную последовательность шагов. От разработчика алгоритма требуется знание особенностей и правил составления алгоритмов.

Основные особенности алгоритмов:

Наличие ввода исходных данных.

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

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

Однозначность – каждый шаг алгоритма должен быть четко определен и не должен допускать произвольной трактовки исполнителем.

Конечность – исполнение алгоритма должно закончиться за конечное число шагов.

Корректность – алгоритм должен задавать правильное решение задачи.

Массовость (общность) – алгоритм разрабатывается для решения некоторого класса задач, различающихся исходными данными.

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

Способы записи алгоритмов

Разработанный алгоритм может быть представлен несколькими способами:

на естественном языке (словесная запись алгоритма);

в виде блок-схем (графическая форма);

на языке программирования.

Словесная запись алгоритма. Словесная форма используется обычно для описания алгоритмов, предназначенных исполнителю – человеку . Команды записываются на обычном языке и выполняются по порядку. В командах могут использоваться формулы, специальные обозначения, но каждая команда должна быть понятна исполнителю. Естественный порядок команд может быть нарушен (если требуется, например, переход к предыдущей команде или требуется обойти очередную команду при каком-то условии), в этом случае команды можно нумеровать и указывать команду, к которой требуется перейти. Например, перейти к п.3 или повторить с п.4 .

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

На языке программирования. Если алгоритм разработан для решения задачи на ЭВМ, то для того, чтобы он мог выполниться исполнителем – ЭВМ , его необходимо записать на языке, понятном этому исполнителю. Для этого разработано множество языков программирования для решения задач разных классов. Запись алгоритма на языке программирования называется программой .

Понятность - алгоритм должен состоять из команд, "понятных" исполнителю (входящих в систему команд исполнителя).

Дискpетность (прерывность, раздельность) - алгоpитм должен пpедставлять пpоцесс pешения задачи как последовательное выполнение пpостых (или pанее опpеделенных) шагов.

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

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

Массовость - алгоpитм pешения задачи pазpабатывается в общем виде, т.е. он должен быть пpименим для некотоpого класса задач, pазличающихся лишь исходными данными. Пpи этом исходные данные могут выбиpаться из некотоpой области, котоpая называется областью пpименимости алгоpитма.

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

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

Эти действия называются допустимыми действиями исполнителя. Только их и можно использовать.

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

Сложность алгоритма

Сложность алгоритма позволяет оценить, насколько быстро растет трудоёмкость алгоритма с увеличением объема входных данных. Под трудоемкостью понимается количество элементарных операций, которые необходимо выполнить для решения задачи с помощью данного алгоритма. Обычно оценка сложности алгоритма представляется в виде O(f(N)), где O – функция сложности, а N – число обрабатываемых наблюдений или примеров. Наименее затратными являются алгоритмы, для которых функция сложности имеет вид f(N)=C и f(N)=C*N, где С – константа. В первом случае вычислительные затраты не зависят от количества обрабатываемых данных, а во втором случае – линейно возрастают. Самыми затратными являются алгоритмы, сложность которых имеет степенную и факториальную зависимости от числа обрабатываемых наблюдений.

СОРТИРОВКА

Сортировка представляет собой процесс упорядочения множества подобных информационных объектов в порядке возрастания или убывания их значений. Например, список i из n элементов будет отсортирован в порядке возрастания значений элементов, если i <= i <= ... <= i.

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

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

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

МЕТОДЫ ПОИСКА

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

Сегодня мы дадим ответ на вопрос о том, что такое алгоритм.

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

Что называется алгоритмом

Понятие алгоритма является довольно древним и относится к одному из главных, а также базовых понятий в математике. Термин происходит от латинского написания имени известного восточного математика 787-850 годов Мухаммеда аль-Хорезми - Algorithmi. Этот ученный был первым, кто сформулировал точные правила для записи натуральных чисел, а также правила для подведения отсчётов в столбик. Довольно интересным фактом является и то, что, несмотря на древние корни, само понятие было точно сформулировано лишь в начале ХХ века. Ныне алгоритм является основной составляющей современного бизнеса, любого учебного процесса или же исследования. Именно поэтому каждому современному человеку просто необходимо точно знать, что означает алгоритм.

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

Что такое свойства алгоритмов

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

1. Одним из важнейших свойств является дискретность. Ее мы рассмотрим чуточку ниже.
2. Не менее важной является определенность. Согласно данному свойству каждая команда должна быть однозначной и наводить исполнителя на конкретное действие.
3. Стоит помнить и о понятности алгоритма. В алгоритме должны использоваться только необходимые команды, которые относятся к поставленной задаче.
4. Важным свойством является и результативность (также часто называют конечностью) алгоритма. Свойство «результативность» указывает на то, что в алгоритме имеется определенное, ранее указанное число шагов, выполнение которых приведет к выполнению поставленной задачи.
5. Также любой алгоритм должен обязательно обладать и таким свойством, как массовость. Если алгоритм обеспечивает выполнение всех задач определенного типа, то он обладает свойством массовости.

Что такое алгоритм в информатике

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

Алгоритм, записанный на формальном языке, принято называть программой. Очень часто понятие алгоритма тесно связывается с процессом его записи в программу. Именно поэтому термин алгоритма и программы зачастую считают синонимами

Как создать алгоритм

Для того, чтобы создать эффективный и качественный алгоритм, следует соблюдать несколько правил:

1. Алгоритм обязательно должен писаться на формальном и ясном языке. Неоднозначность или же неясность указаний недопустима.
2. При составлении алгоритма нужно обязательно учесть и то, для кого он составляется. Исполнитель должен понимать все пункты алгоритма и иметь возможность претворить их в жизнь.
3. Желательно делать алгоритм кратким, точным и ясным.

Что такое линейный алгоритм

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

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

Именно простые операторы наиболее часто используются в линейных алгоритмах.

Свойство дискретности алгоритма и ее значение

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

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

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

ПОНЯТИЕ АЛГОРИТМА. СВОЙСТВА АЛГОРИТМА. ВИДЫ АЛГОРИТМОВ. СПОСОБЫ ОПИСАНИЯ АЛГОРИТМОВ

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

Основными свойствами алгоритма являются:

1. детерминированность (определенность). Предполагает получение однозначного результата вычислительного процecca при заданных исходных данных. Благодаря этому свойству процесс выполнения алгоритма носит механический характер;
2. результативность. Указывает на наличие таких исходных данных, для которых реализуемый по заданному алгоритму вычислительный процесс должен через конечное число шагов остановиться и выдать искомый результат;
3. массовость. Это свойство предполагает, что алгоритм должен быть пригоден для решения всех задач данного типа;
4. дискретность. Означает расчлененность определяемого алгоритмом вычислительного процесса на отдельные этапы, возможность выполнения которых исполнителем (компьютером) не вызывает сомнений.

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

Наибольшее распространение благодаря своей наглядности получил графический (блок-схемный) способ записи алгоритмов.

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

При всем многообразии алгоритмов решения задач в них можно выделить три основных вида вычислительных процессов:

• линейный;
• ветвящийся;
• циклический.

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

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

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

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

Общие определения

Единого «истинного» определения понятия «алгоритм» нет. Наиболее известные варианты определения опираются на интуитивное понятие «задачи»:

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

Формальные признаки алгоритмов

• Детерминированность : в каждый момент времени следующий шаг работы однозначно определяется состоянием исполнителя. Алгоритм выдаёт один и тот же результат (ответ) для одних и тех же исходных данных.
• Понятность : алгоритм должен включать только команды из заранее оговоренной системы команд исполнителя.
• Завершаемость (конечность): при корректно заданных исходных данных алгоритм должен завершать работу и выдавать результат за конечное число шагов.
• Массовость : алгоритм должен быть применим к разным наборам исходных данных.

Алгоритмы анализа данных

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

В машинном обучении понятие алгоритм может употреблять в трёх смыслах.

Литература

1. Рудаков, К. В. Алгебраическая теория универсальных и локальных ограничений для алгоритмов распознавания : Дис. док. физ.-мат. наук: 05-13-17. - Вычислительный центр АН СССР, 1992. - 274 с. (