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

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

Рубрика Программирование, компьютеры и кибернетика
Вид реферат
Язык русский
Дата добавления 12.07.2010
Размер файла 19,6 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

Кафедра «Автоматизированные системы управления»

Реферат на тему:

«Математическая логика и теория алгоритмов»

СОДЕРЖАНИЕ

1 Сравнительные оценки алгоритмов

2 Система обозначений в анализе алгоритмов

3 Классификация алгоритмов по виду функции трудоёмкости

4 Асимптотический анализ функций

1 СРАВНИТЕЛЬНЫЕ ОЦЕНКИ АЛГОРИТМОВ

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

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

В целях дальнейшего анализа примем следующие допущения:

· каждая команда выполняется не более чем за фиксированное время;

· исходные данные алгоритма представляются машинными словами по битов каждое.

Конкретная проблема задается N словами памяти, таким образом, на входе алгоритма:

N = N* бит информации.

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

Программа, реализующая алгоритм для решения общей проблемы состоит из М машинных инструкций по м битов — М = М* м бит информации.

Кроме того, алгоритм может требовать следующих дополнительных ресурсов абстрактной машины:

· Sd — память для хранения промежуточных результатов;

· Sr — память для организации вычислительного процесса (память, необходимая для реализации рекурсивных вызовов и возвратов).

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

Определение Трудоёмкость алгоритма. Под трудоёмкостью алгоритма для данного конкретного входа — Fa(N), будем понимать количество «элементарных» операций совершаемых алгоритмом для решения конкретной проблемы в данной формальной системе.

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

c1 * Fa(N) + c2 * + c3 * Sd + c4 * Sr,

где ci — веса ресурсов.

2 СИСТЕМА ОБОЗНАЧЕНИЙ В АНАЛИЗЕ АЛГОРИТМОВ

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

Пусть DА — множество конкретных проблем данной задачи, заданное в формальной системе. Пусть D DА — задание конкретной проблемы и |D| = N. В общем случае существует собственное подмножество множества DА, включающее все конкретные проблемы, имеющие мощность N:

обозначим это подмножество через DN:

обозначим мощность множества DN через

MDN > MDN = |DN |.

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

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

Fa (N) = max a (D)> — худший случай на DN

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

Fa (N) = min a (D)> — лучший случай на DN

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

Fa(N) = (1 / MDN)* a (D)> — средний случай на DN

3 КЛАССИФИКАЦИЯ АЛГОРИТМОВ ПО ВИДУ ФУНКЦИИ ТРУДОЁМКОСТИ

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

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

Fa (D) = Fa (|D|) = Fa (N)

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

2. Параметрически-зависимые по трудоемкости алгоритмы. Это алгоритмы, трудоемкость которых определяется не размерностью входа (как правило, для этой группы размерность входа обычно фиксирована), а конкретными значениями обрабатываемых слов памяти:

Fa (D) = Fa (d1,…,dn) = Fa (P1,…,Pm), m n

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

а) Вычисление x k последовательным умножением Fa(x, k) = Fa (k).

б) Вычисление e x = (x n /n!), с точностью до Fa = Fa (x, )

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

Fa (D) = Fa (||D||, P1,…,Pm) = Fa (N, P1,…,Pm)

В качестве примера можно привести алгоритмы численных методов, в которых параметрически-зависимый внешний цикл по точности включает в себя количественно-зависимый фрагмент по размерности.

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

Пусть множество D состоит из элементов (d1,…,dn), и ||D||=N, определим Dp = <(d1,…,dn)>-множество всех упорядоченных N-ок из d1,…,dn, отметим, что |Dp|=n!. Если

Fa (iDp) Fa (jDp),

где iDp, jDp Dp, то алгоритм будем называть порядково-зависимым по трудоемкости.

Примерами таких алгоритмов могут служить ряд алгоритмов сортировки, алгоритмы поиска минимума и максимума в массиве. Рассмотрим более подробно алгоритм поиска максимума в массиве S, содержащим n элементов:

MaxS (S,n; Max)

Max S1

For i 2 to n

if Max < Si

then Max Si (количество выполненных операций присваивания зависит от порядка следования элементов массива)

4 АСИМПТОТИЧЕСКИЙ АНАЛИЗ ФУНКЦИЙ

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

Оценка (тетта). Пусть f(n) и g(n) — положительные функции положительного аргумента, n ? 1 (количество объектов на входе и количество операций — положительные числа), тогда:

f(n) = (g(n)),

если существуют положительные с1, с2, n0, такие, что:

с1 * g(n) f(n) c2 * g(n), при n > n0

Обычно говорят, что при этом функция g(n) является асимптотически точной оценкой функции f(n), т.к. по определению функция f(n) не отличается от функции g(n) с точностью до постоянного множителя. Отметим, что из f(n) = (g(n)) следует, что g(n) = (f(n)).

1) f(n)=4n 2 +nlnN+174 — f(n)= (n 2 );

2) f(n)= (1) — запись означает, что f(n) или равна константе, не равной нулю, или f(n) ограничена константой на : f(n) = 7+1/n = (1).

Оценка О (О большое). В отличие от оценки , оценка О требует только, что бы функция f(n) не превышала g(n) начиная с n > n, с точностью до постоянного множителя:

f(n) c * g(n), n n0

Вообще, запись O(g(n)) обозначает класс функций, таких, что все они растут не быстрее, чем функция g(n) с точностью до постоянного множителя, поэтому иногда говорят, что g(n) мажорирует функцию f(n).

Например, для всех функций:

f(n)=1/n, f(n)= 12, f(n)=3*n+17, f(n)=n*Ln(n), f(n)=6*n 2 +24*n+77

будет справедлива оценка О(n 2 )

Указывая оценку О есть смысл указывать наиболее «близкую» мажорирующую функцию, поскольку например для f(n)= n 2 справедлива оценка О(2 n ), однако она не имеет практического смысла.

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

c * g(n) f(n)

Например, запись (n*Ln(n)) обозначает класс функций, которые растут не медленнее, чем g(n) = n*Ln(n), в этот класс попадают все полиномы со степенью большей единицы, равно как и все степенные функции с основанием большим единицы.

Асимптотическое обозначение О восходит к учебнику Бахмана по теории простых чисел (Bachman, 1892), обозначения , введены Д. Кнутом — (Donald Knuth) [6].

Отметим, что не всегда для пары функций справедливо одно из асимптотических соотношений, например для f(n)=n 1+sin(n) и g(n)=n не выполняется ни одно из асимптотических соотношений.

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

Подобные документы

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

курсовая работа [27,9 K], добавлен 23.07.2011

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

контрольная работа [831,0 K], добавлен 24.11.2013

Положения алгоритмов сжатия изображений. Классы приложений и изображений, критерии сравнения алгоритмов. Проблемы алгоритмов архивации с потерями. Конвейер операций, используемый в алгоритме JPEG. Характеристика фрактального и рекурсивного алгоритмов.

реферат [242,9 K], добавлен 24.04.2015

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

презентация [262,8 K], добавлен 19.01.2015

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

реферат [35,2 K], добавлен 24.07.2010

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

курсовая работа [1,3 M], добавлен 11.03.2014

Понятие и классификация алгоритмов маршрутизации. Основное определение теории графов. Анализ и разработка алгоритмов Дейкстры и Флойда на языке программирования C# для определения наилучшего пути пакетов, передаваемых через сеть. Их сравнительный анализ.

Источник

Реферат на тему: Алгоритмы

В статье «Как научиться правильно писать реферат», я написала о правилах и советах написания лучших рефератов, прочитайте пожалуйста.

Собрала для вас похожие темы рефератов, посмотрите, почитайте:

Введение

Алгоритм — точная инструкция исполнителю выполнить определенную последовательность действий для достижения цели в ограниченном количестве шагов.

Одним из фундаментальных понятий в информатике является понятие алгоритма. Происхождение самого термина «алгоритм» связано с математикой. Это слово происходит от алгоритма — латинского написания Мухаммада ал-Хорезми (787-850), выдающегося математика средневекового Востока. В своей книге «Об индийских счетах» он сформулировал правила ввода натуральных чисел с арабскими цифрами и правила действий с ними с помощью столбца. Позже алгоритмом стало точное правило, определяющее последовательность действий, обеспечивающих требуемый результат из исходных данных.

Алгоритм может быть сконструирован таким образом, что он может быть выполнен человеком или автоматическим устройством. Создание алгоритма, даже самого простого, — это творческий процесс. Она доступна только живым существам, и долгое время считалось, что она только человеческая. Латинский перевод его математического трактата был подготовлен в 19 в. Европейцы узнали о десятичной системе счисления и правилах арифметики для многозначных чисел. Именно эти правила тогда назывались алгоритмами.

Приведенное выше определение алгоритма нельзя считать строгим — не совсем понятно, что такое «точное правило» или «последовательность действий для достижения желаемого результата».

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

Такие качества:

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

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

Данная интерпретация термина «алгоритм» является неполной и неточной.

Во-первых, неправильно связывать алгоритм с решением проблемы. Алгоритм может вообще не решить проблему.

Во-вторых, термин «масса» относится не к алгоритмам как таковым, а к математическим методам в целом. Решение задач, поставленных практикой математических методов, основано на абстракции — мы присваиваем набор существенных признаков, характерных для определенного набора явлений, и строим на основе этих признаков математическую модель, упуская из виду незначительные признаки каждого конкретного явления. В этом смысле каждая математическая модель обладает свойством массы. Если мы решим задачу в рамках построенной модели, а решение представляем как алгоритм, то решение будет «массовым» благодаря природе математических методов, а не «массовым» алгоритма.

Типы алгоритмов

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

  1. Механические или другие детерминированные, жесткие алгоритмы (например, алгоритм машины, двигателя и т.д.);
  2. Гибкие алгоритмы, такие как стохастические, т.е. вероятностные и эвристические. Механический алгоритм определяет определенные действия, отмечает их в единой и надежной последовательности и тем самым обеспечивает четкий требуемый или желаемый результат, если выполнены условия процесса, задачи, для которых был разработан алгоритм.
  3. Вероятностный (стохастический) алгоритм дает программе возможность решать проблему различными способами или способами, приводящими к вероятному результату.
  4. Эвристический алгоритм (от греческого слова «эврика») — это алгоритм, в котором достижение конечного результата программы действий четко не предопределено, как будто не отмечена вся последовательность действий, не распознаны все действия исполнителя. Примеры эвристических алгоритмов включают инструкции и правила. В этих алгоритмах используются универсальные логические процедуры и методы принятия решений, основанные на аналогиях, ассоциациях и предыдущем опыте решения аналогичных задач.

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

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

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

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

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

На всех этапах подготовки к алгоритмизации задачи часто используется структурное представление алгоритма.

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

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

Можно даже сделать такое утверждение: «Внешне алгоритм представляет собой схему — набор прямоугольников и других символов, в пределах которых она записывается, вычисляется, вводится в автомобиль и выводится на экран при помощи печати и других средств отображения информации». Здесь форма представления алгоритма смешивается с самим алгоритмом.

Требования к алгоритму

Первое правило заключается в том, что при создании алгоритма необходимо сначала указать набор объектов, с которыми алгоритм будет работать. Формализованное (закодированное) представление этих объектов называется данными. Алгоритм начинает работать с определенным набором данных, называемым Input, и в результате его работы выдает данные, называемые Output. Таким образом, алгоритм преобразует входные данные в выходные. Это правило позволяет сразу отделить алгоритмы от «методов» и «процедур». Пока у нас нет формализованных входных данных, мы не можем создать алгоритм.

Второе правило заключается в том, что алгоритму необходима память для работы. Память содержит входные данные, с которыми начинает работать алгоритм, промежуточные данные и выходные данные, являющиеся результатом работы алгоритма. Память дискретная, то есть состоит из отдельных ячеек. Именованная ячейка памяти называется переменной. В теории алгоритмов объем памяти не ограничен, то есть предполагается, что мы можем предоставить алгоритму любой объем памяти, необходимый для его работы. Эти два правила не рассматриваются в школе «теории алгоритмов». В то же время практическая работа с алгоритмами (программирование) начинается с реализации этих правил.

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

Третье правило — усмотрение. Алгоритм состоит из отдельных шагов (действий, операций, команд). Множество шагов, из которых алгоритм естественно составлен.

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

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

Заключение

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

Источник

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

Нисходящим проектированием алгоритмов, проектированием алгоритмов «сверху вниз» или методом последовательной (пошаговой) нисходящей разработки алгоритмов называется такой метод составления алгоритмов, когда исходная задача ( алгоритм ) разбивается на ряд вспомогательных подзадач (подалгоритмов), формулируемых и решаемых в терминах более простых и элементарных операций (процедур). Последние, в свою очередь , вновь разбиваются на более простые и элементарные, и так до тех пор, пока не дойдём до команд исполнителя. В терминах этих команд можно представить и выполнить полученные на последнем шаге разбиений подалгоритмы (команд системы команд исполнителя).

Восходящий метод, наоборот, опираясь на некоторый, заранее определяемый корректный набор подалгоритмов, строит функционально завершенные подзадачи более общего назначения, от них переходит к более общим, и так далее, до тех пор, пока не дойдем до уровня, на котором можно записать решение поставленной задачи. Этот метод известен как метод проектирования «снизу вверх».

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

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

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

Одним из широко используемых методов проектирования и разработки алгоритмов (программ) является модульный метод (модульная технология).

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

Свойства модулей:

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

Свойства (преимущества) модульного проектирования алгоритмов:

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

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

Пример. Для задачи решения квадратного уравнения ax 2 + bx + c = 0 такими исключительными случаями, например, будут: 1) a = b = c = 0; 2) a = 0, b, c – отличны от нуля; 3) D = b 2 – 4ac < 0 и др.

Тестирование алгоритма не может дать полной (100%-ой) гарантии правильности алгоритма для всех возможных наборов входных данных, особенно для достаточно сложных алгоритмов.

Полную гарантию правильности алгоритма может дать описание работы и результатов алгоритма с помощью системы аксиом и правил вывода или верификация алгоритма.

Пример. Составим алгоритм нахождения числа всех различных двоичных сообщений (двоичных последовательностей) длины n битов, используя при этом не более одной операции умножения, и докажем правильность этого алгоритма. Вначале найдем число всех таких сообщений. Число двоичных сообщений длины 1 равно 2 = 2 1 (это «0» и «1»), длины 2 равно 4 = 2 2 («00», «01», «10», «11»). Отправляясь от этих частных фактов, методом математической индукции докажем, что число различных сообщений длины n равно 2 n . Этот индуктивный вывод докажет правильность алгоритма.

Пусть это наше утверждение верно для n = k . Тогда для n = k + 1 получаем, что добавление каждого бита (0 или 1) к любому из 2 k сообщений длины k приведет к увеличению числа сообщений в 2 раза, то есть их число будет равно 2 x 2 k = 2 k+1 , что и доказывает наше индуктивное предположение.

Составим теперь алгоритм вычисления числа 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) Улучшение поиска с возвратом для оптимизационных

2) Для каждого узла (частично построенного решения) в

дереве пространства состояний метод вычисляет оценку

величины оптимизируемой функции во всех потомках

этого узла (расширений этого частичного решения)

3) Оценка используется для

· отбрасывания бесперспективных вершин

· определения порядка построения дерева (узел с лучшей оценкой обычно исследуется раньше остальных)

Вопрос 29

Исполнитель алгоритма — это человек или автомат (в частности, им может быть процессор ЭВМ), умеющий выполнять некоторый, вполне определенный набор действий.
Исполнителя характеризуют:
• среда;
• элементарные действия;
• система команд;
• отказы.
Исполнитель ничего не знает о цели алгоритма. Он выполняет все полученные команды, не задавая вопросов «почему» и «зачем».
Про компьютер говорят, что он универсальный исполнитель алгоритмов, созданных для обработки информации. Компьютер может исполнять алгоритм, если он написан на одном из языков программирования. Такой алгоритм называют компьютерной программой. Программу можно ввести в память компьютера и запустить её. Тогда она может быть автоматически исполнена компьютером. В этом случае исполнителем алгоритма является компьютер.

Источник

Читайте также:  Кулонометрический метод анализа задачи
On: