 |
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
XII. ЭЛЕМЕНТЫ ТЕОРИИ АЛГОРИТМОВ
Выделяют следующие этапы решения задачи на ЭВМ:
1) постановка задачи;
2) математическое описание задачи;
3) разработка алгоритма решения;
4) написание программы на языке программирования;
5) подготовка исходных данных;
6) ввод программы и данных в ЭВМ;
7) отладка и тестирование программы;
8) решение задачи;
9) обработка и интерпретация результатов.
Определение. Алгоритм – это последовательность арифметических и логических действий, приводящая к получению результата и решению задачи (любая конечная система правил преобразования информации).
Свойства алгоритма:
1) детерминированность (применение алгоритма к одним и тем же данным должно приводить к одному результату);
2) массовость (алгоритм дает результат при различных исходных данных);
3) результативность (алгоритм дает результат через конечное число шагов);
4) дискретность (алгоритм должен представлять процесс решения задачи как последовательное выполнение простых шагов; каждое действие, предусмотренное алгоритмом, исполняется только после того, как закончилось исполнение предыдущего).5) определенность (каждое правило алгоритма должно быть четким, однозначным и не оставлять места для произвола). Благодаря этому свойству выполнение алгоритма носит механический характер и не требует никаких дополнительных указаний или сведений о решаемой задаче.Структура алгоритмов может быть:
1) линейной: вычислительные действия выполняются последовательно друг за другом, алгоритм не содержит условий;
2) разветвляющейся: в зависимости от выполнения некоторого условия вычислительный процесс осуществляется по одной или по другой ветви;
3) циклической: содержать многократно повторяющиеся участки вычислительного процесса.
Определение. Функциональный блок - это часть алгоритма, имеющая один вход (выполнение начинается с одного оператора) и один выход (после завершения начинает выполняться один и тот же оператор).
Определение. Структурным называется алгоритм, являющийся комбинацией линейного, разветвляющегося и циклического алгоритмов.
Сложность алгоритма характеризуется числом элементарных шагов выполнения программы, что пропорционально времени выполнения алгоритма, а также требуемым объемом оперативной памяти. Алгоритмически неразрешимой называется задача, для решения которой невозможно построить алгоритм.
На практике наиболее распространены следующие формы представления алгоритмов:· словесная (записи на естественном языке);· графическая (изображения из графических символов);· программная (тексты на языках программирования). Словесное описание алгоритма не является распространенным из-за его многословности и отсутствия наглядности. Структурная (блок-, граф-) схема алгоритма – это графическое изображение алгоритма в виде схемы связанных между собой с помощью стрелок (линий перехода) блоков – графических символов, каждый из которых соответствует одному шагу алгоритма. Внутри блока дается описание соответствующего действия. Графическое изображение алгоритма широко используется перед программированием задачи вследствие его наглядности, т.к. зрительное восприятие обычно облегчает процесс написания программы, ее корректировки при возможных ошибках, осмысливание процесса обработки информации. При решении сколько-нибудь серьезной задачи блок-схема «расползется» до такой степени, что ее невозможно будет охватить одним взглядом. Блок-схемы алгоритмов удобно использовать для объяснения работы уже готового алгоритма, при этом в качестве блоков берутся действительно блоки алгоритма, работа которых не требует пояснений. Блок-схема алгоритма должна служить для упрощения изображения алгоритма, а не для усложнения.При записи алгоритма в словесной форме, в виде блок-схемы допускается определенный произвол при изображении команд. Вместе с тем такая запись точна настолько, что позволяет человеку понять суть дела и исполнить алгоритм. Однако на практике в качестве исполнителей алгоритмов используются специальные автоматы — компьютеры. Поэтому алгоритм, предназначенный для исполнения на компьютере, должен быть записан на «понятном» ему языке. И здесь на первый план выдвигается необходимость точной записи команд, не оставляющей места для произвольного толкования их исполнителем. Следовательно, язык для записи алгоритмов должен быть формализован.Такой язык принято называть языком программирования, а запись алгоритма на этом языке — программой для компьютера. К основным методам структурного программирования относится, прежде всего, отказ от бессистемного употребления оператора непосредственного перехода и преимущественное использование других структурированных операторов, методы нисходящего проектирования разработки программы, идеи пошаговой детализации и некоторые другие соглашения, касающиеся дисциплины программирования. Всякая программа, в соответствии с структурным подходом к программированию, может быть построена только с использованием трех основных типов блоков:1. Функциональный блок, который на блок-схеме изображается в виде прямоугольников с одним входом и одним выходом: Функциональному блоку в языках программирования соответствуют операторы ввода и вывода или любой оператор присваивания. В виде функционального блока может быть изображена любая последовательность операторов, выполняющихся один за другим, имеющая один вход и один выход.2. Условная конструкция. Этот блок включает проверку некоторого логического условия (P), в зависимости от которого выполняется либо один (S1), либо другой (S2) операторы.3. Блок обобщенного цикла. Этот блок обеспечивает многократное повторение выполнения оператора S пока выполнено логическое условие P.XIII. ВВЕДЕНИЕ В ЯЗЫК
Поиск по сайту: