Методы разработки алгоритмов конспект
Обновлено: 05.07.2024
Аннотация: Рассматриваются основные понятия о методах проектирования (нисходящем, восходящем, модульном, структурном) и разработки алгоритмов (программ), тестирование и верификация алгоритма, трассировка алгоритма.
Нисходящим проектированием алгоритмов, проектированием алгоритмов "сверху вниз" или методом последовательной (пошаговой) нисходящей разработки алгоритмов называется такой метод составления алгоритмов, когда исходная задача ( алгоритм ) разбивается на ряд вспомогательных подзадач (подалгоритмов), формулируемых и решаемых в терминах более простых и элементарных операций (процедур). Последние, в свою очередь , вновь разбиваются на более простые и элементарные, и так до тех пор, пока не дойдём до команд исполнителя. В терминах этих команд можно представить и выполнить полученные на последнем шаге разбиений подалгоритмы (команд системы команд исполнителя).
Восходящий метод, наоборот, опираясь на некоторый, заранее определяемый корректный набор подалгоритмов, строит функционально завершенные подзадачи более общего назначения, от них переходит к более общим, и так далее, до тех пор, пока не дойдем до уровня, на котором можно записать решение поставленной задачи. Этот метод известен как метод проектирования "снизу вверх".
Структурные принципы алгоритмизации ( структурные методы алгоритмизации) – это принципы формирования алгоритмов из базовых структурных алгоритмических единиц (следование, ветвление , повторение), используя их последовательное соединение или вложение друг в друга с соблюдением определённых правил, гарантирующих читабельность и исполняемость алгоритма сверху вниз и последовательно.
Структурированный алгоритм – это алгоритм , представленный как следования и вложения базовых алгоритмических структур . У структурированного алгоритма статическое состояние (до актуализации алгоритма) и динамическое состояние (после актуализации) имеют одинаковую логическую структуру, которая прослеживается сверху вниз ("как читается, так и исполняется"). При структурированной разработке алгоритмов правильность алгоритма можно проследить на каждом этапе его построения и выполнения.
Теорема (о структурировании). Любой алгоритм может быть эквивалентно представлен структурированным алгоритмом, состоящим из базовых алгоритмических структур .
Одним из широко используемых методов проектирования и разработки алгоритмов (программ) является модульный метод (модульная технология).
Модуль – это некоторый алгоритм или некоторый его блок, имеющий конкретное наименование, по которому его можно выделить и актуализировать. Иногда модуль называется вспомогательным алгоритмом, хотя все алгоритмы носят вспомогательный характер. Это название имеет смысл, когда рассматривается динамическое состояние алгоритма; в этом случае можно назвать вспомогательным любой алгоритм , используемый данным в качестве блока (составной части) тела этого динамического алгоритма. Используют и другое название модуля – подалгоритм. В программировании используются синонимы – процедура, подпрограмма .
Свойства модулей:
- функциональная целостность и завершенность (каждый модуль реализует одну функцию, но реализует хорошо и полностью);
- автономность и независимость от других модулей (независимость работы модуля-преемника от работы модуля-предшественника; при этом их связь осуществляется только на уровне передачи/приема параметров и управления);
- эволюционируемость (развиваемость);
- открытость для пользователей и разработчиков (для модернизации и использования);
- корректность и надежность;
- ссылка на тело модуля происходит только по имени модуля, то есть вызов и актуализация модуля возможны только через его заголовок.
Свойства (преимущества) модульного проектирования алгоритмов:
- возможность разработки алгоритма большого объема (алгоритмического комплекса) различными исполнителями;
- возможность создания и ведения библиотеки наиболее часто используемых алгоритмов (подалгоритмов);
- облегчение тестирования алгоритмов и обоснования их правильности ;
- упрощение проектирования и модификации алгоритмов ;
- уменьшение сложности разработки ( проектирования ) алгоритмов (или комплексов алгоритмов);
- наблюдаемость вычислительного процесса при реализации алгоритмов.
Тестирование алгоритма – это проверка правильности или неправильности работы алгоритма на специально заданных тестах или тестовых примерах – задачах с известными входными данными и результатами (иногда достаточны их приближения). Тестовый набор должен быть минимальным и полным, то есть обеспечивающим проверку каждого отдельного типа наборов входных данных, особенно исключительных случаев.
Пример. Для задачи решения квадратного уравнения ax 2 + bx + c = 0 такими исключительными случаями, например, будут: 1) a = b = c = 0; 2) a = 0, b, c – отличны от нуля; 3) D = b 2 – 4ac и др.
Тестирование алгоритма не может дать полной (100%-ой) гарантии правильности алгоритма для всех возможных наборов входных данных, особенно для достаточно сложных алгоритмов.
Полную гарантию правильности алгоритма может дать описание работы и результатов алгоритма с помощью системы аксиом и правил вывода или верификация алгоритма.
Составим теперь алгоритм вычисления числа x = 2 n с использованием операции умножения только один раз.
Прологарифмируем последнее равенство . Получим ln(x) = ln(2 n ) = n ln(2) .
Используя равенство exp(ln(x)) = x , получим, что exp(ln(x)) = x = exp(n ln(2)) .
Остается теперь записать простейший алгоритм вычисления числа x .
Для несложных алгоритмов грамотный подбор тестов и полное тестирование может дать полную картину работоспособности (неработоспособности).
- Для учеников 1-11 классов и дошкольников
- Бесплатные сертификаты учителям и участникам
2.2 Методы разработки и способы представления алгоритмов
1. Основные принципы методов ветвей и границ, понятия сложности и сводимости задач.
Метод ветвей и границ в случае точного вычисления оценок относится к точным методам решения задач выбора и потому в неблагоприятных ситуациях может приводить к экспоненциальной временной сложности. Однако метод часто используют как приближенный, поскольку можно применить приближенные алгоритмы вычисления оценок.
Перечислим основные этапы решения задачи методом МВГ.
1) Трансформация задачи (ТЗ). Исходную задачу заменяют другой задачей так, что множество решений исходной задачи содержится в множестве решений трансформированной задачи. Найти оптимальное решение трансформированной задачи значительно проще, чем решение исходной задачи.
2) Построение дерева решений. Множество решений ТЗ разбивают на подзадачи. Затем каждую подзадачу в свою очередь разбивают на подзадачи. В результате получается дерево решений. Процесс разбиения прекращается, если подзадача содержит не более одного решения исходной задачи, такая задача называется концевой. Если в результате работы МВГ будет построено полное дерево решений, то МВГ будет эквивалентен полному перебору, чем лучше работает МВГ, тем он дальше от полного перебора.
3) Получение нижних оценок каждая подзадача трансформированной задачи содержит какое-то число решений исходной задачи (плата за упрощение). Отсюда оптимальное решение подзадачи меньше или равно лучшему из решений исходной задачи, содержащихся в этой подзадаче. Поэтому оптимальное решение трансформированной подзадачи называют оценкой снизу для решений исходной задачи, содержащихся в этой подзадаче.
Для каждой вновь полученной подзадачи оценка снизу будет не меньше, чем оценка родительской подзадачи, так как в нее входит только часть решений.
4) Получение верхней оценки. Любое решение исходной задачи называют верхней оценкой. Верхняя оценка больше (хуже) или равна оптимальному решению.
5) Отсечения. Если для подзадачи нижняя оценка получилась больше или равна верхней оценке, то эта подзадача заведомо не содержит решения лучше одного из уже найденных решений. Поэтому дальнейшее ее исследование не имеет смысла. Идущий от нее фрагмент дерева отсекается. Чем больше ветвей дерева отсекается, тем быстрее работает МВГ. А отсечения зависят как от качества нижних оценок, так и от качества верхней оценки (исходного размещения).
6) Ветвление. Чаще всего используется следующий способ ветвления:
- для подзадач верхнего уровня получают оценки снизу;
- подзадача с лучшей оценкой разбивается на подзадачи следующего уровня, и для них определяются оценки снизу;
- эти подзадачи добавляются к тем подзадачам, от которых еще не производилось ветвление, из них выбирается для разбиения подзадача с лучшей нижней оценкой;
- если таких подзадач несколько, то из них выбирается самого низкого уровня, если и их несколько, то выбор производится случайно.
Динамическое программирование определяет оптимальное решение n-мерной задачи путем ее декомпозиции на n этапов, каждый из которых представляет собой подзадачу относительно одной переменной.
Этот метод имеет под собой достаточно серьезную научную основу, однако его суть вполне можно объяснить на простом примере чисел Фибоначчи.
Вычислить Af чисел в последовательности Фибоначчи: 1,1,2,3,5,8. где первые два члена равны единице, а все остальные представляют собой сумму двух предыдущих, N меньше 100.
function F(X: integer): longint; begin
if (X = 1) or (X = 2) then F := 1
else F := F(X-l) + F(X-2) end;
При этом на шестом-седьмом десятке программе перестанет хватать временных ресурсов самой современной вычислительной машины. Это происходит по следующим причинам.
Для вычисления, например, F (40) вначале вычисляется F (39) и F (38). Причем F (3 8) вычисляется заново, без использования значения, которое было вычислено, когда считалось F (39), т. е. значение функции при одном и том же значении аргумента считается много раз. Если исключить повторный счет, то функция станет заметно эффективней. Для этого приходится завести массив, в котором хранятся значения нашей функции:
var D: array[1..100] of longint;
Функция принимает следующий вид:
function F(X: integer): longint; begin
if (X=l) or (X=2) then D[X] := 1
else D[X] := F(X-l) + F(X-2); F := D[X]; end;
Можно еще более упростить решение, убрав рекурсию вообще. Для этого необходимо сменить нисходящую логику рассуждения (от того, что надо найти, к тривиальному) на восходящую (соответственно наоборот). В этой задаче такой переход очевиден и описывается простым циклом:
D[12] := 1; D[2] := 1; For i := 3 to N do
Очень часто для его написания приходится использовать как промежуточный результат нисходящую форму, а иногда безрекурсивная (итеративная) форма оказывается чрезвычайно сложной и малопонятной.
Таким образом, если алгоритм превышает отведенное ему время на тестах большого объема, то необходимо осуществлять доработку этого алгоритма.
Таким образом, алгоритм - это точное и понятное предписание исполнителю совершить последовательность действий для достижения поставленной цели за конечное число шагов.
Основные свойства алгоритмов:
1. Понятность для исполнителя.
2. Дискpетность (прерывность, раздельность) -- алгоpитм должен пpедставлять пpоцесс pешения задачи как последовательное выполнение пpостых (или pанее опpеделенных) шагов (этапов).
3. Опpеделенность -- каждое пpавило алгоpитма должно быть четким, однозначным и не оставлять места для пpоизвола.
4. Pезультативность -- это свойство состоит в том, что алгоpитм должен пpиводить к pешению задачи за конечное число шагов.
5. Массовость. Алгоpитм pешения задачи pазpабатывается в общем виде.
Разрабатывать алгоритмы может только человек.
Исполнитель алгоритма -- это устройство управления, соединенное с набором инструментов. Устройство управления понимает алгоритмы и организует их выполнение, командуя соответствующими инструментами.
Исполняют алгоритмы люди и всевозможные устройства - роботы, станки, спутники, сложная бытовая техника. В информатике универсальным исполнителем алгоритмов является компьютер.
Формы представления алгоритмов.
- словесная (записи на естественном языке);
- графическая (изображения из графических символов);
- псевдокоды (полуформализованные описания алгоритмов на условном алгоритмическом языке);
- программная (тексты на языках программирования).
1. Словесный способ записи алгоритмов представляет собой описание последовательных этапов обработки данных. Алгоритм задается в произвольном изложении на естественном языке.
Например. Записать алгоритм нахождения наибольшего общего делителя (НОД) двух натуральных чисел. Алгоритм может быть следующим:
1. задать два числа;
2. если числа равны, то взять любое из них в качестве ответа и остановиться, в противном случае продолжить выполнение алгоритма;
3. определить большее из чисел;
4. заменить большее из чисел разностью большего и меньшего из чисел;
5. повторить алгоритм с шага 2.
Описанный алгоритм применим к любым натуральным числам и должен приводить к решению поставленной задачи. Однако, словесный способ не имеет широкого распространения по следующим причинам:
- такие описания строго не формализуемы;
- страдают многословностью записей;
- допускают неоднозначность толкования отдельных предписаний.
2. Графическом представление -- алгоритм изображается в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий. Такое графическое представление называется схемой алгоритма или блок-схемой. В блок-схеме каждому типу действий (вводу исходных данных, вычислению значений выражений, проверке условий, управлению повторением действий, окончанию обработки и т.п.) соответствует геометрическая фигура, представленная в виде блочного символа. Блочные символы соединяются линиями переходов, определяющими очередность выполнения действий.
В таблице приведены наиболее часто употребляемые символы
Обозначение и пример заполнения
Вычислительное действие или последовательность действий
Вычисления по подпрограмм-ме, стандартной подпрог-рамме
Ввод-вывод в общем виде
Начало, конец алгоритма, вход и выход в подпрограмму
Применяется для обозначения действия или последовательности действий, изменяющих значение, форму представления или размещения данных. Для улучшения наглядности схемы несколько отдельных блоков обработки можно объединять в один блок. Представление отдельных операций достаточно свободно.
Блок данные (ввод-вывод). Преобразование данных в форму, пригодную для обработки (ввод) или отображения результатов обработки (вывод). Данный символ не определяет носителя данных (для указания типа носителя данных используются специфические символы).
Терминатора (пуск - останов). Элемент отображает вход из внешней среды или выход из нее (наиболее частое применение ? начало и конец программы). Внутри фигуры записывается соответствующее действие.
3. Программная форма. При записи алгоритма в словесной и в графической форме допускается определенный произвол при изображении команд. Вместе с тем такая запись точна на столько, что позволяет человеку понять суть дела и исполнить алгоритм. Однако на практике в качестве исполнителей алгоритмов используются специальные автоматы - компьютеры. Поэтому алгоритм, предназначенный для исполнения на компьютере, должен быть записан на понятном ему языке. Такой язык принято называть языком программирования, а форму представления алгоритма - программной, т.е. программная форма записи алгоритма - это запись на языке программирования.
1) Словесная форма:
2. определить температуру воздуха
3. если температура ниже 0, то надеть шубу, иначе надеть куртку
2) Программная форма:
writeln(`введите температуру воздуха t=');
if t одеть шубу ') else writeln(` одеть куртку ');
3) Графическая форма записи:
4. Псевдокод представляет собой систему обозначений и правил, предназначенную для единообразной записи алгоритмов. Псевдокод занимает промежуточное место между естественным и формальным языками.
С одной стороны, он близок к обычному естественному языку, поэтому алгоритмы могут на нем записываться и читаться как обычный текст.
С другой стороны, в псевдокоде используются некоторые формальные конструкции и математическая символика, что приближает запись алгоритма к общепринятой математической записи.
В псевдокоде не приняты строгие синтаксические правила для записи команд, присущие формальным языкам, что облегчает запись алгоритма на стадии его проектирования и дает возможность использовать более широкий набор команд, рассчитанный на абстрактного исполнителя.
Однако в псевдокоде обычно имеются некоторые конструкции, присущие формальным языкам, что облегчает переход от записи на псевдокоде к записи алгоритма на формальном языке. В частности, в псевдокоде, так же, как и в формальных языках, есть служебные слова, смысл которых определен раз и навсегда. Они выделяются в печатном тексте жирным шрифтом, а в рукописном тексте подчеркиваются. Единого или формального определения псевдокода не существует, поэтому возможны различные псевдокоды, отличающиеся набором служебных слов и основных (базовых) конструкций.
Сайт учителя информатики. Технологические карты уроков, Подготовка к ОГЭ и ЕГЭ, полезный материал и многое другое.
Информатика. 9 класса. Босова Л.Л. Оглавление
Ключевые слова:
- последовательное построение алгоритма
- вспомогательный алгоритм
- формальные параметры
- фактические параметры
- рекурсивный алгоритм
Последовательное построение алгоритма
Процесс последовательного построения алгоритма выглядит следующим образом.
Если исполнитель не обучен исполнять заданное предписание, то необходимо представить это предписание в виде совокупности более простых предписании (команд). Для этого:
- задачу разбивают на несколько частей, каждая из которых проще всей задачи;
- решение каждой части задачи формулируют в отдельной команде, которая также может выходить за рамки системы команд исполнителя;
- при наличии в алгоритме предписаний, выходящих за пределы возможностей исполнителя, такие предписания вновь представляются в виде совокупности ещё более простых предписаний.
Процесс продолжается до тех пор, пока все предписания не будут понятны исполнителю.
Объединяя полученные предписания в единую совокупность выполняемых в определённой последовательности команд, получаем требуемый алгоритм решения исходной задачи.
Разработка алгоритма методом последовательного уточнения для исполнителя Робот
Вы уже знакомы с исполнителем Робот. Он действует на клетчатом поле, между клетками которого могут быть стены.
Система команд исполнителя Робот:
В одном условии можно использовать несколько команд, применяя логические операций И, ИЛИ, НЕ.
Известно, что Робот находится где-то в горизонтальном коридоре. Ни одна из клеток коридора не закрашена.
Составим алгоритм, под управлением которого Робот закрасит все клетки этого коридора и вернётся в исходное положение.
Представим план действий Робота следующими укрупнёнными шагами (модулями):
Детализируем каждый из пяти модулей.
1. Чтобы закрасить все клетки коридора, находящиеся левее Робота, прикажем Роботу шагнуть влево и выполнить цикл-ПОКА:
Под управлением этого алгоритма Робот закрасит все клетки коридора, находящиеся левее от него, и окажется на клетке рядом с левой границей коридора.
2. Командой вправо вернём Робота в коридор. Наша задача — вернуть Робота в исходную точку. Эта точка имеет единственный отличительный признак — она не закрашена. Поэтому пока занимаемая Роботом клетка оказывается закрашенной, будем перемещать его вправо.
Под управлением этого алгоритма Робот окажется в исходной клетке.
4. Так как, выполнив предыдущий алгоритм, Робот оказался правее коридора, командой влево вернём его в коридор. Возвращение в исходную точку обеспечивается алгоритмом:
5. По команде закрасить Робот закрашивает исходную клетку.
Полностью программа управления Роботом выглядит так:
Вспомогательные алгоритмы
При построении новых алгоритмов нередко возникают ситуации, когда в разных местах алгоритма необходимо выполдение одной и той же последовательности шагов обработки данных. Для такой последовательности шагов создают отдельный алгоритм, называемый вспомогательным. В качестве вспомогательных могут использоваться алгоритмы, ранее разработанные для решения других задач.
Вспомогательный алгоритм — алгоритм, целиком используемый в составе другого алгоритма.
Пример 1. В среде КуМир составим алгоритм для исполнителя Робот, под управлением которого он нарисует узор:
Начальное положение Робота отмечено звёздочкой. В алгоритме использован вспомогательный алгоритм фигура.
Вспомогательный алгоритм делает структуру алгоритма более понятной.
Пример 2.
Вспомним алгоритм вычисления степени с натуральным показателем у = а n . Соответствующая блок-схема:
Степень с целым показателем у = а х , где х — целое число, а ? 0 вычисляется так:
В приведённой записи дважды фигурирует вычисление степени с натуральным показателем. Поэтому в алгоритм вычисления степени с целым показателем можно включить вызов вспомогательного алгоритма вычисления степени с натуральным показателем. Соответствующая блок-схема:
Алгоритм, представленный на блок-схеме, является основным по отношению к вызываемому в нём вспомогательному алгоритму.
Параметрами используемого вспомогательного алгоритма являются величины а, n, у. Это формальные параметры, они используются при описании алгоритма. При конкретном обращении к вспомогательному алгоритму формальные параметры заменяются фактическими параметрами, т. е. именно теми величинами, для которых будет исполнен вспомогательный алгоритм. Типы, количество и порядок следования формальных и фактических параметров должны совпадать.
Команда вызова вспомогательного алгоритма исполняется следующим образом (рис. 2.4):
- 1) формальные входные данные вспомогательного алгоритма заменяются значениями фактических входных данных, указанных в команде вызова вспомогательного алгоритма;
- 2) для заданных входных данных исполняются команды вспомогательного алгоритма;
- 3) полученные результаты присваиваются переменным с именами фактических результатов;
- 4) осуществляется переход к следующей команде основного алгоритма.
Алгоритм, в котором прямо или косвенно содержится ссылка на него же как на вспомогательный алгоритм, называют рекурсивным.
Рассмотрим несколько примеров рекурсивных алгоритмов.
Пример 3. Алгоритм вычисления степени с натуральным показателем n для любого вещественного числа а можно представить в виде рекурсивного:
n-я степень числа а есть не что иное, как произведение а n-1 • а; в свою очередь, а n-1 = а n-2 • а и т. д.
Пример 5. Рассмотрим алгоритм построения геометрической фигуры, которая называется снежинкой Коха. Шаг процедуры построения состоит в замене средней трети каждого из имеющихся отрезков двумя новыми такой же длины, как показано на рисунке:
С каждым шагом фигура становится всё причудливее. Граница снежинки Коха — положение кривой после выполнения бесконечного числа шагов.
Попробуйте подсчитать, сколько рёбер в границе снежинки Коха после четвёртого шага; после пятого шага.
САМОЕ ГЛАВНОЕ
Один из основных методов конструирования алгоритмов — метод последовательного построения алгоритма. Его суть состоит в том, что: исходная задача разбивается на несколько частей, каждая из которых проще всей задачи, и решение каждой части формулируется в отдельной команде; если получаются команды, выходящие за пределы возможностей исполнителя, то они представляются в виде совокупности ещё более простых предписаний. Процесс продолжается до тех пор, пока все предписания не будут понятны исполнителю.Вспомогательный алгоритм — алгоритм, целиком используемый в составе другого алгоритма.Алгоритм, в котором прямо или косвенно содержится ссылка на него же как на вспомогательный алгоритм, называют рекурсивным.
1. Ознакомьтесь с материалами презентации к параграфу, содержащейся в электронном приложении к учебнику. Дополняет ли презентация информацию, содержащуюся в тексте параграфа?
Разработка алгоритмов и программ. Операциональный и структурный подход. Новые методологии разработки программ. Жизненный цикл программного обеспечения. Декларативный подход в разработке компьютерных программ. Процедурно-ориентированное программирование.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | доклад |
| Язык | русский |
| Дата добавления | 19.02.2014 |
| Размер файла | 19,0 K |
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Доклад на тему
Выполнил студент 1курса
Введение
Алгоритмизация наряду с моделированием выступает в качестве общего метода информатики. Алгоритмы являются объектом систематического исследования граничащего с математикой и информатикой, это исследование является научной дисциплиной близкой к математической логике и называется теорией алгоритмов.
Принципы и методы разработки алгоритмов и программ
Если программа составлена из команд, непосредственно исполняющихся компьютером; простейших арифметических операции операций сравнения чисел; операторов безусловного и условных переходов; операторов вызова подпрограмм, то такой подход в программировании, направленный на исполнение конкретных операций называют операциональным.
Операция присваивания состоит в том, что некоторое значение фигурирующей в программе величины помещается в ячейку памяти компьютера. После этого указанное значение сохраняется до тех пор, пока не будет заменено другим в результате другого присваивания. Ячейка памяти, где размещается значение, в программе обозначается идентификатором соответствующей переменной.
Операции сравнения числовых значений сводится к определению знака разности этих значений. Этот знак отображается с помощью специальной ячейки памяти вычислительного устройства компьютера и может использоваться при выполнении условных переходов между командами алгоритма.
Безусловным называется переход, для которого изменение порядка выполнения команд определено раз и навсегда и не зависит ни от каких условий. Условным называется переход, для которого порядок выполнения команд определяется по некоторому условию, чаще всего условию сравнения числовых величин.
Операция вызова подпрограмм - это такой переход в последовательности команд алгоритма, при котором на определенном этапе алгоритма происходит вначале переход на другую программу, а затем после ее завершения возврат в точку вызова подпрограммы и продолжения выполнения команд, начиная со следующей за вызовом подпрограммы.
Операционный подход в программировании имеет недостатки:
· запутанная структура программы;
· непонятности, сложность в модификации, трудоемкость и высокая стоимость.
В основе технологических принципов структурного программирования лежит утверждение о том, что логическая структура программы может быть выражена комбинацией трех базовых структур: следования, ветвления и цикла.
Следование - самая важная структура, означающая, что действия могут быть выполнены друг за другом.
Цикл предусматривает повторное выполнение некоторого набора команд программы.
Эти структуры можно комбинировать одну с другой - как путем организации их следований, так и путем суперпозиции (вложений одной структуры в другую). Используя описанные структуры, можно полностью исключить использование каких-либо еще операторов условного и безусловного перехода, что является важным признаком структурного программирования.
Умение образовывать из базовых структур их суперпозиции в соответствии с условиями конкретной задачи - одно из важнейших в программировании.
Одним важнейшим компонентом структурного подхода к разработке алгоритмов является модульность. Модуль - это последовательность логически связанных операций, оформленных как отдельная часть программы. Использование модулей имеет следующие преимущества:
1. возможность создания программы несколькими программистами;
2. простота проектирования и последующей модификаций программы;
3. управляющие программы;
4. возможность использования готовых библиотек наиболее употребительных модулей.
Самым важным достижением структурного подхода к разработке программ является нисходящее проектирование, основанное на идее уровней абстракций, которые становятся уровнями модулей в разрабатываемой программе.
Новые методологии разработки программ
Структурный подход сыграл огромную роль в программировании и вычислительной технике. С его использованием создан большой запас программного обеспечения, решено множество практически значимых задач. Однако развитие программирования на этом не остановилось. Дополняющим структурное программирование, создающим основу для разработки современных аудиовизуальных программных комплексов стало объектное (иногда говорят объектно-ориентированное) программирование, а противостоящим ему при решении определенных классов задач является декларативное программирование, выраженное двумя разными подходами -- функциональным и логическим.
Само структурное программирование, наиболее отчетливо выраженное в языке Паскаль (Pascal), возникло в ходе развития процедурно-ориентированного подхода, заложенного в исторически первом из языков программирования -- Фортране (Fortran). Во всех языках этого направления разработчик алгоритма (он же, как правило, и программист) описывает, какими действиями следует реализовать процесс. В основе языков этой группы лежат понятия команд (операторов) и данных. Отдельные группы операторов могут объединяться во вспомогательные алгоритмы (процедуры, подпрограммы).
Декларативный подход в разработке компьютерных программ появился в начале 1970-х гг. Он не получил столь широкого применения как процедурный, поскольку был направлен на относительно узкий круг задач искусственного интеллекта. При его применении программист описывает свойства исходных данных, их взаимосвязи, свойства, которыми должен обладать результат, а не алгоритм получения результата. Разумеется, для получения результата этот алгоритм все равно нужен, но он должен порождаться автоматически той системой, которая поддерживает декларативно-ориентированный язык программирования. При логическом варианте такого подхода -- прежде всего это относится к языку Пролог (Prolog) -- задача описывается совокупностью фактов и правил в некотором формальном логическом языке, при функциональном варианте -- в виде функциональных соотношений между фактами, например язык Лисп (Lisp).
Процедурно-ориентированное программирование развивается и в другом направлении -- так называемого параллельного программирования. В привычных алгоритмах и программах действия совершаются последовательно одно за другим. Однако логика решения множества задач вполне допускает одновременное выполнение нескольких операций, что ведет к многократному увеличению эффективности. Реализация параллельных алгоритмов на ЭВМ стала возможной с появлением многопроцессорных компьютеров, в которых специалисты видят будущее вычислительной техники.
Методы разработки алгоритмов
Существует весьма большое количество методов и приемов разработки алгоритмов, среди них можно выделить небольшой набор основных и часто применяемых.
1. Метод частных целей. Позволяет свести трудную задачу к последовательности более простых.
3. Программирование с отходом назад. Используется совместно с методом перебора, для избегания перебора всех возможных вариантов.
4. Алгоритмы ветвей и границ. Как и большая часть алгоритмов применяется для решения переборных задач. Они исследуют древовидную модель пространства решений и ориентированы на поиск в некотором смысле оптимального решения (из конечного множества возможных решений).
Жизненный цикл программного обеспечения
алгоритм программа компьютерный обеспечение
Жизненный цикл программного обеспечения включает в себя шесть этапов:
· Анализ требований. При разработке программного обеспечения он исключительно важен. Ошибки, допущенные на этом этапе, даже при условии безупречного выполнения последующих этапов могут привести к тому, что разработанный программный продукт не будет соответствовать требованиям практики, сферы его применения. Для создания конкурентоспособных продуктов в ходе выполнения этого этапа должны быть получены четкие ответы на следующие вопросы:
· Что должна делать программа?
· В чем состоят реальные проблемы, разрешению которых она должна способствовать?
· Что представляют собой входные данные?
· Какими должны быть выходные данные?
· Какими ресурсами располагает проектировщик?
Определение спецификаций. В определенной степени этот этап можно рассматривать как формулировку выводов, следующих из результатов предыдущего этапа. Требования к программе должны быть Представлены в виде ряда спецификаций, явно определяющих рабочие характеристики будущей программы. В число таких характеристик могут входить скорость выполнения, объем потребляемой памяти, гибкость применения и др.
На этом этапе создается общая структура программы, которая должна удовлетворять спецификациям; определяются общие принципы управления и взаимодействия между различными компонентами программы.
Кодирование. Заключается в переводе на язык программирования конструкций, записанных на языке проектирования.
Тестирование. На этом этапе производится всесторонняя проверка программ. Тестирование более подробно рассмотрено ниже.
Подобные документы
Разработка алгоритма как конструктивный компонент программирования, не зависящий от особенностей синтаксиса языков программирования и специфики функционирования конкретных ЭВМ. Алгоритм - операциональный подход к программированию. Экономичность алгоритма.
учебное пособие [346,8 K], добавлен 09.02.2009
Понятие и свойства алгоритмов: рекурсивного, сортировки и поиска. Простая программа и структурный подход к разработке алгоритмов. Язык блок-схем и проектирования программ (псевдокод). Рассмотрение принципов объектно-ориентированного программирования.
презентация [53,1 K], добавлен 13.10.2013
Особенности разработки программ для ЭВМ. Этапы планирования программы. Понятие и особенности алгоритмов. Средства, используемые для создания программ. Виды и классификация языков программирования. Структурное и объектно-ориентированное программирование.
реферат [59,7 K], добавлен 19.08.2010
Рассмотрение основ разработки технического задания. Проектирования структуры программ; описание соответственного алгоритма. Собственно программирование. Тестирование и отладка компьютерных программ. Ознакомление с основными правилами защиты проекта.
реферат [157,4 K], добавлен 15.11.2014
Характеристика предприятия ТОО "Com Sales Group". Составление программ на языке программирования. Составление алгоритмов, разработка численных методов решения задач. Методы откладки программ. Анализ технологии машинной обработки экономической информации.
Читайте также: