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