Какие виды алгоритмов вы знаете

Виды алгоритмов и способы их записи

Существует два вида алгоритмов: работы с величинами (числовыми, символьными, логическими) и работы «в обстановке» (например, робот). Они должны быть записаны на алгоритмическом языке, т. е. представлены в виде графического и/или словесного описания, таблицы, последовательности формул, на учебном алгоритмическом языке, языке программирования. Иногда их записывают на псевдокодах (специальных языках). Алгоритмический язык — это система обозначений и правил для единообразной и точной записи алгоритмов и исполнения их. Язык записи алгоритма должен быть понятным для человека.

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

Наиболее распространен специальный графический язык описания алгоритмов — структурные схемы. Схема в стандарте определена как «графическое представление определения, анали-

Алг Сложение цел А, В, С нач

ввод А ввод В С:=А+В вывод С

Рис. 3.1. Структурная схема исполнения компьютером вычислений алгоритма за или метода решения задачи, в котором используются символы для отображения операций, данных, потока, оборудования и др.». Могут быть схемы данных, программ, работы системы, взаимодействия программ, ресурсов системы. Схемы обеспечивают наглядность, читаемость, отображение последовательности выполняемых процессов. Схема — это ориентированный граф, стрелками (или линиями) указывающий порядок исполнения команд алгоритма, а вершины (события) такого графа представлены геометрическими фигурами, которые называются символами. Например, (рис. 3.2): начало и конец записи алгоритма обозначаются овалом, данные (носитель которых не определен) — параллелограммом, процесс (обработка данных любого вида) — в виде прямоугольника, решение (или функция переключательного типа, например условие) — в виде ромба и т. д. Стандарт на этот специальный графический язык дан в ЕСПД (Единая система программной документации — ГОСТ 19.701—90).

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

В основе построения алгоритмических структур лежит теорема структурного программирования, включающая следующие основные принципы:

• 1) всякий реальный алгоритм может быть построен с использованием трех базовых элементов: следования, ветвления и цикла;
• 2) любая алгоритмическая структура, состоящая из базовых элементов, может быть представлена как единый процесс;
• 3) алгоритм проектируется по нисходящей схеме;
• 4) поэтапное уточнение или пошаговая детализация алгоритма.

В графической форме базовые вершины могут быть одного из трех типов:

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

Рис. 3.3. Схемы основных алгоритмических структур

Первая схема на рис. 3.3 — самая простая структура алгоритма — последовательность, когда команды следуют одна за другой в естественном порядке. Такой алгоритм называется линейным. Здесь 51 и 52 — некоторые серии команд для использования (5 — функциональные вершины).

Вторая схема — структура, в которой порядок следования команд определяется в зависимости от результатов проверки некоторых условий. Такой алгоритм называется разветвляющимся, здесь действия записываются не подряд, а в зависимости от выполнения (невыполнения) некоторого условия. В — условие (предикатная вершина), в зависимости от истинности (Т) или ложности (F) которого управление передается по одной из двух ветвей. Объединяющая вершина обозначена символом О.

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

Схему алгоритма можно нарисовать, например, вызвав через меню текстового процессора MS Word команды Вид Панели инструментов Рисование, с помощью автофигур (группа Блок-схема), где представлены начертания всех стандартных фигур и их обозначения. Надписи в фигурах следует создать с помощью команд Вставка -> Надпись.

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

На рис. 3.4 представлена структурная схема линейного алгоритма для решения следующей задачи: «Найти энергию магнитного поля при заданных значениях магнитного потока, силы

Рис. 3.4. Структурная схема алгоритма к задаче линейной структуры

тока и количества витков». (Программу к этой задаче см. в разделе 3.2.)

В схеме разветвляющегося алгоритма проверку условия выполняет логический блок, который изображается ромбом. Внутри него указывается проверяемое условие (отношение), и имеется два выхода: Да и Нет. Если условие истинно, то выходим на Да, если ложно — то на Нет (рис. 3.5).

На рис. 3.6 представлена схема циклического алгоритма.

Для составления алгоритма следует:

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

Рис. 3.5. Типовая структурная схема разветвляющегося алгоритма

Рис. 3.6. Типовая структурная схема циклического алгоритма: а — цикл с предусловием; б — цикл с постусловием

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

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

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

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

инициализация начального действия

repeat (повторять до тех пор) выбор очередного действия if подходит then его запись; if решение не полное then RETR;

if неудача then стирание оператора и возврат на предыдущий

until (пока) удача or (или) нет действия

Такая рекурсивная процедура поможет правильно построить программу.

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

Например, кривые Серпинского первого и второго порядка можно разбить на части, которые соединяются четырьмя отрезками. Эти четыре части кривой представляют одну и ту же ломаную, поворачивающуюся каждый раз на 90°.

Контрольные вопросы

• 1. Что такое алгоритм?
• 2. Что такое система команд исполнителя?
• 3. Какие вы знаете виды алгоритмов?
• 4. Что такое алгоритмический язык?
• 5. Каков графический язык описания алгоритмов?
• 6. Какие вы знаете графические символы записи действий алгоритма?
• 7. Какая теорема лежит в основе построения алгоритмических структур?
• 8. Какие вы знаете структуры алгоритмов?
• 9. Дайте характеристику алгоритмическим структурам.
• 10. Что такое рекурсия и рекурсивный алгоритм?

Информатика

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

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

1.Универсальность (массовость) — применимость алгоритма к различным наборам исходных данных.

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

3.Конечность — каждое из действий и весь алгоритм в целом обязательно завершаются.

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

5.Выполнимость (эффективность) — результата алгоритма достигается за конечное число шагов.

6.Детерминированность (определенность) — алгоритм не должен содержать предписаний, смысл которых может восприниматься неоднозначно. Т.е. одно и то же предписание после исполнения должно давать один и тот же результат.

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

1. вычислительные алгоритмы , работающие со сравнительно простыми видами данных, такими как числа и матрицы, хотя сам процесс вычисления может быть долгим и сложным;

2. информационные алгоритмы , представляющие собой набор сравнительно простых процедур, работающих с большими объемами информации (алгоритмы баз данных);

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

По типу передачи управления алгоритмы бывают: основные (главные выполняемые программы) и вспомогательные (подпрограммы).

Для задания алгоритма необходимо описать следующие его элементы:

1.набор объектов, составляющих совокупность возможных исходных данных, промежуточных и конечных результатов;

3.правило непосредственной переработки информации (описание последовательности действий);

5.правило извлечения результатов.

Способы описания алгоритмов.

Символьный, когда алгоритм описывается с помощью специального набора символов (специального языка).

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

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

Правила создания блок – схем:

1.Линии, соединяющие блоки и указывающие последовательность связей между ними, должны проводится параллельно линиям рамки.

2.Стрелка в конце линии может не ставиться, если линия направлена слева направо или сверху вниз.

3.В блок может входить несколько линий, то есть блок может являться преемником любого числа блоков.

4.Из блока (кроме логического) может выходить только одна линия.

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

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

7.Схему алгоритма следует выполнять как единое целое, однако в случае необходимости допускается обрывать линии, соединяющие блоки.

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

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

1.«да» — условие выполнено.

2.«нет» — условие не выполнено.

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

Линейные алгоритмыЛинейные алгоритмыПовторение: Что такое алгоритм? Какие виды алгоритмов вы знаете? В чем особенность линейного алгоритма? Что обязательно. — презентация

Презентация на тему: » Линейные алгоритмыЛинейные алгоритмыПовторение: Что такое алгоритм? Какие виды алгоритмов вы знаете? В чем особенность линейного алгоритма? Что обязательно.» — Транскрипт:

2 Повторение: Что такое алгоритм? Какие виды алгоритмов вы знаете? В чем особенность линейного алгоритма? Что обязательно есть в алгоритме с условием? Какова особенность циклического алгоритма? Приведите примеры каждого из видов алгоритмов.

3 НАЧАЛО ВВОД R S:=3,14*R 2 КОНЕЦ S ВЫВОД S

4 КОМАНДА ВЕТВЛЕНИЯ ИМЕЕТ ПОЛНУЮ (1) ИЛИ СОКРАЩЕННУЮ ФОРМУ(2) Условие Серия 1Серия 2 Да Нет 1 Условие Серия 1 ДаНет 2

5 НАЧАЛО ВВОД A,B КОНЕЦ ВЫВОД M A>B M:=AM:=B ДаНет

6 НАЧАЛО КОНЕЦ I I

7 Задание на дом: Повторить параграф 3.4. Выполнить в Word практическую работу. Задание 2 стр. 159 учебника

8 Практическая работа (стр. 159, задание 3) 1.Необходимые операции: Разгруппировать Цвет заливки, Порядок – на передний план, Группировать,

9 Задание: Собрать домик из частей

10 Дата: 6-а – 1 апреля, 6-б -, 6-в. Цель урока: 1.Закрепить умение работать в текстовом редакторе MS Word. 2.Повторить типы алгоритмических структур. 3.Развивать навыки работы с «горячими клавишами»

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

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

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

История возникновения термина

Сегодня это понятие является фундаментальным и в математике, и в информатике. Однако сам термин возник задолго до появления компьютеров и прочих электронных средств вычислительной техники. Впервые об алгоритме заговорили в средние века — именно тогда европейские ученые ознакомились с методами вычисления арифметических действий, производимых в десятичной системе счисления азиатским математиком по имени Мухаммед ибн Муса аль-Хорезми (от имени этого математика и сформировался термин Algorithm). Сочинение аль-Хорезми перевели, а в последующие столетия появилось много трудов, посвященных вопросу обучения искусству счёта посредством цифр. Можно вспомнить описание алгоритма в европейской науке в те годы:

Также значение слова «алгоритм» сегодня нередко связывают со значениями таких слов, как «рецепт», «метод», «процесс», «инструкция».

Исполнитель и программа

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

Отличительная черта исполнителя — способность выполнять команды, которые включены в алгоритм. Это становится возможным, благодаря описанию последнего на формальном языке, который исключает неоднозначность толкования. Множество команд задано изначально строго и является конечным. Действия, которые должен выполнить исполнитель, называют элементарными действиями, а сама запись алгоритмической последовательности на формальном языке — это программа. Разработка алгоритма в целях решения задачи — это алгоритмизация.

Главные характеристики

Выделяют следующие свойства алгоритма: массовость, дискретность, результативность, определенность, понятность, формальность, завершаемость. Будет не лишним рассмотреть их более подробно, дав каждому свойству алгоритма пояснение: 1. Массовость (универсальность). Благодаря этому свойству, алгоритм можно успешно применять к различным наборам исходных данных. Пусть существует запись некой абстрактной последовательности, выраженная формулой. Подставляя в эту формулу значения (каждый раз новые), пользователь будет получать верные решения в соответствии с определенным алгоритмом действий. 2. Дискретность (разрывность). Это свойство характеризует структуру. Каждая алгоритмическая последовательность действий делится на этапы (шаги), а процесс решения задачи — это последовательное исполнение простых шагов. Также дискретность обозначает, что для выполнения каждого этапа потребуется конечный временной отрезок (исходные данные преобразуются во времени в результат дискретно). 3. Определенность (точность, детерминированность) — это свойство указывает алгоритму, что каждый его шаг должен быть строго определенным, то есть различные толкования должны быть исключены. Строго определяется и порядок выполнения шагов. В результате каждый шаг определяется состоянием системы однозначно, когда четко понятно, какая команда станет выполняться на следующем шаге. Как итог — при любом исполнителе для одних и тех же исходных данных при выполнении одной и той же цепочки команд будет выдаваться одинаковый результат. Да, существуют вероятностные алгоритмы — в них на последующий шаг влияют как текущее состояние системы, так и генерируемое случайное число. Но при включении способа генерации рандомных чисел в перечень «исходных данных», вероятностный алгоритм превращается в подвид обычного. 4. Понятность. Должны быть включены лишь те команды, которые доступны и понятны исполнителю, то есть входят в систему его команд. 5. Формальность. Любой исполнитель действует формально и лишь выполняет инструкции, не вникая в смысл. Он не отвлекается от поставленной задачи и не рассуждает, зачем и почему они нужны. Рассуждениями занимается разработчик алгоритма, задача же исполнителя — просто исполнить предложенные команды и получить результат. «Приказы не обсуждают, а выполняют». 6. Завершаемость (конечность). Если исходные данные заданы корректно, алгоритм завершит свое действие и выдаст результат за конечное число шагов. 7. Результативность. Согласно этому свойству, любой алгоритм должен завершаться конкретными результатами.

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

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