72814

Алгоритм, его свойства. Виды алгоритмов. Формы записи алгоритмов

Доклад

Информатика, кибернетика и программирование

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

Русский

2014-11-30

53 KB

5 чел.

Алгоритм, его свойства. Виды алгоритмов. Формы записи алгоритмов.


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

Алгоритм означает точное описание некоторого процесса, инструкцию по его выполнению. Разработка алгоритма является сложным и трудоемким процессом. Алгоритмизация – это техника разработки (составления) алгоритма для решения задач на ЭВМ.

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

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

  1.  
    Наличие ввода исходных данных.
  2.  
    Наличие вывода результата выполнения.
  3.  
    Однозначность (компьютер «понимает» только однозначные инструкции).
  4.  
    Общность – алгоритм предназначен для решения некоторого класса задач.
  5.  
    Корректность – алгоритм должен давать правильное решение задачи.
  6.  
    Конечность – решение задачи должно быть получено за конечное число шагов.
  7.  
    Эффективность – для решения задачи должны использоваться ограниченные ресурсы компьютера (процессорное время, объем оперативной памяти и т.д.).


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

  1.  
    Массовость – алгоритм должен описывать круг однотипных задач, исходные данные которых могут изменяться в определенных пределах.
  2.  
    Детерминированность – это обусловленность всех шагов алгоритма потребностью решения данных задач. Свойство детерминированности выражается в том, что при заданных значениях параметров алгоритм выполняется формально, т.е. строго выполняется последовательностьдействий до появления результата.
  3.  
    Понятность – предписания алгоритма должны быть сформулированы так, чтобы они понимались одинаково разработчиком и исполнителем, т.е. они должны быть однозначно понятны.
  4.  
    Дискретность – четкое разделение всего пути решения задачи на отдельные этапы (шаги) так, чтобы ход выполнения алгоритма проходил поэтапно, вовремя корректируя действия исполнителя.
  5.  
    Результативность – точное выполнение предписаний алгоритма должно привести к результату за n шагов, если правильно разработана исходная модель и сам алгоритм.


Всякий человек при планировании деятельности обязательно выполняет две операции:

  1.  
    Оценивает исходные данные (создает исходную модель).
  2.  
    Прогнозирует результат (прогнозирует какую-то конечную модель).


Суть решения задачи в переходе от исходной модели к прогнозируемому результату, через конечное число действий.

Несмотря на многообразие алгоритмов все они строятся из 3-х типов алгоритмических структур.

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

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

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

Изобразительные средства для описания (представление) алгоритма


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

  •  
    Словесно- формульное описание


Блок-схема (схема графических символов)

  •  
    Алгоритмические языки


Операторные схемы

  •  
    Псевдокод


Для записи алгоритма существует общая методика:

  •  
    Каждый алгоритм должен иметь имя, которое раскрывает его смысл.


Необходимо обозначить начало и конец алгоритма.


Описать входные и выходные данные.

  •  
    Указать команды, которые позволяют выполнять определенные действия над выделенными данными 


Общий вид алгоритма

Алгоритм: Название алгоритма

Описание данных

Начало

Команды

Конец

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

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

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

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

Основные блоки.(Рис.1)

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

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

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

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

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

Принципы разработки алгоритмов и программ


Типы алгоритмических процессов

По структуре выполнения алгоритмы и программы делятся на три вида:

  •  
    Линейные


Ветвящиеся

  •  
    Циклические


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

Алгоритмы разветвляющейся структуры

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

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

(Рис.2)

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

(Рис.3) (Рис.4)
Особенностью первой схемы является то, что проверка условия выхода из цикла проводится до выполнения тела цикла. В том случае, если условие выхода из цикла выполняется, то тело цикла не выполняется ни разу. 

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

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

Алгоритм любой сложности может быть представлен комбинацией трех базовых структур:

  •  
    следование;


ветвление (в полной и сокращенной форме);

  •  
    цикл (с предусловием или постусловием).


Характерной особенностью этих структур является наличие у них одного входа и одного выхода. 

PAGE   \* MERGEFORMAT 6


 

А также другие работы, которые могут Вас заинтересовать

81730. Образ скучающего героя в произведениях отечественной классики 19 века 32.94 KB
  Лермонтов Герой нашего времени В романе Л. но и многих молодых людей того времени: жизнь была только цепь грустных и неудачных противоречий сердцу и рассудку Герой романа не всегда был циником скептиком духовно черствым человеком. Причину превращения Печорина в нравственного калеку автор видит в социальных условиях в которых воспитывался герой. И вот на страницах своего дневника герой приходит к страшному выводу: во мне душа испорчена светом Судьбу талантливого человека не нашедшего себе достойного применения в обществе его...
81731. Идейное содержание поэмы Н. А. Некрасова «Кому на Руси жить хорошо». Язык и стиль поэмы 33.13 KB
  Некрасова Кому на Руси жить хорошо. Достойным финалом эпического творчества Н явилась эпопея Кому на Руси жить хорошо; 1865 1877 Композиция этого произведения строится по законам классического эпоса оно состоит из отдельных относительно автономных частей и глав Пролог Часть первая. Внешне эти части связаны темой дороги: семь мужиковправдоискателей странствуют по просторам Руси пытаясь разрешить не дающий им покоя вопрос Кому на Руси жить хорошо В Прологе намечена и первоначальная схема путешествия встречи с попом помещиком.
81732. Нравственная проблематика прозы А. Солженицына (по рассказам «Один день Ивана Денисовича» или «Матренин двор») 34.36 KB
  Шухов не желая потерять человеческое достоинство вовсе не склонен принимать на себя все удары лагерной жизни иначе просто не выжить. помогает ему выжить и сохранить себя человеком не ставя перед собой вечных вопросов не стремясь обобщить опыт своей военной и лагерной жизни куда он попал после плена. островок естественной русской жизни а народный характер сумевший в этой смуте себя сохранить. В чем суть праведности Матрены В жизни не по лжи.
81733. Предыстория героя как способ его характеристики в произведениях отечественной классики 19 века 31.99 KB
  Не так легко понять этот характер трудно схватить даже внешний облик: не красавец но и не дурной наружности; не слишком толст но и не слишком тонок; нельзя сказать чтобы стар однако же и не так чтобы слишком молод; человек средних лет. Характер его показан в динамике история воспитания помогает Гоголю выявить многообразные условия общественной среды семьи под влиянием которых формируется характер человека. исследует характер подлеца его личные качества обстоятельства воспитания и среду.
81734. Герои и проблематика сатиры М.Е.Салтыкова - Щедрина 38.82 KB
  Первым отдельным изданием сказочный цикл вышел в 1886 году 23 сказки М. и те сказки которые не могли появиться в легальной русской печати по цензурным причинам. Сказки стали своего рода малым миром сжатыи изложением всего что создано писателем его наблюдения над идейнополитической жизнью страны психологией социальных групп сатирической энциклопедией творчества Салтыкова. Сказки опираются на традиции фольклора отсюда сказочные сюжеты образы события описания обстановки социальнополитическая направленность бытовых...
81735. Психологизм изображения внутреннего мира личности в лирике А. Ахматовой (на примере 3 – 4 стихотворений) 37.04 KB
  Ахматовой на примере 3 4 стихотворений Я научила женщин говорить так пишет А. Уже в ранних сборниках сформировались основные принципы лирики Ахматовой: сдержанность недосказанность внутреннее эмоциональное напряжение и скрытая страстность сжатость и сила афористичность и краткость психологическая достоверность в передаче чувств и взаимоотношений. Акмеистическое внимание к деталям внешнего мира к предметам обихода у Ахматовой связано с отражением внутреннего мира. С годами эти тенденции в стихах Ахматовой только усиливаются в...
81736. Мотив поиска истины в произведениях отечественной литературы 33.66 KB
  является проблема человеческого счастья проблема поисков смысла жизни. В жизни обоих можно выделить несколько этапов на которых меняется их мировоззрение в душе происходит определенный перелом. Он понял что в жизни есть нечто более важное чем слава. Медленно возвращается он к жизни к людям.
81737. Правда Раскольникова и правда Сони в романе Ф. М. Достоевского «Преступление и наказание». Роль евангельских мотивов и образов в романе 33.02 KB
  Все идущие оттуда идеи будь то буржуазный утилитаризм Лужина коммунистическое общежитие Лебезятникова наполеонизм Раскольникова носят разрушительный нигилистический характер. диспуты Раскольникова с Разумихиным и Порфирием сколько опровергает его постулаты на практике. Кроткая и жертвенная Соня живущая по евангельским заповедям подвигает Раскольникова на путь покаяния отказа от теории воссоединения с людьми и жизнью.
81738. Особенности творчества одного из современных отечественных поэтов второй половины хх века 41.92 KB
  Поэт ведет разговор с читателем и слушателем как бы один на один с глазу на глаз с абсолютной индивидуальной доверительностью. Окуджава снискал себе известность как поэт города. Изменения которые происходили в стране и порой далеко не в лучшую сторону не могли не сказаться на характере творчества поэта.