Что такое вычислительный алгоритм
Что такое вычислительные алгоритмы?
вычислительные алгоритмы они представляют собой последовательность шагов, предназначенных для выполнения конкретной задачи. Можно также сказать, что они представляют собой набор четких инструкций, которые запрограммированы в компьютере для решения проблемы..
В компьютерной области или в любой науке алгоритм служит основой для создания методологии с определенными и конечными этапами..
Его использование предназначено, чтобы дать общее решение дилеммы, которая позволяет нам использовать это снова и снова, чтобы получить ожидаемый результат.
Характеристики вычислительных алгоритмов
Предложенный математиком Аланом Тьюрингом, чтобы перенести эту концепцию математики в область компьютерных наук, алгоритм представляет собой процесс, определяемый следующим:
-Ограниченная последовательность шагов, которые четко определены и каждый из которых не зависит от других.
-Агент имеет возможность интерпретировать инструкции по эксплуатации и одновременно сохранять предоставленную информацию..
-При выполнении конкретной методологии результат всегда будет одинаковым на каждом этапе и в соответствии с исходными данными.
-Как и в любом процессе, он заканчивается результатом.
Примером их являются операционные системы, такие как Windows, MacOS и Linux, которые должны продолжать функционировать в качестве платформы для других программ и процессов..
тип
Как в информатике, так и в других дисциплинах можно выделить 3 типа алгоритмов: последовательный, условный и повторяющийся. Кроме того, существуют качественные (используйте слова) и количественные (используйте численные расчеты).
Некоторые известные вычислительные алгоритмы, которые очень полезны на практике, выполняют различные функции.
Таким образом, мы находим алгоритм Евклида, который используется для деления, алгоритм Гаусса для решения линейных уравнений или алгоритм Флойда-Врашалла, чтобы найти кратчайший путь между взвешенными графами.
примеров
Алгоритмы используются в разных ситуациях, стремятся дать решение проблемы и не следуют стандартной процедуре.
Когда механизм обнаружен для быстрого и эффективного решения конкретной задачи, его выполнение не требует понимания того, как работает метод..
Кроме того, компьютеры могут решать различные типы проблем, применяя формулы, которые имеют специальный язык.
В этом случае вычислительные алгоритмы представляют код, написанный по-разному, который может быть понят только для машины..
Важной частью этой процедуры является преобразование идеи в логическую последовательность, которую ПК может интерпретировать.
Таким образом, программисты переходят от простых задач к более сложным. Для этого они часто прибегают к рецептам, созданным другими, чтобы приспособить их к тому, что им нужно решить..
ВЫЧИСЛИТЕЛЬНЫЙ АЛГОРИТМ
точно определенное указание действий над данными, позволяющее с помощью цифровой вычислительной машины дискретного действия преобразовать за конечное количество операций нек-рый массив данных (входные данные) в другой массив данных (выходные данные). В. а. реализуется в виде вычислительного процесса, т. е. в виде дискретно распределенной во времени конечной последовательности состояний реальной ЭВМ, имеющей, в отличие от абстрактной вычислительной машины, ограниченные скорость выполнения операций, разрядность чисел и объем памяти.
Машинная команда есть машинное слово, к-рое содержит информацию об операции, напр, арифметической, и ее оперантах (объектах, над к-рыми производится операция, и результате операции). Арифметич. операция над парой машинных чисел может вывести результат из совокупности Мпо двум причинам: вследствие превышения допустимого числа значащих цифр; вследствие превышения допустимой величины машинного числа. В первом случае применяется операция округления, к-рая возвращает результат действия в множество М, но делает само действие приближенным и приводит к потере точности. Второй случай приводит к аварийной остановке ЭВМ (АВОСТ, или «аварийный останов»).
Композиция арифметич. операции, примененной к паре машинных чисел, и операции округления называется кваз и операцией. Множество Мвместе с определенной над ним совокупностью квазиопераций образует замкнутую систему N, однако, в отличие от поля действительных чисел, Nне образует поля. Система Nзависит от выбора ЭВМ.
Реальный В. а. складывается из двух частей:
а) абстрактного (или собственно) В. а., к-рый применяется к математич. объектам (элементам конечномерных векторных пространств, полей, алгебраич. систем, функциональных пространств и т. д.), не связан с конкретной ЭВМ и может записываться в общепринятых математич. терминах или ча каком-либо алгоритмич. языке;
б) программы, т. е. совокупности машинных команд, описывающих В. а., к-рая организует реализацию вычислительного процесса в конкретной ЭВМ.
Первая часть В. а. является исходной и переходит во вторую часть с помощью различных методов программирования. В. а. содержит ряд управляющих параметров, к-рые остаются неопределенными в первой части и фиксируются в программе, полностью определяя вычислительный процесс, обеспечивая адаптацию его первой части к конкретной ЭВМ.
В. а. осуществляет переработку числовой и символьной информации и, как правило, связан с потерей информации и точности. Потеря точности является следствием ряда погрешностей, появляющихся на различных этапах вычислений: погрешности модели, аппроксимации, входных данных, округления. Погрешность модели является следствием приближенности математич. описания реального процесса. Погрешность входных данных зависит от ошибок наблюдения, измерения и т. п., но также может включать в себя и ошибку округления входной информации. Иногда погрешность модели и погрешность входных данных объединяют одним названием неустранимая погрешность. Погрешность аппроксимации возникает, если рассматривать абстрактный В. а. как нек-рую дискретную модель, к-рая, как правило, аппроксимирует континуальную модель. В нек-рых случаях абстрактный В. а. является самостоятельной дискретной моделью, к-рая не сопоставляется ни с какой другой моделью; в этом случае нет смысла говорить о погрешности аппроксимации. Погрешности округления могут встречаться только в реальном вычислительном процессе и зависят от выбора ЭВМ. При заданных входных данных и абстрактном В. а. промежуточные и выходные данные, получаемые в ЭВМ, зависят от выбора ЭВМ и режима ее работы (вычисления с одинарной и двойной точностью). Абстрактный В. а. допускает эквивалентные преобразования, к-рые при заданных входных данных могут менять промежуточные данные, но оставляют неизменным окончательный результат. В. а., соответствующий двум различным эквивалентным представлениям абстрактного В. а., может при фиксированной ЭВМ и входных данных приводить к различным окончательным результатам.
Помимо свойства точности, В. а. должен обладать свойством устойчивости. Устойчивость В. а. определяется как свойство В. а., позволяющее судить о скорости накопления суммарной вычислительной погрешности. Имеется градация устойчивости (соответственно неустойчивости), основанная на измерении исходной ошибки округления и суммарной вычислительной погрешности в различных нормах. В тех случаях, когда В. а. сводится к последовательности линейных рекуррентных соотношений, устойчивость В. а. определяется в терминах норм конечномерных матриц в конечномерных векторных пространствах. Свойство устойчивости определяется как структурой абстрактного В. а., так и влиянием ошибок округления. Так, устойчивость итерационного процесса x n+1 =A n x n +b n , где матрица А п также вычисляется, будет зависеть от влияния ошибок округления в коэффициентах матрицы на ее норму. Ошибки округления, входя в коэффициенты различных уравнений и операторов, вносят возмущения в математич. модель абстрактного В. а. и в этом смысле могут интерпретироваться так же, как и ошибки модели. Чем лучше свойства устойчивости абстрактного В. а., тем меньше, при заданном абстрактном В. а., результаты вычислений зависят от выбора ЭВМ и эквивалентных представлений абстрактного В. а.
Другим условием, особенно важным в массовых вычислениях, является экономичность В. а., измеряемая затратой машинного времени, необходимой для достижения заданной точности вычисления. Экономичные В. а. получили широкое распространение в задачах математич. физики (см., напр., дробных шагов метод). Важной задачей теории В. а. является оптимизация В. а.
При построении В. а. характерна тенденция к контролю точности. Контроль точности может косвенно осуществляться за счет увеличения устойчивости и порядка аппроксимации В. а., изменения параметров В. а. (внутренняя сходимость), сравнения двух численных решений одной и той же задачи, соответствующих различным В. а., применения тестов и т. д. Прямой контроль точности осуществляется в том случае, когда удается получить двусторонние оценки (или, по крайней мере, односторонние оценки) результата вычислений. Теоретич. оценки такого рода не всегда возможны и эффективны, т. к. не всегда дают достаточно точные границы отклонения численного решения от точного. Получил распространение интервальный анализ, к-рый дает возможность в процессе вычислений строить доверительные границы для вычисляемых величин.
Различия в результатах абстрактного и реального В. а. определяются довольно сложными связями между их параметрами. Так, в абстрактном В. а. для сходящегося итерационного процесса точность е, вообще говоря, тем больше, чем больше число итераций п. В случае реального В. а. эта ситуация может измениться вследствие влияния ошибок округления и, начиная с нек-рого момента, разность между n-й итерацией и точным решением может потерять тенденцию к убыванию.
Вообще говоря, абстрактный В. а. строится независимо от выбора конкретной ЭВМ и только косвенно учитывает ее конфигурацию своими свойствами аппроксимации и устойчивости. Так, для машин с большим быстродействием, но при малой оперативной памяти при решении дифференциальных уравнений с частными производными целесообразно применение экономичных абсолютно устойчивых схем высокой точности. В связи с появлением ЭВМ с параллельно действующими процессорами получили развитие параллельные алгоритмы и параллельное программирование. Сущность параллельного программирования заключается в разбиении перерабатываемых численных массивов на части (подмассивы), независимо перерабатываемые соответствующими процессорами; производится обмен информацией между подмассивами, причем время, затрачиваемое на этот обмен, существенно меньше, чем выигрыш времени, достигаемый в результате распараллеливания счета. Это делает эффективным применение ЭВМ с параллельным действием, позволяя достигать резкого увеличения быстродействия, особенно при решении больших задач.
Многообразие ЭВМ приводит к многообразию программ, реализующих один и тот же абстрактный В. а. Составление программ является трудоемким процессом, и поэтому особое значение приобретает проблема адаптации, т. е. быстрого и по возможности автоматич. преобразования (при заданном абстрактном В. а.) программы с одной ЭВМ на другую (см. Программирование). Н. Н. Яненко.
Вычислительный процесс и вычислительные алгоритмы
Эффективность алгоритмов и оценка их вычислительной сложности. Модель вычислительного процесса и классификация алгоритмов по вычислительной сложности. Принцип «разделяй и властвуй». Общие свойства базовых алгоритмов цифровой обработки сигналов.
вычислительный процесс и вычислительные алгоритмы
Эффективность алгоритмов и оценка их вычислительной сложности
Модель вычислительного процесса
Классификация алгоритмов по вычислительной сложности
Стратегия дублирования (расщепления). Принцип «разделяй и властвуй».
Общие свойства базовых алгоритмов цифровой обработки сигналов
Процесс построения вычислительного алгоритма цифровой обработки сигналов во многом определяется численным методом, под которым понимается такая интерпретация математической модели, которая доступна для реализации на заданных средствах обработки (ЭВМ, цифровые сигнальные процессоры, контроллеры). При переходе от математической модели к численному методу возникают погрешности, называемые погрешностью метода, связанные с точностью приближения. Выделяют погрешность дискретизации и погрешность округления.
Обычно построение численного метода разбивают на два этапа: формулировку дискретной задачи и разработка вычислительного алгоритма, позволяющего отыскать решение дискретной задачи. В этом случае говорят, что произошла дискретизация исходной математической задачи. Например, замена системы дифференциальных уравнений разностными алгебраическими уравнениями. Ясно, что решение дискретной задачи отличается от исходной задачи. Разность соответствующих решений и называется погрешностью дискретизации.
Входные данные при цифровой обработки часто задаются не точно, а с округлением. В результате решение будет отличаться от решения дискретизированной задачи. Результирующая погрешность называется погрешностью округления. Величина этой погрешности определяется двумя факторами: точность. Представления вещественных (комплексных) чисел и чувствительностью данного алгоритма к погрешностям округления.
Эффективность алгоритмов и оценка их вычислительной сложности
Вопросы сложности алгоритмов и устройств являются основополагающими в цифровой обработки сигналов. Понятие сложности имеет сложную историю развития. Понятие сложности алгоритма также допускает различные трактовки. Могут учитываться или не учитываться таки факторы, как размер машинного слова, емкость памяти, различие в длительности выполняемых команд и т.д.
Известен ряд моделей вычислительного процесса, позволяющих раскрыть сложность отдельных задач и сравнить различные алгоритмы.
Модель вычислительного процесса
алгоритм вычислительный цифровой сигнал
Определение. Пусть заданы:
1) набор входных переменных
2) поле F (или кольцо K);
3) множество базисных операций
— унарная операция умножения на элемент поля (кольца).
Неветвящаяся программа представляет собой последовательность строк (команд), l-я из которых имеет вид
1) для любой базисной операции из множества P фиксируется число ( f ), называемое сложностью этой операции;
2) Сложностью НП называется сумма всех ( f ) по всем строкам этой программы;
4) Пусть ( + ) = 1, а для всех остальных ( f ) = 0. Соответствующая сложность называется аддитивной ( Ca );
5) Пусть ( ) = ( / ) = 1, а остальные операции не учитываются. Сложность такого рода называется мультипликативной ( Cm ).
1) тотальная сложность используется при анализе матричных процессов, в которых все операции оцениваются одинаково;
2) аддитивная сложность является хорошим критерием при обработке бинарных или троичных данных, элементы которых представляются в алфавитах <0,1>, <1,-1>, <1,0,-1>.
Качество (эффективность) алгоритма оценивается асимптотической сложностью, т.е. порядком роста сложности как функции от числа входов N при неограниченном росте N без учета мультипликативных констант.
Классификация алгоритмов по вычислительной сложности
В зависимости от порядка сложности и вида результирующих данных алгоритмы обработки можно отнести к четырем уровням.
3) К третьему уровню относятся векторные алгоритмы сложности O(N 2). Сюда включаются умножение матрицы на вектор для вычисления линейных преобразований (Фурье, Ганкеля-Теплица и др ), вычисление свертки векторов (полиномов) (их спектров и корреляций), фильтрация с КИХ и т.д. Некоторые из этих алгоритмов ( для случая специальных матриц) можно улучшить до оценки O(N log N ).Примером является быстрое преобразование Фурье (БПФ).
Стратегия дублирования (расщепления). Принцип «разделяй и властвуй»
Выберем объем задачи N в качестве параметра и разобъем задачу на две подзадачи объема (N / 2) той же самой структуры, что и исходная задача. Если решение этих подзадач можно скомбинировать в решение исходной задачи, то получается эффективный алгоритм.
Общие свойства базовых алгоритмов цифровой обработки сигналов
Подобные документы
Оценка алгоритмов цифровой обработки сигналов в условиях наличия и отсутствия помех. Проектирование модели дискретной свертки в среде Mathcad 14. Анализ кодопреобразователей циклических кодов и их корректирующие способности. Работа цифрового фильтра.
курсовая работа [3,0 M], добавлен 11.02.2013
Исследование теоретических основ математического аппарата теории цифровой обработки сигналов. Расчет параметров рекурсивных цифровых фильтров с использованием средств вычислительной техники. Методы проектирования алгоритмов цифровой обработки сигналов.
контрольная работа [572,7 K], добавлен 04.11.2014
дипломная работа [4,0 M], добавлен 22.06.2012
Конструкторско-технологический анализ элементной базы функциональной ячейки вычислительного модуля. Выбор компоновочной схемы. Расчет площади печатной платы, определение вибропрочности конструкции. Технологический процесс сборки и монтажа ячейки модуля.
дипломная работа [2,8 M], добавлен 29.11.2014
Обоснование необходимости использования вычислительной техники для решения комплекса задач по автоматизации учёта движения грузов. Исследование алгоритмов сортировки грузов и их распределение по паллетам. Типы и методы циклических инвентаризаций.
дипломная работа [119,7 K], добавлен 21.02.2009
Проектирование табличным методом алгоритмов работы на сотовом мобильном телефоне GA 628 Ericsson. Использование символьных наборов. Описание работы автомата таблицей переходов. Разработка алгоритмов функций. Использование телефона как блокнота.
контрольная работа [92,3 K], добавлен 09.05.2011
Характеристика и область применения сигналов в системах цифровой обработки. Специализированный процессор цифровой обработки сигналов СПФ СМ: разработчики и история, структура и характеристики, область применения, алгоритмы и программное обеспечение.
курсовая работа [224,9 K], добавлен 06.12.2010
Вариант применения персональных компьютеров (ПК) для решения задач вторичной обработки радиолокационной информации. Сравнительный анализ используемых и предлагаемых алгоритмов. Схемы устройств для сопряжения ПК с цифровой станцией 55Ж6; расчет затрат.
дипломная работа [4,3 M], добавлен 27.06.2011
Анализ эксплуатации средств вычислительной техники и факторов, влияющих на их работоспособность. Требования к функциональным характеристикам и конструкции элементов вычислительной техники. Качества транспортируемой, морской, бортовой, портативной техники.
курсовая работа [750,0 K], добавлен 05.05.2013
Алгоритмы, учитывающие систему визуального восприятия человека. Мультиразмерная ошибка. Мера качества видео на основе дискретного косинусного преобразования. Модификация алгоритмов оценки качества изображения с применением предварительной обработки.
реферат [62,6 K], добавлен 19.11.2008
Приведем несколько определений понятия алгоритма:
· Алгоритм — это конечный набор правил, который определяет последовательность операций для решения конкретного множества задач и обладает пятью важными чертами: конечность, определённость, ввод, вывод, эффективность». (Д. Э. Кнут)
· Алгоритм — это всякая система вычислений, выполняемых по строго определённым правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи». (А. Колмогоров)
· Алгоритм — точное предписание о выполнении в определённом порядке некоторой системы операций, ведущих к решению всех задач данного типа». (Философский словарь / Под ред. М. М. Розенталя)
· Алгоритм — строго детерминированная последовательность действий, описывающая процесс преобразования объекта из начального состояния в конечное, записанная с помощью понятных исполнителю команд». (Николай Дмитриевич Угринович, учебник «Информатика и информ. технологии»)
В информатике универсальным исполнителем алгоритмов является компьютер.
Исполнителя характеризуют: среда; система команд; элементарные действия; отказы.
Отказы исполнителя возникают, если команда вызывается при недопустимом для нее состоянии среды.
Свойства алгоритма:
Обычно формулируют несколько общих свойств алгоритмов, позволяющих отличать алгоритмы от других инструкций :
Чтобы алгоритм выполнил свое предназначение, его необходимо строить по определенным правилам. Поэтому нужно говорить не о свойствах алгоритма, а о правилах построения алгоритма, или о требованиях, предъявляемых к алгоритму.
2. Графическое представление алгоритмов.
Алгоритм задается в содержательном (вербальном), графическом или операторном (символьном) виде.
Содержательный способ записи алгоритмов представляет собой описание последовательных этапов обработки данных. Алгоритм задается в произвольном изложении на естественном языке.
содержательный способ не имеет широкого распространения, так как такие описания:
Графический способ представления алгоритмов является более компактным и наглядным по сравнению с содержательным.
При графическом представлении алгоритм изображается в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий. Внутри блока дается описание соответствующего действия.
Такое графическое представление называется схемой алгоритма или блок-схемой.
Графическое изображение алгоритма широко используется перед программированием задачи вследствие его наглядности, т.к. зрительное восприятие обычно облегчает процесс написания программы, ее корректировки при возможных ошибках, осмысливание процесса обработки информации.
ГОСТ 19.701-90 (обозначение символов соответствует международному стандарту ИСО 5807-85) распространяется на условные обозначения (символы) в схемах алгоритмов, программ, данных и систем и устанавливает правила выполнения схем, используемых для отображения различных видов задач обработки данных и средств их решения.
Графические символы на схеме соединяются линиями потока информации. Основное направление потока информации идет сверху вниз и слева на право (стрелки на линиях могут не указываться). В других случаях применение стрелок обязательно. По отношению к блоку линии потока могут быть входящими или выходящими. Количество входящих линий для блока принципиально не ограничено. Выходящая линия может быть только одна. Исключение оставляют логические блоки, имеющие не менее двух выходящих линий потока, каждая из которых соответствует одному из возможных исходов проверки логического условия, а также блоки модификации.
При записи алгоритма в словесной форме, в виде блок-схемы допускается определенный произвол при изображении команд. Вместе с тем такая запись точна настолько, что позволяет человеку понять суть дела и исполнить алгоритм.
Однако на практике в качестве исполнителей алгоритмов используются специальные автоматы — компьютеры. Поэтому алгоритм, предназначенный для исполнения на компьютере, должен быть записан на понятном ему языке. И здесь на первый план выдвигается необходимость точной записи команд, не оставляющей места для произвольного толкования их исполнителем.
Следовательно, язык для записи алгоритмов должен быть формализован. Такой язык принято называть языком программирования, а запись алгоритма на этом языке — программой для компьютера.
3. Виды вычислительный процессов.
1. Линейные вычислительные процессы
2. Циклические вычислительные процессы
3. Разветвляющиеся вычислительные процессы
4. Многоступенчатые вычислительные процессы
5. Комбинированные вычислительные процессы
Для организации циклических вычислительных процессов выделяется специальная переменная, называемая параметром цикла. По этой переменной ведется управление счетом, то есть, количеством выполнения тела цикла. В каждом цикле происходит изменение параметра цикла по определенной рекурсивной зависимости.
Различают циклические вычислительные процессы (ЦВП) с известным количеством повторения тела цикла и неизвестным количеством повторений тела цикла.
Цикл, в котором известно количество раз, которое выполнится тело цикла, называется детерминированным циклическим вычислительным процессом (ДЦВП).
Цикл, в котором нельзя заранее сказать, сколько раз выполнится тело цикла, называется итерационным циклическим вычислительным процессом (ИЦВП) (итерация – последовательное приближение.). Пример – задачи на вычисление с заданной точностью